Exercise 1.4.5 (Shepherd's principle)

Question

Show that if $a$ and $b$ are positive integers, then $a!^b b ! \mid (ab)!$.

(Hint: Consider the number of ways of partitioning a set of $ab$ elements into $b$ disjoint subsets each containing $a$ elements.)

Richard Ganaye · Accepted Answer

\begin{proof} This is a generalization of the preceding exercise, where we adopt the alternative strategy. Let $\mathscr{S}$ be a set containing $ab$ elements.

Let $\mathscr{P}'$ be the set of ordered partitions $(A_1,\ldots,A_b)$ of $\mathscr{S}$ (partition-families), where $|A_i|= a$ for every index $i$, and let $\mathscr{P}$ be the set of unordered partitions $\{A_1,\ldots,A_b\}$ with the same conditions for $A_i$ (partition-sets). Consider the map
$$\chi
\left\{
\begin{array}{ccl}
\mathscr{P}' & 	o &\mathscr{P}\
(A_1,\ldots,A_b) & \mapsto &\{A_1,\ldots,A_b\}
\end{array}
ight.
$$
Then every element of $\mathscr{P}$ has $b!$ pre-images, explicitly the partition-families $(A_{\sigma(1)}, \ldots,A_{\sigma(b)})$, where $\sigma$ is any permutation of $S_b$. Therefore 
$$ b! \cdot |\mathscr{P}| = |\mathscr{P}'|.$$
To count the elements of $\mathscr{P}'$, we choose first the $a$ elements of $A_1$ among $ab$ elements, in $\binom{ab}{a}$ ways, then the $a$ elements of $A_2$, in $\binom{ab -b}{a}$ ways, and so on, the two last elements of $A_b$ in $\binom{a}{a} = 1$ way. Thus
$$|\mathscr{P}'| =\binom{ab}{a} \binom{ab - a}{a} \cdots \binom{a}{a}.$$
and so 
\begin{align*}
 |\mathscr{P}| &= \frac{1}{b!} \binom{ab}{a} \binom{ab - a}{a} \cdots \binom{a}{a}\
 &=  \frac{1}{b!}  \frac{(ab)!}{(ab-a)! a!}  \frac{(ab -a)!}{(ab- 2a)! a!} \cdots  \frac{a!}{0! a!} \
 &=\frac{(ab)!}{ (a!)^b b!}.
 \end{align*}
 
Since $\frac{(ab)!}{ (a!)^b b!} =  |\mathscr{P}| $ is an integer,
$$a!^b b ! \mid (ab)!.$$
\end{proof}

Exercise 1.4.5 (Shepherd's principle)

Answers

Comments

Exercise 1.4.5 (Shepherd's principle)

Answers

Comments

Add answer