Кое-что о комбинаторике

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

При решении многих задач полезно, прежде чем изучать и подсчитывать какие-то объекты, сначала аккуратно все это «разложить по полочкам», говоря по-научному - классифицировать. Для этого, изучаемые объекты разбивают на группы (классы) так, чтобы каждый из них вошел точно в один класс. И далее рассматривают каждый класс по отдельности.

То есть, множество всех рассматриваемых предметов разбивается на непересекающиеся подмножества по какому-либо признаку (каждый элемент множества может входить только в одно из подмножеств).

В математике классификации используются очень часто. Например, целые числа часто разбивают на 2 класса – четные и нечетные числа. Многоугольники разбивают на классы в соответствии с числом сторон, а потом отдельно изучают треугольники, четырехугольники и другие фигуры.

Рассмотрим некоторые понятия связанные с комбинаторикой. Познакомимся с «правилом произведения» и «правилом суммы».

«Правило произведения» заключается в следующем. Пусть для выполнения некоторой задачи необходимо сделать два шага. Известно, что первый шаг можно сделать n различными способами, после чего второй шаг выполним m способами. Тогда задачу целиком можно решить n · m способами.

Другими словами, если в множестве А - n элементов, а в множестве В - m элементов, то число пар (а,b), где а берется из А, а b - из В, равно n · m.

Например, есть три города: А, Б и В. Из города А в город Б ведет 5 дорог, а из города Б в город В – 3 дороги. Сколько разных путей из города А в город В?

По «Правилу произведения» вариантов получается 15 = 5 · 3. Это: 1-6, 1-7, 1-8, 2-6, 2-7, 2-8 и т.д.

Рассмотрим еще один прием решения комбинаторных задач. Основная задача разбивается на несколько частных случаев, которые не могут происходить одновременно. Подсчитав число вариантов в каждом случае, надо сложить все найденные результаты. Такой прием называют «Правилом суммы».

То есть «Правило суммы» говорит о том, что если все возможные варианты рассортированы на группы так, что каждый вариант попал ровно в одну группу, то общее число вариантов равно сумме количеств вариантов по всем группам. Например, первый случай дает n вариантов, второй случай, исключающий первый, дает m вариантов. Другие случаи невозможны. Тогда общее количество вариантов n + m.

Например, на столе стоят три цветных коробки: желтая, синяя и красная. Посмотрим, каким числом способов можно положить в эти карманы два одинаковых шарика.

Так как шарики одинаковые, то варианты «первый шарик - в красную коробку, второй – в желтую» и «второй шарик - в красную коробку, первый – в желтую» одинаковы.

Поэтому надо отдельно рассматривать два случая:

  • шарики кладут в разные коробки;
  • оба шарика кладут в одну коробку.

В первом случае одна коробка остается пустой - получаем три различных способа размещения шариков. Во втором случае опять выбираем одну коробку из трех, но теперь кладем в нее оба шарика. Получаем еще три способа. Итак, шарики можно разместить в коробках 3 + 3 – шестью разными способами.

Иногда правило сложения и правило умножения используются одновременно.

Введем еще одно понятие комбинаторики. Рассмотрим множество, состоящее из n различных элементов. Например, можно рассмотреть множество, состоящее из первых n натуральных чисел. Для простоты будем считать, что каждое число написано на отдельной карточке. Будем располагать эти карточки в линию – одну за другой. Понятно, что это можно сделать различными способами. Каждое такое расположение называется перестановкой. Перестановки (и любые другие упорядоченные наборы чисел или других объектов) будем записывать в круглых скобках. Таким образом, (1, 4, 5, 3, 2) – одна перестановка из пяти чисел, а (2, 5, 1, 3, 4) – другая перестановка из тех же чисел. Конечно же, хочется понять, сколько различных перестановок можно образовать из элементов данного множества. Например, из множества {1, 2, 3} можно образовать шесть различных перестановок.

Ясно, что с ростом числа n число перестановок растет очень быстро, и перебрать их все, как в случае n = 3, очень трудно. Как же подсчитать число всех перестановок, которые можно образовать из n элементов?

Введем понятие факториала, так как оно часто встречается в комбинаторике. Пусть n – натуральное число. n! - это произведение 1 · 2 · 3 · . . . · n. Таким образом,

2! = 1 · 2 = 2,
3! = 1 · 2 · 3 = 6,
4! = 1 · 2 · 3 · 4 = 24 и так далее.
Отметим, что принято считать 0! = 1.

Например, у Незнайки есть три разных краски, ему надо покрасить забор из трех досточек, каждую досточку в свой цвет. Сколькими способами Незнайка может это сделать?

Первую досточку он может покрасить любой из трех красок, вторую – любой из двух оставшихся, третью – последней оставшейся краской. То есть всего 6 способов раскраски забора: 6 = 3 · 2 · 1.

Рассуждая аналогично решению данной задачи, легко доказать, что n разных предметов можно выложить в ряд n · (n-1) · (n-2) · . . . · 2 · 1 различными способами, то есть

число перестановок из n различных элементов равно n!

Обозначим число перестановок Pn. Тогда Pn = n!

Copyright © 2008