パスカルの法則 （パスカルのほうそく、英 : Pascal's rule ）は二項係数 に関する恒等式 の一つ。その名前は17世紀のフランスの学者パスカル に由来し、パスカルの式 （パスカルのしき、英 : Pascal's formula ）、パスカルの恒等式 （パスカルのこうとうしき、英 : Pascal's identity ）などとも呼ばれる。具体的には、自然数
k
,
n
{\displaystyle k,n}
(
4
1
)
+
(
4
2
)
=
(
5
2
)
{\displaystyle {\binom {4}{1}}+{\binom {4}{2}}={\binom {5}{2}}}
パスカルの法則は直感的な組合せ論 的意味を持ち、それは数え上げによる証明において明確に示される[ 2] (p44) 。
(証明)
二項係数
(
n
k
)
{\displaystyle {\tbinom {n}{k}}}
n
{\displaystyle n}
集合 から
k
{\displaystyle k}
部分集合 の個数に一致するのであった。今、集合からある要素を取り出し、それに
X
{\displaystyle X}
k
{\displaystyle k}
X
{\displaystyle X}
X
{\displaystyle X}
含む ような部分集合は、 要素
X
{\displaystyle X}
n
−
1
{\displaystyle n-1}
k
−
1
{\displaystyle k-1}
X
{\displaystyle X}
(
n
−
1
k
−
1
)
{\displaystyle {\tbinom {n-1}{k-1}}}
一方、
X
{\displaystyle X}
含まない ような部分集合は、
X
{\displaystyle X}
n
−
1
{\displaystyle n-1}
k
{\displaystyle k}
(
n
−
1
k
)
{\displaystyle {\tbinom {n-1}{k}}}
任意の部分集合は
X
{\displaystyle X}
n
{\displaystyle n}
k
{\displaystyle k}
k
{\displaystyle k}
X
{\displaystyle X}
以上より、示すべき式
(
n
k
)
=
(
n
−
1
k
−
1
)
+
(
n
−
1
k
)
{\displaystyle {\tbinom {n}{k}}={\tbinom {n-1}{k-1}}+{\tbinom {n-1}{k}}}
二項係数が階乗表示により定義される場合、パスカルの法則を以下のようにして証明できる:
(
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}}}
さらに、二項係数が
(
n
k
)
=
n
(
n
−
1
)
⋯
(
n
−
k
+
1
)
k
!
{\displaystyle {\tbinom {n}{k}}={\frac {n(n-1)\cdots (n-k+1)}{k!}}}
(
n
−
1
k
)
+
(
n
−
1
k
−
1
)
=
(
n
−
1
)
⋯
(
(
n
−
1
)
−
k
+
1
)
k
!
+
(
n
−
1
)
⋯
(
(
n
−
1
)
−
(
k
−
1
)
+
1
)
(
k
−
1
)
!
=
(
n
−
1
)
⋯
(
n
−
k
)
k
!
+
(
n
−
1
)
⋯
(
n
−
k
+
1
)
(
k
−
1
)
!
=
(
n
−
1
)
⋯
(
n
−
k
+
1
)
(
k
−
1
)
!
[
n
−
k
k
+
1
]
=
(
n
−
1
)
⋯
(
n
−
k
+
1
)
(
k
−
1
)
!
⋅
n
k
=
n
(
n
−
1
)
⋯
(
n
−
k
+
1
)
k
!
=
(
n
k
)
{\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}}}
(
z
k
)
=
z
(
z
−
1
)
⋯
(
z
−
k
+
1
)
k
!
{\displaystyle {\tbinom {z}{k}}={\frac {z(z-1)\cdots (z-k+1)}{k!}}}
z
{\displaystyle z}
n
{\displaystyle n}
パスカルの法則を、多項係数に対して拡張することができる[ 2] (p144) 。
p
≥
2
{\displaystyle p\geq 2}
p
{\displaystyle p}
k
1
,
k
2
,
k
3
,
…
,
k
p
∈
Z
+
,
n
=
k
1
+
⋯
+
k
p
≥
1
{\displaystyle k_{1},k_{2},k_{3},\dots ,k_{p}\in \mathbb {Z} ^{+}\!,n=k_{1}+\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}}}
が成立する。ただし、多項係数
(
n
k
1
,
k
2
,
k
3
,
…
,
k
p
)
{\displaystyle {n \choose k_{1},k_{2},k_{3},\dots ,k_{p}}}
(
x
1
+
x
2
+
⋯
+
x
p
)
n
{\displaystyle (x_{1}+x_{2}+\dots +x_{p})^{n}}
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}}}
この一般化されたパスカルの法則も、代数的に示すことができる[ 2] (p144) :
(
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}}}
^ 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
![{\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3b50810f60c681cd6ce5919ed1cb87e46fb14f23)
![{\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/da24365061ef9f28530c740c5583f7e5741dafb0)
