Комбинаторика и ее основные формулы

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

Факториал

Произведение n первых натуральных чисел называется n-факториал и обозначается как n!. По определению: 1! = 0; 0! = 1.

Рассмотрим некоторое множество Х, состоящее из n элементов: \(X=\{x_1,x_2,...,x_n\}\). Будем выбирать из этого множества различные упорядоченные подмножества Y из k элементов.

Пусть имеется n различных объектов. Будем выбирать из них m объектов и переставлять всеми возможными способами между собой (то есть меняется и состав выбранных объектов, и их порядок). Размещением из n элементов множества Х по k элементам назовем любой упорядоченный набор \((x_{i_1},x_{i_2},...,x_{i_k})\) элементов множества Х.

Если выбор элементов множества Y из Х происходит с возвращением, т. е. каждый элемент множества Х может быть выбран несколько раз, то число размещений из n по k находится по формуле \(n^k\) (размещения с повторениями).

Если же выбор делается без возвращения, т. е. каждый элемент множества Х можно выбирать только один раз, то количество размещений из n по k обозначается как \(A^k_n\) и определяется равенством \(A^k_n=n(n-1)...(n-k+1)=\frac{n!}{(n-k)!}\)(размещения без повторений).

Пример 1. Пусть даны шесть цифр: 1; 2; 3; 4; 5; 6. Определить, сколько трехзначных чисел можно составить из этих цифр.

Решение: Если цифры могут повторяться, то количество трехзначных чисел будет: \(m=n^k=6^3=216\). Если цифры не повторяются, то \(m=A^3_6=6\cdot 5\cdot 4=120\).

Пример 2. Студенты института изучают в каждом семестре по десять дисциплин. В расписание занятий включаются каждый день по 3 дисциплины. Сколько различных расписаний может составить диспетчерская?

Решение: Расписание на каждый день может отличаться либо предметами, либо порядком расположения этих предметов, поэтому имеем размещения: \(A^3_{10}=10\cdot 9\cdot 8=720\).

Частный случай размещения при n = k называется перестановкой из n элементов. Перестановками называются такие выборки элементов, которые отличаются только порядком расположения элементов, но не самими элементами. Число всех перестановок из n элементов равно \(A^n_n=P_n=n!\).

Пример 3. 30 книг стоят на книжной полке, из них 27 различных книг и три книги одного автора. Сколькими способами можно расставить эти книги на полке так, чтобы книги одного автора стояли рядом?

Решение: Будем считать три книги одного автора за одну книгу, тогда число перестановок будет \(P_{28}\). А три книги можно переставлять между собой \(P_3\) способами, тогда, по правилу произведения, имеем, что искомое число способов равно: \(P_3\cdot P_{28}=3!\cdot 28!\).

Пусть теперь из множества Х выбирается неупорядоченное подмножество Y (порядок элементов в подмножестве не имеет значения). Сочетаниями из n элементов по k называются подмножества из k элементов, отличающиеся друг от друга хотя бы одним элементом. Неупорядоченные выборки называются сочетаниями из n элементов по m. Общее число всех сочетаний из n по k обозначается \(C^k_n\) и равно \(C^k_n=\frac{A^k_n}{k!}=\frac{n!}{(n-k)!k!}=\frac{n(n-1)...(n-k+1)}{k!}\).

Пример 4. В группе из 27 студентов нужно выбрать трех дежурных. Сколькими способами можно это сделать?

Решение: Так как порядок студентов не важен, используем формулу для числа сочетаний: \(m=C^3_{27}=\frac{27!}{3!\cdot 24!}=\frac{27\cdot 26 \cdot 25}{1\cdot 2 \cdot3}=2925\).

При решении задач комбинаторики используют следующие правила:

Правило суммы. Если некоторый объект А может быть выбран из совокупности объектов m способами, а другой объект В может быть выбран n способами, то выбрать либо А, либо В можно m + n способами.

Правило произведения. Если объект А можно выбрать из совокупности объектов m способами и после каждого такого выбора объект В можно выбрать n способами, то пара объектов (А, В) в указанном порядке может быть выбрана m · n способами.

Пример 5. Наряд студентки состоит из блузки, юбки и туфель. Девушка имеет в своем гардеробе четыре блузки, пять юбок и три пары туфель. Сколько нарядов может иметь студентка?

Решение: Пусть сначала студентка выбирает блузку. Этот выбор может быть совершен четырьмя способами, так как студентка имеет четыре блузки, затем пятью способами произойдет выбор юбки и тремя способами выбор туфель. По принципу умножения, получается: 4 · 5 · 3 = 60 нарядов (комбинаций).