59
$\begingroup$

From its definition a combination $\binom{n}{k}$, is the number of distinct subsets of size $k$ from a set of $n$ elements.

This is clearly an integer, however I was curious as to why the expression

$$\frac{n!}{k!(n-k)!}$$ always evaluates to an integer.

So far I figured:

$n!$, is clearly divisible by $k!$, and $(n-k)!$, individually, but I could not seem to make the jump to proof that that $n!$ is divisible by their product.

  • 14
    You answered it in your first sentence. One way to show that something is an integer is to show that it counts something. So I guess you want a non-counting proof.2010-11-23
  • 2
    @Jonas the fact that $nCr$ relates to Pascal's Triangle is another answer. I wouldn't call it a proof though.2014-01-07
  • 1
    This is closely related to the fact that product of $k$ consecutive numbers is divisible by $k!$. See http://math.stackexchange.com/questions/12067/the-product-of-n-consecutive-integers-is-divisible-by-n-without-using-the-prop2016-04-07
  • 0
    Related: https://math.stackexchange.com/questions/514692018-11-29

11 Answers 11

-1

One way to get there: any product of $k$ consecutive positive integers $d := \frac{n!}{(n-k)!} = \prod^k (n-i+1)$ is divisible by $k!$.

You can assure yourself of this by considering divisibility by the primes and prime powers up to $k$. For example, $k!$ has $\lfloor k/p\rfloor$ multiples of $p$, and $d$ will have either the same number of multiples of $p$ or one more, since the "first" multiple of $p$ in $k!$ will be at $p$, whereas it may be earlier in $d$.

The quantity I have denoted by $d$ is the $k$-descending factorial of $n$, sometimes written $n^{\underline k}$ or $(n)_k$.

38

Well, one noncombinatorial way is to induct on $n$ using Pascal's triangle; that is, using the fact that ${n \choose k} = {n-1 \choose k - 1} + {n-1 \choose k}$ (easy to verify directly) and that each ${n - 1 \choose 0}$ is just $1$.

27

See my post here for a simple purely arithmetical proof that every binomial coefficient is an integer. The proof shows how to rewrite any binomial coefficient fraction as a product of fractions whose denominators are all coprime to any given prime $\rm\:p.\,$ This implies that no primes divide the denominator (when written in lowest terms), therefore the fraction is an integer.

The key property that lies at the heart of this proof is that, among all products of $\rm\, n\,$ consecutive integers, $\rm\ n!\ $ has the least possible power of $\rm\,p\,$ dividing it - for every prime $\rm\,p.\,$ Thus $\rm\ n!\ $ divides every product of $\rm\:n\:$ consecutive integers, since it has a smaller power of every prime divisor. Therefore $$\rm\displaystyle\quad\quad {m \choose n}\ =\ \frac{m!/(m-n)!}{n!}\ =\ \frac{m\:(m-1)\:\cdots\:(m-n+1)}{\!\!n\:(n-1)\ \cdots\:\phantom{m-n}1\phantom{+1}}\ \in\ \mathbb Z$$

  • 0
    Thanks, and sorry for the late reply/upvote :)2012-09-03
9

As Jonas mentioned, it counts something so it has to be a natural number.

Another way is to notice that product of $m$ consecutive natural numbers is divisible by $m!$.(Prove this!)

So if we write $n! = n(n-1)(n-2) \cdots (k+1) \times (k!)$, we find that $k!$ divides $k!$ and

$n(n-1)(n-2) \cdots (k+1)$ is a product of $(n-k)$ consecutive natural numbers and hence $(n-k)!$ divides it.

  • 0
    I haven't thought too hard about this, but does there exist a direct proof (that does not rely on induction) of the fact that the product of $m$ consecutive numbers is divisible by $m!$?2010-11-23
  • 0
    @Vladimir: You could prove that the prime factors of the numerator is of higher power than that of the denominator. You can look at Bill's proof which he has posted in the next post.2010-11-24
  • 7
    @Vladimir: Generally, any proof (in Peano arithmetic) that some property is true for all integers must use induction. It may not *explicitly* invoke induction, e.g. the induction might be hidden way down some chain of lemmas. So it's not clear what it means for such a proof to "not rely on induction".2010-11-24
5

According to this, the highest power of a prime number, $p, $ that divides $N!$ is $$s_p(N!) = \left \lfloor \frac{N}{p} \right \rfloor + \left \lfloor \frac{N}{p^2} \right \rfloor + \left \lfloor \frac{N}{p^3} \right \rfloor + \cdots$$

Since $\dbinom{N}{M} = \dfrac{N!}{M! (N-M)!}\,, $ the question then becomes, is $s_p(M!) + s_p((N-M)!) \le s_p(N!)$?

Clearly $\left \lfloor x \right \rfloor + \left \lfloor y \right \rfloor \le x + y. $ Since $\left \lfloor x+y \right \rfloor$ is the greatest integer less than or equal to $x + y, $ it follows that $\left \lfloor x \right \rfloor + \left \lfloor y \right \rfloor \le \left \lfloor x+y \right \rfloor,$

Hence $$\left \lfloor \dfrac{M}{p^{\,i}} \right \rfloor + \left \lfloor \dfrac{N-M}{p^{\,i}} \right \rfloor \le \left \lfloor \dfrac{N}{p^{\,i}} \right \rfloor$$

for all $i$. Summing, we get $s_p(M!) + s_p((N-M)!) \le s_p(N!)$

It follows that $\dbinom{N}{M}$ is an integer.

1

Another way to think of it is combinatorially, which is of course the motivation.

Let $1\le k\le n$. Consider the set $S$ of all sequences of $k$ distinct numbers among $\{1,\dots,n\}$. The size of $S$ is $n\cdot (n-1)\cdots (n-k+1)=\frac{n!}{(n-k)!}$. Say two sequences in $S$ are equivalent if the underlying set of elements is the same. Then each equivalence class has exactly $k!$ elements since any choice of $k$ elements admits $k!$ permutations. So the set $S$ can be partitioned into sets each of which has size $k!$. So $|S|$ is divisible by $k!$.

1

Consider the set

$S=\Big\{k\in\mathbb{N}:(\forall m,n\in \mathbb{N})\left(0\leq m\leq n\wedge m+n=k\Rightarrow \binom{n}{m}\in\mathbb{N}\right)\Big\}$

1) If $0\leq m\leq n$ and $m+n=0$, then $m=n=0\Rightarrow \binom{n}{m}=\binom{0}{0}=1\in \mathbb{N}\Rightarrow 0\in S$

2) If $0\leq m\leq n$ and $m+n=1$, then $m=0\wedge n=1\Rightarrow \binom{n}{m}=\binom{1}{0}=1\in\mathbb{N}\Rightarrow 1\in S$

Assume that $p\in S,\, \forall p\leq k$, then $0\leq m\leq n\wedge m+n=p\leq k\Rightarrow \binom{n}{m}\in\mathbb{N}$

If $m=0$, then $\binom{n}{m}=\binom{n}{0}=1\in \mathbb{N},\, \forall n\in\mathbb{N}$

If $m=n$, then $\binom{n}{m}=\binom{n}{n}=1\in \mathbb{N},\, \forall n\in\mathbb{N}$

Therefore we can only consider the cases in which $0.

If $0 and $m+n=k+1$, then $m+(n-1)=k$ which implies, by induction hypothesis, that $\binom{n-1}{m}\in \mathbb{N}$ since $0.

$(m-1)+(n-1)=k-1\leq k\Rightarrow \binom{n-1}{m-1}\in\mathbb{N}$ since $0(also by induction hypothesis)

By Pascal's rule we have

$\binom{n}{m}=\binom{n-1}{m}+\binom{n-1}{m-1}$

We saw that $\binom{n-1}{m}$ and $\binom{n-1}{m-1}$ are natural number, therefore $\binom{n}{m}$ is also a natural number, by pascal's rule.

Therefore $k+1\in S$ which implies, by strong induction, that $S=\mathbb{N}$. Hence $\binom{n}{m}\in\mathbb{N},\, \forall 0\leq m\leq n$.

0

The proofs I see here so far seemed rather complicated to me, so I came up with what seemed like a simpler proof. However, it proved to have gaps in reasoning; so I came up with an even simpler proof:

Theorem: The product of any k consecutive positive integers [k>=1] is always divisible by k!.

Proof:

  1. (m+1)...(m+k) = (m+k)!/m! (By definition of "factorial"; note that left side, right side, numerator, and denominator are all integers.)
  2. (m+1)...(m+k) = ((m+k)!/((k!)(m!)))k! (Multiplied top and bottom of fraction by integer k!; therefore left side, right side, numerator, denominator, fraction, and k! are all integers.)
  3. Hence, (m+1)...(m+k) is always an integer multiple of k!
  4. Hence, (m+1)...(m+k) is always divisible by k!, QED.

Corollary: n!/((n-k)!k!) [n>=1,k>=1,k<=n] is always an integer.

Proof:

  1. n!/((n-k)!k!) = ((n-k+1)(n-k+2)...(n-k+k)) / k!
  2. This is a product of k consecutive integers, divided by k!.
  3. Any product of k consecutive integers is always divisible by k!, due to the theorem I just proved above.
  4. Therefore n!/((n-k)!k!) is an integer, QED.

[Note: the theorem and its corollary are also valid for n=0, k=0, m=0 if we stipulate certain definitions:

  1. "The product of 0 consecutive integers" = 1
  2. 0 is "divisible" by every positive integer
  3. "0!" = 1.

Without those stipulations, the theorem & corollary fails if k, m, or n is 0.]

  • 0
    Step 5 in your first proof does not sound right. In general, that an integer $m$ is divisible by $1,2,\ldots,n$ does not imply that $m$ is divisible by $n!$ (e.g. $12$ is divisible by $1,2,3,4$ but not by $4!$). This is why some other proofs here want to count prime powers. You need to justify how to proceed from step 4 to step 5.2018-03-30
  • 0
    user1551 : Yes, that is an issue. Thanks for pointing that out. However, the reason 12 isn't divisible by 4! is that some of the factors are "re-used", whereas in 5*6*7*8*9 (for example) they're not. I need to think of a way to show that (for example) 5*6*7*8*9 contains 1 and 2 and 3 and 4 and 5 as independent factors. We know that the first 2 contain 2 as a factor. We know that the first 3 contain 3, first 4 contain 4, etc. But not every integer adds a new factor. the 7 doesn't add anything we need because it's prime. Hmmm. I'll have to think about this.2018-03-30
  • 0
    user1551 : Ok, I corrected my proof. It's no longer quite as simple, but I think it's more accurate. I managed to do with without resorting to counting prime powers or using modular arithmetic, by using integer division instead. The wording may be a bit murky, but I think the logic is now valid. What do you think?2018-03-30
  • 0
    user1551: It suddenly occurred to me that there is a much simpler proof that "product of k consecutive integers is divisible by k!". It's absurdly simple: (m+1)...(m+k) = (m+k)!/m! and since m>k, m! contains k! as a factor.2018-03-31
0

Zarrax's answer is a good start, but to show that $\frac{n!}{k!\,(n-k)!}\in\mathbb{Z}$ we should really show that the definition by Pascal's Rule and $\frac{n!}{k!\,(n-k)!}$ agree.

First, the edge cases match, $\binom{n}{0}=\binom{n}{n}=1$: $$ \frac{n!}{0!\,n!}=1\qquad\text{and}\qquad\frac{n!}{n!\,0!}=1 $$

Next, Pascal's Rule fits, $\binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1}$: $$ \begin{align} \frac{(n-1)!}{(n-k-1)!\,k!}+\frac{(n-1)!}{(n-k)!\,(k-1)!} &=\frac{(n-k)\,(n-1)!}{(n-k)!\,k!}+\frac{k\,(n-1)!}{(n-k)!\,k!}\\ &=\frac{n\,(n-1)!}{(n-k)!\,k!}\\ &=\frac{n!}{(n-k)!\,k!} \end{align} $$ Therefore, by induction on $n$, $$ \binom{n}{k}=\frac{n!}{k!\,(n-k)!} $$

0

Note 1:

  • in any set of y consecutive natural numbers, there will always be a subset where each number is divisible by at least 1 number in the range 1 to y.

    Example: 2,3,4,5,6

  • 6 is divisible by 1,2 or 3

  • 2 is divisible by 1,2
  • 3 is divisible by 1,3
  • 4 is divisible by 1,2, or 4
  • 5 is divisible by 1, or 5

These last 2 in bold, are forced but the others have some freedom.

Note 2:

  • There will be n-k consecutive numbers in the quotient of n! and k! (k+1 to n). Therefore, We know we can find numbers that divide by each of the numbers 1 to n-k.
  • Proving that they don't overlap is the real hard part (effectively proving there are enough prime factors to complete all the factorizations separately) .

Note 3:

  • 1 in m numbers divide by m (specifically every mth number).

This leads us to the conclusion that the density of relevant divisors is sufficient, as it's unchanged under translation along the number line. Therefore it can divide out their product.

-1

Here is how I envision justifying a binomial coefficient (bc) to always be an integer. A bc is of the form n!/((k!(n-k)!) . First consider just n!/(n-k)! which reduces to the terms n,(n-1), : : : (n-k+2),(n-k+1) in the numerator. If n = 14 and k =5 for example, it would be 14!/9! = 14,13,12,11,10 left in the numerator. We now bring in the remaining denominator term, k!, so we have 14,13,12,11,10 /5,4,3,2,1 for our bc. Remembering how a sequence of consecutive integers are created (or invoking the well ordered principle), we can say that any integer k will occur at least once in every sequence of k consecutive integers, and as there are k integers in the numerator, at least one will be divisible in turn by each integer in the denominator. Note in my example that 4 and 3 both divide 12. I hope this helps, but you probably already have a good handle on it by now. Bill