Элементы комбинаторного анализа

Основные задачи комбинаторного анализа – размещение объектов в соответствии со специальными правилами и нахождение числа способов, которыми это можно сделать.

Если правила просты, то основным является подсчет числа возможностей для осуществления искомого размещения. Если правила тонкие или запутанные, то главной проблемой становится вопрос существования таких размещений и нахождения методов их построения.

Пусть дано множество S произвольной природы.

Определение 1. Размещением объема k элементов множества S называется упорядоченная выборка k элементов из множества S.

Определение 2. Сочетанием объема k называется неупорядоченная выборка k элементов множества S.

Определение 3. Размещение (сочетание) называется размещением (сочетанием) с повторением или с возвращением, если элементы в нем могут повторяться.

Пример. S={a, b, c}; n=3, k=2.

aa, ab, ac, ba, bb, bc, ca, cb, cc – размещения с повторением - 9 шт.;

ab, ac, ba, bc, ca, cb – размещения без повторения - 6 шт.;

aa, ab, ac, bb, bc, cc – сочетания с повторением - 6 шт.;

ab, ac, bc – сочетания без повторения - 3 шт.

Определение 4. Произведение первых n натуральных чисел называется n-факториалом и обозначается n!.

.

Например, . По определению полагают 0!=1.

Размещения без повторения. Число размещений без повторений из n элементов по r (объема r) обозначается .

.

Если , то .

.

Сочетания без повторения. Число сочетаний без повторений из n элементов по r (объема r) обозначается .

.

,

Размещения с повторением. Количество размещений с повторением из n элементов по r (объема r) равно n^r.

Сочетания с повторением. Число сочетаний с повторениями из n элементов по r (объема r) равно

.

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

Биномом Ньютона называют выражение вида

.

, или

.

Пример 1..

Пример 2.

.