Комбинаторика. Бином Ньютона

Перестановки. Факториал. Размещения. Сочетания.

Бином Ньютона. Биномиальные коэффициенты.

Треугольник Паскаля. Свойства биномиальных коэффициентов.

Общим термином «соединения» мы будем называть три вида комбинаций, составляемых из некоторого числа различных элементов, принадлежащих одному и тому же множеству (например, буквы алфавита, книги в библиотеке, машины на стоянке и т.д.).

Перестановки. Возьмём  n различных элементов:  a₁ , a₂ , a₃ , …, a_n . Будем переставлять их всеми возможными способами, сохраняя их количество и меняя лишь порядок их расположения. Каждая из полученных таким образом комбинаций называется перестановкой. Общее количество перестановок из n элементов обозначается P_n . Это число равно произведению всех целых чисел от 1 до n :

Символ  n!  ( называется факториал ) - сокращённая запись произведения:  1 · 2 · 3 ·  … · ( n – 1 ) · n .

П р и м е р .  Найти число перестановок из трёх элементов:  a, b, c.

Р е ш е н и е .  В соответствии с приведенной формулой:  P₃ = 1 · 2 · 3 = 6.
                         Действительно, мы имеем 6 перестановок: abc, acb, bac, bca, cab, cba.

Размещения.  Будем составлять группы из  m различных элементов, взятых из множества, состоящего из  n элементов, располагая эти  m взятых элементов в различном порядке. Полученные комбинации называются  размещениями из  n элементов по m .

Их общее количество обозначается:   и равно произведению:

П р и м е р .  Найти число размещений из четырёх элементов  a, b, c, d по два.

Р е ш е н и е .  В соответствии с формулой получим:

                         Вот эти размещения: ab, ba, ac, ca, ad, da, bc, cb, bd, db, cd, dc.

Сочетания.  Будем составлять группы из  m различных элементов, взятых из множества, состоящего из  n элементов, не принимая во внимание порядок расположения этих m элементов. Тогда мы получим сочетания из  n элементов по  m .

Их общее количество обозначается    и может быть вычислено по формуле:

Из этой формулы ясно, что

Заметим, что можно составить только одно сочетание из n элементов по n , которое содержит все  n элементов. Формула числа сочетаний даёт это значение, если только принять, что  0! = 1,  что является определением  0! .

В соответствии с этим определением получим:

Общее число сочетаний можно вычислить, пользуясь и другим выражением:

П р и м е р . Найти число сочетаний из пяти элементов:  a, b, c, d, e  по три.

Р е ш е н и е :

                        Эти сочетания:  abc, abd, abe, acd, ace, ade, bcd, bce, bde, cde.