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

Что такое комбинаторика

Правила сложения и умножения

Перестановки

Перестановки с повторениями

Размещения

Размещения с повторениями

Сочетания

Сочетания с повторениями

Бином Ньютона и биномиальные коэффициенты

Треугольник Паскаля

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

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

Значительную роль комбинаторные методы играют и в  чисто математических вопросах — теории групп и их представлений, изучении основ геометрии,  неассоциативных алгебр и др.

► Пример комбинаторной задачи. Сколько трёхзначных чисел можно составить из цифр 0, 2, 4, 6, 8, используя в записи числа каждую из них не более одного раза?

I способ. Постараемся выписать все такие числа. На первом месте может стоять любая цифра кроме 0. Например, 2. На втором месте любая цифра из 0, 4, 6 и 8. Пусть 0. Тогда в качестве третьей цифры можно выбрать любую из 4, 6, 8. Получаем три числа

204, 206, 208.

Вместо 0 на второе место можно было поставить 4, тогда третье цифрой можно записать или 0, или 6, или 8:

240, 246, 248.

Рассуждая аналогично, получаем ещё две тройки трёхзначных чисел с цифрой 2 на первом месте:

260, 264, 268;

280, 284, 286.

Других, кроме выписанных 12-ти, трёхзначных чисел с цифрой 2 на первом месте, и удовлетворяющих условию,  нет.

Если на первом месте записать цифру 4, а остальные выбирать из цифр 0, 2, 6, 8,  то получим ещё 12 чисел:

402, 406, 408;

420, 426, 428;

460, 462, 468;

480, 482, 486.

По столько же трёхзначных чисел можно составить с цифрой 6 на первом месте и цифрой 8 на первом месте. Значит, искомое количество:

4 · 12 = 48.

Вот эти числа:

204, 206, 208, 240, 246, 248, 260, 264, 268, 280, 284, 286;

402, 406, 408, 420, 426, 428, 460, 462, 468, 480, 482, 486;

602, 604, 608, 620, 624, 628, 640, 642, 648, 680, 682, 684;

802, 804, 806, 820, 824, 826, 840, 842, 846, 860, 862, 864.

Ответ: 48.  ◄

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

Комбинаторное правило сложения (правило "или") — одно из основных правил комбинаторики, утверждающее, что, если имеется n элементов и элемент A₁ можно выбрать m₁ способами, элемент A₂ можно выбрать m₂ способами и так далее, элемент A_n можно выбрать m_n способами, то выбрать или A₁, или A₂, или, и так далее, A_n можно 

m₁ + m₂ + ... + m_n 

способами.

► Например, выбрать подарок ребёнку из 9 машинок, 7 плюшевых медведей и 3 железных дорог можно

9 + 7 + 3 = 19

способами. 

Ответ: 19. ◄

Правило умножения (правило "и") — ещё одно из важных правил комбинаторики. Согласно ему, если элемент A₁ можно выбрать m₁ способами, элемент A₂ можно выбрать m₂ способами и так далее, элемент A_n можно выбрать m_n способами, то набор элементов (A₁, A₂, ... , A_n) можно выбрать

m₁ · m₂ · ... · m_n 

способами. 

► Например.

1) Выбрать ребёнку в подарок машинку, плюшевого медведя и железную дорогу, выбирая из 9 машинок, 7 плюшевых медведей и 3 железных дорог, можно

9 · 7 · 3 = 189

способами.

Ответ: 189. 

2) Воспользуемся правилом умножения для решения задачи, уже рассмотренной выше: Сколько трёхзначных чисел можно составить из цифр 0, 2, 4, 6, 8, используя в записи числа каждую из них не более одного раза?

II способ. 

0 не может стоять первым, значит первую цифру нужно выбрать из 2, 4, 6, 8 — 4 способа;

второй цифрой может быть любая из четырёх оставшихся — 4 способа;

третью цифру можно выбрать среди трёх оставшихся — 3 способа.

Итак, искомое количество трёхзначных чисел:

4 · 4 · 3 = 48. 

Ответ: 48. ◄

Множество из n элементов называется упорядоченным, если каждому его элементу поставлено в соответствие натуральное число от 1 до n.

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

► Например, из 4 элементов  ♦  ♥  ♣  ♠  можно составить следующие 24 перестановки:

 ◄ 

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

P₁ = 1;  P₂ = 2;  P₃ = 6;  P₄ = 24.

Вообще, число всевозможных перестановок из n элементов равно произведению всех натуральных чисел от 1 до n, то есть n! (читается "эн факториал"):

P_n = 1 · 2 · 3 · ... · (n –1) · n = n!.

Для  P_n  справедлива рекуррентная формула:

P_n = n · P_{n – 1} .

Значение факториала определено не только для натуральных чисел, но и для 0:

0! = 1.

► Например, сколькими способами 5 мальчиков и 5 девочек могут занять в театре места в одном ряду с 1-го по 10-е место, если никакие два мальчика и никакие две девочки не сидят рядом?

Возможны два случая с одинаковым количеством способов: 1) мальчики — на нечётных местах, девочки на чётных и 2) наоборот.

Рассмотрим первый случай. Мальчики по нечётным местам могут сесть

 P₅ = 120

способами. Столько способов и для девочек на чётных местах. Согласно правилу умножения, мальчики — на нечётных местах, девочки на чётных могут расположиться

120 · 120 = 14 400

способами. Значит, всего способов

14 400 + 14 400 = 28 800.

Ответ: 28 800.  ◄

Перестановкой с повторениями из n элементов, среди которых k разных, при этом насчитывается n₁ неразличимых элементов первого типа, n₂ неразличимых элементов второго типа и так далее, n_k неразличимых элементов k-го типа  (где n₁ + n₂ + … + n_k = n), называется любое расположение этих элементов по n различным местам.  

Число перестановок с повторениями длины n из k разных элементов, взятых соответственно по n₁, n₂, …, n_k раз каждый обозначается и вычисляется следующим образом:$$P_{n_1,n_2, ... , n_k}=\frac{n!}{n_1!n_2! ... n_k!}~.$$

► Например, сколько различных десятизначных чисел можно составить из цифр: 1, 2, 2, 3, 3, 3, 4, 4, 4, 4?

В данном случае: n = 10,  n₁ = 1,  n₂ = 2, n₃ = 3, n₄ = 4,$$P_{1, 2, 3, 4}=\frac{10!}{1!2! 3! 4!}=\frac{10!}{1!2! 3! 4!}=12~600.$$

Ответ: 12 600.  ◄ 

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

Два размещения из n элементов по m считаются различными, если они различаются самими элементами или порядком их расположения.

► Например, составим все размещения из четырёх элементов  A, B, C, D  по два элемента:

A B;       A C;       A D;

B A;       B C;       B D;

C A;       C В;       C D;

D A;       D В;       D C.

 ◄                   

Число всех размещений из n элементов по m обозначают \(A_n^m\) (читается: "А из n по m") и вычисляется по любой из формул:$$A_n^m=n\cdot (n-1)\cdot (n-2)\cdot ...\cdot (n-m+1)\\A_n^m=\frac{n!}{(n-m)!}$$

► Примеры задач.

1) Воспользуемся понятием размещений из n элементов по m для решения задачи, уже дважды рассмотренной ранее: Сколько трёхзначных чисел можно составить из цифр 0, 2, 4, 6, 8, используя в записи числа каждую из них не более одного раза?

III способ.

Первую цифру можно выбрать четырьмя способами из набора 2, 4, 6, 8. В каждом из этих случаев количество пар второй и третей цифры равно числу размещений из 4 оставшихся цифр по 2. Значит искомое количество трёхзначных чисел равно:$$4\cdot A_4^2=4\cdot \frac{4!}{(4-2)!}=4\cdot \frac{4!}{2!}=4\cdot (3\cdot 4)=48.$$Ответ: 48. 

2) Для полёта в космос необходимо укомплектовать экипаж из шести человек. В него должны входить: командир корабля, первый и второй его помощники, два бортинженера, один из которых старший, и один врач. Командный состав выбирается из 20 лётчиков, бортинженеры — из 15 специалистов, а врач — из 5 медиков. Сколькими способами можно укомплектовать экипаж?

Поскольку в выборе командного состава важен порядок, то командира и двух его помощников можно выбрать \(A_{20}^3\) способами. Порядок бортинженеров тоже важен, значит, для их выбора существует \(A_{15}^2\) способов. Врач всего один, для его выбора существует 5 способов. Воспользуемся комбинаторным правилом умножения и найдём количество возможных экипажей корабля:$$A_{20}^3\cdot A_{15}^2\cdot 5=\frac{20!}{17!}\cdot \frac{15!}{13!}\cdot 5=(18\cdot 19\cdot 20)\cdot (14\cdot 15)\cdot 5=7~182~000.$$Ответ: 7 182 000. ◄  

Понятно, что, если m = n, то$$A_n^m=A_n^n=P_n=n!.$$

Справедливо также, что, если m = n – 1, то$$A_n^{n-1}=A_n^n=P_n=n!.$$

Помимо обычных размещений бывают и размещения с повторениями или выборки с возвращением. 

Пусть имеется n различных объектов. Выберем из них m штук, действуя по следующему принципу. Возьмём любой, но не будем его устанавливать в какой-то ряд, а просто запишем под номером 1 его название, сам же объект после этого вернём к остальным. Затем опять из всех n объектов выберем один (в том числе, возможно, и тот, который был только что взят), запишем его название, пометив номером 2, и снова вернём объект обратно. И так далее, пока не получим m названий. 

Размещения с повторениями обозначаются \(\overline{A}_n^m\) и, согласно правилу умножения, вычисляются по формуле$$\overline{A}_n^m=n^m.$$Заметим, что здесь допустим случай, когда m > n, то есть выбранных объектов больше, чем их всего имеется. Это неудивительно: каждый объект после "использования" возвращается обратно и может быть использован повторно.

► Например, количество вариантов шестизначного пароля, в котором каждый знак является цифрой от 0 до 9 или буквой латинского алфавита (одна и та же строчная и прописная буква — один символ) и может повторяться, равно:$$\overline{A}_{10+26}^6=\overline{A}_{36}^6=36^6=2~176~782~336.$$Если же строчные и прописные буквы считаются различными символами (как это обычно и бывает), то количество возможных паролей становится ещё более колоссальным:$$\overline{A}_{10+26+26}^6=\overline{A}_{62}^6=62^6=56~800~235~584.$$

◄                

Сочетанием из n элементов по m (m ≤ n) называется любое множество, состоящее из m элементов, выбранных из данных n элементов.

В отличии от размещений в сочетаниях не имеет значения, в каком порядке указаны элементы. Два сочетания из n элементов по m считаются различными, если они различаются хотя бы одним элементом.

► Например, составим все сочетания из четырёх элементов  A, B, C, D  по два элемента:

A B;       A C;       A D;

B C;       B D;

C D.

 ◄  

Число всех сочетаний из n элементов по m обозначают \(C_n^m\) (читается: "C из n по m") и вычисляется по любой из формул:$$C_n^m=\frac{A_n^m}{P_m}$$$$C_n^m=\frac{n\cdot (n-1)\cdot (n-2)~\cdot~ ...~\cdot~ (n-m+1)}{1\cdot2\cdot3~\cdot~...~\cdot ~m}$$$$C_n^m=\frac{n!}{m!\cdot (n-m)!}.$$

► Примеры задач. 

1) Бригада, занимающаяся ремонтом школы, состоит из 12 маляров и 5 плотников. Из них для ремонта физкультурного зала надо выделить 4 маляров и 2 плотников. Сколькими способами можно это сделать?

Так как порядок маляров в каждой выбранной четвёрке и порядок плотников в каждой выбранной паре не имеет значения, то, согласно комбинаторному правилу умножения, искомое количество способов равно:$$C_{12}^4 \cdot C_5^2 =\frac{12!}{4!\cdot 8!}\cdot \frac{5!}{2!\cdot 3!}=\frac{9\cdot10\cdot11\cdot12}{1\cdot2\cdot3\cdot4}\cdot \frac{4\cdot5}{1\cdot 2}=4~950.$$Ответ: 4 950. ◄

2) В классе обучаются 30 учащихся, среди которых 13 мальчиков и 17 девочек. Сколькими способами можно сформировать команду из 7 учащихся этого класса, если в неё должна входить хотя бы одна девочка?

Количество всех возможных команд по 7 человек из класса равно \(C_{30}^7\). Количество команд в которых только мальчики — \(C_{13}^7\). Значит, количество команд, в которых есть хотя бы одна девочка, равно:$$C_{30}^7 - C_{13}^7 =\frac{30!}{7!\cdot 23!} - \frac{13!}{7!\cdot 6!}=2~035~800-1~716=2~034~084.$$Ответ: 2 034 084. ◄

Помимо обычных сочетаний рассматривают сочетания с повторениями. 

Пусть в множестве имеется n объектов. Выберем из них m штук, действуя по следующему принципу. Возьмём любой, но не будем его устанавливать в какой-то ряд, а просто запишем, сам же объект после этого вернём к остальным. Затем опять из всех n объектов выберем один (в том числе, возможно, и тот, который был взят и записан ранее), запишем его название и снова вернём объект обратно. И так далее, пока не получим m названий.

Принципиальное отличие от размещений с повторениями заключается в том, что в данном случае элементы списка не нумеруются. Например, список "A, С, A, В" и список "А, А, В, С" считаются одинаковыми. 

Сочетания с повторениями обозначаются \(\overline{C}_n^m\) и вычисляются по формуле$$\overline{C}_n^m=P_{m,~n-1}=\frac{(m+n-1)!}{m!\cdot (n-1)!}.$$И ещё один способ записи той же формулы:$$\overline{C}_n^m=C_{m+n-1}^m=\frac{(m+n-1)!}{m!\cdot (n-1)!}.$$Заметим, что подобно размещениям с повторениями, допустим случай, когда m > n, то есть выбранных объектов больше, чем их всего имеется. Действительно, каждый объект после "использования" возвращается обратно и может быть использован снова и снова.

► Например, выясним сколькими способами можно купить 7 пирожных в кондитерском отделе, если в продаже 4 их сорта?

Естественно полагать, что количество пирожных каждого вида не меньше 7, и при желании можно купить только пирожные одного из них. Так как порядок в котором кладут купленные пирожные в коробку не важен, то имеем дело с сочетаниями с повторениями. Так как нужно выбрать 7 пирожных из 4 его видов, то искомое количество способов равно:$$\overline{C}_4^7=\frac{(7+4-1)!}{7!\cdot (4-1)!}=\frac{10!}{7!\cdot 3!}=\frac{8\cdot 9\cdot 10}{1\cdot 2\cdot 3}=120.$$

Ответ: 120.  ◄

Равенство$$(x+a)^n=C_n^0x^na^0+C_n^1x^{n-1}a^1+...+C_n^mx^{n-m}a^m+...+C_n^nx^0a^n$$называют биномом Ньютона или формулой Ньютона. Правая часть равенства называется биномиальным разложением в сумму, а коэффициенты \(C_n^0,~C_n^1,~...~,~C_n^n\) — биномиальными коэффициентами. 

Свойства биномиальных коэффициентов:

\(~~~~~~~~1.~~C_n^0=C_n^n=1\\ ~~~~~~~~2.~~C_n^m=C_n^{n-m}\\ ~~~~~~~~3.~~C_n^m=C_{n-1}^{m-1}+C_{n-1}^{m}\\ ~~~~~~~~4.~~C_n^0+C_n^1+C_n^2+~...~+C_n^n=2^n\\ ~~~~~~~~5.~~C_n^0+C_n^2+C_n^4+~... =C_n^1+C_n^3+C_n^5+~...=2^{n-1}\\ ~~~~~~~~6.~~C_n^n+C_{n+1}^n+C_{n+2}^n+~...~+C_{n+m-1}^n=C_{n+m}^{n+1}\\ \)

Свойства биномиального разложения:

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

 то есть равно  n + 1.

2.  Сумма показателей степеней x и a каждого члена разложения равна показателю степени бинома,

 то есть  (n – m) + m = n.  

3.  Общий член разложения (обозначается T_n+1) имеет вид$$T_{n+1}=C_n^m x^{n-m}a^m,~~~~m=0,~1,~2,~...~,~n.$$

Все возможные значения биномиальных коэффициентов (числа сочетаний) для каждого показателя степени бинома n можно записать в виде бесконечной треугольной таблицы. Такая таблица называется треугольником Паскаля:

В этом треугольнике крайние числа в каждой строке равны 1. Действительно, \(C_n^0=C_n^n=1\). А каждое не крайнее число равно сумме двух чисел предыдущей строки, стоящих над ним: \(C_n^m=C_{n-1}^{m-1}+C_{n-1}^{m}\). 

Таким образом, этот треугольник предлагает ещё один (рекуррентный) способ вычисления чисел  \(C_n^m\):

В k-й строке таблицы Паскаля записан набор коэффициентов, соответствующий биному с показателем степени n = k – 1.

► Например, в шестой строке записаны коэффициенты для разложения в сумму (x + a)⁵. С учётом свойств биномиального разложения и набора биномиальных коэффициентов из треугольника Паскаля запишем:$$(x+a)^5=x^5+5x^4a+10x^3a^2+10x^2a^3+5xa^4+a^5.$$

◄                  

Обозначения и сокращения

Таблицы чисел

Алгебраические тождества

Степени

Арифметический корень n-й степени

Логарифмы

Графики элементарных функций

Построение графиков функций геометрическими методами

Тригонометрия

Арифметическая и геометрическая прогрессии

Таблицы значений тригонометрических функций

Предел и непрерывность функции

Производная

Первообразная и интегралы

Теория вероятностей

Треугольники

Четырёхугольники

Многоугольники

Окружность

Площади геометрических фигур

Прямые и плоскости

Многогранники

Тела вращения

Декартова система координат