Не плутати із законом Паскаля .
У математиці правило Паскаля (або формула Паскаля ) — це комбінаторна тотожність щодо біноміальних коефіцієнтів . Вона стверджує, що для натуральних чисел
n
{\displaystyle n}
k
{\displaystyle k}
(
n
−
1
k
)
+
(
n
−
1
k
−
1
)
=
(
n
k
)
,
{\displaystyle {n-1 \choose k}+{n-1 \choose k-1}={n \choose k},}
де
(
n
k
)
{\displaystyle {\tbinom {n}{k}}}
x
k
{\displaystyle x^{k}}
розкладі [en]
(
1
+
x
)
n
{\displaystyle (1+x)^{n}}
n
{\displaystyle n}
k
{\displaystyle k}
[ 1]
n
<
k
{\displaystyle n<k}
Правило Паскаля також можна узагальнити на випадок мультиноміальних коефіцієнтів .
Правило Паскаля допускає інтуїтивне комбінаторне розуміння, що чітко продемонстровано в цьому обчислювальному доведені.[ 2]
Доведення. Нагадаємо, що
(
n
k
)
{\displaystyle {n \choose k}}
підмножин з
k
{\displaystyle k}
множині з
n
{\displaystyle n}
X
{\displaystyle X}
n
{\displaystyle n}
Для побудови підмножини з
k
{\displaystyle k}
X
{\displaystyle X}
X
{\displaystyle X}
k
−
1
{\displaystyle k-1}
n
−
1
{\displaystyle n-1}
(
n
−
1
k
−
1
)
{\displaystyle {n-1 \choose k-1}}
Для побудови підмножини з
k
{\displaystyle k}
X
{\displaystyle X}
k
{\displaystyle k}
n
−
1
{\displaystyle n-1}
(
n
−
1
k
)
{\displaystyle {n-1 \choose k}}
Кожна підмножина з
k
{\displaystyle k}
X
{\displaystyle X}
k
{\displaystyle k}
n
{\displaystyle n}
X
{\displaystyle X}
X
{\displaystyle X}
(
n
−
1
k
−
1
)
+
(
n
−
1
k
)
{\displaystyle {n-1 \choose k-1}+{n-1 \choose k}}
(
n
k
)
{\displaystyle {n \choose k}}
(
n
k
)
=
(
n
−
1
k
−
1
)
+
(
n
−
1
k
)
.
{\displaystyle {n \choose k}={n-1 \choose k-1}+{n-1 \choose 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)!}}\\&={n \choose k}.\end{aligned}}}
Правило Паскаля можна узагальнити на випадок мультиноміальних коефіцієнтів.[ 3]
Для будь-якого натурального
p
{\displaystyle 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}+\dots +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}}
Алгебраїчне доведення для цього загального випадку полягає в наступному.
Нехай
p
{\displaystyle 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}}}
↑ Mazur, David R. (2010), Combinatorics / A Guided Tour , Mathematical Association of America, с. 60, ISBN 978-0-88385-762-5 ↑ Brualdi, Richard A. (2010), Introductory Combinatorics (вид. 5th), Prentice-Hall, с. 44, ISBN 978-0-13-602040-0 ↑ Brualdi, Richard A. (2010), Introductory Combinatorics (вид. 5th), Prentice-Hall, с. 144, 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)!}}\\&={n \choose k}.\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ba6d0898a68244920fddfb176a1070579023adc6)
