В результате изучения этой темы читатель
узнает: формулировку понятия комбинаторного объекта, определение комбинаторного числа, формулировку комбинаторного правила умножения, формулировку комбинаторного правила сложения, методику использования комбинаторных принципов (правил);
научится: использовать комбинаторные правила умножения и сложения для решения практических задач по расчёту комбинаторного числа произвольного комбинаторного объекта.
Определение. Пусть S = {s1, . . . , sn} – множество из n элементов, тогда комбинаторным объектом называется подмножество множества S, обладающее заданными (определенными) свойствами.
Определение. Комбинаторным числом называется число комбинаторных объектов с заданными свойствами, т.е. мощность подмножества множества S.
При расчете комбинаторных чисел часто применяются два основных принципа: правило умножения и правило сложения.
Комбинаторное правило умножения.
Комбинаторное правило сложения.
В качестве Упражнения для самостоятельного решения рассмотрите следующее: пусть задано множество цифр Numeral = {a, b, c, d, f, g}, расшифровка цифр представлена в таблице ниже.
Сколько из этих цифр можно составить:
1) четырехзначных чисел;
2) четырехзначных чисел с различными цифрами;
3) нечетных четырехзначных чисел;
4) нечетных четырехзначных чисел с различными цифрами;
5) нечетных четырехзначных чисел, содержащих хотя бы две одинаковые цифры;
6) четных четырехзначных чисел;
7) четырехзначных чисел, составленных из нечетных цифр;
8) четырехзначных чисел, делящихся на 4;
9) четных четырехзначных чисел с различными цифрами;
10) четырехзначных чисел, делящихся на 4, с различными цифрами;
11) нечетных четырехзначных чисел, содержащих хотя бы две одинаковые цифры?
Пример выполнения практического задания (вариант № 30):
Рассмотрим множество Numeral = {0, 1, 2, 3, 4, 5}.
Для решения задания 1 следует выбрать четыре цифры из заданных шести. На первую позицию четырехзначного числа можно выбрать любую цифру, кроме нуля, т.е. имеется пять способов ее выбора. При любой цифре, расположившейся на первой позиции, на вторую позицию может претендовать любая из заданных шести цифр, т.е. 63 вариантов. Используя комбинаторное правило умножения, получаем общее число четырехзначных чисел, равное 5 × 63 = 1 080.
Для решения задания 2 следует отметить, что, как и в предыдущем варианте, цифру на первую позицию можно выбрать 5 способами, иначе четырехзначное число перестанет быть четырехзначным. Далее имеем, что при любом способе выбора цифры на вторую позицию можно поставить одну из пяти цифр, за исключением цифры, стоящей на первой позиции. Две следующие цифры можно выбрать соответственно четырьмя и тремя способами. Таким образом, получаем общее число четырехзначных чисел с различными цифрами, равное 5 × 5 × 4 × 3 = 300.
Для решения задания 3 следует отметить, что четыре цифры, начиная с первой, можно выбрать соответственно пятью (кроме нуля), шестью, шестью и тремя способами (в последнем случае выбранная цифра может одной из трех нечетных цифр: 1, 3, 5). Таким образом, получаем общее число нечетных четырехзначных чисел, равное 5 × 6 × 6 × 3 = 540.
Решение задания 4 начнем с последней цифры, поскольку налагаются условия, как на нечетность, так и на то, чтобы числа состояли из различных цифр. Итак, для последней позиции имеем выбор любой из трех нечетных цифр: 1, 3, 5, тогда цифрой на первой позиции может быть одна из четырех цифр (любая из заданных, кроме нуля и цифры, стоящей на последней позиции). Цифры для второй и третьей позиций можно выбрать соответственно четырьмя и тремя способами. Таким образом, получаем общее число нечетных четырехзначных числа с различными цифрами, равное 3 × 4 × 4 × 3 = 144.
Для решения задания 5 можно от общего числа нечетных четырехзначных чисел вычесть число нечетных четырехзначных чисел с различными цифрами (см. задания 3 и 4): 540 – 144 = 396.
Для решения задания 6 следует отметить, что четыре цифры, начиная с первой позиции, можно выбрать соответственно пятью (кроме нуля), шестью, шестью и тремя способами (в последнем случае выбранная цифра может одной из трех четных цифр: 0, 2, 4). Таким образом, получаем общее число четных четырехзначных чисел, равное 5 × 6 × 6 × 3 = 540.
Конечно, можно было воспользоваться тем, что общее число четырехзначных чисел включает в себя нечетные и четные четырехзначные числа, поэтому из задания 1 имеет общее число четырехзначных чисел, равное 1 080, а из задания 3 знаем общее число нечетных четырехзначных чисел, равное 540. Откуда оставшееся число 1 080 – 540 = 540 будет соответствовать общему числу четных четырехзначных чисел.
Для решения задания 7 следует воспользоваться комбинаторным правилом умножения и, учитывая, что среди заданных цифр имеются только три нечетных цифры (1, 3, 5), получим общее число четырехзначных чисел с нечетными цифрами, равное 3 × 3 × 3 × 3 = 34 = 81.
Для решения задания 8 следует использовать признак делимости на 4, который заключается в том, что на цифру 4 делятся те и только те числа,
в которых число, образованное двумя последними цифрами (в том же порядке), делится на 4. Определим перебором совокупность таких двузначных чисел: 00, 04, 12, 20, 24, 32, 40, 44, 52. Далее следует отметить, что в четырехзначном числе последние две цифры могут располагаться девятью способами, на первую же позицию четырехзначного числа можно выбрать любую цифру, кроме нуля, т.е. 5 вариантов, а на вторую позицию — шесть вариантов. Используя комбинаторное правило умножения, получаем общее число четырехзначных чисел, делящихся на 4, равное 9 × 5 × 6 = 270.
Для решения задания 9 следует отметить, что существует два различных случая: число заканчивается нулем или цифрой, отличной от нуля. Число четных четырехзначных чисел с различными цифрами, оканчивающихся нулем, равно 5 × 4 × 3 = 60, а число четных четырехзначных чисел оканчивающихся цифрой, отличной от нуля, равно 2 × 4 × 4 × 3 = 96.
Таким образом, получаем общее число четных четырехзначных чисел
с различными цифрами, равное 60 + 96 =156.
Для решения задания 10 следует обратить внимание на задание 8 текущего примера выполнения практического задания, где упомянут признак делимости на 4, а также приведены варианты для последних двух цифр, однако с учетом того, что в текущем задании повтор цифр недопустим, то варианты 00 и 44 отбрасываются, остаются следующие семь вариантов: 04, 12, 20, 24, 32, 40, 52. Из них в трех случаях имеется цифра нуль, в четырех — нет нуля. Таким образом, общее число четырехзначных чисел, делящихся на 4, с различными цифрами равно 3 × 4 × 3 + 4 × 3 × 3 = 72.
Для решения задания 11 рассмотрим несколько подмножеств.
Во-первых, подмножество нечетных четырехзначных чисел, не содержащих в записи нуль, у которых одна из двух одинаковых цифр располагается на последней позиции, число таких вариантов чисел равно 3 × 3 × 4 × 3 = 108.
Во-вторых, подмножество нечетных четырехзначных чисел, не содержащих в записи нуль, у которых одна из двух одинаковых цифр располагается не на последней позиции, при этом число таких вариантов чисел равно 3 × 4 × 3 × 3 = 108.
В-третьих, подмножество нечетных четырехзначных чисел, у которых одна из двух одинаковых цифр является цифрой нуль, число таких вариантов чисел равно 3 × 1 × 1 × 4 = 12.
В-четвертых, подмножество нечетных четырехзначных чисел, содержащих в записи цифру нуль, у которых одна из двух одинаковых цифр располагается не на последней позиции, число таких вариантов чисел равно 3 × 4 × 2 = 24.
В-пятых, подмножество нечетных четырехзначных чисел, не содержащих в записи цифру нуль, у которых одна из трех одинаковых цифр располагается на последней позиции, число таких вариантов чисел равно 3 × 3 × 4 = 36.
В-шестых, подмножество нечетных четырехзначных чисел, не содержащих в записи цифру нуль, у которых одна из трех одинаковых цифр не располагается на последней позиции, число таких вариантов чисел равно 3 × 4 × 1 = 12.
В-седьмых, подмножество нечетных четырехзначных чисел, содержащих в записи цифру нуль, у которых одна из двух одинаковых цифр располагается на последней позиции, число таких вариантов чисел равно 3 × 3 × 4 = 36.
В-восьмых, подмножество нечетных четырехзначных чисел, содержащих в записи цифру нуль, у которых одна из трех одинаковых цифр располагается на последней позиции, число таких вариантов чисел равно
3 × 2 = 6.
В-девятых, подмножество нечетных четырехзначных чисел, не содержащих в записи цифру нуль, у которых две пары одинаковых цифр, число таких вариантов чисел равно 3 × 3 × 4 = 36.
В-десятых, подмножество нечетных четырехзначных чисел, не содержащих в записи цифру нуль, у которых одна из трех одинаковых цифр не располагается на последней позиции, число таких вариантов чисел равно 3 × 4 = 12.
В-одиннадцатых, подмножество нечетных четырехзначных чисел, содержащих в записи цифру нуль, у которых две пары одинаковых цифр, число таких вариантов чисел равно трем.
В-двенадцатых, подмножество нечетных четырехзначных чисел, у которых четыре одинаковые цифры, число таких вариантов чисел равно трем.
Наконец, общее число нечетных трехзначных чисел, содержащих хотя бы две одинаковые цифры, равно 108 + 108 + 12 + 24 + 36 + 12 + 36 + 6 + 36 + 12 + 3 + 3 + 396.
