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

A student asked,

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

A more general statement would be to show that if n_{1}+n_{2}+...+n_{k}=n,
then

(1) n! / (n_{1}!n_{2}!...n_{k}!)

is an integer. Then the student's proof is done by letting n_{1}=n_{2}=...=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^{2}] + ...

(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 this Math Help site is
Graeme McRae.