Комбинаторика. Бином Ньютона
Перестановки. Факториал. Размещения. Сочетания.
Бином Ньютона. Биномиальные коэффициенты.
Треугольник Паскаля. Свойства биномиальных коэффициентов.
Общим термином «соединения» мы будем называть три вида комбинаций, составляемых из некоторого числа различных элементов, принадлежащих одному и тому же множеству (например, буквы алфавита, книги в библиотеке, машины на стоянке и т.д.).
Перестановки. Возьмём
n различных элементов: a 1 , a 2 , a 3 , …, a n . Будем переставлять их всеми возможными способами, сохраняя их количество и меняя лишь порядок их расположения. Каждая из полученных таким образом комбинаций называется перестановкой. Общее количество перестановок из n элементов обозначается P n . Это число равно произведению всех целых чисел от 1 до n :
Символ n ! ( называется факториал ) - сокращённая запись произведения: 1 · 2 · 3 · … · ( n – 1 ) · n .
П р и м е р . Найти число перестановок из трёх элементов: a , b , c .
Р е ш
е н и е . В соответствии с приведенной формулой:
P
3
= 1 · 2 · 3 = 6.
Действительно,
Размещения. Будем составлять группы из
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 при положительном целом n в виде многочлена:
Заметим, что сумма показателей степеней для
a и b постоянна и равна n .
П р и м е р
1 .
( См. формулу куба суммы двух чисел ).
Числа
называются
биномиальными коэффициентами.
Их можно вычислить, применяя только сложение, если пользоваться следующей схемой. В верхней строке пишем две единицы. Все последующие строки начинаются и заканчиваются единицей. Промежуточные числа в этих строках получаются суммированием соседних чисел из предыдущей строки. Эта схема называется треугольником Паскаля:
Первая строка в этой таблице содержит биномиальные коэффициенты для n = 1; вторая - для n = 2; третья - для n = 3 и т.д. Поэтому, если необходимо, например, разложить выражение:
( a + b ) 7 ,
мы можем получить результат моментально, используя таблицу:
Свойства биномиальных коэффициентов.
Для доказательства достаточно положить a = b = 1. Тогда в правой части разложения бинома Ньютона мы будем иметь сумму биномиальных коэф фициентов, а слева:
2. Коэффициенты членов, равноудалённых от концов разложения, равны.
Это свойство следует из соотношения:
3. Сумма коэффициентов чётных членов разложения равна сумме коэффи циентов нечётных членов разложения; каждая из них равна
Для
доказательства воспользуемся биномом:
Здесь чётные члены имеют знак « + » ,
а нечётные - «
-
». Так как в результате разложения получается 0, то следовательно, суммы их
биномиальных коэффициентов
равны
между собой, поэтому каждая из них равна:
что и
требовалось доказать
.