Choosing K numbers from n distinct sets

Question

Suppose that I have N different sets, Each set contains some numbers such that :

First set contains only ones., Second set contains only twos, and so on.

It's not necessarily that all sets have the same number of elements.

If I want to calculate how many ways to choose K distinct numbers of those sets, Is there any rule for that ?

Example :

I have 4 sets : {1, 1, 1}, {2, 2}, {3, 3, 3, 3}, {4}.

and K = 3

Then I can choose for example : {1, 2, 3} in 24 different ways.

choose : {1, 2, 4} in 6 different ways.

choose : {2, 3, 4} in 8 different ways.

So I choose 3 different numbers in 24 + 6 + 8 = 38 ways.

The same thing but I don't want to do like this, I want some equation to calculate the answer

Answer 1

There's no formula, but there is an algorithm which makes computing this easy. Let $$ e_k(x_1,x_2,\dots,x_n)=\text{# ways choose $k$ distinct items when $i^{th}$ box has $x_i$ identical items} $$ This is an established notation; what you are computing is known as the $k^{th}$ elementary symmetric function evaluated at $x_1,\dots,x_n$.

It is easy to show that $$ e_k(x_1,\dots,x_{n-1},x_n)=e_k(x_1,\dots,x_{n-1})+x_n\cdot e_{k-1}(x_1,\dots,x_{n-1}) $$ Let $e_{k,n}$ be a shorthand for $e_k(x_1,\dots,x_n)$, so the above is $$e_{k,n}=e_{k,n-1}+x_n\cdot e_{k-1,n-1}.$$ This recursive equation lets you compute $e_{k,n}$ by filling out a $k\times n$ DP table, where the entry in the $i^{th}$ row and $j^{th}$ column is computed by using the previously computed entries at the coordinates $(i,j-1)$ and $(i-1,j-1)$.

For your example with $n=4,k=3$ and $(x_1,x_2,x_3,x_4)=(3,2,4,1)$, the result is

$\begin{matrix}&n\\k&\end{matrix}$	0	1	2	3	4
0	1	1	1	1	1
1	0	3	5	9	10
2	0	0	6	26	35
3	0	0	0	24	50$\color{#0d0}\checkmark$

which is indeed correct. (In your post, you forgot subsets which look like $\{1,3,4\}$, of which there are $12$, adding that to the $38$ you found gives $50$).

Answer 2

Label your sets $A_1, A_2, A_3, ... A_n$. Then, for a value of $K$, $0 \leq K \leq n$, there exist $\frac{n!}{K!(n-K)!}$ combinations of said sets. You can find the required value, call it $\Sigma P$, as being the sum the product of cardinalities of the combinations.

For the example you have given, $|A_{1}| = 3, |A_2| = 2, |A_3| = 1, |A_4| = 4$. For $K = 3$, the combinations are $|A_1||A_2||A_3|, |A_1||A_2||A_4|, |A_1||A_3||A_4|, |A_2||A_3||A_4|$, and finding the sum of the product of the cardinalities you get $6 + 24 +12 + 8 = 50$.

In fact, it becomes obvious that the whole notion of sets in this problem is uncalled for. It can be reduced a problem involving a single set, $S$, containing said cardinalities, $S = (3,2,1,4)$ and simply finding the sum of products of subsets of size $K$ will solve the problem.

Answer 3

In your example, with $n_1, n_2, n_3, n_4$ repeats in respective sets,

it seems to me that the simplest way to express the formula would be

${n_1n_2n_3n_4} \left(\dfrac{1}{n_1}+\dfrac{1}{n_2}+\dfrac{1}{n_3}+\dfrac{1}{n_4}\right)$