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


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.

  • $\begingroup$ excellent! $ \ \ \ \ $ $\endgroup$ – MyCatsHat Dec 28 '12 at 17:01

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.