Элементы комбинаторного анализа (стр. 3 из 4)
В сочетании, в отличие от размещения, порядок следования элементов не учитывается. Поэтому из одного сочетания из n элементов по k получается
размещений. Отсюда для числа 
сочетаний из n элементов по k получается формула 
, 
.Из последней формулы следует
и 
.При
полагают 
. При 
полагают 
, поскольку при не существует сочетаний из 
элементов по 
.Наряду с обозначением
часто используется обозначение 
.Числа
называются также биномиальными коэффициентами, посколькуони фигурируют в функциональном тождестве, называемом формулой бинома Ньютона: 
. (1)Формулу (1) несложно доказать, используя метод математической индукции. Советуем провести доказательства в качестве упражнения.
Полагая в (1)
, получим тождество 
; (2)При
получим 
. (3)При четном n из соотношений (2) и (3) следуют тождества
, 
.При нечетном n из соотношений (2) и (3) следуют тождества
, 
.Упражнение 2. Показать, что для чисел
выполняется тождество 
.Из последнего тождества вытекает эффективный способ рекуррентного вычисления биномиальных коэффициентов
, который можно представить в графической форме, известной как треугольник Паскаля. | 1 | |||||
| 1 | 1 | ||||
| 1 | 2 | 1 | |||
| 1 | 3 | 3 | 1 | ||
| 1 | 4 | 6 | 4 | 1 | |
| . | . | . | . | . | . |
В этом равнобедренном треугольнике каждое число (кроме единиц на боковых сторонах) является суммой двух чисел, стоящих над ним. Число
находится в ( 
) ряду на ( 
) месте.Упражнение 3. Показать, что последовательность
, где 
обладает свойством: 
, если n четнои
если nнечетно.4.Размещения с повторениями.Размещением с повторениями элементов из
по 
(или размещением с повторением из n элементов по k) упорядоченная 
-выборка с повторениями.Пример 4. Пусть
и 
. Выпишем все размещения с повторениями из этого множества по два: 
, 
, 
, 
, 
, 
, 
, 
, 
.Для подсчета числа размещений с повторениями из n элементов по k используем правило произведения. При построении конкретного размещения первым элементом в нем можно взять любой из
элементов множества , вторым элементом – также любой из элементов множества т.д. Таким образом, число размещений из n элементов по kравно 
.В частности, если в качестве множества
взято множество 
, то совокупность всех размещений с повторениями из по называется единичным -мерным кубом и обозначают 
. 
.Пример 5. 3-х мерный куб размера 2 состоит из следующих элементов: (0,0,0), (0,0,1), (0,1,0), (0,1,1), (1,0,0), (1,0,1), (1,1,0), (1,1,1).
5.Сочетания с повторениями.Сочетанием с повторениями элементов из
по (или сочетанием с повторением из n элементов по k) неупорядоченная -выборка с повторениями.Пример 5. Пусть
и . Выпишем все сочетания с повторениями из этого множества по два: , , , , , .Можно показать, что число сочетаний с повторениямииз n элементов по k равно
.6.Булеан множества . Множество всех подмножеств называется булеаноммножества и обозначается как
.Пример 6. Пусть
. Тогда множество 
есть булеан множества .