Главная
Новости
Строительство
Ремонт
Каркасный дом
Несущие конструкции
Металлические конструкции
Прочность дорог
Дорожные материалы
Стальные конструкции
Грунтовые основания
Опорные сооружения




26.06.2022


26.06.2022


26.06.2022


26.06.2022


26.06.2022


25.06.2022


24.06.2022





Яндекс.Метрика

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

28.05.2022

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

( n − 1 k ) + ( n − 1 k − 1 ) = ( n k ) {displaystyle {n-1 choose k}+{n-1 choose k-1}={n choose k}} для 1 ⩽ k ⩽ n {displaystyle 1leqslant kleqslant n} ,

где ( n k ) {displaystyle {n choose k}} является биномиальным коэффициентом. Оно также часто записывается в виде

( n k ) + ( n k − 1 ) = ( n + 1 k ) {displaystyle {n choose k}+{n choose k-1}={n+1 choose k}} для 1 ⩽ k ⩽ n + 1 {displaystyle 1leqslant kleqslant n+1}

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

Правило Паскаля имеет интуитивное комбинаторное значение. Напомним, что ( a b ) {displaystyle {a choose b}} подсчитывает, сколькими способами можно выбрать подмножество с b элементами из множества с a элементами. Таким образом, правая часть тождества ( n k ) {displaystyle {n choose k}} подсчитывает, сколькими способами можно получить k-подмножество из множества с n элементами.

Теперь представим, что вы выделяете определённый элемент X из множества с n элементами. Таким образом, каждый раз, когда вы выбираете k элементов из подмножества, имеется две возможности — X принадлежит выбранному подмножеству или нет.

Если X находится в подмножестве, нужно лишь выбрать ещё k − 1 объектов (поскольку известно, что X будет в подмножестве) из оставшихся n − 1 объектов. Это можно сделать ( n − 1 k − 1 ) {displaystyle n-1 choose k-1} способами.

Если X не принадлежит подмножеству, нужно выбрать все k элементов из подмножества, состоящего из n − 1 объектов, не равных X. Это можно сделать ( n − 1 k ) {displaystyle n-1 choose k} способами.

Мы получаем, что число способов получить k-подмножество из n-элементного множества, которое, как мы знаем, равно ( n k ) {displaystyle {n choose k}} , равно также числу ( n − 1 k − 1 ) + ( n − 1 k ) . {displaystyle {n-1 choose k-1}+{n-1 choose k}.}

См. также Биективное доказательство.

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

Нужно показать, что

( n k ) + ( n k − 1 ) = ( n + 1 k ) . {displaystyle {n choose k}+{n choose k-1}={n+1 choose k}.}


( n k ) + ( n k − 1 ) = n ! k ! ( n − k ) ! + n ! ( k − 1 ) ! ( n − k + 1 ) ! = n ! [ n − k + 1 k ! ( n − k + 1 ) ! + k k ! ( n − k + 1 ) ! ] = n ! ( n + 1 ) k ! ( n − k + 1 ) ! = ( n + 1 k ) {displaystyle {egin{aligned}{n choose k}+{n choose k-1}&={frac {n!}{k!(n-k)!}}+{frac {n!}{(k-1)!(n-k+1)!}}&=n!left[{frac {n-k+1}{k!(n-k+1)!}}+{frac {k}{k!(n-k+1)!}} ight]&={frac {n!(n+1)}{k!(n-k+1)!}}={inom {n+1}{k}}end{aligned}}}

Обобщение

Пусть n , k 1 , k 2 , k 3 , … , k p , p ∈ N ∗ {displaystyle n,k_{1},k_{2},k_{3},dots ,k_{p},pin mathbb {N} ^{*}} и n = k 1 + k 2 + k 3 + ⋯ + k p {displaystyle n=k_{1}+k_{2}+k_{3}+cdots +k_{p}} . Тогда

( 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 {egin{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}}}

Имя:*
E-Mail:
Комментарий: