1
$\begingroup$

Consider the theorem

Let $A_1,\ldots,A_n$ be $n$ sets of cardinalities $N_1\ldots,N_n$, and $S:=A_1\times \ldots\times A_n$. Then $|S|=N_1\cdot \ldots \cdot N_n$.

How do I have to apply this theorem to prove the following statement:

Let $A$ be a set of size $n$. Then there are $\frac{n!}{k_{1}!\cdot\ldots\cdot k_{t}!}$ ways to partition this set into $t$ nonempty set of sizes $k_{i}$.

I have only the following proof: There are $\binom{n}{k_1}$ ways to pick the first partition, $\binom{n-k_1}{k_2}$ ways to pick the second partition, $\binom{n-k_1 - k_2}{k_3}$ ways to pick the third partition ans so on. Calculating $\binom{n}{k_1} \binom{n-k_1}{k_2} \binom{n-k_1 - k_2}{k_3}\ldots$gives the answer.

Where have we applied the above theorem in this proof ? My guess is that we actually implicitly defined in this proof $A_1$ as the set of all subsets of $A$ of size $k_1$ (so that $|A_1|=\binom{n}{k_1}$) and $A_2$ and so in a similar fashion to make use of the above theorem to get that product - but already for $A_2$ I don't know how to define it (such that $|A_2|=\binom{n-k_1}{k_2}$, since $A_2$ doesn't know which of the subset I already removed from $A$...)

1 Answers 1

1

Good catch. You’re right: the theorem on the cardinality of a Cartesian product can’t be applied directly, because the identity of the $i$-th factor depends on which points were chosen in the first $i-1$ factors. It’s intuitively clear that this doesn’t actually affect the final count, and the difficulty is often hand-waved away, but a rigorous proof takes quite a bit more work.

Let’s look at the case $t=2$. Let $\mathscr{M}_1$ be the set of $k_1$-element subsets of $A$, and let $\mathscr{M}_2$ be the set of $k_2$-element subsets of $A$. For each $S\in\mathscr{M}_1$ let $\mathscr{M}_2(S)=\{T\in\mathscr{M}_2:S\cap T=\varnothing\}$. Then $|\mathscr{M}_1|=\binom{n}{k_1}\;,$ and $|\mathscr{M}_2(S)|=\binom{n-k_1}{k_2}$ for each $S\in\mathscr{M_1}$.

Let $\mathscr{M}=\big\{\langle S,T\rangle\in\mathscr{M}_1\times\mathscr{M}_2:T\in\mathscr{M}_2(S)\big\}\;;$ we wish to show that $|\mathscr{M}|=\binom{n}{k_1}\binom{n-k_1}{k_2}\;.\tag{1}$

Let $N_1=\mathscr{M}_1$, and let $N_2$ be any set of cardinality $\binom{n-k_1}{k_2}$. For each $S\in\mathscr{M}_1$ let $\varphi_S:\mathscr{M}_2(S)\to N_2$ be a bijection. Now define a function

$\varphi:\mathscr{M}\to N_1\times N_2:\langle S,T\rangle\mapsto\langle S,\varphi_S(T)\rangle\;.$

It’s easy to verify that $\varphi$ is a bijection, and $(1)$ follows at once from the theorem that you cited.

The case for general $t$ is basically the same, but with more notation to keep track of. Alternatively, you could prove the result by induction on $t$: the induction step is basically the same as the $t=2$ argument.

  • 0
    excellent! $ \ \ \ \ $2012-12-28