§ 7. Перестановки, размещения и сочетания с повторениями
Из букв з, а, м, о, к можно образовать различных слов – анаграмм (не все они имеют смысл). Сколько разных слов можно образовать из букв слова «ротор».
Столько же? Оказывается, нет! Только 30. Известная формула числа перестановок в рассматриваемом случае бессильна, так как элементы в «перестановках» повторяются. При перестановке в слове «ротор» местами букв о и р никаких изменений не происходит, остается то же самое слово.Мы имеем здесь дело с перестановками с повторениями.
Пусть даны п элементов k различных типов. Пусть первый элемент повторяется раз, второй раз,…, k–й повторяется раз
….
Если все элементы были бы различными, то мы имели бы n! перестановок.
Элементы а можно переставить способами, элементы b –– способами,…, элементы l – способами. Но от этого не изменится число перестановок с повторениями. Следовательно, число перестановок с повторениями меньше числа перестановок без повторения в раз. Таким образом, число перестановок с повторениями
.
Пример 1. Сколькими способами можно поставить на книжной полке три экземпляра учебника по алгебре, два экземпляра учебника по геометрии и один экземпляр учебника по белорусскому языку?
Решение.
Пусть данное множество содержит n элементов. Попытаемся образовать размещения по k элементов с повторениями, т.е. в одном размещении тот же самый элемент может повториться 2, 3, …, k раз. Найдем число размещений с повторениями, которое обозначим .
Первый элемент какого–нибудь из отмеченных размещений мы можем выбрать n способами. Второй элемент тоже n способами, тогда пару элементов можно образовать способами. Третий элемент опять можем выбрать n способами, четвертый также и т.д. Таким образом, размещения из n элементов можем образовать способами. Значит,
.
Пример 2. Сколько разных пятизначных чисел можно составить из цифр 0, 2, если одна и та же цифра может повторяться несколько раз?
Решение. Из цифр 0, 2 можем получить пятизначных чисел. Но числа, записанные пятью цифрами, первая из которых нуль, не являются пятизначными.
Их столько, сколько четырехзначных чисел можно составить из цифр 0, 2 при повторении цифр, т.е Поэтому ответ:
Составим выборки из элементов одного и того же множества и не отличаются по своему объему, но отличаются по составу (хотя бы одним элементом). Такие выборки называются сочетаниями с повторениями.
Число сочетаний с повторениями, если объем каждой выборки равен k, а множество, из которого строятся выборки, содержит n элементов, будем обозначать . Имеем:
Таким образом,