Сколько вариантов?

34

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

Разберем теперь несколько задач.

Задача 1. Сколько имеется четырехначную чисел, в десятичной записи которых все цифры различны?

Решение. Построение каждого четырехначного числа, удовлетворяющего условию задачи, можно разбит на четыре шага. На первом шага выбирается первая цифра числа. Такой выбор можно осуществить девятью способами (цифра 0 не может быть первой цифрой числа), так что в первой строке воображаемой схемы 9 цифр. На втором шага выбирается вторая цифра числа. Хотя выбор второй цифры зависит от выбора первой цифры (вторая цифра должна быть отлична от первой), но число возможностей выбора второй цифры, независимо от цифры, выбранной на первом шале, равно 9. Поэтому из каждой цифры первой строки воображаемой схемы выйдет 9 стрелок во вторую строку, в которой, следовательно, будет 9·9 цифр. На третьем шале выбирается третья цифра; так как она должна быть отлична от цифры, выбранных на первых двух шагах, независимо от решения, принятого нами на первых двух шагах, на третьем шале нам предоставляется выбор из возможностей. Следовательно, в третьей строке схемы будет 9·9·8 цифр. На четвертом шале мы можем выбирать любую из семи цифр, не используемых на первых трех шагах, и потому число цифр в нижней строке равно 9·9·8·7 = 4536. Так как число цифр в нижней строке равно, очевидно, числу путей из верхней строки в нижнюю, 4536 и есть требуемое число.

Упражнение 1. Сколько имеется четырехначных чисел, в десятичной записи которых все цифры различны?

Задача 2. Сколько различных натуральных делителей имеет число 2³·3¹⁰·7¹⁵·11⁹?

Решение. Ясно, что каждый делитель такого числа имеет вид

2ⁿ·3¹ⁿ·7ⁿ·11ⁿ, где 0≤k≤7, 0≤l≤10, 0≤m≤15, 0≤n≤9. Выбор каждого делителя может быть поэтому разбит на четыре шага: выбор k, выбор l, выбор m, выбор n. Так как первый шаг мы можем осуществить восемь способами, на втором шале, независимо от первых двух шагов, есть 16 возможностей и, наконец, независимо от первых трех шагов, мы можем десять способами осуществить четвертый шаг, расчудя так же, как и в предыдущих задачах, мы приdem к ответу 8·11·16·10=14080.

Аналогичные рассуждения приводят к общей формуле для числа делителя τ(n) натурального числа n, если известно разложение числа n на простые множители. Именно, если n=p₁^k₁·p₂^k₂·…·p₅^k₅, где p₁, p₂, …, p₅ — различные простые числа, k₁, k₂, …, k₅ — натуральные числа, то

τ(n)=(k₁+1)(k₂+1)…·(k₅+1).

Уражнение 2. Сколько различных натуральных делителей имеет число 20!=1·2·3·…·20?

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

Во всех разобранных задач подсчет числа интерсуцих нас предметов (варinian обеда, четырехначных чисел с неповторяющимся цифрами, делитель данного числа) производил по одному и той же схеме: мы представляли себе построение произвольного из перечисленных предметов в виде последовательности нескольких шагов, на каждом из которых число возможностей выбор легко находилось и не завиSEL от решения, принятых на предыдущих шагах. Произведение этих чисел и давало ответ задачи. Эти схемы решения приято называть «правилом произведение»:

Предположим, что нам нужно подсчитать количество предметов, удовлетворяющих некоторым условиям. Предположим, что построение произвольного такого предмета на несколько последовательных шагов, причем на первом шале у нас есть выбор из a₁ возможного

35

стей; независимо от результата первого шага, у нас есть $a_2$ различных возможностей на втором шале; независимо от результатов первых двух шагов, есть $a_3$ способов осуществления третьего шага и т. д.; наконец, независимо от решений, приятых на предыдущих шагах, у нас есть $a_n$ возможностей осуществления последнего шага. Тогда общее количество перечисленных предметов равно произведению $a_1 \cdot a_2 \cdot \dots \cdot a_n$.

У праванне 3. В номере автоматизиты стояят в начале три буквы русского алфавита (содержащого 33 буквы), а затем четыре цифры. Сколько можно составить различных номеров автоматизии?

У праванне 4. На рояле 88 клавиш. Сколько способами можно последовательно извлечь 6 звуков?

Разберем теперь несколько более трудную задачу.

Задача 3. Сколько имеется четырехзначных чисел, составленных из цифр 1, 3, 4, 6, 7, в записи каждого из которых соседние цифры различны?

Решение. Если на первом шале выбирать первый цифру такого числа, на втором шале — вторую цифру и т. д., то на первом шале у нас 5 возможностей, на втором и третьем шагах по 4 возможностей (на каждом из этих шагов мы можем выбирать любую цифру, кроме той, которая выбрана на предыдущем шале). Однако при осуществлении четверого шага число возможностей зависит от результата предыдущого шага: так как последняя цифра должна быть четной и отличной от предпоследней цифры, то мы имеем на последнем шале две возможности, если на третьем шале была выбрана одна из цифр 1, 3, 7, и одну возможность, если в качестве третьей цифры мы выбрали 4 или 6.

Выходит, что правило произведения к решению данной задачи не применимо? Этот вывод был прежде перегременным. Правило произведения не применимо из-за неудачного выбранной нами последовательности шагов построения четырехзначного числа с требуемыми свойствами. Если же мы на первом шале будем выбирать четверую цифру, а затем третью, вторую и третью, то у нас будет 2 возможности на первом шале и по 4 возможности на каждом из последующих шагов. По правилалу произведения искомое число четырехзначных чисел равно $2 \cdot 4^3 = 128$.

Искусство решения комбинаторов задач (так называют рассматриваемые нами задачи пересечета) в значительной степени состоит в умении выбрать последовательность шагов, приводяших к построению пересечиваемых предметов. Как правило, эту последовательность выбирают так, чтобы на первых шагах удовлетворить максимальным нулю числу ограничений, накладываемых условий задачи.

У праванне 5. Сколько имеется пятизначных чисел $n$, удовлетворяющих условия:

a) $n$ оканчивается двумя семерками;
b) $n$ начинается с двух одинаковых цифр;
b) все цифры числа $n$ различаны, причем вторая и четверняя цифры нечетны;
г) $n$ делится на 4, его соседние цифры различаны и отличны от 0, 4, 8?

У праванне 6*. На координатной плоскости рисунется всевозможные ломаны, все вершины которых имеют целые координаты, а звенья параллельны координатным осмам и не проходят дважды через одну вершину; $L_n$ — число ломанных, выходящих из начала координат и имеющих длину $n$. Докажите, что $4 \cdot 2^n \leq L_n \leq 4 \cdot 3^n$.

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

Начнем с такой задачи.

Задача 4. Сколько способами можно выписать в колонку фамилии 30 учеников?

Решение. Здесь последовательность шагов takes: сначала выбираем ученика на первое место, затем ученика на второе место и т. д. На первом шале у нас 30 возможностей, на втором — 29 возможностей, на третьем — 28 возможностей и т. д., наконец, на последнем, тридцатом шале у нас остается 1 возможность: запись ученика, чья фамилия не была написана ни на одном из 29 предыдущих шагов. Ответом задачи является, следовательно, число $30! = 30 \cdot 29 \cdot 28 \cdot \dots \cdot 3 \cdot 2 \cdot 1$.

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

36

Задание 5 (число перестановок из $n$ элементов). Сколькими способами можно упорядочить данные множества, состоящее из $n$ элементов?

Упорядочить множество — значит расположить его элементы в некотором порядке. Каждый такое расположение называют перестановкой данных множества. Таким образом, задачу можно сформулировать так: сколько существует перестановок множества из $n$ элементов? Рассуjdя так же, как и в задаче ссписком учеников (какый такой список — это перестановка множества учеников), мы получим, что число перестановок $n$-элементного множества равно $n! = 1 \cdot 2 \cdot 3 \cdot \dots \cdot n$.

Упражнение 7. Сколько существует перестановок цифр 0, 1, 2, …, 9, в которых цифра 0 занимает третье место, цифра 4 — пятое место, цифра 7 — седьмое место?

Упражнение 8. Сколькими способами можно расположить на шахматной доске 8 одинаковых ладьей так, чтобы никакие две из них не были друг друга?

Упражнение 9. Сколько существует перестановок цифр 0, 1, 2, …, 9, в которых цифра 6 следует непосредственно за цифрой 9?

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

Задание 6. Сколько существует перестановок цифр 0, 1, 2, …, 9, в которых цифра 0 занимает одно из первых четырех мест, а цифра 9 — одно из трех последних мест?

Решение. Построение произвольной такой перестановки разобем на три шага: выберем место для цифры 0 (первый шаг), выберем место для цифры 9 (второй шаг), расположим остальные восемь цифр на оставшихся восемми местах (третьий шаг). На первом шаг у нас 4 возможности; независимо от того, какую возможность мы изберем, у нас есть 3 возможности на втором шаг и, наконец, как бы мы ни расположили цифры 0 и 9, у нас будет 8! возможностей расположения остальных восемми цифр на восемми местах. Согласно правила произведения, число $4 \cdot 3 \cdot 8! = 12 \cdot 8!$ является решением задачи.

Как видите, на третьем шаг мы воспользовались решенной ранее задачей о числе перестановок восемми предметов. При решении комбинаторов задач на перебор вариантов есть возможность эффективно использовать накопленный опыт: любая решенная задача может помочь на одном из шагов в более сложной задаче.

Задание 7. Сколькими способами можно рассадить за 15 пар 15 мальчиков и 15 девочек так, чтобы за каждой парой следа мальчик, а справа — девочек?

Решение. Построение произвольного варианта рассадки разобем на два шага: рассадим 15 мальчиков на пятнадцатиных длинах местах, а затем рассадим 15 девочек на пятнадцатиных местах. На каждом шаг мы решаем задачу о перестановке пятнадцатиных собраня социненной так, чтобы тома каждой из собраней социненной стояли подряд, хотя и не обязательно в порядке следования томов?

Упражнение 10. Сколькими способами можно расположить на полке четыре десятитомных собраня социненной так, чтобы тома каждой из собраней социненной стояли подряд, хотя и не обязательно в порядке следования томов?

Упражнение 11. Сколько имеется перестановок цифр 0, 1, 2, …, 9, в которых между цифрами 2 и 3 стоит три другие цифры?

Число подмножества конечного множества

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

Выпишем все подмножества каждой из множества:

$A = \{a_1; a_2\}, B = \{a_1; a_2; a_3\},$
$C = \{a_1; a_2; a_3; a_4\}$.

Подмножества множества $A$:
$\emptyset, \{a_1\}, \{a_2\}, \{a_1; a_2\}$.

Подмножества множества $B$:
$\emptyset, \{a_1\}, \{a_2\}, \{a_3\}, \{a_1; a_2\},$
$\{a_1; a_3\}, \{a_2; a_3\}, \{a_1; a_2; a_3\}$.

Подмножества множества $C$:
$\emptyset, \{a_1\}, \{a_2\}, \{a_3\}, \{a_1; a_2\}, \{a_1; a_3\},$
$\{a_1; a_4\}, \{a_2; a_3\}, \{a_2; a_4\}, \{a_3; a_4\},$