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

С повторениями

Из букв з, а, м, о, к можно образовать  различных слов
(не все они имеют смысл). Сколько разных слов можно образовать из букв слова «ротор». Столько же? Оказывается, нет! Только 30. Известная формула числа перестановок в рассматриваемом случае бессильна, так как элементы в «перестановках» повторяются. При перестановке в слове «ротор» местами букв о и р никаких изменений не происходит, остается то же самое слово.

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

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

… .

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

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

.

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

Решение.

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

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

.

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

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

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

Рассмотрим следующую задачу: сколькими способами можно составить набор из 8 пирожных, если имеется 4 сорта пирожных?

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

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

Например, событие «в набор включили 2 пирожных первого сорта, 3 –– второго сорта, 1 –– третьего сорта и 2 –– четвертого сорта» зашифруем так:

11011101011,

Событие «в наборе 2 пирожных первого сорта, 4 –– третьего и
2 –– четвертого сорта» зашифруем так: 11001111011,

событие «в набор включили 3 пирожных второго сорта, 5 –– третьего сорта» зашифруем так: 01110111110.

Легко заметить, что каждый зашифрованный набор представляет комбинацию 8 единиц и трех нулей. Мы получили перестановки с повторениями, где 1 повторяется 8 раз, а нуль –– 3 раза. Используя формулу , находим число всевозможных наборов пирожных:  Значит, существует 165 различных наборов.

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

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

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

        Упражнения

1. Сколькими способами можно расставить белые фигуры (2 коня,
2 слона, 2 ладьи, ферзя и короля) на первой линии шахматной доски?

2. Сколько различных слов можно получить из всех букв слова «перестановка»?

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

4. Пятнадцать занумерованных биллиардных шаров разложены по шести лузам. Сколькими способами можно это сделать?

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

6. Для несения почетного караула из 10 человек могут быть приглашены офицеры авиации, погранвойск, артиллерии, офицеры морского флота, ракетных войск и воздушно–десантных войск. Сколькими способами можно избрать состав почетного караула?

7. Сколькими способами 6 пассажиров могут распределиться по 12 вагонам, если для каждого пассажира существенным является только номер вагона, а не занимаемое им в вагоне место?

8. Из пункта А в пункт В ведут два шоссе, пересекаемые пятью поперечными дорогами. Сколькими способами можно проехать из А в В, не проезжая дважды одно и то же место?

9. Сколькими способами можно отослать 6 писем разным адресатам, если их будут разносить 3 курьера и заранее неизвестно, какому курьеру достанется какое письмо?

10. В некотором государстве (сказочном) не было двух жителей с одинаковым набором зубов. Какова может быть наибольшая численность населения государства (максимальное число зубов
равно 32)?

11. Группу из 20 человек можно разделить на 3 бригады, причем в первую бригаду должны входить 3 человека, во вторую –– 5 и в третью –– 12. Сколькими способами можно это сделать?

12. В продажу поступили открытки 10 разных видов. Сколькими способами можно образовать набор из 12 открыток?

 

⇐ Предыдущая45678910111213Следующая ⇒

Поделиться: