Please also provide a counter-example if this conjecture is invalid.

Let \(a_1,a_2,\cdots,a_n\) be positive integers such that \(\displaystyle a=\sum_{i=1}^na_i\).

Prove that: \[\frac{a!}{\prod_{i=1}^na_i!}\in\mathbb N\]

P.S. I currently have no solution. Help is much appreciated.

## Comments

Sort by:

TopNewestLet's prove, in the first place, that

\(\forall a,n \in \mathbb{N}, \displaystyle\frac{\displaystyle\prod_{i=1}^n \left( a+i \right)}{n!} \in \mathbb{N} \). \( (1) \)

Let \( a \in \mathbb{N} \).

For that achievement, I will prove that

\( \forall i \in \{1,...,n \}, \exists j \in \{a+1,..., a+n \}: i|j \).

Let's suppose, in first place, by reductio ad absurdum, that \( \nexists j \in \{a+1,..., a+n \}: n|j \). Let \(m_1= \max \{j \in \mathbb{N}: n|j \land j\leq a \} \). Let's consider \( m_1+n \). We have that, by hypothesis, \( \nexists j \in \{a+1,..., a+n \}: n|j \), so \( m_1+n>a+n \). By definition of \( m_1 \), we have that \(m_1 \leq a \iff -m_1 \geq -a \). We can conclude that

\(m_1+n>a+n \iff n>a+n-m_1 \implies n>a+n-a \implies n>n \)

which is an absurdum, so \( \exists j \in \{a+1,..., a+n \}: n|j \).

Now, let \( i \in \{1,...,n-1 \} \). Let's suppose, in these conditions, by reductio ad absurdum, that \( \nexists j \in \{a+1,..., a+n \}: i|j \). Let \(m_2= \max \{j \in \mathbb{N}: i|j \land j<a+1 \} \). By definition of \( m_2 \), we have that \(m_2<a+1 \iff -m_2>-(a+1) \). Now, let's consider \(m_2+i \). By hypothesis we have that \( \nexists j \in \{a+1,..., a+n \}: i|j \), so \(m_2+i>a+n \). We can conclude that

\(m_2+i>a+n \iff i>a+n-m_2 \implies i>a+n-(a+1) \implies i>n-1 \implies i \notin \{1,...,n-1 \} \)

which is an absurdum, as wanted. So we have that

\( \forall i \in \{1,...,n \}, \exists j \in \{a+1,..., a+n \}: i|j \).

Let's consider, for each \(i \in \{1,...,n \} \), \(A_i= \{ n \in \{a+1,..., a+n \}: i|n \} \), and \(A= \{A_i: i \in \{1,...,n \} \} \). As \( \forall i \in \{1,...,n \}, A_i \neq \emptyset \), we conclude that \(A \neq \emptyset \). By the Axiom of Choice, we have that

\( \exists f \in \mathscr{F} \left( A, \bigcup A \right): \forall X \in A, f(X) \in X \) .

Let \(f \in \mathscr{F} \left( A, \bigcup A \right) \) be in that conditions. In these conditions, by the definition of \(f \), it is clear that

\(\displaystyle\frac{\displaystyle\prod_{i=1}^n f(A_i) }{n!} \in \mathbb{N} \).

Let \( b \in \mathbb{N} \) be such that \( b= \displaystyle\frac{\displaystyle\prod_{i=1}^n f(A_i) }{n!} \) and let \(Y= \{f(A_i): i \in \{1,...,n \} \} \). We have that

\(\displaystyle\frac{\displaystyle\prod_{i=1}^n \left( a+i \right)}{n!}=\displaystyle\frac{\displaystyle\prod_{i=1}^n f(A_i) }{n!} \cdot \left(\displaystyle\prod\nolimits_{a_i \in\{a+1,..., a+n \}\setminus Y} \left( a_i \right)\right)=b \cdot \left(\displaystyle\prod\nolimits_{a_i \in\{a+1,..., a+n \}\setminus Y} \left( a_i \right)\right) \in \mathbb{N} \)

As wanted.

Now, let's prove that

\( \forall {\left( a_i \right)}_{i \in \{1,...,n\} } \in {\mathbb{N}}^n, \displaystyle\frac{ \left(\displaystyle\sum_{i=1}^n a_i \right)! }{\displaystyle\prod_{i=1}^n a_i !} \in \mathbb{N} \).

Let \(C= \Bigg\{n \in \mathbb{N}: \forall {\left( a_i \right)}_{i \in \{1,...,n \} } \in {\mathbb{N}}^n, \displaystyle\frac{ \left(\sum_{i=1}^n a_i \right)! }{\prod_{i=1}^n a_i !} \in \mathbb{N} \Bigg\} \). Let \(a_1 \in \mathbb{N} \). We have that

\(\displaystyle\frac{ \left(\displaystyle\sum_{i=1}^1 a_i \right)! }{\displaystyle\prod_{i=1}^1 a_i !}=\displaystyle\frac{a_1!}{a_1!}=1 \in \mathbb{N} \)

So, \( 1 \in C \). Now, let's suppose, by induction hypothesis, that \( n \in \mathbb{N} \). Let \( {\left( a_i \right)}_{i \in \{1,...,n+1 \} } \in {\mathbb{N}}^{n+1} \). We have that

\(\displaystyle\frac{ \left(\displaystyle\sum_{i=1}^{n+1} a_i \right)! }{\displaystyle\prod_{i=1}^{n+1} a_i !}=\displaystyle\frac{ \left(\left(\displaystyle\sum_{i=1}^n a_i \right)+a_{n+1}\right)! }{\left(\displaystyle\prod_{i=1}^n a_i !\right) \cdot a_{n+1}!}=\displaystyle\frac{ \left(\displaystyle\sum_{i=1}^n a_i \right)! }{\displaystyle\prod_{i=1}^n a_i !}\cdot \displaystyle\frac{\displaystyle\prod_{k=1}^{a_{n+1}} \left(\left(\displaystyle\sum_{i=1}^{n} a_i \right)+k \right)}{a_{n+1}!} \)

By induction hypothesis, we have that

\(\displaystyle\frac{ \left(\displaystyle\sum_{i=1}^n a_i \right)! }{\displaystyle\prod_{i=1}^n a_i !} \in \mathbb{N} \). Let \(d \in \mathbb{N} \) be such that \(d=\displaystyle\frac{ \left(\displaystyle\sum_{i=1}^n a_i \right)! }{\displaystyle\prod_{i=1}^n a_i !} \). Let \(v=a_{n+1} \) and \(S= \left(\displaystyle\sum_{i=1}^n a_i \right) \). It is clear that

\( \displaystyle\frac{\displaystyle\prod_{k=1}^{a_{n+1}} \left(\left(\displaystyle\sum_{i=1}^{n} a_i \right)+k \right)}{a_{n+1}!}= \displaystyle\frac{\displaystyle\prod_{k=1}^v \left(S+k \right)}{v!}\)

Applying \( (1) \), we conclude that

\(\displaystyle\frac{\displaystyle\prod_{k=1}^v \left(S+k \right)}{v!} \in \mathbb{N} \). Let \(p \in \mathbb{N} \) be such that \(p=\displaystyle\frac{\displaystyle\prod_{k=1}^v \left(S+k \right)}{v!} \). In these conditions we have that

\( \displaystyle\frac{ \left(\displaystyle\sum_{i=1}^{n+1} a_i \right)! }{\displaystyle\prod_{i=1}^{n+1} a_i !}=\displaystyle\frac{ \left(\displaystyle\sum_{i=1}^n a_i \right)! }{\displaystyle\prod_{i=1}^n a_i !}\cdot \displaystyle\frac{\displaystyle\prod_{k=1}^{a_{n+1}} \left(\left(\displaystyle\sum_{i=1}^{n} a_i \right)+k \right)}{a_{n+1}!}=\displaystyle\frac{ \left(\displaystyle\sum_{i=1}^n a_i \right)! }{\displaystyle\prod_{i=1}^n a_i !} \cdot \displaystyle\frac{\displaystyle\prod_{k=1}^v \left(S+k \right)}{v!}=d \cdot p \in \mathbb{N} \), because \(d,p \in \mathbb{N} \).

In these conditions we can conclude that \(n+1 \in C \). In sum, \(C= \mathbb{N} \); so,

\( \forall {\left( a_i \right)}_{i \in \{1,...,n\} } \in {\mathbb{N}}^n, \displaystyle\frac{ \left(\displaystyle\sum_{i=1}^n a_i \right)! }{\displaystyle\prod_{i=1}^n a_i !} \in \mathbb{N} \).

QED – Paulo Guilherme Santos · 1 year, 10 months ago

Log in to reply

– Paulo Guilherme Santos · 1 year, 10 months ago

Where is a complete proof from zero very justified. Hope you enjoy!Log in to reply

Log in to reply

– Kenny Lau · 1 year, 10 months ago

There's a tiny problem in your first lemma. You showed that all elements of \(A\) divide at least one element of \(B\), but not that the product of all elements of \(A\) divides the product of all elements of \(B\).Log in to reply

Log in to reply

– Kenny Lau · 1 year, 10 months ago

That cannot be proved so simply. For example, \(A=\{4,5,6\}\) and \(B=\{1,5,24\}\) satisfy the condition but not the result. Being consecutive numbers adds no validity.Log in to reply

Log in to reply

Log in to reply

Log in to reply

– Kenny Lau · 1 year, 10 months ago

Edited.Log in to reply

Apart from what Brian suggested (but similar), you can also note that your expression is the multinomial coefficient \(\dbinom{a}{a_1,a_2,\ldots, a_n}\) which must be an integer if you use the combinatorial interpretation.

For some purely arithmetical / number-theoretical proofs, see this and choose the answer you find best. – Prasun Biswas · 1 year, 10 months ago

Log in to reply

This is the expression for the number of Permutations with Repetition, and hence must always be a natural number. – Brian Charlesworth · 1 year, 10 months ago

Log in to reply

Do you find my proof clear? – Paulo Guilherme Santos · 1 year, 9 months ago

Log in to reply