-
Перебор вариантов
Как кодировать комбинации
-
Правило умножения
Как считать комбинации без перебора
-
Правило деления
Как учесть беспорядок
-
Метод перегородок
Как вычислить число разбиений
-
Размещения и сочетания
Как систематизировать выборки
-
Треугольник Паскаля
Как вывести свойства числа сочетаний
-
Бином Ньютона
Как раскрывать скобочки
Комбинаторика
Как считать комбинации
Правило умножения
Перебор по возрастанию хорошо работает, если нужно подсчитать сравнительно небольшое число комбинаций. Как же быть, если возможных случаев, например, более ста? Попробуем ответить на этот вопрос, рассмотрев следующую задачу.
Бросают два игральных кубика, белый и черный. На каждом из них может выпасть число от $1$ до $6$. Сколько различных комбинаций может выпасть на этих кубиках?
Решение
Составим таблицу. По строкам будем отмечать число, которое может выпасть на белом кубике, по столбцам — на черном кубике.
| 1 | 2 | 3 | 4 | 5 | 6 | |
|---|---|---|---|---|---|---|
| 1 | 11 | 12 | 13 | 14 | 15 | 16 |
| 2 | 21 | 22 | 23 | 24 | 25 | 26 |
| 3 | 31 | 32 | 33 | 34 | 35 | 36 |
| 4 | 41 | 42 | 43 | 44 | 45 | 46 |
| 5 | 51 | 52 | 53 | 54 | 55 | 56 |
| 6 | 61 | 62 | 63 | 64 | 65 | 66 |
Из таблицы видно, что всего есть $36$ различных комбинаций. Мы хотели избежать перебора. Для этого можно определить размер таблицы, не заполняя ее. В таблице шесть строк и шесть столбцов, следовательно, ее размер равен $6 \cdot 6 = 36$.
Ответ: $36$.
Попробуем решить следующую задачу, не рисуя таблицу.
Назовем натуральное число скромным, если оно состоит только из цифр, меньших $3$. Сколько существует двузначных скромных чисел?
Решение
По условию в разряде десятков у скромного числа могут стоять две цифры: $1$ или $2$. В разряде единиц — три: $0$, $1$ или $2$. Мы можем мысленно составить таблицу, в которой по столбцам будут стоять цифры разряда десятков, а по строкам — цифры разряда единиц. Размер этой таблицы $2 \cdot 3 = 6$. Следовательно, скромных чисел ровно $6$.
Ответ: $6$.
Как решить предыдущую задачу для трехзначных чисел? Можно представлять себе трехмерную таблицу $2 \times 3 \times 3$, но мы поступим по-другому для большей наглядности.
Назовем натуральное число скромным, если оно состоит только из цифр, меньших $3$. Сколько существует трехзначных скромных чисел?
Решение
По условию в разряде сотен у скромного числа могут стоять две цифры: $1$ или $2$. В разрядах десятков и единиц — по три цифры: $0$, $1$ или $2$. Зарисуем наши наблюдения в виде дерева выбора.
Первую цифру мы ставим двумя способами. Каждому варианту первой цифры соответствует три варианта поставить вторую цифру. Далее каждой паре первых двух цифр соответствует еще три варианта третьей цифры. Таким образом, количество вариантов изначально было равно двум, а потом утроилось дважды. Итак, общее число скромных трехзначных чисел равно $$2 \cdot 3 \cdot 3 = 18.$$
Ответ: $18$.
Сформулируем правило умножения для выбора упорядоченной пары. Слово "упорядоченной" означает, что пары, отличающиеся только порядком, например, $\{1,\ 2\}$ и $\{2,\ 1\}$, мы будем считать различными.
Рассмотрим еще несколько важных примеров. Сколькими способами можно выбрать три человека из четырех и разместить их в очереди? Для удобства введем обозначения. "Людьми" у нас будут цифры, а "очередью" — упорядоченный набор из трех цифр без повторений. В этих терминах нашу задачу можно сформулировать так.
Сколько различных упорядоченных наборов из трех цифр можно составить, используя без повторений цифры $1$, $2$, $3$, $4$?
Решение
Чтобы прочувствовать, что от нас требуется, решим эту задачу перебором по возрастанию, а после проанализируем результат. Итак, выпишем все подходящие варианты:
| $123$ | $124$ | $132$ | $134$ | $141$ | $142$ |
| $213$ | $214$ | $231$ | $234$ | $241$ | $243$ |
| $312$ | $314$ | $321$ | $324$ | $341$ | $342$ |
| $412$ | $413$ | $421$ | $423$ | $431$ | $432$ |
Получилось $24$ набора. В первой строке стоят наборы, начинающиеся с $1$, во второй — c $2$, в третьей — с $3$, в четвертой — c $4$. Таким образом, на первую позицию в наборе можно разместить любую из четырех доступных цифр. Рассмотрим, например, первую строку. На второй позиции стоит $2$, $3$ или $4$, то есть какая-то из оставшихся трех цифр. Пусть, например, на второй позиции стоит $2$. Тогда для третьей позиции у нас остается всего два варианта: либо $3$, либо $4$. По правилу умножения искомое количество наборов равно $$4 \cdot 3 \cdot 2 = 24.$$
Ответ: $24$.
Посмотрим на ту же задачу под другим углом.
Сколько различных трехзначных чисел без повторяющихся цифр можно составить, используя цифры $1$, $2$, $3$, $4$, $5$?
Решение
На первую позицию можно разместить любую из пяти доступных цифр, на вторую позицию — любую из четырех оставшихся цифр, на третью позицию претендуют только оставшиеся три цифры. Получаем ответ $$5 \cdot 4 \cdot 3 = 60.$$
Ответ: $60$.
Обратите внимание на важный случай, когда нужно использовать все данные элементы, переставляя их местами. Следующий пример показывает, как найти число перестановок из четырех цифр.
Сколько различных четырехзначных чисел можно составить, используя без повторений цифры $1$, $2$, $3$, $4$?
Решение
На первую позицию можно поставить любую из четырех цифр, на вторую — любую из трех оставшихся, на третью позицию остаются две цифры, последняя цифра в нашем числе определяется однозначно. Итак, $$ 4 \cdot 3 \cdot 2 \cdot 1 = 24. $$
Ответ: $24$.
Рассмотрим задачу составления числа без ограничения на повторение цифр.
Сколько различных трехзначных чисел можно составить, используя цифры $1$, $2$, $3$, $4$, если цифры могут повторяться?
Решение
Попробуем определить общую закономерность. На первую позицию можно разместить любую из четырех данных цифр, на вторую — снова любую из четырех цифр, так как цифры теперь могут повторяться. И на третью позицию снова множно разместить любую из цифр $1$, $2$, $3$, $4$. Получаем, что искомое число равно $$4 \cdot 4 \cdot 4 = 4^3 = 64.$$
Ответ: $64$.
Задачи
От туристической базы на вершину горы ведут пять дорог. Сколько существует маршрутов от базы до вершины и обратно?
Решение.
Подняться на вершину горы можно по любой из пяти дорог, спуститься с горы — тоже по любой из пяти дорог. По правилу умножения получаем, что число маршрутов равно $$5 \cdot 5 = 25.$$
Ответ: $25$.
Монетку бросают трижды. Сколько последовательностей орлов и решек можно при этом получить?
Решение.
Каждое из трех подбрасываний может окончится двумя результатами: выпадением орла или решки. По правилу умножения получаем, что число последовательностей орлов и решек равно $$2 \cdot 2 \cdot 2 = 8.$$
Ответ: $8$.
У ковбоя есть четыре седла, пять уздечек и три попоны. Сколькими способами он может экипировать лошадь?
Решение.
Седло можно выбрать четырьмя способами, уздечку — пятью способами, попону — тремя способами. По правилу умножения получаем, что число экипировок равно $$4 \cdot 5 \cdot 3 = 60.$$
Ответ: $60$.
Автобусу, в котором находится три пассажира, предстоит сделать пять остановок. Сколькими способами могут выйти пассажиры на этих остановках?
Решение.
Каждый из пассажиров может выйти на любой из пяти остановок. По правилу умножения получаем, что искомое число способов равно $$5 \cdot 5 \cdot 5 = 125.$$
Ответ: $125$.
В пассажирском поезде пять вагонов. Сколькими способами можно рассадить в поезде четыре человека при условии, что все они должны ехать в различных вагонах?
Решение.
Первый человек может сесть в любой из пяти вагонов. Второй — в любой из четырех оставшихся (по условию мы не можем посадить двух людей в один вагон). Третьему остается выбор из трех вагонов. Последний выбирает любой из двух оставшихся вагонов. По правилу умножения получаем, что искомое число способов равно $$5 \cdot 4 \cdot 3 \cdot 2 = 120.$$
Ответ: $120$.
В мешке лежит три шара с номерами $1$, $2$ и $3$. Шар достают, записывают его номер и возвращают обратно в мешок. Так повторяют три раза. Сколько различных записей может получиться? Записи $123$ и $321$ будем считать разными.
Решение.
Запись представляет собой трехзначное число. На каждой позиции у него может стоять любая из цифр $1$, $2$, $3$. По правилу умножения получаем, что число таких записей равно $$3 \cdot 3 \cdot 3 = 27.$$
Ответ: $27$.
Фокусник взял из колоды четыре туза и случайным образом выдает по одному тузу каждому из трех зрителей. Сколькими способами он может это сделать?
Решение.
Первому зрителю может достаться любой из четырех тузов, второму зрителю — любой из трех оставшихся, третьему зрителю — любой из двух оставшихся. По правилу произведения получем $$4 \cdot 3 \cdot 2 = 24.$$
Ответ: $24$.
На глобусе проведены $17$ параллелей и $24$ меридиана. На сколько частей разделена поверхность глобуса?
Решение.
Проведя первую параллель, мы разделим глобус на две части. Проведя вторую параллель — уже на три части. $17$ параллелей разделят глобус на $18$ частей. Если теперь провести первый меридиан, то количество частей не изменится (меридиан идет от Северного полюса к Южному). Проведем второй меридиан, он "отрежет" нам еще $18$ частей. Всего частей станет $2 \cdot 18 = 32$. Каждый следующий меридиан будет "отрезать" дополнительно $18$ частей. Так как меридианов всего $24$, по правилу умножения получаем, что количество частей равно $$18 \cdot 24 = 432.$$
Ответ: $432$.
У Васи дома живут четыре кота. Сколькими способами можно рассадить котов по углам комнаты так, чтобы в каждом углу сидело по коту?
Решение.
Первого кота можно посадить в любой из четырех углов. Второго кота — в любой из трех оставшихся. Третьему коту остается выбрать любой из двух оставшихся углов. Четвертый кот садится в последний незанятый угол. По правилу умножения получаем, что количество способов рассадки котов равно $$4 \cdot 3 \cdot 2 \cdot 1 = 24.$$
Ответ: $24$.
Сколько существует кодов из трех цифр, в которых никакие две одинаковые цифры не стоят рядом?
Решение.
На первое место в коде можно поставить любую из десяти цифр. На второе место можно поставить уже только девять цифр, так как одинаковые цифры не должны стоять рядом. На третье место по этой же причине можно поставить только девять цифр. По правилу умножения получаем, что количество таких кодов равно $$10 \cdot 9 \cdot 9 = 810.$$
Ответ: $810$.
На полке стоят три книги. Сколькими способами можно выложить в стопку несколько из них, если стопка может состоять и из одной книги?
Решение.
Стопку из одной книги можно выложить тремя способами. Подсчитаем число стопок из двух книг: внизу стопки может лежать любая из трех книг, а наверху — любая из двух оставшихся книг. По правилу умножения количество стопок из двух книг равно $3 \cdot 2 = 6$. Аналогично подсчитаем количество различных стопок из трех книг: $3 \cdot 2 \cdot 1 = 6$. Значит, общее количество стопок равно $$3 + 6 + 6 = 15.$$
Ответ: $15$.
Словом назовем любую комбинацию букв. Порядок букв имеет значение, то есть слова "аб" и "ба" будем считать различными. Сколько различных слов можно составить, переставляя буквы в слове "жираф"?
Решение.
Заметим, что повторяющихся букв в слове "жираф" нет. На первом месте в нашем слове может стоять любая из пяти букв, на втором — любая из четырех оставшихся, на третье место можно поставить любую из трех оставшихся букв. На четвертое место остается выбор из двух букв, последняя буква определяется однозначно. По правилу умножения получаем, что число перестановок букв в слове "жираф" равно $$5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 120.$$
Ответ: $120$.
Код от сейфа состоит только из цифр. Вору известно, что код состоит либо из трех, либо из четырех символов. Сколько попыток нужно вору, чтобы точно угадать код?
Решение.
По правилу умножения количество кодов из трех цифр равно $10 \cdot 10 \cdot 10 = 1\ 000$. Количество кодов из четырех цифр равно $10 \cdot 10 \cdot 10 \cdot 10 = 10\ 000$. Следовательно, общее число кодов составляет $$1\ 000 + 10\ 000 = 11\ 000.$$
Ответ: $11\ 000$.
Сколько существует трехзначных чисел, в которых ровно две цифры — девятки?
Решение.
Чисел c двумя девятками вида $99*$ ровно девять, так как на последнем месте может стоять любая цифра, кроме $9$. Аналогично чисел вида $9*9$ тоже девять. А вот чисел вида $*99$ уже восемь, так как число не может начинаться с нуля. Получаем, что общее количество искомых чисел равно $$9 + 9 + 8 = 26.$$
Ответ: $26$.
Сколько существует трехзначных чисел, в которых хотя бы один ноль?
Решение.
Всего трехзначных чисел $9 \cdot 10 \cdot 10 = 900$, а чисел, в которых нет нулей, $9 \cdot 9 \cdot 9 = 729$. Следовательно, количество чисел, в которых есть хотя бы один ноль, равно $$900 - 729 = 171.$$
Ответ: $171$.
Сколько чисел, делящихся на $4$ и меньших $1\ 000$, можно составить из цифр $1$, $2$, $3$, $4$, $5$ (цифры могут повторияться)?
Решение.
Мы сможем составить только одно однозначное число, делящееся на четыре, это $4$. Выпишем по возрастанию все двузначные числа, которые мы можем составить согласно условию: $$12,\ 24,\ 32,\ 44,\ 52.$$ Теперь вспомним признак делимости на четыре: "Число делится на четыре, если число, образованное его последними двумя цифрами, делится на четыре". Если мы будем составлять трехзначное число, то на первом месте у него может стоять любая из пяти доступных цифр, а оканчиваться оно должно одной из пяти найденных нами комбинаций. По правилу умножения получаем, что трехзначных чисел, подходящих по условию, ровно $5 \cdot 5 = 25$. А значит, количество чисел, которое спрашивают в задаче, составляет $$1 + 5 + 25 = 31.$$
Ответ: $31$.
Сколькими способами можно поставить на шахматную доску белую и черную ладью так, чтобы они не били друг друга?
Решение.
Первую ладью можно поставить на любое из $64$ шахматных полей. Она занимает одно поле и бьет еще семь клеток по горизонтали и семь клеток по вертикали. Следовально, вторую ладью можно поставить на оставшиеся $64 - 1 - 7 - 7 = 49$ клеток. По правилу умножения получаем, что количество расстановок ладей равно $$64 \cdot 49 = 3\ 136.$$
Ответ: $3\ 136$.
Сколькими способами можно поставить на шахматную доску белого и черного королей так, чтобы получилась допустимая правилами игры позиция?
Решение.
Поставим белого короля в угол ($4$ варианта). Он занимает одно поле и бьет три поля. В этом случае черного короля можно поставить на $64 - 1 - 3 = 60$ полей. По правилу умножения всего расстановок с белым королем на угловой клетке $$4 \cdot 60 = 240.$$ Теперь поставим белого короля на край доски, но не в угол ($24$ варианта). Он занимает одно поле и бьет пять полей. В этом случае черного короля можно поставить на $64 - 1 - 5 = 58$ полей. По правилу умножения всего расстановок с белым королем на краю доски $$24 \cdot 58 = 1\ 392.$$ Наконец, поставим белого короля не на край доски (оставшиеся $36$ вариантов). Он занимает одно поле и бьет восемь полей. В этом случае черного короля можно поставить на $64 - 1 - 8 = 55$ полей. По правилу умножения всего расстановок с белым королем не на краю доски $$36 \cdot 55 = 1\ 980.$$ Получаем, что общее число расстановок двух королей на шахматной доске в игровой позиции равно $$240 + 1\ 392 + 1\ 980 = 3\ 612.$$
Ответ: $3\ 612$.