Сочетания

k-подмножество данного n-множества называется k-сочетанием.

Обозначим через число k-сочетаний из данных n элементов. Формулу для числа получим, рассуждая следующим образом. Если каждое сочетание упорядочить всеми возможными способами, то получим все k-последовательностей из n элементов, без повторений, то есть все k-размещения.

Иными словами,

Откуда:        (1.3)

или

Предполагая, что n и k - целые положительные числа и 0!=1, сформулируем основные свойства сочетаний.

Основные свойства сочетаний.

Условились, что

Сочетания и размещения широко используются при вычислении классической вероятности случайных событий.

Пример. В корзине находятся 20 орехов, из которых 7 грецких. Наудачу выбирают 5 орехов. Найти вероятность того, что среди выбранных орехов содержатся 2 грецких.

Решение. Число исходов опыта . Случайное событие A - среди пяти выбранных орехов содержатся 2 грецких ореха. Число исходов, благоприятствующих событию A, равно: . Искомая вероятность .

В современной литературе наиболее употребителен для обозначения числа k-сочетаний из n элементов символ , n называют верхним индексом, k - нижним индексом. Используя свойства сочетаний 1, 2, 4, составим таблицу1.

Заметим, что Блез Паскаль называл числовой треугольник, начало которого содержится в таблице1, арифметическим. Паскаль посвятил свойствам арифметического треугольника основополагающий "Трактат об арифметическом треугольнике" (1654). Справедливости ради, стоит упомянуть, что биномиальные коэффициенты были хорошо известны в Азии за много веков до рождения Паскаля. В Италии треугольник Паскаля называют треугольником Тартальи.

Сочетания имеют многочисленные интерпретации и приложения. Сочетания являются биномиальными коэффициентами в разложении бинома

     (1.4)

Таблица 1.Треугольник Паскаля

В этой интерпретации индексы могут принимать вещественные значения. Используя свойства биномиальных коэффициентов (при разных ограничениях на выбор верхних и нижних индексов), доказано громадное число комбинаторных тождеств, составивших самостоятельный раздел комбинаторной математики. В частности, из формулы 1.4 при x = 1, получим , при

x = -1, n > 0, получим , продифференцировав равенство 1.4, получим при x = 1, и т.д.

Существует тесная связь между подмножествами множества и разложениями целого (положительного) числа. Разложение n есть представление числа n в виде упорядоченной суммы положительных целых чисел. Например, существует восемь разложений числа 4, именно:

1+1+1+1   3+1

2+1+1      1+3

1+2+1       2+2

1+1+2         4

Если разложение содержит в точности k слагаемых, то говорят, что имеет k частей и называется k-разложением. Для k-разложения числа n: a₁ + a₂ + …+ a_n - определим (k - 1)-подмножество ( ), (n - 1)-множества {1, 2, …, n-1}, формулой.

( ) ={ a₁, a₁ + a₂,…, a₁ + a₂ +…+ a_k-1 }        (1.5)

Эта формула устанавливает биекцию между всеми k-разложениями числа n и (k - 1)-подмножествами (n - 1)-множества.

Следовательно, существует k-разложений числа n и 2^n-1 разложений числа n. Биекцию часто схематично изображают строкой, состоящей из n точек и k - 1 разделяющей вертикальной черты. Точки разделились по k линейно упорядоченным "купе"; числа точек в "купе" соответствуют слагаемым в k-разложении числа n. Например, строка | | | | | соответствует разложению 1+2+1+1+3+2. Другая проблема, тесно связанная с разложениями, есть задача подсчёта числа N(n,k) решений уравнения

x₁ + x₂ + …+ x_k = n                (1.6)

Неотрицательные целые решения уравнения 1.6 называются слабыми k-разложениями числа n. Число неотрицательных целых решений уравнения 1.6 равно числу положительных решений уравнения

y₁ + y₂ + … + y_k = n + k,

то есть числу k-разложений числа n + k. Таким образом, N(n,k) = .

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

       (1.7)

Сочетание можно интерпретировать, как распределение элементов n-множества S между двумя категориями, первая из которых содержит k элементов, вторая содержит n - k элементов. Обобщим это представление. Пусть (a₁, a₂, …, a_m)- последовательность неотрицательных целых чисел, сумма которых равна n. Рассмотрим m категорий C₁, C₂, … C_m.

Обозначим символом        (1.8)

число способов распределения n элементов среди категорий C₁, C₂, … C_m так, чтобы категории C_i принадлежало точно a_i элементов.

Тогда        (1.9)