Комбинаторика

Комбинаторика

ПЕРЕСТАНОВКА:

Перестановка ($\mathbf{P}_{\mathbf{n}}$) – это конечное множество, в котором установлен порядок его элементов.

$P_{n} = n!$

где n – это количество элементов множества,

n! (эн факториал) = $1 \bullet 2 \bullet 3 \bullet ... \bullet n$

На полке стоят семь книг. Сколькими способами их можно расположить на полке?

Если у нас есть множество из семи книг и нам нужно перебрать все возможные варианты порядка их расположения, тогда используем формулу перестановки:

$P_{7} = 7! = 1 \bullet 2 \bullet 3 \bullet 4 \bullet 5 \bullet 6 \bullet 7 = 5040$

Ответ: 5040.

На полке стоят 9 книг, при этом среди них есть трёхтомник одного автора. Сколькими способами их можно расположить на полке, если книги трёхтомника должны находиться вместе, но в любом порядке?

1. При таком условии сначала представим трёхтомник как одну книгу. Тогда у нас не 9 книг, а 7. Тогда способов расположения таких книг существует 7! = 5040

2. При этом книги трёхтомника могут располагаться в разном порядке относительно друг друга. Таких комбинаций будет 3! = 6

3. А таком случае нужно перемножить перестановку трёхтомника относительно других книг и перестановку книг трёхтомника относительно друг друга:

$P_{7} \bullet P_{3} = 7! \bullet 3! = 5040 \bullet 6 = 30240$

Ответ: 30240.

Сколькими способами можно расположить между собой числа 0, 1, 2 и 3, если они не могут повторяться и число 2 не может быть первым?

1. Если у нас 4 элемента множества, тогда их перестановка равна:

$P_{4} = 4! = 1 \bullet 2 \bullet 3 \bullet 4 = 24$

2. При этом все комбинации, где число 2 стоит на первой позиции нужно исключить. Мысленно закрепим число 2 на первой позиции и начнем комбинировать оставшиеся элементы множества. Таким образом количество комбинаций, при которых число 2 стоит на первой позиции равно:

$P_{3} = 3! = 1 \bullet 2 \bullet 3 = 6$

3. Вычтем из количества всевозможных комбинаций количество неподходящих, получим:

$P_{4}\ –\ P_{3} = 24\ –\ 6 = 18$

Ответ: 18.

РАЗМЕЩЕНИЕ:

Например:

У нас есть множество $\left\{ a,\ b,\ c,\ d \right\}$. Оно состоит из 4 элементов. Нам нужно найти количество всех возможных пар этих элементов. То есть будем выделять в этом множестве подмножества, содержащие только 2 элемента из 4. Чтобы найти количество этих пар, нужно посчитать размещение из 4 элементов по 2:

$\boxed{A_{n}^{k} = n(n\ –1)(n\ –\ 2) \bullet ... \bullet (n\ –\ (k\ –\ 1))}$

$A_{4}^{2} = 4 \bullet 3 = 12$

т.е. мы находим произведение двух натуральных множителей, наибольший из которых равен 4.

Эта формула преобразовывается в более ёмкую. Её удобнее использовать, когда мы говорим о большом количестве элементов:

$\boxed{A_{n}^{k} = \frac{n!}{(n\ –\ k)!}}$

$A_{4}^{2} = \frac{4!}{(4\ –\ 2)!} = \frac{4!}{2!} = \frac{1 \bullet 2 \bullet 3 \bullet 4}{1 \bullet 2} = 3 \bullet 4 = 12$

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

Если мы говорим о размещении n элементов по n – тогда размещение, по сути, становится перестановкой.

Сколько существует телефонных номеров, состоящих из 7 цифр, при этом первой цифрой номера не может быть 0 и цифры номера не повторяются?

1. Всего существует 10 цифр, а телефонный номер состоит только из 7 из них. Тогда мы говорим о размещении 10 элементов по 7. Найдем это размещение:

$A_{10}^{7} = \frac{10!}{\left( 10–7 \right)!} = \frac{10!}{3!}$

2. Но из такого количества телефонных номеров нужно исключить те, которые начинаются на 0. Таких размещений уже будет 9 по 6:

$A_{9}^{6} = \frac{9!}{(9\ –\ 6)!} = \frac{9!}{3!}$

3. Вычтем из всех размещений не подходящие условию:

$A_{10}^{7}\ –\ A_{9}^{6} = \frac{10!\ –\ 9!}{3!} = \frac{9!(10\ –\ 1)}{3!} = 4 \bullet 5 \bullet 6 \bullet 7 \bullet 8 \bullet 9 \bullet 9 = 544320$

Ответ: 544320.

СОЧЕТАНИЯ:

$C_{n}^{k} = \frac{A_{n}^{k}}{P_{k}} = \frac{n!}{k!(n\ –\ k)!}$

Например:

Если мы хотим выделить из множества $\left\{ a,\ b,\ c,\ d \right\}$ все подмножества, которые включают в себя 2 элемента, то мы говорим о сочетании 4 элементов по 2. В таком случае, в отличие от размещения, не будут учитываться пары, в которые входят два одинаковых, но стоящих на разных позициях элемента. Например, пара ab – это то же самое, что пара ba. Перестановка элементов подмножества не играет роли, поэтому формула сочетания выглядит как размещение, деленное на перестановку k элементов.

Сколькими способами можно выбрать трёх дежурных из класса, в котором 25 человек?

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

$C_{25}^{3} = \frac{25!}{3!(25\ –\ 3)!} = \frac{25!}{3!22!} = \frac{23 \bullet 24 \bullet 25}{6} = 2300$

Ответ: 2300.

В вазе стоят 8 красных и 5 белых роз. Нужно собрать букет из 3 красных роз и 2 белых. Сколькими способами это можно сделать?

1. Из-за того, что неважно, в каком порядке в букете стоят красные розы, а важно лишь их количество, тогда используем сочетания 8 красных роз по 3:

$C_{8}^{3} = \frac{8!}{3!(8\ –\ 3)!} = \frac{8!}{3!5!} = \frac{1 \bullet 2 \bullet 3 \bullet 4 \bullet 5 \bullet 6 \bullet 7 \bullet 8}{3!1 \bullet 2 \bullet 3 \bullet 4 \bullet 5} = \frac{6 \bullet 7 \bullet 8}{6} = 56$

2. Аналогично с белыми розами важны лишь возможные сочетания 5 красных роз по 2:

$C_{5}^{2} = \frac{5!}{2!(5\ –\ 2)!} = \frac{5!}{2!3!} = \frac{4 \bullet 5}{2} = 10$

3. Каждому выбору красных роз соответствует выбор белых, т.е. независимо от сочетания одного цвета выбирается сочетание другого. Поэтому перемножим эти сочетания:

$C_{8}^{3} \bullet C_{5}^{2} = 56 \bullet 10 = 560$

Ответ: 560.

БИНОМ НЬЮТОНА:

Мы знаем, что:

$\left( a + b \right)^{1} = a + b$

$\left( a + b \right)^{2} = a^{2} + 2ab + b^{2}$

$\left( a + b \right)^{3} = a^{3} + 3a^{2}b + 3ab^{2} + b^{3}$

${(a + b)}^{4} = a^{4} + 4a^{3}b + 6a^{2}b^{2} + 4ab^{3} + a^{4}$

И так далее по мере возрастания степени суммы меняются коэффициенты многочлена. Высчитать эти коэффициенты можно с помощью Бинома Ньютона, который является частным случаем сочетаний в комбинаторике.

$\ {(a + b)}^{n} = C_{n}^{0}a^{n} + C_{n}^{1}a^{n\ –\ 1}b + C_{n}^{2}a^{n\ –\ 2}b^{2} + ... + C_{n}^{k}a^{n\ –k}b^{k} + ... + C_{n}^{n\ –\ 1}ab^{n\ –\ 1} + C_{n}^{n}b$

Где n – натуральное число, коэффициенты $С_{n}^{k}$ – это сочетания k по n, где k – порядковый номер коэффициента начиная с 0.

При этом для чисел a и b при одном коэффициенте сумма показателей степеней равна n.

ТРЕУГОЛЬНИК ПАСКАЛЯ

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

Первая строчка пирамиды показывает нам, чему будут равны коэффициенты многочлена, равного сумме чисел в нулевой степени:

$\left( a + b \right)^{0} = 1$

Существует единственный коэффициент равный 1

У суммы чисел в первой степени будут коэффициенты, соответствующие второй строчке:

$\left( a + b \right)^{1} = a + b$

Коэффициенты при слагаемых равны 1 и 1

Коэффициенты привычного нам квадрата суммы равны 1, 2 и 1 соответственно:

$\left( a + b \right)^{2} = a^{2} + 2ab + b^{2}$

И так далее.

Можем взять, например, сразу узнать коэффициенты многочлена, равного 4-ой степени суммы чисел.

${(a + b)}^{4}$

Для этого посмотрим на 5-ую строчку треугольника.

Коэффициенты равны 1, 4, 6, 4 и 1 соответственно. Действительно, по Биному Ньютона, такими коэффициентами и будет обладать этот многочлен:

${(a + b)}^{4} = a^{4} + 4a^{3}b + 6a^{2}b^{2} + 4ab^{3} + a^{4}$