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

Практическое занятие №18.

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

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

Порядок выполнения работы

Задание №1. Внимательно изучите теоретическую справку. Запишите формулы размещений, сочетаний и перестановок с повторениями, рассмотрите примеры решения задач.

Размещения с повторениями из n элементов по k

Размещение с повторениями из n элементов по k – упорядоченная (n,k)-выборка с повторениями. Количество размещений с повторениями из n элементов по k определяется следующей формулой:

Пример №1. Сколько пятизначных чисел можно составить из множества цифр {5,7,2}?

Решение.

Ответ: 243.

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

Перестановка с повторениями – упорядоченная (n,k)-выборка с повторениями, в которой элемент   повторяется   раз,   повторяется   раз так далее, до последнего элемента  , который повторяется   раз. При этом  + +…+ = . Общее количество перестановок с повторениями определяется формулой:

Пример №2. Сколько различных слов можно составить, переставляя буквы в слове КОЛОСОК? КАРИКАТУРА?

Решение.

Сочетания с повторениями из n элементов по k

Сочетание с повторениями из n элементов по k – неупорядоченная (n,k)-выборка с повторениями. Общее количество сочетаний с повторениями из n элементов по k определяется формулой:

Пример №3. Сколько наборов из 7 пирожных можно купить, если в продаже имеются пирожные 4 сортов?

Задание №2. Решите следующие задачи.

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

Решение.

Если принять, что первому сорту соответствует число 1, второму сорту – число 2 и так далее, то исходное множество в нашей задаче таково: U={1,2,3,4}. Из этого множества мы выбираем 20 элементов (т.е., те самые 20 конфет с конвейера). Пригоршня конфет образует (4,20)-выборку. Естественно, повторения сортов будут. Вопрос в том, играет роль порядок расположения элементов в выборке или нет? Из условия задачи следует, что порядок расположения элементов роли не играет. Нам нет разницы, будут ли в горсти располагаться сначала 15 леденцов, а потом 5 шоколадных конфет, или сначала 5 шоколадных конфеты, а уж потом 15 леденцов. Итак, мы имеем дело с неупорядоченной (4,20) выборкой с повторениями. Чтобы найти общее количество этих выборок используем формулу:

Ответ: 1771.

1. Слова составляются на основе алфавита U={a,b,d}. Сколько различных слов из семи символов может быть составлено, если в этих словах буква "a" должна повторяться 2 раза; буква "b" – 1 раз, а буква "d" – 4 раза?

Решение.

Вот примеры искомых слов: "aabdddd", "daddabd" и так далее. Буквы каждого слова образуют (3,7)-выборку с повторениями: (a,a,b,d,d,d,d), (d,a,d,d,a,b,d) и т.д. Каждая такая выборка состоит из двух элементов "a", одного элемента "b" и четырёх элементов "d". Иными словами, k1=2, k2=1, k3=4. Общее количество повторений всех символов, естественно, равно объёму выборки, т.е. k=k1+k2+k3=7. Подставляя эти данные в формулу, будем иметь:

Ответ: 105.

1. Согласно государственному стандарту, автомобильный номерной знак состоит из 3 цифр и 3 букв. При этом недопустим номер с тремя нулями, а буквы выбираются из набора А, В, Е, К, М, Н, О, Р, С, Т, У, Х  (используются только те буквы кириллицы, написание которых совпадает с латинскими буквами).Сколько различных номерных знаков можно составить для региона?

Решение:   способами можно составить цифровую комбинацию автомобильного номера, при этом одну из них (000) следует исключить:  .
 способами можно составить буквенную комбинацию автомобильного номера.
По правилу умножения комбинаций, всего можно составить: 
 автомобильных номера
(каждая цифровая комбинация сочетается с каждой буквенной комбинацией).
Ответ: 1726272

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

Решение. По условию задачи нужно отобрать группу из 5 человек из имеющихся 23. Но в эту группу обязательно должны входить две девушки, а значит остальные три человека – юноши. Таким образом, нам необходимо вычислить, сколько существует способов отобрать двух девушек из 13 И трех юношей из 10. Так как порядок выбора парней и девушек не имеет значения, значит, это будут сочетания.

=78 – способов выбрать 2 девушки из 13

=120 – способов выбрать 3 юноши из 10

Ответ. 9360.

1. В урне находится 4 белых, 6 черных и 5 красных шаров. Сколькими способами можно достать:

а) три шара; б) три шара одного цвета; в) три шара разного цвета;

г) три шара, из которых обязательно 2 красных;

д) три шара, из которых хотя бы один белый.

Решение.

а) в данном пункте не указывается цвет шаров, поэтому нам нужно извлечь три любых шара из общего количества. Всего в урне находится 4+6+5=15 шаров. Считаем количество сочетаний 3 из 15.

=455 – способов извлечь три шара из урны.

б) в данном пункте необходимо извлечь три шара одного цвета, то есть 3 белых ИЛИ 3 черных ИЛИ 3 красных. Считаем количество сочетаний 3 из 4, 3 из 6 и 3 из 5.

– способа извлечь три белых шара из имеющихся в урне 4 белых шаров

– способов извлечь три черных шара из имеющихся в урне 6 черных

– способов извлечь три красных шара из имеющихся в урне 5 красных

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

4 +20+10=34 способа извлечь три шара одного цвета.

в) в данном пункте необходимо извлечь три шара разного цвета, то есть 1 белый И 1 черный1 И 1 красный. Считаем количество сочетаний 3 из 4, 3 из 6 и 3 из 5.

из имеющихся в урне 4 белых шаров можно достать 4 способами, соответственно 1 черный – 6 способами, 1 красный – 5 способами. По правилу умножения получаем способов (так как в предложении стоит логическая связка И).

г) «три шара, из которых обязательно 2 красных» означает, что среди трех шаров окажется 2 красных, а один третий шар может быть либо черным, либо белым. Считаем количество сочетаний 2 из 5 (2 красных шара):

– способов извлечь 2 красных шара из имеющихся в урне 5 красных.

Теперь найдем количество способов, которыми можно извлечь 1 белый ИЛИ 1 черный шар. Так как в урне всего 4 белых и 6 черных шаров, то один из них можно извлечь 4+6=10 способами.

Так как нам необходима комбинация 2 красных И 1 любой другой(белый или черный), получаем:

способов.

Задание №3. Выполните самостоятельную работу по вариантам

1. Сколько различных слов можно получить, переставляя буквы в слове ИНСТИТУТ?

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

3. В студенческой столовой продают сосиски в тесте, ватрушки и пончики. Сколькими способами можно приобрести шесть пирожков?

Вариант 2

1. Сколько различных слов можно получить, переставляя буквы в слове МОНОМАХ?

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

3. В буфете продают пирожки трех видов: с капустой, с яблоками и с картофелем. Сколькими способами можно приобрести семь пирожков?

Вариант 3

1. Сколько различных слов можно получить, переставляя буквы в слове КОЛОКОЛ?

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

3. В магазине продаются ручки четырех цветов: синие, красные, черные и зеленые. Сколько существует способов купить 10 ручек?

Вариант 4

1. Сколько различных слов можно получить, переставляя буквы в слове КОЛОБОК?

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

3. В кармане лежат монеты разного достоинства: по 1,2,5 и 10 рублей (каждых не менее 6 штук). Сколько существует способов достать 6 монет?