правило Паскаля

Не путать с законом Паскаля .

В математике ( правило Паскаля или формула Паскаля ) представляет собой комбинаторное тождество о биномиальных коэффициентах . Он утверждает, что для положительных натуральных чисел n и k , $${n-1 \choose k}+{n-1 \choose k-1}={n \choose k},$$ где ${\tbinom {n}{k}}$ – биномиальный коэффициент; одна интерпретация коэффициента x ^к в разложении x (1 + ) член ^н . Нет ограничений на относительные размеры n и k , поскольку, если n < k, значение биномиального коэффициента равно нулю и тождество остается действительным.

Правило Паскаля также можно рассматривать как утверждение о том, что формула $${\frac {(x+y)!}{x!y!}}={x+y \choose x}={x+y \choose y}$$ решает линейное двумерное разностное уравнение $$N_{x,y}=N_{x-1,y}+N_{x,y-1},\quad N_{0,y}=N_{x,0}=1$$ над натуральными числами. Таким образом, правило Паскаля — это также утверждение о формуле чисел, входящих в треугольник Паскаля .

Правило Паскаля также можно обобщить и применить к полиномиальным коэффициентам .

Комбинаторное доказательство

Иллюстрирует комбинаторное доказательство: ${\binom {4}{1}}+{\binom {4}{2}}={\binom {5}{2}}.$

Правило Паскаля имеет интуитивный комбинаторный смысл, который ясно выражен в этом счетном доказательстве.

Доказательство . Напомним, что ${\tbinom {n}{k}}$ равно количеству подмножеств с k элементами из множества с n элементами. Предположим, что один конкретный элемент однозначно помечен X в наборе из n элементов.

Чтобы создать подмножество из k элементов, содержащее X , включите X и выберите k - 1 элемент из оставшихся n - 1 элементов в наборе. Есть ${\tbinom {n-1}{k-1}}$ такие подмножества.

Чтобы создать подмножество из k элементов, не содержащих X , выберите k элементов из оставшихся n - 1 элементов в наборе. Есть ${\tbinom {n-1}{k}}$ такие подмножества.

Каждое подмножество из k элементов либо содержит X , либо нет. Общее количество подмножеств с k элементами в наборе из n элементов представляет собой сумму количества подмножеств, содержащих X , и количества подмножеств, которые не содержат X , ${\tbinom {n-1}{k-1}}+{\tbinom {n-1}{k}}$.

Это равно ${\tbinom {n}{k}}$; поэтому, ${\tbinom {n}{k}}={\tbinom {n-1}{k-1}}+{\tbinom {n-1}{k}}$.

Алгебраическое доказательство

В качестве альтернативы следует алгебраический вывод биномиального случая. $${\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}}$$

Обобщение

Правило Паскаля можно обобщить на полиномиальные коэффициенты. Для любого целого числа p такого, что $p\geq 2$, $k_{1},k_{2},k_{3},\dots ,k_{p}\in \mathbb {N} ^{+}\!,$ и $n=k_{1}+k_{2}+k_{3}+\cdots +k_{p}\geq 1$, $${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 \choose k_{1},k_{2},k_{3},\dots ,k_{p}}$ коэффициент $x_{1}^{k_{1}}x_{2}^{k_{2}}\cdots x_{p}^{k_{p}}$ срок в расширении $(x_{1}+x_{2}+\dots +x_{p})^{n}$.

Алгебраический вывод для этого общего случая следующий. Пусть p — целое число такое, что $p\geq 2$, $k_{1},k_{2},k_{3},\dots ,k_{p}\in \mathbb {N} ^{+}\!,$ и $n=k_{1}+k_{2}+k_{3}+\cdots +k_{p}\geq 1$. Затем $${\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}}$$

См. также

• Треугольник Паскаля
• Идентичность хоккейной клюшки

Библиография

• Меррис, Рассел. Комбинаторика . Джон Уайли и сыновья. 2003 г. ISBN   978-0-471-26296-1

Внешние ссылки

• «Центральный биномиальный коэффициент» . ПланетаМатематика .
• «Биномиальный коэффициент» . ПланетаМатематика .

Эта статья включает в себя материал из треугольника Паскаля на PlanetMath , который доступен под лицензией Creative Commons Attribution/Share-Alike License .

Эта статья включает в себя материал из доказательства правил Паскаля на PlanetMath , который распространяется по лицензии Creative Commons Attribution/Share-Alike License .