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

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

• Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
• Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
• Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
• Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

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}$

## Comments

Sort by:

Top Newest

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

- 5 years, 11 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.

- 5 years, 11 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. By definition of $m_2$, we have that $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

- 5 years, 10 months ago

Log in to reply

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

- 5 years, 10 months ago

Log in to reply

Do you find my proof clear?

- 5 years, 10 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...