All Questions
Tagged with integer-partitions set-partition
31
questions
3
votes
2
answers
111
views
high school math: summands
Let's say we have a question that asks you to find the amount of all possible integers adding up to a random number, lets just say 1287. However, the possible integers is restricted to explicitly 1's ...
- 31
0
votes
1
answer
31
views
A variant of the partition problem or subset sum problem
Given a target list $T = (t_1, t_2, \ldots, t_N)$ and a multiset $S = \{s_1, s_2, \ldots, s_M\}$, both with non-negative integer elements, $t_k\in \mathbb{N}_>$ and $s_k\in \mathbb{N}_>$, ...
- 125
0
votes
0
answers
28
views
Do we have recurrences for evaluating the Partition Function on Graphs?
Inspired by this question about defining the partition function on non integers, I was thinking about what sorts of other objects can a partition function be defined on.
I noticed that if we have an ...
- 17.4k
0
votes
1
answer
110
views
How to fill a set of container by partition of set?
Let $\{A,B,C,D\}$ be a table with $4$ containers of sizes respectively $5,5,3,2$. Let $\pi=\{B_1,B_2,\cdots B_k\}$ a partition of a set, where $k\in \mathbb{N}$. I wonder how to enumerate the ...
1
vote
1
answer
77
views
Another formulation for Stirling numbers of the second kind
I find another formulation for Stirling numbers of the second kind:
Let $n\ge k\ge 1$. Denote by
$$\mathbb N_<^n := \{ \alpha = (\alpha_1,\cdots,\alpha_n): 0\le \alpha_1\le\cdots\le\alpha_n, \...
- 1,972
0
votes
1
answer
44
views
Is the following Knapsack Variant NP-Hard?
The problem: Let $A_1 = \{a^1_1,\ldots,a^1_n\}, A_2 = \{a^2_1,\ldots,a^2_n\}, \ldots, A_k = \{a^k_1,\ldots,a^k_n\} \subset \mathbb{N}$ be $k$ sets of $n$ integers, and let $U,L \in \mathbb{N}$ be ...
- 193
0
votes
1
answer
74
views
Derivation of Integer Partition from Partition of a Set
Definition.
Let $A$ be a non-empty set. A collection $P$ of subsets $A_1,A_2,A_3,\ldots$ of $A$ is called a partition of $A$ if the following three conditions hold:
$\emptyset \notin P$,
$A_1 \cup ...
- 447
0
votes
1
answer
198
views
Link Between Integer Partition and Partition of a Set
Definition.
Let $A$ be a non-empty set. A collection $P$ of subsets $A_1,A_2,A_3,\ldots$ of $A$ is called a partition of $A$ if the following three conditions hold:
$\emptyset \notin P$,
$A_1 \cup ...
- 447
2
votes
1
answer
137
views
A number partition problem
I have encountered the following interesting integer partitioning problem.
Let $n,k,t \in \mathbb{N}$ be given parameters and let $S_1,\ldots, S_t$ be a partition of the numbers $1,2,\ldots,n$ such ...
- 193
1
vote
0
answers
121
views
Minimizing the magnitude of the sum of a vector of complex numbers with an integer constraint
Let $h_{1}, ..., h_{N} \in \mathbb{C} $
Consider minimizing the function below:
$ \min \left| \sum\limits_{i=1}^N h_{i} x_{i} \right| $
with the constraints $x_{i}^2 = 1$
i.e., $x_{i}$ can only take ...
- 11
0
votes
1
answer
256
views
Number of integer $k$-tuples with sum $n$? [duplicate]
I wish to know how many elements are there in the set
$$
S_{n,k} = \left\{(n_1,\ldots, n_k): \forall i,n_i \in \mathbb Z, n_i \geq 0, \sum_i n_i = n\right\}.
$$
It appears to me that we have a simple ...
- 7,534
-3
votes
4
answers
129
views
Find a minimal set whose elements determine explicitly all integer solutions to $x + y + z = 2n$
Is there a way to exactly parameterise all the solutions to the equation $x + y + z = 2n$, for $z$ less than or equal to $y$, less than or equal to $x$, for positive integers $x,y,z$?
For example, for ...
- 67
3
votes
1
answer
109
views
Distributing $n$ distinct objects into $m$ types of urns with $k_1,k_2...k_m$ urns of each type
I came accross this (rather complex?) combinatorial problem:
I have $18$ distinct objects, $3$ red urns, $7$ blue urns, and $11$
green urns. In how many ways can I distribute the objects into those
...
- 1,022
2
votes
1
answer
414
views
Given a set of both positive and negative numbers, what is a time optimal approach to find the two numbers whose sum, plus a third number is zero
Coming from an engineering background I want to solve this question.
Question:
Given a set of positive, and negative numbers, how do I time optimally find two numbers whose sum is the mathematical ...
- 173
1
vote
1
answer
121
views
Why is the following not $S(n,3)$ where $S(n,k)$ is a Stirling number of the second kind? (almost solved)
In an attempt to relate the number of partitions of integers to that of partitions of distincts objects I stumbled, in the particular case of $k:=3$, on the following sum
$$\sum_{\genfrac{}{}{0pt}{1}{...
- 3,679