9
$\begingroup$

Let $\alpha = (\alpha_1,\dots, \alpha_n) \in \mathbb{N}_0^n$ be a multiindex with $\alpha_1 + \dots + \alpha_n = k$. Let $\alpha! = \alpha_1! \dots \alpha_n!$ with the convention that $0! = 1$.

I think I proved the following claim in a somewhat unexpected way, and would like some feedback if it is correct.

Claim $\alpha!$ divides $k!$

Proof: We define an action of the symmetric group $S_k$ on the set $M := \{1,\dots,k\}^k$ by $\sigma (n_1,\dots,n_k) := (n_{\sigma(1)},\dots,n_{\sigma(k)})$. Now consider the element $x = (1, \dots, 1, 2, \dots 2, \dots, n)\in M$, where each number $i$ appears $\alpha_i$ times. This is in $M$ exactly because of the hypothesis $\alpha_1 + \dots + \alpha_n = k$.

Now the stabilizer subgroup $H$ of $x$ in $S_k$ is the group which acts independently on the blocks of size $\alpha_i$. But this is isomorphic to $\prod_i S_{\alpha_i}$, which has order $\alpha!$. Because the order of any subgroup divides the order of the group we have $\alpha! = \#H \mid \#(S_k) = k!$.

What I like about this is that it is free of any calculations, which would be my first approach to prove this claim.

$\endgroup$
0

1 Answer 1

4
$\begingroup$

Your proof is entirely correct, and it seems to me the cleanest way to formalize the fact that $\frac{k!}{\alpha!}$ is the multinomial coefficient counting the number of ways to split $k$ objects into $n$ groups of $\alpha_i$ objects.

You may want to emphasize in (the conditions of) your claim that $k$ and the $\alpha_i$ are nonnegative integers.

As a small variation on your argument, instead of considering the stabilizer of $x$, you could also partition the set $\{1,\ldots,k\}$ into $n$ subsets of sizes $\alpha_i$. Then the actions of the $S_{\alpha_i}$ on these subsets give rise to an embedding $\prod_iS_{\alpha_i}$ into $S_k$, leading to the same conclusion.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .