Интернет-энциклопедия по школьным предметам от Maximum Education. Учебник поможет решить домашнее задание, подготовиться к контрольной и вспомнить прошлые темы.
Комбинаторика
ПЕРЕСТАНОВКА:
Перестановка (\(\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}\)