Правило Паскаля - Pascal's rule

В математике , правило Паскаля (или формула Паскаля ) является комбинаторное тождество о биномиальных коэффициентов . В нем говорится, что для положительных натуральных чисел n и k ,

${\ Displaystyle {п-1 \ выбрать k} + {n-1 \ выбрать k-1} = {п \ выбрать k},}$

где - биномиальный коэффициент; одно толкование которого является коэффициент х ^K члена в разложении по (1 + х ) ^п . Нет ограничений на относительные размеры n и k , поскольку, если n < 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}$

над натуральными числами. Таким образом, правило Паскаля - это также утверждение о формуле для чисел, появляющихся в треугольнике Паскаля .

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

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

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

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

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

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

Каждое подмножество из k элементов либо содержит X, либо нет. Общее число подмножеств с K элементов в множестве п элементов является суммой числа подмножеств , содержащих 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 {align} {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 {выравнивается}}}$

Обобщение

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

где - коэффициент при разложении . ${\ displaystyle {n \ select k_ {1}, k_ {2}, k_ {3}, \ dots, k_ {p}}}$${\ displaystyle x_ {1} ^ {k_ {1}} x_ {2} ^ {k_ {2}} \ dots x_ {p} ^ {k_ {p}}}$${\ displaystyle (x_ {1} + x_ {2} + \ dots + x_ {p}) ^ {n}}$

Алгебраический вывод для этого общего случая следующий. Пусть 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 {align} & {} \ quad {n-1 \ select 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 \ выбрать k_ {1}, k_ {2}, k_ {3}, \ dots, k_ {p}}. \ end {align}}}$

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

• Треугольник Паскаля

Рекомендации

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

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

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

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

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

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