2

$n, j_1, j_2, j_3, \ldots, j_k \in \mathbb{N}$ are such that: $j_1+ j_2+ j_3+\cdots+ j_k = n$. Prove that $$\frac{n!}{j_1! j_2! j_3! \cdots j_k!} \in \mathbb{Z}.$$ I don't know how to do it. Tried induction and $e^{\ln(j_1! j_2! j_3! \cdots j_k!)}$ but non of those seem to be working.

Sangchul Lee
  • 167,468
theboyboy
  • 397
  • What is a "total number"? – Luke Collins Nov 26 '20 at 18:39
  • I ment that "$\in \mathbb{Z}$". I am sorry. – theboyboy Nov 26 '20 at 18:40
  • Induction works. Can you show your attempt and where you're stuck at? – Calvin Lin Nov 26 '20 at 18:41
  • Use induction on $n$ and the concept of the binomial coefficient. – Sangchul Lee Nov 26 '20 at 18:41
  • I don't see how induction would work for n= 2. n = 1 (base case) is fine. But n = 2? Then $j_1 + j_2 = 2$, so $j_1 = j_2$? – theboyboy Nov 26 '20 at 18:43
  • Your base case will be $n=2$. The case $n=1$ is trivial and can be separated from the general argument. Also, using $\exp(\cdot)$ and $\ln(\cdot)$ in this type of problem is not a good idea, because you have almost no control over when they become integers. – Sangchul Lee Nov 26 '20 at 18:45
  • I would use the fact that writing the factorial's prime factorization $n! = \prod_i p_i^{a_i}$, we have $a_i = \sum_{m=1}^\infty \left \lfloor \frac{n}{p^m} \right \rfloor$. – aschepler Nov 26 '20 at 18:46
  • Yeah, but as I mentioned, I don't see how is that true for my base case then (I mean for n = 2). – theboyboy Nov 26 '20 at 18:50
  • 1
    Induction on $n$ doesn't get far, right. Induction on $k$ can work, though. – aschepler Nov 26 '20 at 18:53
  • 1
    Are you aware of the notion of binomial coefficient? $$\binom{n}{k}=\frac{n!}{k!(n-k)!}$$ counts the number of ways of arranging $k$ objects of type 1 and $n-k$ objects of type 2, hence is an integer. – Sangchul Lee Nov 26 '20 at 18:53

3 Answers3

3

The given expression counts the number of ways to order $n$ objects, with $j_1$ objects of type $1$, $j_2$ of type $2$ and so on until $j_k$ objects of type $k$, and there are no other objects or types. Thus the expression must be an integer.

Parcly Taxel
  • 103,344
2

For induction on $k$, the base step $k=1$ gives a ratio $\tfrac{n!}{n!}=1$. To go from $k=j$ to $k=j+1$ in the inductive step, replace $\tfrac{1}{j_k^\text{old}!}$ with $\frac{1}{j_k^\text{new}!j_{k+1}!}$, wth $j_k^\text{new}=j_k^\text{old}-j_{k+1}$. This multiplies the ratio by $\frac{j_k^\text{old}!}{j_k^\text{new}!j_{k+1}!}=\binom{j_k^\text{old}}{j_{k+1}}$, which is an integer. In fact, this insight allows us to prove by telescoping product$$\frac{n}{\prod_{j=1}^kj_j!}=\prod_{l=1}^{k-1}\binom{n-\sum_{j=1}^{l-1}j_j}{j_l}.$$

J.G.
  • 115,835
1

Assuming that binomial coefficients are integers (they are, by a simple combinatorial argument), you can use them with telescoping to write your expression: \begin{align*} &\binom{j_1+\cdots +j_k}{j_1}\cdot \binom{j_2+\cdots +j_k}{j_2}\cdots \binom{j_{k-1}+j_k}{j_{k-1}}\cdot \binom{j_k}{j_k}\\ &= \frac{(j_1+\cdots +j_k)!}{j_1!\cdot (j_2+\cdots +j_k)!}\cdot \frac{(j_2+\cdots +j_k)!}{j_2!\cdot (j_3+\cdots +j_k)!}\cdots \frac{(j_{k-1}+j_k)!}{j_{k-1}!\cdot j_k!}\cdot \frac{j_k!}{j_k!\cdot 0!}\\ &= \frac{(j_1+j_2+\cdots +j_k)!}{j_1!\cdot j_2!\cdots j_k!} \end{align*}

Favst
  • 3,385
  • 1
  • 9
  • 25