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

Комбинаторика Опр. Комбинаторика – это раздел математики, который позволяет подсчитать, сколькими способами можно сделать тот или иной выбор, выполнить какое-либо условие. Опр. Факториал – это произведение последовательных натуральных чисел, начиная с 1 до заданного. . Например, . Важно уметь сокращать факториалы: , Опр. Пусть имеется множество, содержащее упорядоченное подмножество, состоящее из размещением из элементов по Число размещений из без повторений элементов, называется элементов. по ( элементов. Каждое его вычисляется по формулам: ) . с повторениями Пример 1. В группе 20 студентов. Выбирают старосту и культорга. Каждый может занимать любую должность, но только одну. Сколькими способами это можно сделать? Решение. Дано множество из 20 элементов (студентов). Выбирают 2 элемента, порядок выбора важен, так как пары (староста – Иванов, культорг – Петров) и (староста – Петров, культорг – Иванов) – разные. Следовательно, число способов выбрать пару равно числу размещений без повторений из 20 по 2: ( ) Если бы разные должности мог занимать один человек, то надо было бы воспользоваться формулой с повторениями , . Эту задачу можно решить и путем рассуждений. Но нам важно понять, когда «работает» это понятие (и формулы), особенно в том случае, когда рассуждения не помогут или громоздки. Опр. Частный случай размещений – перестановки. Размещения из элементов по элементов называются перестановками из Число перестановок из элементов. элементов вычисляется по формулам: без повторений с повторениями ( ( ) ) , где сколько раз может повторяться соответствующий элемент. Пример 2. Сколькими способами можно расставить 6 книг на одной полке? Решение. Переставляем все 6 книг, книги разные, порядок следования книг на полке важен. Это можно сделать способами. Опр. Пусть имеется множество, состоящее из n элементов. Каждое его подмножество, содержащее k элементов, называется сочетанием из n элементов по k элементов. В этом понятии порядок следования выбранных элементов не важен. Число сочетаний из n элементов по k вычисляется по формулам: без повторений с повторениями ( ( ) ) ( ) Пример 3. Сколько матчей будет сыграно в футбольном чемпионате с участием 16 команд, если каждые две команды встречаются между собой один раз? Решение. Из 16 команд выбирают 2 команды для матча, порядок выбора команд для матча не важен (Спартак-Динамо или Динамо-Спартак – это один и тот же матч). Поэтому число матчей равно ( ) . Пример 4. Сколько шестизначных чисел, кратных пяти, можно составить из цифр 0,1, 2, 3, 4, 5 при условии, что в числе цифры не повторяются? Решение. Число кратно 5, если оно оканчивается 0 или 5. Пусть цифра 0 стоит на последнем месте. Остальные пять цифр могут стоять на оставшихся пяти местах в любом порядке. Тогда, число шестизначных чисел, с 0 на конце равно числу перестановок из пяти элементов, т.е. Пусть цифра 5 стоит на последнем месте. Рассуждения такие же, получим тоже 120 чисел. НО среди этих 120 есть числа вида 0????5 – число с 0 начинаться не может. На 4 позиции осталось 4 цифры, таких чисел . Таким образом, 120+120-24=240-24=216 Ответ : 216.