I have the following problem. Let's start from a simple case. Suppose i have to sets, A and B with 4 and 5 elements respectively. I need to pick a certain number of elements from these two sets that match a certain value. For example, if I need to pick 7 elements, there are
$$
\binom{4}{2} \cdot \binom{5}{5} + \binom{4}{3} \cdot \binom{5}{4} + \binom{4}{4} \cdot \binom{5}{3} = 36
$$
possible combinations (the sum of the $k$'s in $\binom{n}{k}$ is 7). This case is simple. The problem I face is to find a general formula to find all the possible combinations of elements that sum to a given number. So, suppose I have N sets, each with $N_i$ elements. I need to select k total elements. How can i express this using a formula? Any hints or reference? This formula, when provided with 2 sets with 4 and 5 elements should output the previous equation, with the sum of the product of two binomal coefficients. Clearly, a formula with N sets will have a sum of a certain number of factors, each one with N binomial coefficients. What i'm looking for is the $k$'s for these N binomial coefficients. Hope this is clear.
Possible combinations of elements from different sets
combinationscombinatorics
Related Question
- Number of Combinations of Items from Sets with Dependencies
- Sum of all the possible $\binom{N}{n}$ elements of a $N$ elements set
- Combinations of elements from multiple sets with constraints
- Combinatorics – Sets – Min number of items from combinations that, when generated combination os its elements, equals superset
- N-element combinations from K sets of different size
Best Answer
The $k_i$ values (meaning the number of elements you choose from the set $N_i$) come from the weak compositions of $n$. A composition of $n$ is a sequence of positive integers that add up to $n$. For example, the compositions of $3$ are $3$, $2+1$, $1+2$, and $1+1+1$. A weak composition is a composition allowing $0$ as a term. To count weak compositions, we need to bound the number of terms. The weak compositions of $3$ into three terms are $3+0+0,\ 0+3+0,\ 0+0+3,\ 2+1+0,\ 2+0+1,\ 0+2+1,\ 1+2+0,\ 1+0+2,\ 0+1+2$, and $1+1+1$.
The $k_i$ values that appear in your sum will form a weak composition of $k$ into $N$ terms. You can express this sum as $$\sum_{k_1+k_2+\cdots +k_N=k,\ k_i\geq 0}{N_1\choose k_1}{N_2\choose k_2}\ldots{N_N\choose k_N}.$$
The number of weak compositions of $k$ into $N$ terms is ${k+N-1\choose N-1}$, which you can show using the stars-and-bars method. This formula isn't too nice because you still have to compute the individual terms in the sum, but it at least tells you where the $k_i$ values come from.