How to prove this?

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.

Note by Kenny Lau
3 years, 6 months ago

No vote yet
1 vote

  Easy Math Editor

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 \( 2 \times 3 \)
2^{34} \( 2^{34} \)
a_{i-1} \( a_{i-1} \)
\frac{2}{3} \( \frac{2}{3} \)
\sqrt{2} \( \sqrt{2} \)
\sum_{i=1}^3 \( \sum_{i=1}^3 \)
\sin \theta \( \sin \theta \)
\boxed{123} \( \boxed{123} \)

Comments

Sort by:

Top Newest

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

Brian Charlesworth - 3 years, 6 months ago

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 - 3 years, 5 months ago

Log in to reply

Let'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 - 3 years, 5 months ago

Log in to reply

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

Paulo Guilherme Santos - 3 years, 5 months ago

Log in to reply

Do you find my proof clear?

Paulo Guilherme Santos - 3 years, 5 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...