Задание 8Комбинаторика

Аналитическая комбинаторика

Обновлено 11 сентября 2026 г.

Что такое комбинаторика Комбинаторика — раздел математики, посвящённый подсчёту количества различных объектов, способов выбора или вариантов расположения элементов. Главный вопрос большинства комбинаторных задач можно сформулировать следующим образом: Сколькими способами можно выполнить некоторое действие? Например: • сколькими способами можно выбрать трёх человек из десяти; • сколько различных четырёхзначных чисел можно составить из заданных цифр; • сколько существует способов расположить книги на полке; • сколько различных паролей заданной длины можно создать; • сколько существует маршрутов, удовлетворяющих определённым условиям. При решении комбинаторных задач важно определить, имеет ли значение порядок элементов и разрешено ли использовать один и тот же элемент несколько раз. Именно эти два вопроса обычно позволяют определить, какую формулу необходимо использовать. Правило суммы Если некоторый объект можно выбрать первым способом в $n$ вариантах, а вторым способом — в $m$ вариантах, причём эти варианты не пересекаются, то общее количество способов равно $n+m.$

Это правило называется правилом суммы.

Например, в магазине имеется $5$ видов тетрадей и $7$ видов блокнотов. Необходимо купить либо одну тетрадь, либо один блокнот.

Количество вариантов:

5+7=12.

Следовательно, покупку можно совершить $12$ различными способами.

Правило суммы применяется в ситуациях, когда между вариантами используется логическое условие ``или''.

Правило произведения

Если первое действие можно выполнить $n$ способами, а после каждого из них второе действие можно выполнить $m$ способами, то последовательность этих двух действий можно выполнить

n \cdot m

способами.

Это называется правилом произведения.

Например, имеется $4$ футболки и $3$ пары брюк. Для каждого комплекта необходимо выбрать одну футболку и одну пару брюк.

Количество комплектов:

4 \cdot 3 = 12.

Если действий больше двух, правило применяется аналогично:

n_1 \cdot n_2 \cdot n_3 \cdots n_k.

Например, пароль состоит из трёх цифр. На каждой позиции может находиться любая цифра от $0$ до $9$ .

Для каждой позиции имеется $10$ вариантов, поэтому количество паролей равно

10 \cdot 10 \cdot 10 = 10^3 = 1000.

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

Факториал

В комбинаторике часто используется понятие факториала.

Факториалом натурального числа $n$ называется произведение всех натуральных чисел от $1$ до $n$ :

n! = 1 \cdot 2 \cdot 3 \cdots n.

Например,

5! = 1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 = 120.

Также по определению

0! = 1.

Несколько первых значений факториала:

1! = 1,

2! = 2,

3! = 6,

4! = 24,

5! = 120,

6! = 720.

Факториал особенно часто появляется в задачах, связанных с перестановками и выбором элементов.

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

Перестановкой из $n$ элементов называется расположение всех этих элементов в определённом порядке.

Количество перестановок из $n$ различных элементов обозначается $P_n$ и вычисляется по формуле

P_n = n!.

Рассмотрим пример.

Пусть имеются три книги: $A$ , $B$ и $C$ . Их можно расположить на полке следующими способами:

ABC,\quad ACB,\quad BAC,\quad BCA,\quad CAB,\quad CBA.

Всего получилось

3! = 6

вариантов.

Для пяти различных книг количество способов расположения будет равно

P_5 = 5! = 120.

Важно заметить, что при перестановках:

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

Размещения

Размещением из $n$ элементов по $k$ называется упорядоченный выбор $k$ различных элементов из $n$ .

Количество размещений обозначается $A_n^k$ и вычисляется по формуле

A_n^k = \frac{n!}{(n-k)!}.

Или эквивалентно:

A_n^k = n(n-1)(n-2)\cdots(n-k+1).

Например, из $10$ участников необходимо определить победителя, участника, занявшего второе место, и участника, занявшего третье место.

Для первого места существует $10$ вариантов, для второго — $9$ , для третьего — $8$ .

Поэтому

A_{10}^{3}=10\cdot9\cdot8=720.

То же самое можно получить по формуле:

A_{10}^{3} = \frac{10!}{(10-3)!} = \frac{10!}{7!} = 10\cdot9\cdot8 = 720.

Порядок здесь имеет принципиальное значение: результат, в котором Иван занял первое место, а Алексей второе, отличается от результата, в котором Алексей занял первое место, а Иван второе.

Сочетания

Сочетанием из $n$ элементов по $k$ называется выбор $k$ различных элементов из $n$ , при котором порядок выбранных элементов не имеет значения.

Количество сочетаний обозначается

C_n^k

и вычисляется по формуле

C_n^k = \frac{n!}{k!(n-k)!}.

Например, из $10$ учеников необходимо выбрать команду из $3$ человек.

В данном случае порядок выбора не имеет значения. Команда

\{\text{Анна, Иван, Олег}\}

является той же самой командой, что и

\{\text{Олег, Иван, Анна}\}.

Поэтому необходимо использовать сочетания:

C_{10}^{3} = \frac{10!}{3!7!}.

Сократим факториалы:

C_{10}^{3} = \frac{10\cdot9\cdot8}{3\cdot2\cdot1} = 120.

Следовательно, существует $120$ различных команд.

Разница между размещениями и сочетаниями

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

Главное отличие заключается в порядке элементов.

Если порядок имеет значение, используются размещения:

A_n^k = \frac{n!}{(n-k)!}.

Если порядок не имеет значения, используются сочетания:

C_n^k = \frac{n!}{k!(n-k)!}.

Например, выберем двух человек из десяти.

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

A_{10}^{2}=10\cdot9=90.

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

C_{10}^{2} = \frac{10\cdot9}{2} = 45.

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

Свойства сочетаний

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

Во-первых,

C_n^0 = C_n^n = 1.

Действительно, выбрать ноль элементов можно только одним способом — ничего не выбирать. Аналогично, выбрать все $n$ элементов также можно только одним способом.

Кроме того,

C_n^1=n.

Выбрать один элемент из $n$ можно $n$ способами.

Важное свойство симметрии:

C_n^k = C_n^{n-k}.

Например,

C_{10}^{3}=C_{10}^{7}.

Смысл этого равенства достаточно естественный: выбрать $3$ человека из $10$ — то же самое, что определить $7$ человек, которые не были выбраны.

Ещё одно важное равенство:

C_n^k = C_{n-1}^{k-1} + C_{n-1}^{k}.

Оно лежит в основе построения треугольника Паскаля.

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

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

\begin{array}{ccccccccc} &&&&1&&&&\\ &&&1&&1&&&\\ &&1&&2&&1&&\\ &1&&3&&3&&1&\\ 1&&4&&6&&4&&1 \end{array}

Строка с номером $n$ содержит значения

C_n^0,\ C_n^1,\ C_n^2,\ldots,C_n^n.

Например, для $n=4$ :

C_4^0=1,\quad C_4^1=4,\quad C_4^2=6,\quad C_4^3=4,\quad C_4^4=1.

Эти числа образуют строку

1,\ 4,\ 6,\ 4,\ 1.

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

Иногда один и тот же элемент можно использовать несколько раз.

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

n^k.

Это называется размещением с повторениями.

Например, рассмотрим четырёхзначный код, в котором каждая позиция может содержать одну из десяти цифр:

0,1,2,\ldots,9.

На каждой позиции имеется $10$ вариантов. Поэтому

10^4 = 10000.

Если запрещено начинать код с нуля, ситуация изменяется. Для первой позиции имеется $9$ вариантов, а для остальных трёх — по $10$ :

9\cdot10^3 = 9000.

Таким образом, перед применением формулы необходимо внимательно учитывать ограничения задачи.

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

Рассмотрим слово

\text{МАМА}.

В нём четыре буквы, однако две буквы М одинаковые и две буквы А также одинаковые.

Если считать все буквы различными, получилось бы

4! = 24

перестановки. Но перестановка двух одинаковых букв не создаёт нового слова.

Если среди $n$ элементов имеются группы одинаковых элементов численностью

n_1,n_2,\ldots,n_m,

где

n_1+n_2+\ldots+n_m=n,

то количество различных перестановок равно

P = \frac{n!} {n_1!n_2!\cdots n_m!}.

Для слова МАМА получаем

P= \frac{4!}{2!2!} = \frac{24}{4} = 6.

Следовательно, из букв слова МАМА можно составить $6$ различных последовательностей.

Рассмотрим другой пример: сколько различных перестановок можно получить из букв слова МАТЕМАТИКА?

Всего букв:

10.

Буква А встречается $3$ раза, буква М — $2$ раза, буква Т — $2$ раза. Остальные буквы встречаются по одному разу.

Следовательно,

P= \frac{10!}{3!2!2!}.

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

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

Например, имеется $5$ видов конфет. Необходимо выбрать $3$ конфеты, причём можно взять несколько конфет одного вида.

Количество таких способов вычисляется по формуле сочетаний с повторениями:

\overline{C}_n^k = C_{n+k-1}^{k}.

В нашем случае

\overline{C}_5^3 = C_{5+3-1}^{3} = C_7^3 = 35.

Следовательно, существует $35$ различных вариантов выбора.

Бином Ньютона

Формула сочетаний непосредственно связана с разложением степени суммы.

Бином Ньютона имеет вид

(a+b)^n = \sum_{k=0}^{n} C_n^k a^{n-k}b^k.

В развёрнутой форме:

(a+b)^n = C_n^0a^n + C_n^1a^{n-1}b + C_n^2a^{n-2}b^2 +\ldots+ C_n^nb^n.

Например,

(a+b)^3 = a^3+3a^2b+3ab^2+b^3.

Коэффициенты

1,\ 3,\ 3,\ 1

являются значениями

C_3^0,\ C_3^1,\ C_3^2,\ C_3^3.

Для четвёртой степени:

(a+b)^4 = a^4+4a^3b+6a^2b^2+4ab^3+b^4.

Коэффициенты

1,\ 4,\ 6,\ 4,\ 1

совпадают с соответствующей строкой треугольника Паскаля.

Подсчёт через дополнение

В некоторых задачах проще посчитать не количество подходящих вариантов, а количество неподходящих вариантов.

Если всего имеется $N$ вариантов, а условию не удовлетворяют $M$ вариантов, то количество подходящих вариантов равно

N-M.

Рассмотрим пример.

Сколько существует трёхзначных чисел, содержащих хотя бы одну цифру $7$ ?

Всего трёхзначных чисел:

999-100+1=900.

Теперь посчитаем количество трёхзначных чисел, в которых цифра $7$ отсутствует.

Первая цифра может принимать $8$ значений:

1,2,3,4,5,6,8,9.

Вторая и третья цифры могут принимать по $9$ значений: любую цифру кроме $7$ .

Следовательно,

8\cdot9\cdot9=648.

Тогда количество чисел, содержащих хотя бы одну семёрку:

900-648=252.

Такой способ особенно удобен в задачах, содержащих слова ``хотя бы один'', ``не менее одного'', ``есть хотя бы'' и похожие формулировки.

Принцип включения и исключения

Рассмотрим два множества $A$ и $B$ .

Если просто сложить количество элементов этих множеств,

|A|+|B|,

то элементы, входящие одновременно в $A$ и $B$ , будут посчитаны дважды.

Поэтому необходимо вычесть количество элементов пересечения:

|A\cup B| = |A|+|B|-|A\cap B|.

Это называется принципом включения и исключения.

Например, среди $100$ учеников $60$ изучают английский язык, $40$ — немецкий, а $20$ изучают оба языка.

Количество учеников, изучающих хотя бы один из двух языков:

60+40-20=80.

Если бы мы просто сложили $60+40$ , то $20$ учеников, изучающих оба языка, были бы посчитаны два раза.

Для трёх множеств формула имеет вид

|A\cup B\cup C| = |A|+|B|+|C| -|A\cap B| -|A\cap C| -|B\cap C| +|A\cap B\cap C|.

Комбинаторика и вероятность

Комбинаторика часто используется при вычислении вероятностей.

В классической модели вероятность события $A$ определяется формулой

P(A)=\frac{m}{n},

где $n$ — количество всех равновозможных исходов, а $m$ — количество исходов, благоприятных для события $A$ .

Например, из колоды в $36$ карт случайно выбирают одну карту. Найдём вероятность получить туза.

Всего карт:

n=36.

Тузов в колоде четыре:

m=4.

Поэтому

P(A) = \frac{4}{36} = \frac{1}{9}.

Теперь рассмотрим более сложный пример.

Из $10$ человек случайно выбирают команду из $3$ человек. Какова вероятность того, что два конкретных человека окажутся в этой команде?

Всего команд:

C_{10}^{3}.

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

C_8^1.

Следовательно,

P = \frac{C_8^1}{C_{10}^{3}} = \frac{8}{120} = \frac{1}{15}.

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

Как определить нужную формулу

При решении задачи полезно последовательно ответить на несколько вопросов.

1. Используются все элементы или только часть?

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

P_n=n!.

Если выбирается только часть элементов, необходимо определить значение порядка.

2. Имеет ли значение порядок?

Если порядок важен:

A_n^k=\frac{n!}{(n-k)!}.

Если порядок не важен:

C_n^k=\frac{n!}{k!(n-k)!}.

3. Разрешены ли повторения?

Если элементы могут повторяться и порядок важен:

n^k.

Если порядок не важен, но повторения разрешены:

\overline{C}_n^k=C_{n+k-1}^{k}.

Типичные ошибки

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

Игнорирование порядка

Например, выбор двух человек и назначение двух человек на разные должности — это разные задачи.

В первом случае:

C_n^2.

Во втором:

A_n^2.

Неправильный учёт повторений

При составлении чисел необходимо внимательно следить за тем, разрешено ли повторять цифры.

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

4^3=64.

Если повторения запрещены:

A_4^3 = 4\cdot3\cdot2 = 24.

Ноль на первой позиции

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

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

9\cdot10\cdot10\cdot10=9000,

а не

10^4.

Двойной подсчёт

Иногда один и тот же объект может быть получен несколькими способами. В таком случае простой подсчёт по правилу произведения может завышать ответ.

Именно поэтому при работе с неупорядоченными наборами часто появляется деление на факториал.

Например,

A_n^k

считает все возможные порядки выбранных $k$ элементов. Каждый набор из $k$ элементов учитывается

k!

раз.

Поэтому

C_n^k = \frac{A_n^k}{k!}.

Подставляя формулу размещений, получаем

C_n^k = \frac{n!}{k!(n-k)!}.

Пример комплексной задачи

Рассмотрим задачу.

Из $12$ учеников необходимо выбрать команду из $4$ человек и назначить одного из выбранных учеников капитаном.

Сначала выбираем команду:

C_{12}^{4}.

После этого из четырёх выбранных учеников выбираем капитана:

4.

По правилу произведения получаем

C_{12}^{4}\cdot4.

Вычислим:

C_{12}^{4} = \frac{12!}{4!8!} = \frac{12\cdot11\cdot10\cdot9} {4\cdot3\cdot2\cdot1} = 495.

Следовательно,

495\cdot4=1980.

Ответ:

\boxed{1980}.

Эту же задачу можно решить другим способом.

Сначала выберем капитана:

12

способами.

После этого необходимо выбрать ещё трёх участников из оставшихся $11$ :

C_{11}^{3}.

Получаем

12\cdot C_{11}^{3}.

Так как

C_{11}^{3}=165,

то

12\cdot165=1980.

Оба подхода дают одинаковый результат.

Итог

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

Перед использованием формулы необходимо определить:

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

Основные формулы комбинаторики можно свести к следующему набору:

P_n=n!,

A_n^k=\frac{n!}{(n-k)!},

C_n^k=\frac{n!}{k!(n-k)!},

\overline{A}_n^k=n^k,

\overline{C}_n^k=C_{n+k-1}^{k}.

Однако знание формул само по себе не гарантирует правильного решения. Важно понимать, что именно считается и когда два варианта считаются различными.

Если порядок объектов изменился и полученный результат считается новым — порядок важен. Если перестановка выбранных объектов ничего не меняет — порядок не важен.

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