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

Определение. Перестановка с повторениями, состоящая из элементов, содержит одинаковых элементов 1-го вида, одинаковых элементов 2-го вида,…, одинаковых элементов - го вида,

Число различных перестановок с повторениями обозначим символом Построим расчетную формулу.

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

Ø выбрать мест из имеющихся для элементов 1-го вида ( способов);

Ø выбрать мест из имеющихся для элементов 2-го вида ( способов);

Ø ……………………………………………………………;

Ø выбрать мест из , оставшихся для элементов -го вида ( способ);

По принципу умножения

(2.7)

Пример 2.3.4. Последовательность 112314123 – это перестановка с повторениями, содержащая единицы; двойки; тройки и четверку,

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

Пример 2.3.5. Сколько чисел, больших 3000000, можно составить из цифр 3, 2, 2, 1, 1, 1, 0.

Решение. На первом месте обязательно должна стоять тройка. Оставшиеся 6 цифр образуют перестановку, в которой повторяются двойки; единицы и ноль. Всего таких перестановок

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

Пример 2.3.6. Располагая тремя цифрами 1, 2, 3, составить из них всевозможные сочетания с повторениями, содержащие по 2 элемента.

Решение. Перечислим такие сочетания: (1,1); (1,2); (1,3); (2,2); (2,3); (3,3). Подчеркнем, что (1,2) и (2,1) – это одно и то же сочетание, но – два разных размещения.

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

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

Пусть оно содержит элементов 1-го типа; 2-го типа;… -го типа,

Закодируем каждое сочетание с повторениями последовательностью из нулей и единиц, устроенной так. Сначала запишем единиц, потом запишем 0. Затем запишем единиц и 0,…. Наконец, запишем единиц. Всего последовательность содержит единиц и нулей.

В случае примера 3 и каждая последовательность содержит 2 единицы и 2 нуля.

Запишем последовательности, соответствующие каждому из 6 сочетаний с повторениями: (1, 1) – 1100; (1,2) – 1010; (1,3) –1001; (2,2) – 0110; (2,3) – 0101; (3,3) –0011.

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

Для примера 3: Итак,

(2.8)

Пример 2.3.7. Число неотрицательных целых решений уравнения равно , ведь всякое решение данного уравнения можно трактовать как сочетание с повторениями, содержащее элементов первого типа ( элементов второго типа ( …, элементов -го типа (

При решении практических задач также может быть использована

Теорема 1.Число разбиений n одинаковых объектов на k множеств, где , равно .