# Choosing K numbers from n distinct sets

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

• In general, I don't think there's a better way to do it. Jul 24, 2021 at 12:16

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$$).

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.

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)$$