2
$\begingroup$

Let $B(n)$ be the set of the integer partitions of the integer $n\gt0$, with the notation: $$B(n)=\left\{(b_1,\ldots,b_n)\in\mathbb{N}^n \ \ ; \sum_{i=1}^{n} i\cdot b_i=n \right\}$$

Ex: the 7 elements of B(5) are: 
(5,0,0,0,0) for 1+1+1+1+1
(3,1,0,0,0) for 1+1+1+2 
(2,0,1,0,0) for 1+1+3
(1,0,0,1,0) for 1+4
(0,0,0,0,1) for 5
(0,1,1,0,0) for 2+3
(1,2,0,0,0) for 1+2+2

How can it be shown that:

$$n!=\operatorname{lcm} \left\{\prod_{i=1}^{n}i^{b_i}\cdot b_i!\ \ ;(b_1,\ldots,b_n)\in B(n) \right\} $$

I know that $\operatorname{lcm} \left\{\prod_{i=1}^{n}i^{b_i}\cdot b_i!;(b_1,\ldots,b_n)\in B(n) \right\} $ is a multiple of $n!$

since $n!$ is one of the $\prod_{i=1}^n i^{b_i}\cdot b_i!$ corresponding to $(b_1,\ldots,b_n)=(n,0,\ldots,0)$

now I need to prove that $n!$ is a multiple of $\prod_{i=1}^n i^{b_i}\cdot b_i!$ for all $(b_1,\ldots,b_n)\in B(n)$

I know that $n!$ is a multiple of $\prod_{i=1}^n {i!}^{b_i}$, since $\dfrac{n!} {\prod_{i=1}^n {i!}^{b_i}}$ is a multinomial coefficient, but this does not seem to help...

LATER EDIT After some research, I have found another (weaker but sufficient) argument that does not need to refer to the combinatorial interpretation of the $\frac{n!} {\prod_{i=1}^n i^{b_i}\cdot b_i!}$ (as in the answer herefater)

The coefficients $\frac{n!} {\prod_{i=1}^n i!^{b_i}\cdot b_i!}$ in Faa di Bruno's formula are integers as they count the number of partitions of a set of $n$ elements in subsets whose sizes make a given partition of the integer $n$. Then it is clear that $\frac{n!} {\prod_{i=1}^n i^{b_i}\cdot b_i!}$ are also integers.

$\endgroup$
3
  • $\begingroup$ If $\left(b_1,b_2,b_3,\ldots\right)$ satisfies $\sum_i i b_i = n$, then the number of all permutations $\pi \in S_n$ which have $b_1$ cycles of length $1$ and $b_2$ cycles of length $2$ and $b_3$ cycles of length $3$ and so on is $n! / \prod_i i^{b_i} b_i!$. See Theorem 2 in cip.ifi.lmu.de/~grinberg/algebra/witt4b.pdf for a proof (though I hope there are better writeups somewhere). $\endgroup$ Sep 19, 2015 at 21:17
  • $\begingroup$ #Michael thanks for the edit $\endgroup$
    – René Gy
    Sep 19, 2015 at 21:33
  • $\begingroup$ #darij thank you too; I was not suspecting it would go that far. I will try to catch up $\endgroup$
    – René Gy
    Sep 19, 2015 at 21:36

1 Answer 1

0
$\begingroup$

As darij grinberg said in the comments, the number of permutations of $[n]$ of type $\beta=\langle b_1,\ldots,b_n\rangle$ is

$$\frac{n!}{\prod_{k=1}^nk^{b_k}b_k!}\;;\tag{1}$$

Miklós Bóna gives a pretty easy proof in his Introduction to Enumerative Combinatorics. Write down any one of the $n!$ permutations of $[n]$. Now insert pairs of parentheses to get a string in cycle notation whose first $b_1$ cycles have length $1$, whose next $b_2$ cycles have length $2$, and so on. Every permutation of $[n]$ of type $\beta$ is generated in this way, but of course each is generated more than once. Fortunately, it’s easy to see how often each permutation is generated: for each $k\in\{1,\ldots,n\}$ there are $b_k!$ permutations of the set of $k$-cycles, and each of the $b_k$ $k$-cycles can be listed with any one of its $k$ elements appearing first, so each permutation of type $\beta$ is generated $\prod_{k=1}^nk^{b_k}b_k!$ times. Thus, $(1)$ gives the number of distinct permutations of $[n]$ of type $\beta$.

$\endgroup$

You must log in to answer this question.

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