Комбинаторика.
Комбинаторика — это раздел математики, который занимается подсчётом количества вариантов, способов сделать что-либо. Если считать варианты беспорядочно, то очень легко пропустить какой-то вариант или посчитать один и тот же вариант несколько раз. Поэтому в задачах на комбинаторику очень важно придумать некоторый порядок подсчёта вариантов.
Кроме того, важно внимательно прочитать условие задачи и понять:
- могут ли повторяться элементы в каждом варианте,
- важен ли порядок расположения элементов.
- считаются ли симметричные варианты разными.
Рассмотрим несколько задач.
Задача 1.
Белка делает запасы на зиму. Она нашла три гриба — белый, лисичку и подосиновик — и хочет надеть их в ряд на ветку дерева. Сколькими способами она может это сделать? Разными способами считаются те, которые отличаются порядком расположения грибов на ветке.
Решение.
Придумаем порядок перебора вариантов.
Пусть сначала Белка наденет на ветку белый гриб, тогда дальше она может надеть лисичку и потом подосиновик или сначала подосиновик и потом лисичку. Всего 2 варианта, когда первым надет белый гриб:
Если сначала надеть на ветку лисичку, то тоже есть 2 варианта расположения белого гриба и подосиновика:
Если первым надеть подосиновик, то тоже 2 варианта:
Таким образом, мы перебрали все возможные варианты расположения грибов на ветке. Их получилось 2+2+2=6.
В этой задаче все грибы разные (не повторяются) и важен их порядок расположения на ветке.
Ответ: 6 способами.
Задача 2.
Белка набрала много грибов: корзину белых, корзину лисичек и корзину подберезовиков. Теперь она хочет надеть грибы на ветки. На одну ветку умещается только 3 гриба. Сколькими способами можно надеть грибы на одну ветку? Разными способами считаются те, которые отличаются порядком расположения грибов на ветке.
Решение.
Теперь грибы на ветке могут повторяться.
1 способ.
Если все три гриба разные, то, как мы получили в задаче 1, есть 6 вариантов их надеть на ветку.
Если все три гриба одинаковые, то будет 3 варианта:
Рассмотрим варианты, когда два гриба одного вида и один гриб другого вида.
Для белого гриба и лисички будет 6 вариантов:
Аналогично, будет 6 вариантов для белого гриба и подосиновика и 6 вариантов для лисички и подосиновика.
Таким образом, всего есть 6+6+6=18 способов расположить на ветке два гриба одного вида и 1 гриб другого вида.
А всего получаем 6+3+18=27 вариантов расположить 3 гриба на ветке.
2 способ.
Если первым надеть на ветку белый гриб, то дальше можно надеть:
- еще 2 белых гриба,
- белый и лисичку,
- белый и подосиновик,
- 2 лисички,
- лисичку и белый,
- лисичку и подосиновик,
- 2 подосиновика,
- подосиновик и белый,
- подосиновик и лисичку.
Всего 9 вариантов надеть на ветку 3 гриба, если первым будет белый гриб.
Несложно догадаться, что столько же вариантов будет, если первой надеть лисичку, и столько же, если первым надеть подосиновик. А всего будет 9+9+9=27 вариантов расположить 3 гриба на ветке.
В этой задаче грибы на ветке могут повторяться и важен их порядок расположения на ветке.
Ответ: 27 способами.
Задача 3.
Белка собирается в гости к своему другу Ёжику. Она хочет принести в подарок ему 2 гриба. Сколькими способами Белка может выбрать подарок для Ёжика, если
- а) у неё есть только три гриба — белый, лисичка и подосиновик?
- б) у неё есть три корзины грибов — белых, лисичек и подосиновиков?
Разными способами считаются те, которые отличаются набором грибов в подарке.
Решение.
а) Если у белки только три гриба, то для Ёжика она может выбрать:
- белый и лисичку,
- белый и подосиновик,
- лисичку и подосиновик.
Всего 3 способа выбрать подарок. Заметим, что подарок для Ёжика — это просто набор из двух грибов, порядок их в подарке не важен. Например, «белый + лисичка» и «лисичка + белый» — это один и тот же вариант подарка.
В этом случае все грибы разные (не повторяются) и порядок их не важен.
б) Если у белки три корзины грибов, то для Ёжика она может выбрать:
- 2 белых гриба,
- 2 лисички,
- 2 подосиновика,
- белый и лисичку,
- белый и подосиновик,
- лисичку и подосиновик.
Всего 6 способов выбрать подарок.
В этом случае грибы в подарке могут повторяться и порядок их не важен.
Ответ: а) 3 способами, б) 6 способами.
Задача 4.
Маша вырезала из бумаги много звёздочек с четырьмя лучами и хочет их раскрасить. У нее есть голубой и фиолетовый фломастеры. Каждый луч звезды Маша раскрашивает одним цветом. Сколько разных звёздочек у нее получится?
Решение.
В этой задаче нужно учесть, что звёздочки, получающиеся друг из друга поворотом, являются одинаковыми.
Придумаем порядок, с котором можно пересчитать разные варианты звёзд:
- звёздочек, у которых все лучи голубые — 1,
- звёздочек, у которых 1 луч фиолетовый и 3 луча голубые, — 1,
- звёздочек, у которых 2 луча фиолетовые и 2 луча голубые, — 2,
- звёздочек, у которых 3 луча фиолетовые и 1 луч голубой, — 1,
- звёздочек, у которых все лучи фиолетовые, — 1.
Всего 1+1+2+1+1=6 различных звёздочек.
В этой задаче важно учитывать симметрию звёздочек.
Ответ: 6 разных звёздочек.
Задача 5.
Из города А в город Б ведут 2 дороги. Из города Б в город В — 3 дороги. И одна дорога ведёт из города А в город В. Сколько существует разных путей из А в В?
Решение.
Нарисуем схему.
Один путь – это прямой путь из города А в город В (отмечен фиолетовым цветом):
Посчитаем, сколько разных путей ведёт из города А в город В через город Б.
Если из А в Б мы идём по синей дороге, то у нас есть 3 варианта пути в В: синий-красный, синий-оранжевый и синий-жёлтый.
Если из А в Б мы идём по зелёной дороге, то тоже 3 варианта: зелёный-красный, зелёный-оранжевый и зелёный-жёлтый.
Получаем, что из А в В через город Б ведут 6 разных путей. А вместе с прямым путём из А в В всего 7 разных путей.
Ответ: 7 путей.
Перебор вариантов помог нам решить предыдущие задачи, но часто вариантов в задаче так много, что перебрать их все очень сложно. Поэтому постепенно переходим от перебора вариантов к рассуждениям и соответствующим вычислениям.
Задача 6.
У Миши есть 4 кубика разных цветов (по 1 кубику каждого цвета). Сколько разных башенок из 2 кубиков он может построить?
Решение.
Первый кубик Миша может выбрать 4 способами – любой из 4 имеющихся у него кубиков.
После того, как он уже выбрал 1 кубик, их осталось только 3.
Значит, для любого из 4 первых кубиков он может выбрать 3 варианта второго:
Всего получаем 3+3+3+3=12 вариантов башенок.
Ответ: 12 разных башенок.