8
$\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$
3
$\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$

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.