Divided powers are an algebraic gadget that emulate, in an arbitrary ring, the functions $x\mapsto x^n/n!$ for all integers $n$, together with the natural functional equations that they satisfy.
One of them is a nice binomial theorem without binomial coefficients : denoting $x^n/n!$ by $x^{[n]}$, one has $$ (x+y)^{[n]}=\sum_{k=0}^n x^{[n-k]} y^{[k]}. $$
Another formula looks at what happens when one iterates the construction: if everything happens nicely, one has $$ (x^{[n]})^{[m]}=\frac1{m!}\left(x^n/n!\right)^m = \frac1{(n!)^m m!} x^{nm} = \frac{(mn)!}{m! n!^m} x^{[mn]}. $$
In the development of the theory, the remark that comes then is the necessary observation that the coefficient $(mn)!/{m! n!^m}$ is an integer, which is not obvious since it is written as a fraction. Two arguments are given to justify this fact.
- The formula $$ \frac{(mn)!}{m! n!^m} = \prod_{k=1}^{m} \binom{k n-1}{n-1} $$ which the authors claim can be proved by induction
- The observation that $(mn)!/m!n!^m$ is the number of (unordered) partitions of a set with $mn$ elements into $m$ subsets with $n$ elements.
The latter fact is a particular case of a more general counting question: if $n=(n_1,\dots,n_r)$ are integers and $N=n_1+\dots+n_r$, then the number of (unordered) partitions of a set with $N$ elements into subsets of cardinalities $n_1,\dots,n_r$ is equal to $$\frac{N!}{\prod n_i! \prod_{k>0} m_k(n)!},$$ where $m_k(n)$ is the number of occurences of $k$ in the sequence $(n_1,\dots,n_r)$.
The goal of this blog post is to present a combinatorial argument for the first equality, and an alternative expression of the second number as a product of integers. We also give a formal, group theoretical proof, that this quotient of factorials solves the given counting problem.
$\gdef\abs#1{\lvert#1\rvert}$ $\gdef\Card{\operatorname{Card}}$
Counting partitions of given type
Let $S$ be a set with $N$ elements.
A partition of $S$ is a subset $\{s_1,\dots,s_r\}$ of $\mathfrak P(S)$
consisting of nonempty, pairwise disjoint, subsets whose union is $S$.
Its *type* is the “multiset” of integers given by their cardinalities.
Because no $s_i$ is empty, the type is a multiset of nonzero integers.
It is slightly easier to authorize zero in this type;
then a partition has to be considered as a multiset of subsets of $S$,
still assumed pairwise disjoint, so that only the empty subset can be repeated.
The group $G$ of permutations of $S$ acts
on the set $\Pi_S$ of partitions of $S$.
This action preserves the type of a partition, so that
we get an action on the set $\Pi_{S,n}$ on the set of partitions of type $n$,
of any multiset of integers $n$. It is nonempty if and only if $\abs n=N$.
This action is transitive: Given two partitions
$(s_1,\dots,s_r)$ and $(t_1,\dots t_r)$ with the same type $(n_1,\dots,n_r)$,
numbered so that $\abs{s_i}=\abs{t_i}={n_i}$ for all $i$,
we just define a permutation of $S$ that maps the elements of $s_i$ to $t_i$.
By the orbit-stabilizer theorem, the number of partitions of type $n$
is equal to $\Card(G)/\Card(G_s)$, where $G_s$ is the stabilizer
of any partition $s$ of type $n$.
Since $\Card(S)=N$, one has $\Card(G)=N!=\abs n!$.
On the other hand, the stabilizer $G_s$ of a partition $(s_1,\dots,s_r)$
can be described as follows. By an element $g$ of this stabilizer,
the elements of $s_i$ are mapped to some set $s_j$
which has the same cardinality as $s_i$. In other words,
there is a morphism of groups from $G_s$ to the subgroup of the
symmetric group $\mathfrak S_r$ consisting of permutations
that preserve the cardinality. This subgroup is a product
of symmetric groups $\mathfrak S_{m_k}$, for all $k> 0$,
where $m_k$ is the number of occurrences of $k$ in $(n_1,\dots,n_r)$.
Here, we omit the factor corresponding to $k=0$ because our morphism
doesnt' see it.
This morphism is surjective, because it has a section.
Given a permutation $\sigma$ of $\{1,\dots,r\}$ that preserves
the cardinalities, we have essentially shown above how to construct
a permutation of $S$ that induces $\sigma$, and this permutation
belongs to $G_s$. More precisely, if we number the elements
of $s_i$ as $(x_{i,1},\dots,x_{i,n_i})$, we lift $\sigma$
to the permutation that maps $x_{i,j}$ to $x_{\sigma(i),j}$ for all $i,j$.
This makes sense since $n_{i}=n_{\sigma(i)}$ for all $i$.
The kernel of this morphism $G_s\to \prod_{k>0} \mathfrak S_{m_k}$
consists of permutations that fix each $s_i$.
It is clearly equal to the product of the symmetric groups $\prod \mathfrak S_{n_i}$.
One thus has
$\Card(G_s)=\prod n_i! \prod_{k>0} m_k!$,
as was to be shown.
A combinatorial interpretation of the first relation
As we said above, that relation
$$ \frac{(mn)!}{m^ n!^m} = \prod_{k=1}^{m-1} \binom{kn-1}{n-1} $$
can be proved by induction, just playing with factorials,
but we want a combinatorial interpretation for it.
(Here we assume that $n\geq 1$.)
By the preceding paragraph,
the left hand side is the number of partitions of a set with $mn$ elements
of type $(n,\dots,n)$.
We may assume that this set is numbered $\{1,\dots,mn\}$.
Such a partition can be defined as follows.
First, we choose the subset that contains $1$: this amounts to choosing
$n-1$ elements among $\{2,\dots,mn\}$, and there are $\binom{mn-1}{n-1}$
possibilities.
Now, we have to choose the subset that contains the smallest element
which is not in the first chosen subset.
There are $n-1$ elements to choose among the remaining $mn-n-1=(m-1)n-1$ ones,
hence $\binom{(m-1)n-1}{n-1}$ possibilities.
And we go on in the same way, until we have chosen the $m$ required subsets.
(For the last one, there is course only one such choice, and
notice that the last factor is $\binom{n-1}{n-1}=1$.)
An integral formula for the number of partitions of given type
Finally, we wish to give an alternating formula for the number
of partitions of given type of a set $S$
that makes it clear that it is an integer.
Again, we can assume that the set $S$ is equal to $\{1,\dots,N\}$
and that $n=(n_1,\dots,n_r)$ is a multiset of integers such that $\abs n=N$.
Let us write $n$ in an other way, $n=(0^{m_0},1^{m_1},\dots)$,
meaning that $0$ is repeated $m_0$ times, $1$ is repeated $m_1$ times, etc.
One has $N=\sum k m_k$.
The idea is that we can first partition $S$ into a
subsets of cardinalities $m_1$, $2m_2$,… and then
subpartition these subsets: the first one into $m_1$ subsets with one element,
the second into $m_2$ subsets with two elements, etc.
The number of ordered partitions with $m_1$, $2m_2$… elements
is the multinomial number
$$ \binom{N}{m_1,2m_2,\dots}.$$
And the other choice is the product of integers as given in the preceding
section.
This gives
$$ \frac{\abs n!}{\prod_i n_i! \prod_{k>0}m_k(n)!}
= \binom{N}{m_1,2m_2,\dots}\prod_{k>0} \frac{(km_k)!}{k!^{m_k} m_k(n)!}.$$
We can also write the fractions that appear in the product
as integers:
$$ \frac{\abs n!}{\prod_i n_i! \prod_{k>0}m_k(n)!}
=\binom{N}{m_1,2m_2,\dots} \prod_{k>0} \prod_{m=1}^{m_k}
\binom {km-1}{k-1}.$$
