Бином Ньютона

Бином Ньютона

Бином Ньютона. Свойства биномиальных коэффициентов. Производящие функции и применение при решении задач комбинаторики

Выполнил: Студентка ТУИТ
компьютерный инжиниринг
группы №717-20
Садикова З.М. 

План:

• Бином Ньютона
• Свойства биномиальных коэффициентов
• Производящие функции и применение при решении задач комбинаторики

Исаак Ньютон

Бином Ньютона

Бином Ньютона — это формула для разложения на отдельные слагаемые целой неотрицательной степени суммы двух переменных, имеющая вид




— биномиальные коэффициенты,
— неотрицательное целое число.
n
Где

Степени бинома

В таком виде эта формула была известна ещё индийским и персидским математикам; Ньютон вывел формулу бинома Ньютона для более общего случая, когда показатель степени — произвольное действительное (или даже комплексное) число.

Блез Паскаля

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

*Треугольник Паскаля — это бесконечная таблица биномиальных коэффициентов, имеющая треугольную форму. В этом треугольнике на вершине и по бокам стоят единицы. Каждое число равно сумме двух расположенных над ним чисел. Строки треугольника симметричны относительно вертикальной оси.
* Назван он в честь Блеза Паскаля. Числа, составляющие треугольник Паскаля, возникают естественным образом в алгебре, комбинаторике, теории вероятностей, математическом анализе, теории чисел

Свойства биномиальных коэффициентов.

Биномиальными коэффициентами являются величины
,
которые выражают число сочетаний из n элементов по k. Эти величины обладают следующими свойствами.

Свойство симметрии.

В формуле бинома это означает, что коэффициенты, стоящие на одинаковых местах от левого и правого концов формулы, равны, например:
Действительно,
это количество подмножеств, содержащих k элементов, множества, содержащего n элементов.
количество дополнительных к ним подмножеств. Сколько подмножеств, столько и дополнений.

Свойство Паскаля.

Пусть
Число
это количество подмножеств из k элементов
множества X. Разделим все подмножества на два класса:
1) подмножества, не содержащие элемент 
их будет
2) подмножества, содержащие элемент 
их будет
Т.к. эти классы не пересекаются, то по правилу суммы количество всех k-элементных подмножеств множества X будет равно
На этом свойстве основано построение треугольника Паскаля , в n-ой строке которого стоят коэффициенты разложения бинома

Свойство суммы.

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

Производящие функции.

Одним из методов получения значения комбинаторных сумм и тождеств является метод производящих функций.
Для последовательности чисел {an} (конечной или бесконечной) рассмотрим формальную сумму (конечную или бесконечную)
Если последовательность {an} конечна, то эта сумма всегда определяет функцию
которая называется производящей функцией для последовательности {an}.

Применение при решении задач комбинаторики.