Lucas' theorem asserts that, for p prime,
|(1)||k·C(n, k) = n·C(n - 1, k - 1).|
This identity admits an elegant combinatorial proof. Assume the task is to choose a k-member committee and its chairman out of a group of n candidates. We can approach the task in two ways:
First select k members of the committee (which can be done in
C(n, k)ways) and out of the selected group choose one person to head the committee. This can be done in k ways. In all, there are k·C(n, k)ways to choose a committee and its chairman.
First, choose the committee's chairman out of n candidate. Next choose
k - 1committee members out of the remaining n - 1 candidates. This can be accomplished in n·C(n - 1, k - 1)ways.
(1) merely asserts that the number of ways to compose the committee is the same regardless of the manner in which it is counted.
Now, for Lucas' theorem. Let n = pa, with p prime,
|(2)||k·C(pa, k) = pa·C(pa - 1, k - 1),|
so that the left hand side has a prime factor p. However,
|(3)||C(pa, k) ≡ 0 (mod p).|
- A. T. Benjamin, J. J. Quinn, Proofs That Really Count: The Art of Combinatorial Proof, MAA, 2003
- I. Stewart, Game, Set and Math, Penguin Books, 1989
Copyright © 1996-2018 Alexander Bogomolny