Дипломная работа: Элементы комбинаторики
4.3. Понятие «перестановки с повторениями»
Пусть дан кортеж длинны п, составленный из элементов множества Х= {х1 , …, х k }. Причем буква х1 входит в этот кортеж п1 раз, буква х k = п k раз. Тогда п=п1 + … +п k . Если переставлять в этом кортеже буквы, то будут получаться новые кортежи, имеющие тот же состав. Эти кортежи называются перестановками с повторениями из букв х1 ,… , х k , имеющими состав (п1 , … , п k ).
Число таких перестановок обозначается Р(п1 , … , п k ) и находится по формуле:
Упражнение. Вычислите: Р (2, 5, 3); Р (1, 2, 3, 4).
Решение. Р (2, 5, 3); п =2+5+3=10, п1 =2, п2 =5, п3 =3
5. Закрепление
Задача 1. Найдите число способов расстановки 8 ладьей на шахматной доске, при которых они не бьют друг друга.
Решение. Каждый искомый способ задается перестановкой 8 чисел1,2, … 8. Эти числа указывают номера горизонталей занятых полей на первой, второй, …, восьмых вертикалей. Значит, таких перестановок 8!. Таким образом, ладьи можно расставить 8!=40 320 способами.
Задача 2. Сколькими способами можно представлять друг с другом цифры 1, 2, 3, 4?
Решение. Р4 =4!=24.
Задача 3. За столом пять мест. Сколькими способами можно расставить пятерых гостей?
Решение. Р5 =5!=120
Задача 4. У Лены есть 8 разных красок. Она хочет написать ими слова «Новый Год». Сколькими способами она может это сделать, если каждая буква может быть раскрашена одним цветом и все 8 букв должны быть разные по цвету.
Решение. Присвоим каждой краске номер от 1 до 8. Тогда каждый искомый способ задается перестановкой 8 чисел 1,2, …, 8. Значит, таких перестановок 8!. Поэтому она может написать «Новый Год» 8!=40 320 способами.
Задача 5 . Сколько пятизначных чисел можно составить из цифр 1, 2, 3, 4, 5?
Решение. 5!=120
Задача 6 . Сколько различных кортежей получится, если переставлять буквы слова «математика»?
Решение. Это слово имеет состав: м – 2, а – 3, т – 2, е – 1, и – 1, к – 1, то есть (2, 3, 2, 1, 1, 1), поэтому получим Р(2,3,2,1,1,1)=
Задача 7 . У мамы 2 яблока и 3 груши. Каждый день в течение 5 дней она дает сыну по 1 фрукту. Сколькими способами это может быть сделано.
Решение. Р(2,3)=
Задача 8 . Сколькими способами можно положить 28 различных открыток в 4 одинаковых конверта так, чтобы в каждом конверте было по 7 открыток?
Решение. Пометим конверты цифрами 1,2,3,4, тогда число различных раскладок равно Р(7,7,7,7)= 
. Вычислять это значение не будем, так как оно очень большое.
Сотрем пометки. Теперь конверты можно произвольно переставлять друг с другом, не меняя результата расклада (теперь они не отличаются друг от друга). Так как число различных перестановок четырех конвертов равно Р4 =4!, то число различных раскладов уменьшается в Р4 =4! и поэтому оно равно 
.
Задача 9 . Сколькими способами можно усадить за стол трех мальчиков и трех девочек так, чтобы никакие две девочки не сидели рядом?
Решение. 3!∙3!=36 способами
6. Итог урока