Exercise 4.1.13* ($\rho = \frac{n!}{a_1!a_2!\cdots a_r!}$ is an integer if $(a_1,a_2,\ldots,a_r) = 1$ and $a_1+a_2+ \cdots + a_r = n+1$)

Proof.

(a)

If $\mathit{a\rho }=m\in \mathbb{Z}$ and $\mathit{b\rho }=n\in \mathbb{Z}$, then $$\mathit{mb}=\mathit{ab\rho }=\mathit{na}.$$

Since $a\mid \mathit{mb}$, where $a\wedge b=1$, we obtain $a\mid m$, thus $\rho =m∕a$ is an integer.

(b)

If $n=0$, then $0!∕(1!0!)$ is an integer, so we can assume that $n$ is a positive integer. Suppose that $a\wedge b=1$ and $a+b=n+1$.

If $a=0$, then $b=n+1$, and $a\wedge b=0\wedge (n+1)=n+1\ne 1$. This shows that $a\ne 0$, and similarly $b\ne 0$. Therefore $a\le n$ and $b\le n$. This justifies

$$\{\begin{array}{cc}\mathit{\rho a}\hfill & =\frac{n!}{(a-1)!b!}=\left(\genfrac{}{}{0.0pt}{}{n}{a-1}\right)\in \mathbb{Z},\hfill \\ \mathit{\rho b}\hfill & =\frac{n!}{a!(b-1)!}=\left(\genfrac{}{}{0.0pt}{}{n}{b-1}\right)\in \mathbb{Z}.\hfill \end{array}$$

By part (a), since $a\wedge b=1$, $\rho \in \mathbb{Z}$.

This shows that $\rho =n!∕(a!b!)$ is an integer if $(a,b)=1$ and $a+b=n+1$. Put $\rho =\frac{n!}{a!b!}$

(c)

Let $a_1,\dots ,a_r$ be positive integers. Suppose first that $\rho$ is a real number such that $\rho a_1=n_1,\cdots ,\rho a_r=n_r$ are integers, where $a_1\wedge \cdots \wedge a_r=1$. Then for all $({\lambda }_1,\dots ,{\lambda }_r)\in {\mathbb{Z}}^r$, $$\rho =\frac{n_1}{a_1}=\cdots =\frac{n_r}{a_r}=\frac{{\lambda }_1{n}_1+\cdots +{\lambda }_r{n}_r}{{\lambda }_1{a}_1+\cdots +{\lambda }_r{a}_r}.$$

Since $a_1\wedge \cdots \wedge a_r=1$, we can choose ${\lambda }_1,\dots ,{\lambda }_r$ such that ${\lambda }_1{a}_1+\cdots +{\lambda }_r{a}_r=1$, thus

$$\rho ={\lambda }_1{n}_1+\cdots +{\lambda }_r{n}_r\in \mathbb{Z}.$$

This is a generalization of the Lemma of part (a).

Suppose now that $a_1\wedge \cdots \wedge a_r=1$ and $a_1+\cdots +a_r=n+1$ ( $n\in \mathbb{N}$).

If $n=0$, then $0!∕(1!0!\cdots 0!)$ is an integer, so we can assume that $n$ is a positive integer. Put $\rho =\frac{n!}{a_1!a_2!\cdots a_r!}$.

If $a_i=n+1$ for some index $i$, then the other $a_j$ are $0$, thus $a_1\wedge \cdots \wedge a_r=n+1\ne 1$. This shows that $a_i\le n$ for all $i\in [[1,r]]$.

Then for all $i\in [[1,r]]$,

$$\rho a_i=\{\begin{array}{cc}\hfill \frac{n!}{a_1!a_2!\cdots (a_i-1)!\cdots a_r!}\hfill & \text{ if }{a}_i\ge 1,\hfill \\ \hfill 0\hfill & \text{ if }{a}_i=0.\hfill \end{array}$$

We write for simplicity $b_1=a_1,b_2=a_2,\dots ,b_i=a_i-1,\dots ,b_r=a_r$, so that $N=\frac{n!}{a_1!a_2!\cdots (a_i-1)!\cdots a_r!}=\frac{n!}{b_1!b_2!\cdots b_r!}$ and $b_1+b_2+\cdots +b_r=n$.

Since $(n-b_1-b_2-\cdots -b_r)!=0!=1$,

$$\begin{array}{llll}\hfill \frac{n!}{b_1!b_2!\cdots b_r!}& =\frac{n!}{b_1!(n-b_1)!}\frac{(n-b_1)!}{b_2!(n-b_1-b_2)!}\cdots \frac{(n-b_1-b_2-\cdots -b_{r-1})!}{b_r!(n-b_1-b_2-\cdots -b_r)!}& \hfill & \\ \hfill & =\left(\genfrac{}{}{0.0pt}{}{n}{b_1}\right)\left(\genfrac{}{}{0.0pt}{}{n-b_1}{b_2}\right)\cdots \left(\genfrac{}{}{0.0pt}{}{n-b_1-b_2-\cdots -b_{r-1}}{b_r}\right)\in \mathbb{Z}.& \hfill & \end{array}$$

( $\left(\genfrac{}{}{0.0pt}{}{n}{b_1,b_2,\dots ,b_r}\right)=\frac{n!}{b_1!b_2!\cdots b_r!}$ is a multinomial coefficient, an another proof p.183 shows that such a multinomial coefficient is an integer when $b_1+b_2+\cdots +b_r=n$). Therefore, in both cases $a_i=0,a_i\ge 1$,

$$\rho a_i\in \mathbb{Z},i=1,2,\dots ,r.$$

By the generalized lemma proven above, we obtain $\rho \in \mathbb{Z}$.

In conclusion, $\rho =\frac{n!}{a_1!a_2!\cdots a_r!}$ is an integer if $a_1\wedge a_2\wedge \dots \wedge a_r=1$ and $a_1+a_2+\cdots +a_r=n+1$.