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$
  • $\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$ – darij grinberg Sep 19 '15 at 21:17
  • $\begingroup$ #Michael thanks for the edit $\endgroup$ – René Gy Sep 19 '15 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 '15 at 21:36
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$

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.