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

В задачах по комбинаторике могут встретиться множества, в которых какие-либо компоненты повторяются. Например, в задачах о составлении числа из заданных цифр – цифры могут повторяться. Например, используя цифры 7, 4 и 5, можно образовать различные двузначные числа: 77, 74, 75, 47, 44, 45, 57, 54, 55. В записи этих чисел цифры повторяются.

С теоретико-множественной точки зрения запись любого двузначного числа – это кортеж длины 2. Записывая различные двузначные числа с помощью цифр 7, 4 и 5, мы по сути дела образовывали из данных 3 цифр различные кортежи длины 2 с повторяющимися элементами. В комбинаторике такие кортежи называют размещениями с повторениями из 3 элементов по 2.

Определение.Размещением с повторениями из k элементов по m элементов называют кортеж, составленный из m элементов k-элементного множества. Число всевозможных размещений с повторениями из k элементов по m элементов обозначают .

Из определения следует, что два размещения из k элементов по m элементов отличаются друг от друга либо составом элементов, либо порядком их расположения.

Например, два двузначных числа из перечисленных выше отличаются друг от друга либо составом элементов (77 и 75), либо порядком их расположения (74 и 47).

Относительно размещений часто возникает вопрос: «Сколько всевозможных размещений по m элементов каждое можно образовать из k элементов данного множества?»

Теорема 7.Число всевозможных размещений с повторениями из k элементов по m элементов подсчитывают по формуле: .

 Доказательствопроведем методом математической индукции по k, где k – число элементов в размещении при фиксированном значении т. Прежде всего заметим, что размещения с повторениями по k элементов могут быть получены из размещений по (k–1) элементу присоединением еще одного элемента. Так как к каждому размещению по (k–1) элементу можно присоединить любой из имеющихся т элементов, то каждое размещение по (k–1) элементу порождает т различных размещений по k элементов, то есть .

1. При k = 1 каждое размещение состоит только из одного элемента, а число элементов равно т, значит, и число размещений равно т. Итак, , что соответствует формуле.

2. Допустим, что для некоторого числа k равенство справедливо.

3. Найдем число размещений с повторениями из т элементов по k + 1. Пользуясь формулой ,

получаем: = т∙m =m .

Таким образом, доказываемая формула справедлива для k=1 и из ее справедливости для некоторого k следует и справедливость для (k+1). Теорема.  доказана.

С помощью этой формулы легко подсчитать, например, сколько двузначных чисел можно записать, используя цифры 7, 4 и 5. Так как речь идет о размещениях с повторениями из трех элементов по два, то .

Задача. Обезьяну посадили за пишущую машинку с 45 клавишами. Определите число попыток, необходимых для того, чтобы обезьяна напечатала первую строку романа Л.Н. Толстого «Анна Каренина», если строка содержит 52 знака?

Решение.В данной задаче имеет значение порядок следования букв. Буквы при этом могут повторяться.

Значит, всего есть (вариантов)

Ответ: 45⁵² вариантов.

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

Решение.Так как порядок следования цифр в числе существенен, цифры могут повторяться, то это размещения с повторениями из 5 элементов по 3, а их число равно  (чисел).

Ответ: 125 чисел.

Задача. Каждый телефонный номер состоит из семи цифр. Сколько всего телефонных номеров, не содержащих других цифр, кроме 2, 3, 5 и 7?

Решение.Эта задача о числе размещений на семи разных позициях семи цифр, выбранных из четырех различных цифр с повторениями каждой из них любое число раз, но не более семи, то есть о кортежах длины 7, составленных из элементов множества А, содержащего 4 элемента.

Поскольку = 4⁷ = 16 384, то число всех указанных номеров равно 16 384.

Ответ: 16384.

Определение. Набор из к элементов, составленный из повторяющихся элементов m элементного множества, называют сочетанием с повторениями из m по к.

Сочетание с повторениями из m элементов по к обозначают символом .

Теорема 9. Число всевозможных сочетаний с повторениями из к элементов по m элементов подсчитывают по формуле:

.

 Фактически нам надо выяснить, сколько различных составов могут иметь кортежи длины к из m элементов. Любой состав кортежа длины к из т элементов имеет вид (к₁, к ₂, к₃,... ,к_т), где к₁, к₂, ..., к_m – неотрицательные целые числа, сумма которых равна к. Заменяя каждое из чисел к_j (1<j<к) соответствующим количеством единиц и разделяя нулями единицы, отвечающие различным числам, получаем кортеж из (т –1) нулей и к единиц. При этом каждому составу отвечает одна и только одна запись с помощью нулей и единиц, а каждая такая запись задает один и только один состав. Поэтому число различных составов равно числу перестановок с повторениями из (т –1) нулей и к единиц, то есть

=Р(т–1,к)= .

Теорема доказана.

Задача. В кондитерском магазине продавались четыре сорта пирожных: эклеры, песочные, наполеоны и слоеные. Сколькими способами можно купить 7 пирожных?

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

 (способов)

Ответ: 120 способов.

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

Решение.Число костей домино можно рассматривать как число сочетаний с повторениями по два из десяти. Число таких сочетаний равно:

=С = =55(штук).

Ответ: 55 костей домино.