Элементы комбинаторики

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

Напомним, что комбинаторика — раздел математики, посвящённый решению задач выбора и расположения элементов некоторого конечного множества в соответствии с заданными правилами.

Давайте вспомним два основных правила, с помощью которых решается много комбинаторных задач.

Итак, первое правило называется правилом суммы. Сформулируем его: если элемент некоторого множества  можно выбрать  способами, а элемент множества  —  способами, то элемент из множества  или из множества  можно выбрать  способами.

Правило суммы распространяется и на большее количество множеств.

Решим задачу. В городе  есть три университета — педагогический, политехнический и экономический. Абитуриенту нравятся 2 факультета в педагогическом университете, 3 — в политехническом университете и 1 — в экономическом. Сколько возможностей имеет студент для поступления в университет?

Решение.

Второе правило. Правило произведения: если первый компонент пары можно выбрать  способами, а второй —  способами, то такую пару можно выбрать  способами.

Правило произведения распространяется также и на упорядоченные тройки, четвёрки и любые другие упорядоченные конечные множества.

Решим задачу. Сколько различных трёхзначных чисел можно записать с помощью цифр , , , ,  при условии, что ни одна цифра не повторяется?

Решение.

Решим ещё одну задачу. Сколько разных поездов можно составить из восьми вагонов, если каждый из вагонов можно поставить на любом месте?

Решение.

Напомним, что произведение всех натуральных чисел от  до  называют  факториалом и обозначают так: .

Тогда , .

Напомним, что принято считать  и .

В комбинаторике различают три вида различных соединений (комбинаций) элементов фиксированного (конечного) множества. Это перестановки, размещения и сочетания.

Давайте вспомним о каждом из этих видов поподробнее.

Начнём с перестановок. Перестановками из  элементов называются соединения, которые состоят из одних и тех же  элементов и отличаются одно от другого только порядком их расположения.

Кстати, перестановки – это простейшие комбинации, которые можно составить из элементов конечного множества.

Классической задачей комбинаторики является задача о числе перестановок без повторения, содержание которой можно выразить вопросом: сколькими способами можно разместить  различных предметов на  различных местах?

Число перестановок из  элементов обозначают .

Формула числа перестановок  из  различных элементов имеет вид:

.

Для случая, когда среди выбираемых  элементов есть одинаковые, задачу о числе перестановок с повторениями можно выразить вопросом: сколькими способами можно переставить  предметов, расположенных на  различных местах, если среди этих н предметов имеется  различных типов (), то есть среди предметов есть одинаковые.

Формула числа перестановок с повторениями имеет вид:

 ,

 .

Решим задачу. Сколько слов можно получить, переставляя буквы в слове «гора» и

«институт»?

Решение.

Теперь перейдём к следующему виду комбинаций – размещениям.

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

Классической задачей комбинаторики является задача о числе размещений без повторений, содержание которой можно выразить вопросом: сколькими способами можно выбрать и разместить по  различным местам  из  различных предметов?

Число всевозможных размещений из  элементов по  элементов обозначают . Формула числа размещений  элементов по  имеет следующий вид:

.

В случае, когда нужно найти число размещений из  элементов по  элементов, оно равно числу перестановок из этих элементов.

Также классической задачей комбинаторики является задача о числе размещений с повторениями, содержание которой можно выразить вопросом: сколькими способами можно выбрать и разместить по  различным местам  из  предметов, среди которых есть одинаковые?

Формула числа размещений с повторениями имеет следующий вид:

.

Решим задачу. В пассажирском поезде  вагонов. Сколькими способами можно рассадить в поезде  человека, при условии, что все они должны ехать в различных вагонах?

Решение.

Решим ещё одну задачу. В лифт восьмиэтажного дома вошли  пассажиров. Сколькими способами могут выйти пассажиры на каждом этаже, начиная со второго?

Решение.

Ну а теперь давайте поговорим о последнем виде комбинаций элементов, о сочетаниях.

Сочетаниями из  элементов по  в каждом () называются соединения, каждое из которых содержит  элементов, взятых из данных  разных элементов, и которые отличаются одно от другого по крайней мере одним элементом.

Классической задачей комбинаторики является задача о числе сочетаний без повторений, содержание которой можно выразить вопросом: сколькими способами можно выбрать  из  различных предметов?

Число всевозможных размещений из  различных элементов по  элементов обозначают .

Формула числа сочетаний из  элементов по  имеет следующий вид:

, или .

Задачу о числе сочетаний с повторениями можно выразить вопросом: имеется по  одинаковых предметов каждого из различных типов; сколькими способами можно выбрать  из этих  предметов?

Формула числа сочетаний с повторениями имеет следующий вид:

.

Решим задачу. Необходимо выбрать в подарок  из  имеющихся различных книг. Сколькими способами можно это сделать?

Решение.

И решим ещё одну задачу. В кондитерском магазине продавались  сорта пирожных: наполеоны, эклеры, песочные и слоёные. Сколькими способами можно купить  пирожных?

Решение.