二項係数に関する組み合わせ恒等式
数学 において 、 パスカルの法則 （パスカルのほうそく、または パスカルの公式 ）は、 二項係数 に関する 組合せ論的 恒等式 である。これは、正の自然数 n および k に対して、二項係数が (1 + x ) n の展開における x k 項の係数の1つの解釈であることを述べている
。n と k の 相対 的
な 大き さ に 制限 は ない [ 1 ] 。 なぜなら 、 n < k の場合 、 二 項 係数 の値は0であり、恒等式は有効なままであるからである。
（
ん − 1
け
）
+
（
ん − 1
け − 1
）
=
（
ん け
）
、
{\displaystyle {n-1 \choose k}+{n-1 \choose k-1}={n \choose k},}
（
ん け
）
{\displaystyle {\tbinom {n}{k}}}
パスカルの法則は、式が自然数上の2次元の線形差分方程式を解くという
ステートメントとして見ることもできます
。したがって、パスカルの法則は、 パスカルの三角形
に現れる数の式に関するステートメントでもあります 。
（ x + ええ ） ！
x ！ ええ ！
=
（
x + ええ
x
）
=
（
x + ええ
ええ
）
{\displaystyle {\frac {(x+y)!}{x!y!}}={x+y \choose x}={x+y \choose y}}
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}
パスカルの法則は一般化して多項式係数 にも適用できます 。
組み合わせ論的証明 組み合わせ証明を示します。
(
4
1
)
+
(
4
2
)
=
(
5
2
)
.
{\displaystyle {\binom {4}{1}}+{\binom {4}{2}}={\binom {5}{2}}.}
パスカルの 法則は直感的な組み合わせ論的意味を持ち、それはこの数え上げの証明で明確に表現されている。 [2] : 44
証明 。は、 n 個の要素を持つ 集合 から k 個の 要素を持つ サブセット の数に等しいことを思い出してください 。n 個の要素を持つ集合で、特定の 1 つの要素が一意に X というラベルが付けられているとします 。
(
n
k
)
{\displaystyle {\tbinom {n}{k}}}
X を含む k 個の要素 のサブセットを構築するには 、 X を含め、 セット内の残りの n − 1 個の要素から k − 1 個の要素を選択します。 このようなサブセットが存在します。
(
n
−
1
k
−
1
)
{\displaystyle {\tbinom {n-1}{k-1}}}
X を 含ま ない k 個の要素 のサブセットを構築するには 、 セット内の 残りの n − 1 個の要素から k 個の 要素を選択します。このようなサブセットが存在します。
(
n
−
1
k
)
{\displaystyle {\tbinom {n-1}{k}}}
k 個の要素を持つ すべてのサブセットには、 X が 含まれるか含まれないかのどちらかです。n 個の要素を持つセット内の k 個の要素を持つサブセットの総数 は 、 X を 含むサブセットの数 と
X を 含まないサブセットの数の合計です 。
(
n
−
1
k
−
1
)
+
(
n
−
1
k
)
{\displaystyle {\tbinom {n-1}{k-1}}+{\tbinom {n-1}{k}}}
これは に等しい ので、 です 。
(
n
k
)
{\displaystyle {\tbinom {n}{k}}}
(
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}}}
一般化 パスカルの法則は多項式係数に一般化できる。 [2] : 144 、およびと なる任意の 整数 p に対して 、 は
の展開における項 の係数
である 。
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} ^{+}\!,}
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}}}
(
n
k
1
,
k
2
,
k
3
,
…
,
k
p
)
{\displaystyle {n \choose k_{1},k_{2},k_{3},\dots ,k_{p}}}
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}}}
(
x
1
+
x
2
+
⋯
+
x
p
)
n
{\displaystyle (x_{1}+x_{2}+\dots +x_{p})^{n}}
この一般的な場合の代数的導出は次の通りである。 [2] : 144 pを 、、 および となる整数とする 。 すると、
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} ^{+}\!,}
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
−
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}}}
参照
参考文献
^ マズール、デビッド・R.（2010）、 組合せ論/ガイドツアー 、アメリカ数学協会、p. 60、 ISBN 978-0-88385-762-5 ^ abc Brualdi, Richard A. (2010)、 Introductory Combinatorics (第 5 版)、Prentice-Hall、 ISBN 978-0-13-602040-0
文献 メリス、ラッセル。組合せ論。ジョン・ワイリー・アンド・サンズ。2003年 ISBN 978-0-471-26296-1
外部リンク この記事には、Creative Commons Attribution-Share-Alike License に基づいてライセンスされている PlanetMath の Pascal's triangle の資料が組み込まれています 。
この記事には、 Creative Commons Attribution-Share-Alike License に基づいてライセンスされている PlanetMath のパスカルの規則の証明の資料が組み込まれています 。
![{\displaystyle {\begin{aligned}{n-1 \choose k}+{n-1 \choose k-1}&={\frac {(n-1)!}{k!(n-1-k )!}}+{\frac {(n-1)!}{(k-1)!(nk)!}}\\&=(n-1)!\left[{\frac {nk}{k !(nk)!}}+{\frac {k}{k!(nk)!}}\right]\\&=(n-1)!{\frac {n}{k!(nk)!}}\\&={\frac {n! }{k!(nk)!}}\\&={\binom {n}{k}}.\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8d348389186612f23ba1949234a48a43f0c311ef)
