A. Комбинаторика

Содержание

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

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

A.3. Примеры задач

решаемых при помощи комбинаторики.

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

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

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

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

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

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

Примечание(A001)

или

Замечание(A002)

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

Важно! (A003)

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

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

(A004)

(A005)

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

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

П Л А Н

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

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

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

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

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

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

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

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

(A006)

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

(A007)

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

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

(A008)

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

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

(A009)

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

A.1.1.1. (A010)

Z.1.1.1.13. (A011)

(A012)

(A013)

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

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

Xnm = n^m (A014)

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

A.3. Примеры задач

решаемых при помощи комбинаторики.

Содержание:

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

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

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

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

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

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

1. Для ввода пароля необходимо ввести m = 4 определенных чисел вне зависимости от порядка. Число таких вариантов – Cnm;

2. Для ввода пароля необходимо ввести m = 4 уникальных чисел в определенном порядке. Число таких вариантов – Anm;

3. Для ввода пароля необходимо ввести любое m = 4 (четырехзначное) число. Число таких вариантов – nm.

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

1. C104 = 210 (по формуле A.009);

2. A104 = 5040 (по формуле A.008);

3. 104 = 10 000 (по формуле A.014).

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

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

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

Дополнительные соображения.

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

1. Количество парт в классе – n;

2. Количество мест за партами – 2;

3. Сажать за парту мы будем только девочку и мальчика (ситуация «две девочки» и «два мальчика» не рассматривается);

4. Порядок, в котором девочка и мальчик садятся за парту (мальчик слева, справа), несущественен.

Решение.

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

1. В качестве «учетной единицы» выбираем одного мальчика;

2. Количество мальчиков, как следует из условия задачи, равно n;

3. Таким образом, n мальчиков по n партам можно посадить n! раз;

4. Число «посадочных мест», за которые можно посадить мальчика и девочку, равно n («одна парта – два школьника»), а число «перестановок» парт равно n!;

5. Таким образом, если «правильно» разбить первоклассников по парам (по условию задачи), то количество таких пар будет равно n!;

6. Количество способов, с помощью которых можно рассадить всех детей по партам, будет равно: n!xn!, или (n!)^2.

Ответ: (n!)^2.

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

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

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

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

2. Сколькими способами можно «поженить» n юношей и n девушек?

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

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

Л И Т Е Р А Т У Р А

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

Глоссарий

[[files/Math_Glossary.xls] файл Excel]

[[files/Math_Glossary.ods] файл Calc]

* просто

- просто

1. просто

2) просто