§ 7. Перестановки, размещения и сочетания с повторениями

Из букв з, а, м, о, к можно образовать различных слов – анаграмм (не все они имеют смысл). Сколько разных слов можно образовать из букв слова «ротор».

Мы имеем здесь дело с перестановками с повторениями.

Пусть даны п элементов k различных типов. Пусть первый элемент повторяется раз, второй раз,…, k–й повторяется раз

….

Если все элементы были бы различными, то мы имели бы n! перестановок.

Элементы а можно переставить способами, элементы b –– способами,…, элементы l – способами. Но от этого не изменится число перестановок с повторениями. Следовательно, число перестановок с повторениями меньше числа перестановок без повторения в раз. Таким образом, число перестановок с повторениями

.

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

Решение.

Пусть данное множество содержит n элементов. Попытаемся образовать размещения по k элементов с повторениями, т.е. в одном размещении тот же самый элемент может повториться 2, 3, …, k раз. Найдем число размещений с повторениями, которое обозначим .

Первый элемент какого–нибудь из отмеченных размещений мы можем выбрать n способами. Второй элемент тоже n способами, тогда пару элементов можно образовать способами. Третий элемент опять можем выбрать n способами, четвертый также и т.д. Таким образом, размещения из n элементов можем образовать способами. Значит,

.

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

Решение. Из цифр 0, 2 можем получить пятизначных чисел. Но числа, записанные пятью цифрами, первая из которых нуль, не являются пятизначными.

Их столько, сколько четырехзначных чисел можно составить из цифр 0, 2 при повторении цифр, т.е Поэтому ответ:

Составим выборки из элементов одного и того же множества и не отличаются по своему объему, но отличаются по составу (хотя бы одним элементом). Такие выборки называются сочетаниями с повторениями.

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

Таким образом,