Основы комбинаторики

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

ЗАДАЧИ ПЕРВОГО ТИПА:

Турист собирается посетить за лето три города – Москву, Санкт-Петербург и Казань. Сколько существует вариантов поездок, если каждый город турист посетит один раз?

1. У нас есть множество, состоящее из трёх городов. Обозначим их как М, С и К. Задачи такого типа отличаются тем, что мы должны комбинировать все элементы множества между собой без повторений.

2. Подумаем, какие варианты поездок существуют. Обозначим три ситуации, где первым город является один из городов:

3. Если города не могут повторяться, тогда после М возможно поехать только в С или К, после С только в М или К, а после К только в М или С. Дополним схему:

4. Если турист уже посетил города в порядке \(M \Rightarrow C\), то ему остается посетить только К. Если он проехал путь \(M \Rightarrow K,\) ему остается посетить только С. Аналогично проанализируем каждый маршрут и заполним схему до конца:

5. В итоге у нас получились следующие комбинации посещения городов: МСК, МКС, СМК, СКМ, КМС, КСМ. Итого 6 различных маршрутов.

Ответ: 6.

ЗАДАЧИ ВТОРОГО ТИПА:

При встрече 7 приятелей пожали друг другу руки. При этом каждый пожал руку с каждым. Сколько всего было рукопожатий?

1. Обычно друг другу жмут руки именно два человека, поэтому будет рассматривать всевозможные пары друзей. Этот тип задач отличается от первого тем, что в наших комбинациях будут участвовать не все 7 элементов множества друзей сразу, а только по два из них. То есть обозначим каждого друга цифрой от 1 до 7 и будем комбинировать из этих чисел пары, они будут являться подмножеством множества друзей.

2. При этом пары, содержащие одинаковые элементы, неважно в каком порядке, считаются одинаковыми. Это значит, что рукопожатия друзей, например, 2 и 7 равно рукопожатию друзей 7 и 2. Будем брать именно ту пару, которая начинается на меньшую цифру. В данном случае рукопожатие именно этих людей запишем как 27.

3. Аналогично примеру №1 будем анализировать друзей по одному. Выпишем, какому количеству человек может пожать руку первый приятель:

12, 13, 14, 15, 16, 17 – 6 раз пожмёт кому-либо руку первый друг.

Сам себе он пожать руку не может, поэтому получилось 7 – 1 = 6 рукопожатий

4. Второй друг пожмёт руку друзьям такими комбинациями:

23, 24, 25, 26, 27 – 5 раз.

Он не пожмет руку сам себе и первому другу, т.к. их рукопожатие мы уже посчитали. Аналогично рукопожатия каждого следующего приятеля будет уменьшаться на 1:

34, 35, 36, 37 – 4 раза пожал руку третий приятель;

45, 46, 47 – 3 раза четвёртый;

56, 57 – 2 раза пятый;

67 – и 1 раз шестой.

5. Посчитаем, сколько раз происходило рукопожатие каких-либо друзей. Получим

\(6 + 5 + 4 + 3 + 2 + 1 = 21\)

Ответ: 21.

ЗАДАЧИ ТРЕТЬЕГО ТИПА:

Есть лампочки четырех цветов – синего (с), красного (к), зеленого (з) и жёлтого (ж). Сколько существует комбинаций их включения? Вариант, когда все выключены тоже является одной из комбинаций.

1. Здесь нам снова неважен порядок включения лампочек, важно сколько и какие именно могут гореть одновременно. Будем рассматривать варианты включения разного количества лампочек.

2. Существует только один вариант, что лампочки выключены. Если лампочки включены по одной, то это может быть 4 варианта: с, к, ж или з:

3. Если горят две лампочки, то существует 6 таких комбинаций. Подобрать их можно так же, как мы находили пары в примере №2. Аналогично найдем уже тройки горящих лампочек, таких вариантов будет 4. И существует один вариант, когда горят все лампочки.

4. Таким образом существует 16 различных вариантов одновременного включения лампочек, включая вариант, когда горят все лампочки и не горит не одной.

То есть мы нашли все возможные варианты подмножеств множества лампочек, включая пустое множество и само множество лампочек.