N-element combinations from K sets of different size

combinationscombinatorics

Sorry for the noob question, I can't find the answer anywhere else.

I am looking for a formula for the number of combinations of size N, from K sets, where each set has different number of elements.

Example:

I want to know the number of pairs -> N=2.
I have 3 sets -> K=3.
The size (cardinality) of these stets are -> K1=2, K2=3, K3=4.

My sets are:

K1 = (a, b)
K2 = (A, B, C)
K3 = (1, 2, 3, 4)

I am looking for the number of all unique pairs (no repetition) like these:

a-A, a-B, a-C, a-1, a-2, a-3, a-4,

b-A, b-B, b-C, b-1, b-2, b-3, b-4,

A-1, A-2, A-3, A-4,

B-1, B-2, B-3, B-4,

C-1, C-2, C-3, C-4

= total 26.

What is the formula for given size of combinations N, number of set K and their cardinalities (number of elements) Kx?

Best Answer

There is not a nice formula per se. Suppose that the sizes of the sets are $x_1,x_2,\dots,x_k$. In your example, $x_1=2,x_2=3,x_3=4$. The number of ways to select $n$ items, such that each selected item comes from a different set, can be written as $$ \sum_{1\le i_1<i_2<\dots<i_n\le k}x_{i_1}\cdot x_{i_2} \cdots x_{i_n} \tag1 $$ The summation ranges over all selections of $n$ distinct numbers $\{i_1,\dots,i_k\}$ between $1$ and $k$, so there are $\binom{n}k$ summation terms, each a product of the sizes of $n$ distinct sets. In your example, this becomes $$ x_1\cdot x_2+x_1\cdot x_3+x_2\cdot x_3=2\cdot 3+2\cdot 4+3\cdot 4=26 $$ The expression in $(1)$ comes up so often that it is given a special name. It is known as the elementary symmetric polynomial in variables $x_1,\dots,x_k$. If we let $e_n(x_1,\dots,x_k)$ denote the expression in $(1)$, then you can compute $(1)$ recursively as follows: $$ e_n(x_1,\dots,x_k)=x_k\cdot e_{n-1}(x_1,\dots,x_{k-1})+e_n(x_1,\dots,x_{k-1}) $$ This leads to a dynamic programming algorithm to calculate $(1)$ using $O(nk)$ arithmetic operations.

Related Solutions

[Math] Number of combinations w/o repetition that include a certain element

You must choose 1 element, then you can choose any k-1 elements from the remaining n-1. It's the same formula but with n and k replaced with n-1 and k-1 respectively.

(n-1)! / (k-1)! * ((n-1) - (k-1))!

Number of Combinations of Items from Sets with Dependencies

My common use case is large sets (thousands or millions of elements) but only a handful of links.

For me a clustered recursion seems to be a good algorithm. The idea is simple but it is a bit hard for me to explain it clearly. I’ll hope you’ll understand it from the below. An input for a clustered recursion is the following. Assume that we are given sets $S_1,\dots, S_n$. Then for each $i$ and each subset $I$ of $\{i+1,\dots, n\}$ we count a number $(i,I)$ of elements of $S_i$ which linked to exactly members of $I$. Also assume that we are given a subset $Z$ of $\{1,\dots, n\}$ of indices $i$ of sets $S_i$ which do not need links to be listed. Clearly, suffices to consider reduced inputs $(i,I)$ with $I\cap Z\varnothing$, with $(i,I):=\sum \{(i,I’):I\subset I’\subset I\cup Z\}$. For instance, in your example we have $n=3$, $Z=\{1\}$, $(1,\{2\})=1$, $(1,\{3\})=2$, $(1,\varnothing)=1$, $(2,\varnothing)=3$, $(3,\varnothing)=2$, and all other $(i,I)$ are zero. Then using the same arguments as in the question, we can count the total number $N$ of possibilities as follows. For each subset $I$ of $\{2,\dots, n\}$ we recursively calculate the total number $N_I$ of possibilities in which the first element is linked with exactly members of $I$ and then count $N=\sum \{N_I: I\subset \{2,\dots, n\}\}$. For instance, in your example there are

$(1,\{2\})=1$ choice to choose an element linked exactly with the set $S_2$. In this case we add $2$ to and remove $1$ from the set $Z$ of indices of sets which do not need links to be listed. This gives us the same problem, but with the smaller number of sets. Since the elements of the set $S_2$ are not linked with other sets, in this case we have only $(2,\varnothing)=3$ choices. So in total we have $N_{\{2\}}=(1,\{2\})(2,\varnothing)=3$.
$(1,\{3\})=2$ choices to choose an element linked exactly with the set $S_3$. In each of these cases we add $3$ to and remove $1$ from the set $Z$. This gives us the same problem, but with the smaller number of sets. Since the elements of the set $S_3$ are not linked with other sets, in this case we have only $(3,\varnothing)=2$ choices. So in total we have $N_{\{3\}}=(1,\{3\})(3,\varnothing)=4$.
$(1, \varnothing)=1$ choice to choose an element not linked with any set $S_i$. In this case we remove $1$ from the set $Z$, but add to it nothing. So in total we have $N_\varnothing =(1,\varnothing)=1$.

Thus we have $N= N_\varnothing + N_{\{2\}}+ N_{\{3\}}=1+3+4=8$.

Best Answer

Related Solutions

[Math] Number of combinations w/o repetition that include a certain element

Number of Combinations of Items from Sets with Dependencies

Related Question