Правило Паскаля - Википедия - Pascals rule

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

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

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

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

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

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

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

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

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

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

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

Обобщение

Правило Паскаля можно обобщить на полиномиальные коэффициенты.^[3] Для любого целое число п такой, что ${ 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} + точки + x_ {p}) ^ {n}}$.

Алгебраический вывод для этого общего случая следующий.^[3] Позволять п быть таким целым числом, что ${ 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.

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