A. КомбинаторикаСодержаниеA.1. Факториал и его приближения A.3. Примеры задач Материал рассчитан на студентов ВУЗов, техникумов и учащихся старших классов средних школ. A.1. Факториал и его приближения.В комбинаторике, теории вероятностей, математической статистике и др., основанных на них областях широко используется функция «факториал». В [1] дается следующее определение факториала: Факториалом целого положительного числа n (обозначается n!) называется произведение: (A001) или (A002) Основное свойство факториала: (A003) Из определения факториала видно, что данная функция растет очень быстро, примерно как функция ~ nn. По [1], факториалы больших чисел могут быть выражены приближенно формулой Стирлинга: (A004) (A005) Эти формулы имеют место и не при целых n. A.2. СоединенияСодержание:=== *** === *** === В разделе дается описание наиболее используемых основного понятия комбинаторики – соединений, показывающих, сколькими способами можно организовывать множества элементов между собой. Этот раздел важен для изучения связанных с комбинаторикой дисциплин: теории множеств, теории вероятностей, математической статистики, статистической физике и т.п. A.2.1. ПерестановкиПерестановками из n элементов называются соединения, отличающиеся друг от друга порядком входящих в них элементов. Например, перестановки из трех элементов a, b и c: abc, bca, cab, cba, bac, acb. Число всех перестановок из n различных элементов обозначается Pn: (A006) Если среди n элементов a, b и c есть одинаковые элементы (a повторяется α раз, b – β раз, с – γ раз и т.д.), то формула для перестановок будет следующей: (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) Свойства сочетаний: (A010) (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. (A014) Повторения часто используются в теории кодирования информации. A.3. Примеры задачрешаемых при помощи комбинаторикиСодержание:=== *** === *** === Приведенные в примерах задачи являются задачами повышенной сложности. Ниже рассматривается их решение. Особо следует обратить внимание на аргументацию при выборе нужного соединения. A.3.1. Подбор кода к замкуПусть нам необходимо подобрать кодовое сочетание цифр для кодового замка. Обычно для кодирования используются числа от 0 до 9 (всего 10 цифр) . Предположим, нам известна длина ключа – 4 цифры. В таком случае n = 10 (число элементов), а m = 4 (количество «посадочных мест» в замке). Далее нам необходимо разобраться с «конструкцией» замка:
Подставив числа n и m в формулы соединений, получим:
Как следует из этих расчетов, наихудшим положение дел с безопасностью от «взлома» паролей – у первого варианта конструкции замка: даже неопытный взломщик подберет код за два часа. Второй вариант превосходит по безопасности первый в 24 раза, а третий превосходит второй ~ в два раза. Но все равно эти пароли не надежны: перебором вариантов их «угадает» любая программ для «взлома» паролей. Именно поэтому для дополнительной защиты таких паролей применяют метод «блокировки» записей, который при превышении лимита ввода неправильной комбинации цифр блокирует доступ к содержимому: (SIM-карте сотового телефона, банковской карте и т.п.) A.3.2. «Первый раз в первый класс»Пусть в одну из школ в один из его первых классов поступило n мальчиков и n девочек. Скольким способами их можно посадить «попарно» за парты? Дополнительные соображения. В начале определим условия этого разделения:
Решение. Продолжим рассуждения.
Ответ: (n!)2. A.4. Задачи и упражнения
a) с помощью цикла; b) с помощью рекурсии. A.5. ПриложениеЛ И Т Е Р А Т У Р А 1. Бронштейн И.Н., Семендяев К.А. Справочник по математике (для инженеров и учащихся ВТУЗОВ) Издание седьмое, стереотипное. //М.: Государственное издательство Технико-Теоретической литературы, 1957. – 608 с., ил. Г Л О С С А Р И Й Версия 1.00.00 release candidat 05.04.2008
|
||