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

Комбинаторное тождество биномиальных коэффициентов

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

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

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

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

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

Правило Паскаля имеет интуитивное комбинаторное значение, которое ясно выражено в этом счетном доказательстве. ^{[2] : 44}

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

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

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

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

Это равно ; следовательно, . ${\displaystyle {\tbinom {n}{k}}}$ ${\displaystyle {\tbinom {n}{k}}={\tbinom {n-1}{k-1}}+{\tbinom {n-1}{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 такого, что , и , где — коэффициент при члене в разложении . ${\displaystyle p\geq 2}$ ${\displaystyle k_{1},k_{2},k_{3},\dots ,k_{p}\in \mathbb {N} ^{+}\!,}$ ${\displaystyle n=k_{1}+k_{2}+k_{3}+\cdots +k_{p}\geq 1}$ $${\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}}}$$ ${\displaystyle {n \choose k_{1},k_{2},k_{3},\dots ,k_{p}}}$ ${\displaystyle x_{1}^{k_{1}}x_{2}^{k_{2}}\cdots x_{p}^{k_{p}}}$ ${\displaystyle (x_{1}+x_{2}+\dots +x_{p})^{n}}$

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

Смотрите также

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

Ссылки

1. Мазур, Дэвид Р. (2010), Комбинаторика / Экскурсия , Математическая ассоциация Америки, стр. 60, ISBN 978-0-88385-762-5
2. Brualdi, Richard A. (2010), Введение в комбинаторику (5-е изд.), Prentice-Hall, ISBN 978-0-13-602040-0

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

• Меррис, Рассел. Комбинаторика. John Wiley & Sons. 2003 ISBN 978-0-471-26296-1 

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

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

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

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