# 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\}$. Jan 31, 2018 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$. Jan 31, 2018 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$. Jan 31, 2018 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. Jan 31, 2018 at 17:21
• Can you give us a full enumeration for the two-set example you give? Feb 1, 2018 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. Jan 31, 2018 at 17:19
• @Y.Forman is correct. I've edited the question to clarify (I hope). Jan 31, 2018 at 17:33
• If $|S_i|=i$ for all $i$ and $n$ is even, the product here is $0$. Jan 31, 2018 at 17:33