Pascal's rule

In mathematics, Pascal's rule (or Pascal's formula) is a combinatorial identity about binomial coefficients. It states that for positive natural numbers n and k, $(\binom{n - 1}{k}) + (\binom{n - 1}{k - 1}) = (\binom{n}{k}),$ where $(\binom{n}{k})$ is a binomial coefficient; one interpretation of the coefficient of the $x k$ term in the expansion of $(1 + x) n$ . There is no restriction on the relative sizes of $n$ and $k$ ,^[1] since, if $n < k$ the value of the binomial coefficient is zero and the identity remains valid. Pascal's rule can also be viewed as a statement that the formula $\frac{(x + y)!}{x! y!} = (\binom{x + y}{x}) = (\binom{x + y}{y})$ solves the linear two-dimensional difference equation $N_{x, y} = N_{x - 1, y} + N_{x, y - 1}, N_{0, y} = N_{x, 0} = 1$ over the natural numbers. Thus, Pascal's rule is also a statement about a formula for the numbers appearing in Pascal's triangle. Pascal's rule can also be generalized to apply to multinomial coefficients.

Combinatorial proof

File:Pascal's rule 4c1 plus 4c2 equals 5c2.svg

Illustrates combinatorial proof:

(\binom{4}{1}) + (\binom{4}{2}) = (\binom{5}{2}) .

Pascal's rule has an intuitive combinatorial meaning, that is clearly expressed in this counting proof.^[2]^: 44 Proof. Recall that $(\binom{n}{k})$ equals the number of subsets with k elements from a set with n elements. Suppose one particular element is uniquely labeled X in a set with n elements. To construct a subset of k elements containing X, include X and choose k − 1 elements from the remaining n − 1 elements in the set. There are $(\binom{n - 1}{k - 1})$ such subsets. To construct a subset of k elements not containing X, choose k elements from the remaining n − 1 elements in the set. There are $(\binom{n - 1}{k})$ such subsets. Every subset of k elements either contains X or not. The total number of subsets with k elements in a set of n elements is the sum of the number of subsets containing X and the number of subsets that do not contain X, $(\binom{n - 1}{k - 1}) + (\binom{n - 1}{k})$ . This equals $(\binom{n}{k})$ ; therefore, $(\binom{n}{k}) = (\binom{n - 1}{k - 1}) + (\binom{n - 1}{k})$ .

Algebraic proof

Alternatively, the algebraic derivation of the binomial case follows. $\begin{aligned} (\binom{n - 1}{k}) + (\binom{n - 1}{k - 1}) & = \frac{(n - 1)!}{k! (n - 1 - k)!} + \frac{(n - 1)!}{(k - 1)! (n - k)!} \\ = (n - 1)! [\frac{n - k}{k! (n - k)!} + \frac{k}{k! (n - k)!}] \\ = (n - 1)! \frac{n}{k! (n - k)!} \\ = \frac{n!}{k! (n - k)!} \\ = (\binom{n}{k}) . \end{aligned}$

Generalization

Pascal's rule can be generalized to multinomial coefficients.^[2]^: 144 For any integer p such that $p \geq 2$ , $k_{1}, k_{2}, k_{3}, \dots, k_{p} \in ℕ^{+},$ and $n = k_{1} + k_{2} + k_{3} + \dots + k_{p} \geq 1$ , $(\binom{n - 1}{k_{1} - 1, k_{2}, k_{3}, \dots, k_{p}}) + (\binom{n - 1}{k_{1}, k_{2} - 1, k_{3}, \dots, k_{p}}) + \dots + (\binom{n - 1}{k_{1}, k_{2}, k_{3}, \dots, k_{p} - 1}) = (\binom{n}{k_{1}, k_{2}, k_{3}, \dots, k_{p}})$ where $(\binom{n}{k_{1}, k_{2}, k_{3}, \dots, k_{p}})$ is the coefficient of the $x_{1}^{k_{1}} x_{2}^{k_{2}} \dots x_{p}^{k_{p}}$ term in the expansion of $(x_{1} + x_{2} + \dots + x_{p})^{n}$ . The algebraic derivation for this general case is as follows.^[2]^: 144 Let p be an integer such that $p \geq 2$ , $k_{1}, k_{2}, k_{3}, \dots, k_{p} \in ℕ^{+},$ and $n = k_{1} + k_{2} + k_{3} + \dots + k_{p} \geq 1$ . Then $\begin{aligned} (\binom{n - 1}{k_{1} - 1, k_{2}, k_{3}, \dots, k_{p}}) + (\binom{n - 1}{k_{1}, k_{2} - 1, k_{3}, \dots, k_{p}}) + \dots + (\binom{n - 1}{k_{1}, k_{2}, k_{3}, \dots, k_{p} - 1}) \\ = \frac{(n - 1)!}{(k_{1} - 1)! k_{2}! k_{3}! \dots k_{p}!} + \frac{(n - 1)!}{k_{1}! (k_{2} - 1)! k_{3}! \dots k_{p}!} + \dots + \frac{(n - 1)!}{k_{1}! k_{2}! k_{3}! \dots (k_{p} - 1)!} \\ = \frac{k_{1} (n - 1)!}{k_{1}! k_{2}! k_{3}! \dots k_{p}!} + \frac{k_{2} (n - 1)!}{k_{1}! k_{2}! k_{3}! \dots k_{p}!} + \dots + \frac{k_{p} (n - 1)!}{k_{1}! k_{2}! k_{3}! \dots k_{p}!} = \frac{(k_{1} + k_{2} + \dots + k_{p}) (n - 1)!}{k_{1}! k_{2}! k_{3}! \dots k_{p}!} \\ = \frac{n (n - 1)!}{k_{1}! k_{2}! k_{3}! \dots k_{p}!} = \frac{n!}{k_{1}! k_{2}! k_{3}! \dots k_{p}!} = (\binom{n}{k_{1}, k_{2}, k_{3}, \dots, k_{p}}) . \end{aligned}$

References

↑ Mazur, David R. (2010), Combinatorics / A Guided Tour, Mathematical Association of America, p. 60, ISBN 978-0-88385-762-5
↑ ^2.0 ^2.1 ^2.2 Brualdi, Richard A. (2010), Introductory Combinatorics (5th ed.), Prentice-Hall, ISBN 978-0-13-602040-0

Bibliography

Merris, Russell. Combinatorics. John Wiley & Sons. 2003 ISBN 978-0-471-26296-1

External links

This article incorporates material from Pascal's triangle on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License. This article incorporates material from Pascal's rule proof on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License.

[1] Mazur, David R. (2010), Combinatorics / A Guided Tour, Mathematical Association of America, p. 60, ISBN 978-0-88385-762-5

[Brualdi-2] 2.0 ^2.1 ^2.2 Brualdi, Richard A. (2010), Introductory Combinatorics (5th ed.), Prentice-Hall, ISBN 978-0-13-602040-0

[1]

[2]

Pascal's rule

Contents

Combinatorial proof

Algebraic proof

Generalization

See also

References

Bibliography

External links

Navigation menu

Page actions

Page actions

Personal tools

Navigation

Search

Tools

In other projects

In other languages