Основной вопрос комбинаторики — «сколько?», основная задача — подсчёт числа элементов конечного множества. В комбинаторных задачах нас обычно интересует, сколько комбинаций, удовлетворяющих тем или иным условиям, можно составить из заданного конечного набора объектов.
В простейших случаях мы можем выписать все нужные нам комбинации и непосредственно подсчитать их. Однако при бессистемном выписывании легко упустить какую-то комбинацию или, наоборот, посчитать некоторую комбинацию дважды. Поэтому при переборе вариантов желательно придерживаться двух правил.
1. Обозначаем наши комбинации буквами или цифрами так, что каждая комбинация будет обозначена своей уникальной последовательностью букв или цифр.
2. Выписываем комбинации в алфавитном порядке (при обозначении буквами) или по возрастанию чисел (при обозначении цифрами).
При таком переборе ни один вариант не ускользнёт от нас и, с другой стороны, будет исключена возможность повторения вариантов.
Задача. Маша собирается съесть яблоко, сливу и мандарин, но пока не решила, в какой последовательности. Сколькими способами Маша может выбрать эту последовательность?
Решение. Обозначаем буквами: Я — яблоко, С — слива, М — мандарин. Тогда, например, СМЯ — это вариант, когда Маша сначала съест сливу, потом — мандарин, потом — яблоко.
Выпишем варианты в алфавитном порядке: МСЯ, МЯС, СМЯ, СЯМ, ЯМС, ЯСМ.
Получилось 6 вариантов.
Задача. Сколько существует четырёхзначных чисел, сумма цифр которых меньше 4?
Решение. Здесь обозначать нечего — мы и так имеем дело с числами. Остаётся лишь выписать по возрастанию все четырёхзначные числа, сумма цифр которых равна 1, 2 или 3:
1000, 1001, 1002, 1010, 1011, 1020, 1100, 1101, 1110, 1200, 2000, 2001, 2010, 2100, 3000.
Всего получилось 15 чисел.
Задача. Четыре гостя при входе в ресторан отдали швейцару свои шляпы, а при выходе получили их обратно. Невнимательный швейцар раздал шляпы случайным образом. Сколько существует вариантов, при которых каждый гость получил чужую шляпу?
Решение. Занумеруем гостей цифрами 1, 2, 3, 4 и так же занумеруем их шляпы. Считаем, что шляпа с данным номером принадлежит гостю с этим же номером (то есть, например, шляпа 2 принадлежит гостю 2).
Тогда каждый вариант получения шляп обозначается четырёхзначным числом, составленным из цифр 1, 2, 3 и 4, в котором номер позиции цифры есть номер гостя, а сама цифра есть номер полученной им шляпы (номера позиций будем считать слева направо).
Например, комбинация 4132 означает, что первый гость получил четвёртую шляпу, второй — первую, третий — третью, а четвёртый — вторую. Такой вариант не годится по условию, поскольку третий получил свою шляпу.
Теперь понятно, что нужно сделать — выписать по возрастанию все четырёхначные числа, содержащие по одной цифре 1, 2, 3 и 4, такие, что никакая цифра не стоит на позиции со своим номером. Эти числа выписаны ниже под чертой. Красные цифры над чертой — номер позиции (номер гостя), с которым не должна совпадать цифра в соответствующем столбце (номер шляпы).
1 2 3 4
2 1 4 3
2 3 4 1
2 4 1 3
3 1 4 2
3 4 1 2
3 4 2 1
4 1 2 3
4 3 1 2
4 3 2 1
Как видим, всего имеется 9 вариантов нужной раздачи шляп.
Перебор вариантов
