Предварительные сведения

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

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

Решение многих комбинаторных задач основывается на двух фундаментальных правилах, называемых соответственно правилами суммы и произведения.

Правило суммы. Если X1 и X2 – непересекающиеся конечные множества, содержащие соответственно n 1 и n 2 элементов, то

объединение X 1∪ X 2 содержит n 1 + n 2 элементов.

Сформулированное правило можно распространить на случай произвольного числа слагаемых:

если множества X 1, X 2, …, Xk образуют разбиение множества X, то n = n 1 + n 2 +…+ nk, где n = | X | – число элементов множества X, а ni = | Xi | – число элементов множества Xi, i = 1, 2,…, k.

Правило суммы можно приспособить и для подсчета числа элементов объединения двух множеств с непустым

пересечением:

| X 1∪ X 2| = | X 1| + | X 2| – | X 1∩ X 2|. (1)

В самом деле, множества X 1\ X 2 и X 1∩ X 2 образуют разбиение множества X 1, поэтому

| X 1| = | X 1\ X 2| + | X 1∩ X 2|.

Аналогично

| X 2| = | X 2\ X 1| + | X 1∩ X 2|.

Кроме того, множества X 1\ X 2, X 2\ X 1 и X 1∩ X 2 образуют разбиение множества X 1∪ X 2, так что

| X 1∪ X 2| = | X 1\ X 2| + | X 2\ X 1| + | X 1∩ X 2|.

Соотношение (1) является следствием трех последних формул.

Формула (1) обобщается на произвольное число слагаемых с помощью так называемого принципа включения и исключения (см. п. 8.4).

Пример. Найдем число правильных несократимых дробей со знаменателем 100. Числителем правильной несократимой

дроби со знаменателем 100 должно быть целое число в промежутке от 1 до 100, не имеющее среди своих делителей чисел 2 и 5. Обозначим через X 2, X 5 и X 10 множества чисел из промежутка от 1 до 100, делящихся соответственно на 2, на 5 и на 10. Легко видеть, что | X 2| = 100/2 = 50 и | X 5| = 100/5 = 20 и

| X 10| = 100/10 = 10. Так как X 2 ∩ X 5 = X 10, то по формуле (1)

получаем | X 2 ∪ X 5| = 50 + 20 – 10 = 60. Таким образом, среди чисел от 1 до 100 имеется 60 чисел, делящихся на 2 или 5, и

100 – 60 = 40 чисел, взаимно простых с числом 100. Следовательно, среди правильных дробей со знаменателем 100 ровно 40 являются несократимыми.

Правило произведения. Будем рассматривать упорядоченные наборы (кортежи) вида (a 1, a 2,…, ak) заданной длины k. Предположим, что элемент a 1 может быть выбран n 1 способами; при фиксированном a 1 элемент a 2 может быть выбран n 2 способами; при фиксированных a 1 и a 2 элемент a 3 может быть выбран n 3 способами и т. д. (при фиксированных a 1, a 2,…, ak –1 элемент ak может быть выбран nk способами). Тогда число различных кортежей равно произведению n 1 n 2⋅…⋅ nk. В частности, по правилу произведения для конечных множеств X 1, X 2, …, Xk имеем:

| X 1 X 2… Xk | = | X 1|| X 2|…| Xk |.

Пример. Используя правило произведения и правило суммы, найдем число различных трехзначных чисел, не

содержащих одинаковых цифр, и число различных трехзначных чисел, содержащих хотя бы две одинаковые цифры.

Пусть a 1, a 2, a 3 – цифры трехзначного числа. Первую цифру a1 можно выбрать девятью способами (в качестве нее можно взять любую цифру, кроме нуля); при фиксированной первой цифре вторую цифру a 2 можно выбрать также девятью способами (в качестве нее можно взять любую цифру, кроме a 1); наконец, при фиксированных первой и второй цифрах третью цифру можно выбрать восемью способами. По правилу произведения число трехзначных чисел, не содержащих одинаковых цифр, равно 9⋅9⋅8 = 648. Всего имеется 900 различных трехзначных чисел. Каждое из них либо содержит две одинаковых цифры, либо нет. Следовательно, имеется 900 –

648 = 252 различных трехзначных числа, содержащих хотя бы две одинаковые цифры.

Факториалы. Напомним, что факториалом целого положительного числа n (обозначение n!) называется произведение 1⋅⋅⋅ n. По определению считается, что 0! = 1. Факториал как функция натурального аргумента может быть однозначно определен рекурсивно:

0! = 1; (n + 1)! = n!⋅(n + 1).

Приближенное значение n! при больших n дает следующая

формула Стирлинга:

  n  n

n! ∼

2р n 

. (2)

 e 

Символ ∼ означает здесь, что отношение

  n  n

2р n 

 / n!

 e 

стремится к единице при n, стремящемся к бесконечности. Хотя разность правой и левой частей в формуле Стирлинга неограниченно возрастает, относительная ошибка быстро убывает. Например, уже при n = 10 относительная ошибка составляет менее одного процента:

10! = 3628800;

2р ⋅10 ⋅ 

 e 

≈ 3598696.

Не нашли, что искали? Воспользуйтесь поиском: