3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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\}$. $\endgroup$ – Guilherme Salomé Jan 31 '18 at 16:49
  • $\begingroup$ @GuilhermeSalomé I don't think so? $E_2$ can come from $S_2 \setminus S_1$ or it can come from $S_1$. $\endgroup$ – Maxpm Jan 31 '18 at 17:03
  • $\begingroup$ 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$. $\endgroup$ – Guilherme Salomé Jan 31 '18 at 17:15
  • $\begingroup$ @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. $\endgroup$ – Maxpm Jan 31 '18 at 17:21
  • $\begingroup$ Can you give us a full enumeration for the two-set example you give? $\endgroup$ – neoholopogon Feb 1 '18 at 21:12
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – BallBoy Jan 31 '18 at 17:19
  • $\begingroup$ @Y.Forman is correct. I've edited the question to clarify (I hope). $\endgroup$ – Maxpm Jan 31 '18 at 17:33
  • $\begingroup$ If $|S_i|=i$ for all $i$ and $n$ is even, the product here is $0$. $\endgroup$ – Barry Cipra Jan 31 '18 at 17:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.