# 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

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. 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 1paragraph 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}$$

Sort by:

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

- 3 years, 6 months ago

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.

- 3 years, 5 months ago

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

- 3 years, 5 months ago

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

- 3 years, 5 months ago

Do you find my proof clear?

- 3 years, 5 months ago