Pascal's rule

Not to be confused with Pascal's law.

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,

$${\displaystyle {n-1 \choose k}+{n-1 \choose k-1}={n \choose k},}$$

where ${\displaystyle {\tbinom {n}{k}}}$ is a binomial coefficient; one interpretation of the coefficient of the x^k term in the expansion of (1 + x)ⁿ. 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

$${\displaystyle {\frac {(x+y)!}{x!y!}}={x+y \choose x}={x+y \choose y}}$$

solves the linear two-dimensional difference equation

$${\displaystyle N_{x,y}=N_{x-1,y}+N_{x,y-1},\quad 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

Illustrates combinatorial proof: ${\displaystyle {\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 ${\displaystyle {\tbinom {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 ${\displaystyle {\tbinom {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 ${\displaystyle {\tbinom {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, ${\displaystyle {\tbinom {n-1}{k-1}}+{\tbinom {n-1}{k}}}$.

This equals ${\displaystyle {\tbinom {n}{k}}}$; therefore, ${\displaystyle {\tbinom {n}{k}}={\tbinom {n-1}{k-1}}+{\tbinom {n-1}{k}}}$.

Algebraic proof

Alternatively, the algebraic derivation of the binomial case follows.

$${\displaystyle {\begin{aligned}{n-1 \choose k}+{n-1 \choose k-1}&={\frac {(n-1)!}{k!(n-1-k)!}}+{\frac {(n-1)!}{(k-1)!(n-k)!}}\\&=(n-1)!\left[{\frac {n-k}{k!(n-k)!}}+{\frac {k}{k!(n-k)!}}\right]\\&=(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 ${\displaystyle p\geq 2}$, ${\displaystyle k_{1},k_{2},k_{3},\dots ,k_{p}\in \mathbb {N} ^{+}\!,}$ and ${\displaystyle n=k_{1}+k_{2}+k_{3}+\cdots +k_{p}\geq 1}$,

$${\displaystyle {n-1 \choose k_{1}-1,k_{2},k_{3},\dots ,k_{p}}+{n-1 \choose k_{1},k_{2}-1,k_{3},\dots ,k_{p}}+\cdots +{n-1 \choose k_{1},k_{2},k_{3},\dots ,k_{p}-1}={n \choose k_{1},k_{2},k_{3},\dots ,k_{p}}}$$

where ${\displaystyle {n \choose k_{1},k_{2},k_{3},\dots ,k_{p}}}$ is the coefficient of the ${\displaystyle x_{1}^{k_{1}}x_{2}^{k_{2}}\cdots x_{p}^{k_{p}}}$ term in the expansion of ${\displaystyle (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 ${\displaystyle p\geq 2}$, ${\displaystyle k_{1},k_{2},k_{3},\dots ,k_{p}\in \mathbb {N} ^{+}\!,}$ and ${\displaystyle n=k_{1}+k_{2}+k_{3}+\cdots +k_{p}\geq 1}$. Then

$${\displaystyle {\begin{aligned}&{}\quad {n-1 \choose k_{1}-1,k_{2},k_{3},\dots ,k_{p}}+{n-1 \choose k_{1},k_{2}-1,k_{3},\dots ,k_{p}}+\cdots +{n-1 \choose k_{1},k_{2},k_{3},\dots ,k_{p}-1}\\&={\frac {(n-1)!}{(k_{1}-1)!k_{2}!k_{3}!\cdots k_{p}!}}+{\frac {(n-1)!}{k_{1}!(k_{2}-1)!k_{3}!\cdots k_{p}!}}+\cdots +{\frac {(n-1)!}{k_{1}!k_{2}!k_{3}!\cdots (k_{p}-1)!}}\\&={\frac {k_{1}(n-1)!}{k_{1}!k_{2}!k_{3}!\cdots k_{p}!}}+{\frac {k_{2}(n-1)!}{k_{1}!k_{2}!k_{3}!\cdots k_{p}!}}+\cdots +{\frac {k_{p}(n-1)!}{k_{1}!k_{2}!k_{3}!\cdots k_{p}!}}={\frac {(k_{1}+k_{2}+\cdots +k_{p})(n-1)!}{k_{1}!k_{2}!k_{3}!\cdots k_{p}!}}\\&={\frac {n(n-1)!}{k_{1}!k_{2}!k_{3}!\cdots k_{p}!}}={\frac {n!}{k_{1}!k_{2}!k_{3}!\cdots k_{p}!}}={n \choose k_{1},k_{2},k_{3},\dots ,k_{p}}.\end{aligned}}}$$

See also

• Pascal's triangle
• Hockey-stick identity

References

1. Mazur, David R. (2010), Combinatorics / A Guided Tour, Mathematical Association of America, p. 60, ISBN   978-0-88385-762-5
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

• "Central binomial coefficient". PlanetMath .
• "Binomial coefficient". PlanetMath .

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.