Combinatorial identity about binomial coefficients
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 ,
(
n
−
1
k
)
+
(
n
−
1
k
−
1
)
=
(
n
k
)
,
{\displaystyle {n-1 \choose k}+{n-1 \choose k-1}={n \choose k},}
where
(
n
k
)
{\displaystyle {\tbinom {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
(
x
+
y
)
!
x
!
y
!
=
(
x
+
y
x
)
=
(
x
+
y
y
)
{\displaystyle {\frac {(x+y)!}{x!y!}}={x+y \choose x}={x+y \choose 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
{\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 [ edit ]
Illustrates combinatorial proof:
(
4
1
)
+
(
4
2
)
=
(
5
2
)
.
{\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
(
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
(
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
(
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 ,
(
n
−
1
k
−
1
)
+
(
n
−
1
k
)
{\displaystyle {\tbinom {n-1}{k-1}}+{\tbinom {n-1}{k}}}
.
This equals
(
n
k
)
{\displaystyle {\tbinom {n}{k}}}
; therefore,
(
n
k
)
=
(
n
−
1
k
−
1
)
+
(
n
−
1
k
)
{\displaystyle {\tbinom {n}{k}}={\tbinom {n-1}{k-1}}+{\tbinom {n-1}{k}}}
.
Algebraic proof [ edit ]
Alternatively, the algebraic derivation of the binomial case follows.
(
n
−
1
k
)
+
(
n
−
1
k
−
1
)
=
(
n
−
1
)
!
k
!
(
n
−
1
−
k
)
!
+
(
n
−
1
)
!
(
k
−
1
)
!
(
n
−
k
)
!
=
(
n
−
1
)
!
[
n
−
k
k
!
(
n
−
k
)
!
+
k
k
!
(
n
−
k
)
!
]
=
(
n
−
1
)
!
n
k
!
(
n
−
k
)
!
=
n
!
k
!
(
n
−
k
)
!
=
(
n
k
)
.
{\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 [ edit ]
Pascal's rule can be generalized to multinomial coefficients.[2] : 144 For any integer p such that
p
≥
2
{\displaystyle p\geq 2}
,
k
1
,
k
2
,
k
3
,
…
,
k
p
∈
N
+
,
{\displaystyle k_{1},k_{2},k_{3},\dots ,k_{p}\in \mathbb {N} ^{+}\!,}
and
n
=
k
1
+
k
2
+
k
3
+
⋯
+
k
p
≥
1
{\displaystyle n=k_{1}+k_{2}+k_{3}+\cdots +k_{p}\geq 1}
,
(
n
−
1
k
1
−
1
,
k
2
,
k
3
,
…
,
k
p
)
+
(
n
−
1
k
1
,
k
2
−
1
,
k
3
,
…
,
k
p
)
+
⋯
+
(
n
−
1
k
1
,
k
2
,
k
3
,
…
,
k
p
−
1
)
=
(
n
k
1
,
k
2
,
k
3
,
…
,
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
(
n
k
1
,
k
2
,
k
3
,
…
,
k
p
)
{\displaystyle {n \choose k_{1},k_{2},k_{3},\dots ,k_{p}}}
is the coefficient of the
x
1
k
1
x
2
k
2
⋯
x
p
k
p
{\displaystyle x_{1}^{k_{1}}x_{2}^{k_{2}}\cdots x_{p}^{k_{p}}}
term in the expansion of
(
x
1
+
x
2
+
⋯
+
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
p
≥
2
{\displaystyle p\geq 2}
,
k
1
,
k
2
,
k
3
,
…
,
k
p
∈
N
+
,
{\displaystyle k_{1},k_{2},k_{3},\dots ,k_{p}\in \mathbb {N} ^{+}\!,}
and
n
=
k
1
+
k
2
+
k
3
+
⋯
+
k
p
≥
1
{\displaystyle n=k_{1}+k_{2}+k_{3}+\cdots +k_{p}\geq 1}
. Then
(
n
−
1
k
1
−
1
,
k
2
,
k
3
,
…
,
k
p
)
+
(
n
−
1
k
1
,
k
2
−
1
,
k
3
,
…
,
k
p
)
+
⋯
+
(
n
−
1
k
1
,
k
2
,
k
3
,
…
,
k
p
−
1
)
=
(
n
−
1
)
!
(
k
1
−
1
)
!
k
2
!
k
3
!
⋯
k
p
!
+
(
n
−
1
)
!
k
1
!
(
k
2
−
1
)
!
k
3
!
⋯
k
p
!
+
⋯
+
(
n
−
1
)
!
k
1
!
k
2
!
k
3
!
⋯
(
k
p
−
1
)
!
=
k
1
(
n
−
1
)
!
k
1
!
k
2
!
k
3
!
⋯
k
p
!
+
k
2
(
n
−
1
)
!
k
1
!
k
2
!
k
3
!
⋯
k
p
!
+
⋯
+
k
p
(
n
−
1
)
!
k
1
!
k
2
!
k
3
!
⋯
k
p
!
=
(
k
1
+
k
2
+
⋯
+
k
p
)
(
n
−
1
)
!
k
1
!
k
2
!
k
3
!
⋯
k
p
!
=
n
(
n
−
1
)
!
k
1
!
k
2
!
k
3
!
⋯
k
p
!
=
n
!
k
1
!
k
2
!
k
3
!
⋯
k
p
!
=
(
n
k
1
,
k
2
,
k
3
,
…
,
k
p
)
.
{\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 [ edit ]
References [ edit ]
^ Mazur, David R. (2010), Combinatorics / A Guided Tour , Mathematical Association of America, p. 60, ISBN 978-0-88385-762-5
^ a b c Brualdi, Richard A. (2010), Introductory Combinatorics (5th ed.), Prentice-Hall, ISBN 978-0-13-602040-0
Bibliography [ edit ]
External links [ edit ]
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 .