Основные правила комбинаторики
Правило сложения
Пусть есть два множества объектов A = {a1, ..., an} и B = {b1, ..., bm}, тогда количество способов выбрать один объект из A или один объект из B равно n + m.
Пример 1. Пусть множество A состоит из десяти цифр, а B – из 33 букв русского алфавита. Тогда в силу правила сложения мы можем взять одну цифру или одну букву 43 способами.
Правило умножения
Пусть есть два множества объектов A = {a1, ..., an} и B = {b1, ..., bm}, тогда количество способов выбрать сперва один объект из A, а затем выбрать один объект из B равно n · m.
Пример 2. Мама и папа дяди Федора отправились на юг. Мама взяла с собой на отдых семь платьев разных цветов и семь разных туфель. Сколько разных нарядов может скомбинировать мама для вечерних прогулок?
Решение: Каждое платье можно скомбинировать с разными туфлями. Получится 7 вариантов. Платьев 7, поэтому 7 х 7 = 49 различных нарядов.
Принцип Дирихле
Пусть есть n ящиков и n+ 1 кролик. Если рассадить всех кроликов по этим ящикам, то обязательно найдется ящик в котором не меньше двух кроликов. Доказательство этого принципа очевидно. Действительно, пусть это утверждение неверно, тогда в каждой клетке сидит не более одного кролика, и, следовательно, в 50 клетках — не более 50 кроликов, а их должно быть 51. Получили противоречие.
Пример 3. В школе учатся 400 учеников. Доказать, что хотя бы у двоих из них дни рождения совпадают.
Решение: В году 565(366) дней. Если предположить, что каждый день года - это день рождения одного из 365 учеников, то оставшиеся дни рождения будут совпадающими.
Факториал
Факториал числа n – это произведение чисел от 1 до n. Определён только для целых неотрицательных чисел. Формула факториала: n! = 1 * 2 * … * n
Математическая формула представлена восклицательным знаком «!». Термин был введен в 1800 году, а обозначение появилось только в 1808. В формуле нужно умножить все целые числа от 1 до значения самого числа, стоящего под знаком факториала.
Пример 4. 7! = 1 * 2 * 3 *4* 5 * 6 * 7 = 5040.