Proving C(n,k) is an integer by counting primes

A student asked,

How do you prove that for every k, n>=1, (k!)ⁿ divides (kn)!

A more general statement would be to show that if n₁+n₂+...+n_k=n, then

(1)   n! / (n₁!n₂!...n_k!)

is an integer.  Then the student's proof is done by letting n₁=n₂=...=n/k

Consider the prime factorizations of the numerator and denominator of expression (1), above.

Pick a prime number, p.  This prime appears as a factor in the numerator F_n,p times, where F_n,p is given by

(2)   F_n,p = [n/p] + [n/p²] + ...

(Square brackets indicate the "floor" function.)  The number of times p appears in the denominator is

(3)   F_n1,p + F_n2,p + ... F_nk,p

Expression (3) is not larger than expression (2) because for any real numbers a and b,

(4) [a] + [b] <= [a+b]

So any prime number, p, appears as a factor at least as many times in the numerator as in the denominator.

Intuitively, this is clear, because the numerator doesn't "hit" a factor of 5, for example, until it's had 4 misses. It doesn't hit a double-whammy, 25, until it's had 24 misses or singles.

This is like getting paid in arrears on Friday for the work you've been doing all week.

The denominator, on the other hand, is starting over at 1 again and again.  In my pay day analogy, the denominator works until Thursday, then is told the next day is Monday and to shut up and quit griping.  This poor denominator won't get paid until he's ticked off at least nine days!

Outline of a Proof that (2a)!(2b)!/((a+b)!a!b!) is an integer

Borrowing the "counting primes" logic, above, this proof boils down to showing

[2x]+[2y] >= [x+y] + [x] + [y],

where [x] represents the "floor" of x.  Changing x or y by any integer obviously changes both sides by the same integer, so we can assume that x and y are both in [0,1), and then we have [x]=[y]=0 and just have to show that [2x]+[2y] >= [x+y].  Well, the RHS is at most 1, and it's 1 iff x+y >= 1, and in that case either x or y must be at least 1/2, and we're done.

The actual proof, as they say, is left to the reader.

Related pages in this website

Counting

Combination identities proves the standard combination identities, including C(n,k) = C(n-1,k-1) + C(n-1,k) and many others.

Floor Function Identities, which are used in proofs that combinatorial identities are integers

The webmaster and author of the Math Help site is Graeme McRae.
     [home]  [email]  [search]  [Links to Math Sites]  [Whiteboard]