# How do I count combinations whose elements are drawn from nested sets?

I have $n$ finite sets. Each set is a strict subset of the next, i.e.,

$$S_1 \subset S_2 \subset S_3 \subset \ldots \subset S_n$$

I want to count the combinations of $n$ unordered elements where one element is drawn from $S_1$, one element is drawn from $S_2$, and so on.

Ideally, I'd like this both for the case where duplicate elements within a combination are allowed and for the case where they are not.

In other words, I want the number of $n$-sets (for the without-duplicate-elements case) or $n$-multisets (for the with-duplicate-elements case) $\{E_1,\cdots,E_n\}$ where $E_x \in S_x$.

For example, let's say I have the following sets.

\begin{align} S_1 &= \{1, 2\} \\ S_2 &= \{1, 2, 3, 4\} \end{align}

I can then draw these 5 combinations:

$$\{1,2\}, \{1,3\}, \{1,4\}, \{2,3\}, \{2,4\}$$

And, depending on whether or not duplicate elements within a combination are allowed, I could also include these two: $$\{1,1\}, \{2,2\}$$

Note that the combinations $\{3,3\}, \{3,4\}, \{4,4\}$ are not counted. Each of those is impossible to draw in such a way that one element comes from $S_1$ and one element comes from $S_2$.

• Do you want to count the combinations of elements in $S_1,S_2\setminus S_1,S_3\setminus S_2,\dots,S_n\setminus S_{n-1}$? In your example, that would be combinations of elements from the sets $\{1,2\},\{3\}$. – Guilherme Salomé Jan 31 '18 at 16:49
• @GuilhermeSalomé I don't think so? $E_2$ can come from $S_2 \setminus S_1$ or it can come from $S_1$. – Maxpm Jan 31 '18 at 17:03
• I am confused then. You say you want to draw one element from each set, but in your example you don't want to count $(E_1=2,E_2=1)$, where $E_2$ is an element of both $S_2$ and $S_1$. In any case, think about what you actually want to do for a low number of sets, say $n=2$. – Guilherme Salomé Jan 31 '18 at 17:15
• @GuilhermeSalomé Sorry, let me clarify. I do want to count $(2, 1)$ or $(1, 2)$ but not both, because I want combinations, not permutations. That's where the strawman solution of $|S_1|\times\ldots\times|S_n|$ breaks down. – Maxpm Jan 31 '18 at 17:21
• Can you give us a full enumeration for the two-set example you give? – neoholopogon Feb 1 '18 at 21:12

Edited: This is answering a different question; I had misinterpreted the direction of set containment. If the $S_i$'s were shrinking rather than growing... so e.g if $|S_i| = n+1-i$, then there's only one way to choose all the way up.

Imagine choosing in reverse order. Let's write $m_i = |S_i|$, and I'll write $x_i$ for your $E_i$ because I can't stand element variables being capital letters.

Then there are

• $m_n$ ways to choose $x_n \in S_n$,
• $m_{n-1} - 1$ ways to choose $x_{n-1} \in S_{n-1}$, distinct from $x_n$
• $m_{n-2} - 2$ ways to choose $x_{n-2} \in S_{n-2}$, distinct from $x_n$ and $x_{n-1}$

$\vdots$

• $m_1 - (n-1)$ ways to choose $x_1 \in S_1$, distinct from all other $x_i$'s.

Your answer (if I've interpreted your question correctly: you want an ordered list $(x_1, \dots, x_n)$ of distinct elements, where each $x_i \in S_i$ and the $S_i$'s are nested) is thus $$\prod_{i=1}^n \left(|S_i| - (n-i) \right).$$

• The OP mentioned that $(1,2)$ and $(2,1)$ should be considered the same, so I don't think the list is supposed to be ordered. But the OP should clarify explicitly. – BallBoy Jan 31 '18 at 17:19
• @Y.Forman is correct. I've edited the question to clarify (I hope). – Maxpm Jan 31 '18 at 17:33
• If $|S_i|=i$ for all $i$ and $n$ is even, the product here is $0$. – Barry Cipra Jan 31 '18 at 17:33