A.1. Факториал и его приближения

A.2. Соединения

A.3. Примеры задач
решаемых при помощи комбинаторики.

A.4. Задачи и упражнения

A.5. Приложение

Материал рассчитан на студентов ВУЗов, техникумов и учащихся старших классов средних школ.

В комбинаторике, теории вероятностей, математической статистике и др., основанных на них областях широко используется функция «факториал». В [1] дается следующее определение факториала:

Факториалом целого положительного числа n (обозначается n!) называется произведение:

(A001)

или

(A002)

Основное свойство факториала:

(A003)

Из определения факториала видно, что данная функция растет очень быстро, примерно как функция ~ nⁿ.

По [1], факториалы больших чисел могут быть выражены приближенно формулой Стирлинга:

(A004)

(A005)

Эти формулы имеют место и не при целых n.

A.2.1. Перестановки

A.2.2. Размещения

A.2.3. Сочетания

A.2.4. Повторения

=== *** === *** ===

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

Перестановками из n элементов называются соединения, отличающиеся друг от друга порядком входящих в них элементов. Например, перестановки из трех элементов a, b и c: abc, bca, cab, cba, bac, acb. Число всех перестановок из n различных элементов обозначается P_n:

(A006)

Если среди n элементов a, b и c есть одинаковые элементы (a повторяется α раз, b – β раз, с – γ раз и т.д.), то формула для перестановок будет следующей:

(A007)

Размещениями из n элементов по m называются такие соединения, которые различаются друг от друга самими элементами или их порядком. Например, размещения из 3-х элементов a, b и c по два будут: ab, ac, cb, ca, bc, ba. Размещение обозначается как A_n^m:

(A008)

Сочетанием n элементов по m называется соединения, различающиеся друг от друга только самими элементами. Сочетания обозначаются как C_n^m. Например, сочетаниями из 3 различных элементов a, b и c по 2: ab, ac и bc.

(A009)

Свойства сочетаний:

(A010)

(A011)

(A012)

(A013)

Повторением n элементов в m ячейках называется общее количество повторений любого числа n различных элементов в любой последовательности m раз. Повторения одного элемента допускаются произвольное число раз. Для повторений нет определенного устоявшегося обозначения, и автор обозначает его как X_n^m. При n=2 и m=2 повторения символов a и b будут следующими: aaa, aab, aba, abb, baa, bab, bba, bbb.

(A014)

Повторения часто используются в теории кодирования информации.

A.3.1. Подбор кода к замку

A.3.2. «Первый раз в первый класс»

=== *** === *** ===

Приведенные в примерах задачи являются задачами повышенной сложности. Ниже рассматривается их решение. Особо следует обратить внимание на аргументацию при выборе нужного соединения.

Пусть нам необходимо подобрать кодовое сочетание цифр для кодового замка. Обычно для кодирования используются числа от 0 до 9 (всего 10 цифр) . Предположим, нам известна длина ключа – 4 цифры. В таком случае n = 10 (число элементов), а m = 4 (количество «посадочных мест» в замке). Далее нам необходимо разобраться с «конструкцией» замка:

1. Для ввода пароля необходимо ввести m = 4 определенных чисел вне зависимости от порядка. Число таких вариантов – C_n^m;
2. Для ввода пароля необходимо ввести m = 4 уникальных чисел в определенном порядке. Число таких вариантов – A_n^m;
3. Для ввода пароля необходимо ввести любое m = 4 (четырехзначное) число. Число таких вариантов – n^m.

Подставив числа n и m в формулы соединений, получим:

1. C₁₀⁴ = 210 (по формуле A.009);
2. A₁₀⁴ = 5040 (по формуле A.008);
3. 10⁴ = 10 000 (по формуле A.014).

Как следует из этих расчетов, наихудшим положение дел с безопасностью от «взлома» паролей – у первого варианта конструкции замка: даже неопытный взломщик подберет код за два часа. Второй вариант превосходит по безопасности первый в 24 раза, а третий превосходит второй ~ в два раза. Но все равно эти пароли не надежны: перебором вариантов их «угадает» любая программ для «взлома» паролей. Именно поэтому для дополнительной защиты таких паролей применяют метод «блокировки» записей, который при превышении лимита ввода неправильной комбинации цифр блокирует доступ к содержимому: (SIM-карте сотового телефона, банковской карте и т.п.)

Пусть в одну из школ в один из его первых классов поступило n мальчиков и n девочек. Скольким способами их можно посадить «попарно» за парты?

В начале определим условия этого разделения:

1. Количество парт в классе – n;
2. Количество мест за партами – 2;
3. Сажать за парту мы будем только девочку и мальчика (ситуация «две девочки» и «два мальчика» не рассматривается);
4. Порядок, в котором девочка и мальчик садятся за парту (мальчик слева, справа), несущественен.

Продолжим рассуждения.

1. В качестве «учетной единицы» выбираем одного мальчика;
2. Количество мальчиков, как следует из условия задачи, равно n;
3. Таким образом, n мальчиков по n партам можно посадить n! раз;
4. Число «посадочных мест», за которые можно посадить мальчика и девочку, равно n («одна парта – два школьника»), а число «перестановок» парт равно n!;
5. Таким образом, если «правильно» разбить первоклассников по парам (по условию задачи), то количество таких пар будет равно n!;
6. Количество способов, с помощью которых можно рассадить всех детей по партам, будет равно: n!×n!, или (n!)².

Ответ: (n!)².

1. Напишите программу для подсчета факториала:

a) с помощью цикла;

b) с помощью рекурсии.

2. Сколькими способами можно «поженить» n юношей и n девушек?
3. Чья «мощность» множества больше: у перестановок, размещений, сочетаний или повторений?

1. Бронштейн И.Н., Семендяев К.А. Справочник по математике (для инженеров и учащихся ВТУЗОВ) Издание седьмое, стереотипное. //М.: Государственное издательство Технико-Теоретической литературы, 1957. – 608 с., ил.

Версия 1.00.00 release candidat

05.04.2008