Proposition 11

Let E be a finite set with n elements, and let $(p_i)_{1 \leqslant i \leqslant h}$ be a finite sequence of integers such that $\sum_{i=1}^{h} p_i = n$. Then the number of coverings $(X_i)_{1 \leqslant i \leqslant h}$ of E by mutually disjoint sets $X_i$ such that $\mathrm{Card}\,(X_i) = p_i$ for $1 \leqslant i \leqslant h$ is equal to

Let G be the set of permutations of E and let P be the set of coverings $(X_i)_{1 \leqslant i \leqslant h}$ which satisfy the conditions of the Proposition. Since $\sum_{i=1}^{h} p_i = n$, P is not empty. Let $(A_i)_{1 \leqslant i \leqslant h}$ be an element of P. For each permutation $f \in G$ the family $(f(A_i))_{1 \leqslant i \leqslant h}$ again belongs to P; let us denote it by $\varphi(f)$. For each element $(X_i)_{1 \leqslant i \leqslant h}$ let us calculate the number of permutations $f \in G$ such that $\varphi(f) = (X_i)$. We shall have $\varphi(f) = (X_i)$ if and only if for each index $i$ we have $f(A_i) = X_i$. Hence the set of permutations $f$ under consideration is equipotent to the product of the sets of bijections of $A_i$ onto $X_i$ (Chapter II, § 4, no. 7, Proposition 8); consequently the set $\overset{-1}{\varphi}((X_i)_{1 \leqslant i \leqslant h})$ has $\prod_{i=1}^{h} p_i!$ elements (Corollary to Proposition 10). Since G has $n!$ elements, the result now follows from Proposition 9.