Pascal's rule

In mathematics, Pascal's rule (or Pascal's formula) is a combinatorial identity about binomial coefficients. The binomial coefficients are the numbers that appear in Pascal's triangle. Pascal's rule states that for positive integers n and k, $${\displaystyle {n-1 \choose k}+{n-1 \choose k-1}={n \choose k},}$${\displaystyle {n-1 \choose k}+{n-1 \choose k-1}={n \choose k},} where ${\displaystyle {\tbinom {n}{k}}}${\displaystyle {\tbinom {n}{k}}} is the binomial coefficient, namely 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] in particular, the above identity remains valid when n < k since ${\displaystyle {\tbinom {n}{k}}=0}${\displaystyle {\tbinom {n}{k}}=0} whenever n < k.

Together with the boundary conditions ${\displaystyle {\tbinom {n}{0}}={\tbinom {n}{n}}=1}${\displaystyle {\tbinom {n}{0}}={\tbinom {n}{n}}=1} for all nonnegative integers n, Pascal's rule determines that $${\displaystyle {\binom {n}{k}}={\frac {n!}{k!(n-k)!}},}$${\displaystyle {\binom {n}{k}}={\frac {n!}{k!(n-k)!}},} for all integers 0 ≤ k ≤ n. In this sense, Pascal's rule is the recurrence relation that defines the binomial coefficients.

Pascal's rule can also be generalized to apply to multinomial coefficients.

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}}}${\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}}}${\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}}}${\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}}}${\displaystyle {\tbinom {n-1}{k-1}}+{\tbinom {n-1}{k}}}.

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

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}}}$${\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}}}

An alternative algebraic proof using the alternative definition of binomial coefficients: ${\displaystyle {\tbinom {n}{k}}={\frac {n(n-1)\cdots (n-k+1)}{k!}}}${\displaystyle {\tbinom {n}{k}}={\frac {n(n-1)\cdots (n-k+1)}{k!}}}. Indeed

$${\displaystyle {\begin{aligned}{n-1 \choose k}+{n-1 \choose k-1}&={\frac {(n-1)\cdots ((n-1)-k+1)}{k!}}+{\frac {(n-1)\cdots ((n-1)-(k-1)+1)}{(k-1)!}}\\&={\frac {(n-1)\cdots (n-k)}{k!}}+{\frac {(n-1)\cdots (n-k+1)}{(k-1)!}}\\&={\frac {(n-1)\cdots (n-k+1)}{(k-1)!}}\left[{\frac {n-k}{k}}+1\right]\\&={\frac {(n-1)\cdots (n-k+1)}{(k-1)!}}\cdot {\frac {n}{k}}\\&={\frac {n(n-1)\cdots (n-k+1)}{k!}}\\&={\binom {n}{k}}.\end{aligned}}}$${\displaystyle {\begin{aligned}{n-1 \choose k}+{n-1 \choose k-1}&={\frac {(n-1)\cdots ((n-1)-k+1)}{k!}}+{\frac {(n-1)\cdots ((n-1)-(k-1)+1)}{(k-1)!}}\\&={\frac {(n-1)\cdots (n-k)}{k!}}+{\frac {(n-1)\cdots (n-k+1)}{(k-1)!}}\\&={\frac {(n-1)\cdots (n-k+1)}{(k-1)!}}\left[{\frac {n-k}{k}}+1\right]\\&={\frac {(n-1)\cdots (n-k+1)}{(k-1)!}}\cdot {\frac {n}{k}}\\&={\frac {n(n-1)\cdots (n-k+1)}{k!}}\\&={\binom {n}{k}}.\end{aligned}}}

Since ${\displaystyle {\tbinom {z}{k}}={\frac {z(z-1)\cdots (z-k+1)}{k!}}}${\displaystyle {\tbinom {z}{k}}={\frac {z(z-1)\cdots (z-k+1)}{k!}}} is used as the extended definition of the binomial coefficient when z is a complex number, thus the above alternative algebraic proof shows that Pascal's rule holds more generally when n is replaced by any complex number.

Pascal's rule can be generalized to multinomial coefficients.^{[2] : 144} For any integer p such that ${\displaystyle p\geq 2}${\displaystyle p\geq 2}, ${\displaystyle k_{1},k_{2},k_{3},\dots ,k_{p}\in \mathbb {Z} ^{+}\!,}${\displaystyle k_{1},k_{2},k_{3},\dots ,k_{p}\in \mathbb {Z} ^{+}\!,} and ${\displaystyle n=k_{1}+k_{2}+k_{3}+\cdots +k_{p}\geq 1}${\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}}}$${\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}}}${\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}}}${\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}}${\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 p\geq 2}, ${\displaystyle k_{1},k_{2},k_{3},\dots ,k_{p}\in \mathbb {N} ^{+}\!,}${\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=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}}}$${\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}}}

• Pascal's triangle
• Hockey-stick identity

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

• "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.

• Combinatorics
• Algebraic identities

• Articles with short description
• Short description matches Wikidata
• Wikipedia articles incorporating text from PlanetMath
• Articles containing proofs