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.

No vote yet

1 vote

×

Problem Loading...

Note Loading...

Set Loading...

## 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

Log in to reply

Where is a complete proof from zero very justified. Hope you enjoy!

Log in to reply

Comment deleted Jul 24, 2015

Log in to reply

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

Comment deleted Jul 24, 2015

Log in to reply

Log in to reply

Comment deleted Jul 24, 2015

Log in to reply

Log in to reply

Comment deleted Jul 24, 2015

Log in to reply

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.

Log in to reply

This is the expression for the number of Permutations with Repetition, and hence must always be a natural number.

Log in to reply

Do you find my proof clear?

Log in to reply