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

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

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

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

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

Перестановки. Возьмём 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.

Бином Ньютона. Это формула, представляющая выражение (a + b) ⁿ при положительном целом n в виде многочлена:

Заметим, что сумма показателей степеней для a и b постоянна и равнаn.

П р и м е р 1.

(См. формулу куба суммы двух чисел).

Числа называются биномиальными коэффициентами.

Их можно вычислить, применяя только сложение, если пользоваться следующей схемой. В верхней строке пишем две единицы. Все последующие строки начинаются и заканчиваются единицей. Промежуточные числа в этих строках получаются суммированием соседних чисел из предыдущейстроки. Эта схема называется треугольником Паскаля:

Первая строка в этой таблице содержит биномиальные коэффициенты для n = 1; вторая - для n = 2; третья - для n = 3 и т.д. Поэтому, если необходимо, например, разложить выражение:

(a + b)⁷,

мы можем получить результат моментально, используя таблицу:

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

1. Сумма коэффициентов разложения (a + b) ⁿ равна 2 ⁿ.

Для доказательства достаточно положить a = b = 1. Тогда в правой частиразложения бинома Ньютона мы будем иметь сумму биномиальных коэффициентов, а слева:

2. Коэффициенты членов, равноудалённых от концов разложения, равны.

Это свойство следует из соотношения:

3. Сумма коэффициентов чётных членов разложения равна сумме коэффициентов нечётных членов разложения; каждая из них равна

Для доказательства воспользуемся биномом: Здесь чётные члены имеют знак «+», а нечётные - «-». Так как в результате разложения получается 0, то следовательно, суммы их биномиальных коэффициентов равны между собой, поэтому каждая из них равна: что и требовалось доказать.