Lucas' Theorem
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 arek·C(n, k) ways to choose a committee and its chairman.First, choose the committee's chairman out of n candidate. Next choose
k - 1 committee members out of the remaining n - 1 candidates. This can be accomplished inn·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 = p^{a}, with p prime,
(2) | k·C(p^{a}, k) = p^{a}·C(p^{a} - 1, k - 1), |
so that the left hand side has a prime factor p. However,
(3) | C(p^{a}, k) ≡ 0 (mod p). |
References
- 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
Pascal's Triangle and the Binomial Coefficients
- Binomial Theorem
- Arithmetic in Disguise
- Construction of Pascal's Triangle
- Dot Patterns, Pascal Triangle and Lucas Theorem
- Integer Iterations on a Circle
- Leibniz and Pascal Triangles
- Lucas' Theorem
- Lucas' Theorem II
- Patterns in Pascal's Triangle
- Random Walks
- Sierpinski Gasket and Tower of Hanoi
- Treatise on Arithmetical Triangle
- Ways To Count
- Another Binomial Identity with Proofs
- Vandermonde's Convolution Formula
- Counting Fat Sets
- e in the Pascal Triangle
- Catalan Numbers in Pascal's Triangle
- Sums of Binomial Reciprocals in Pascal's Triangle
- Squares in Pascal's Triangle
- Cubes in Pascal's Triangle
- Pi in Pascal's Triangle
- Pi in Pascal's Triangle via Triangular Numbers
- Ascending Bases and Exponents in Pascal's Triangle
- Determinants in Pascal's Triangle
|Contact| |Front page| |Contents| |Algebra|
Copyright © 1996-2017 Alexander Bogomolny
62608270 |