06. Размещения
Пусть имеется некоторое множество, содержащее n элементов. Выберем из этого множества k элементов без возвращения, но упорядочивая их по мере их выбора в последовательную цепочку. Такие цепочки называются размещениями.
Размещениями из n элементов по k элементов называются такие комбинации, из которых каждое содержит k элементов, взятых из числа данных n элементов, и которые отличаются друг от друга либо самими элементами (хотя бы одного), либо порядком их расположения.
Поясним это на следующем примере. Пусть имеется три элемента: a, b и c. Тогда из этих трёх элементов можно составить шесть размещений по два элемента: ab, ac, ba, bc, ca, cb. Все приведённые размещения отличаются друг от друга хотя бы одним элементом или порядком их расположения.
Число размещений 
(читается: число размещений из n элементов по k элементов) можно найти из принципа умножения. Первый элемент размещения можно выбрать n способами. Как только такой выбор будет сделан, останется (n–1) возможностей, чтобы выбрать второй элемент; после этого останется (n–2) возможностей для выбора третьего элемента и т. д.; для выбора k-го элемента будет (n–k+1) возможностей. По принципу умножения находим
. (4.1)
Легко понять, что 
.
Пример 4.1. В некоторой газете 12 страниц. Необходимо на страницах этой газеты поместить 4 различных фотографии. Сколькими способами это можно сделать, если ни одна страница газеты не должна содержать более одной фотографии?
Решение. Для размещения фотографий следует отобрать 4 различных страницы из 12 имеющихся. Затем нужно отобранные страницы упорядочить, т. е. определить, на какую страницу поместить первую фотографию, на какую – вторую и т. д. Полученная упорядоченная совокупность страниц является, согласно определению, размещением из 12 элементов по 4, а число таких размещений является искомым результатом:
.
Пример 4.2. Сколькими способами можно составить трехцветный полосатый флаг, если имеются ткани пяти различных цветов? Решите эту же задачу при условии, что одна полоса должна быть красной.
Решение. Поскольку в данной задаче важен порядок следования полос и все цвета во флаге должны быть разными, то исходная задача сводится к подсчету числа размещений из 5 по 3:
способов.
При условии, что одна полоса должна быть красной, получаем, что для выбора места для красной полосы существует 3 способа, а для оставшихся двух полос останется 
способов. Таким образом, трехцветный полосатый флаг из имеющихся 5 цветов при условии, что один цвет должен быть красным можно составить
способами.
Пример 4.3. Сколькими способами 10 человек можно поставить парами в ряд?
Решение. Первую пару можно выбрать 
способами, вторую – 
способами, и т. д. В результате получаем
способами.
4.1. Научное общество состоит из 25 человек. Надо выбрать президента общества, вице-президента, ученого секретаря и казначея. Сколькими способами может быть сделан этот выбор, если каждый член общества может занимать лишь один пост?
Ответ: В этом случае надо число размещений из 25 элементов по 4. Здесь играет роль и то, кто будет выбран в руководство общества, и то, какие посты займут выбранные. Поэтому ответ дается формулой 
.
4.2. В цехе работают 8 токарей. Сколькими способами можно поручить трем из них изготовление различных видов деталей (по одному виду на каждого).
Ответ: 
.
4.3. Из 10 книг выбирают 4 для рассылки по разным адресам. Сколькими способами это можно сделать?
Ответ: 
.
4.4. Сколькими способами можно опустить 5 писем в 11 почтовых ящиков, если в каждый ящик опускают не более одного письма?
Ответ: 
.
4.5. Студенту необходимо сдать 5 экзаменов в течение 12 дней. Сколькими способами можно составить расписание экзаменов, если в течение дня он может сдать не более одного экзамена?
Ответ: 
.
4.6. Сколькими способами можно преподнести 4 различных подарка 6 ученикам таким образом, чтобы каждый ученик получил не более одного подарка?
Ответ: 
.
4.7. Сколько различных четырехзначных чисел можно составить из цифр 0, 1, 2, …, 9, если каждая цифра в обозначении числа встречается не более одного раза? (Учесть, что число не может начинаться с нуля.)
Ответ: 
.
Источник
Комбинаторика 3
Решение многих комбинаторных задач сводится к умножению друг на друга числа возможных вариантов независимого выбора. Вы наверняка обратили на это внимание — таковы были, например, задачи 19 и 20 из листка «Комбинаторика 1». Рассмотрим другие примеры.
1. Сколькими способами можно купить пиджак и брюки, если в магазине есть 7 видов пиджаков и 5 видов брюк?
Допустим, что пиджак уже куплен. Тогда в пару к нему можно выбрать любые из 5 брюк. Таким образом, существует 5 наборов пиджак—брюки, содержащих выбранный пиджак. Поскольку пиджаков всего 7, то имеется 7·5 = 35 различных наборов из пиджака и брюк, т.е. покупку можно сделать 35 способами.
2. В магазин привезли еще 4 вида галстуков. Сколькими способами можно теперь купить комплект из пиджака, брюк и галстука?
Допустим, что пара пиджак—брюки уже выбрана. К ней можно купить галстук 4 способами. Поскольку пар пиджак—брюки всего 35, имеется 35·4 = 140 способов купить пиджак, брюки и галстук. Заметим, что искомое число способов получается прямым перемножением вариантов: 140 = 7·5·4.
В некоторых задачах выбор не является независимым: осуществление выбора ограничивает число возможных вариантов на следующем этапе. Вот пример.
3. Сколькими способами можно составить трехцветный флаг из трех горизонтальных полос, если имеется материя 5 различных цветов?
Для верхней полосы флага существует 5 способов выбора цвета. Когда цвет верхней полосы выбран, для средней полосы остается 4 возможных цвета. После выбора цвета верхней и средней полос цвет нижней полосы можно выбрать 3 способами. Итого получается 5·4·3 = 60 способов составить флаг.
- В буфете продаются 4 вида булочек и 5 видов пирожных. Сколькими способами можно купить булочку и пирожное?
- У Кати есть 6 ручек, 3 карандаша и 4 тетради. Сколькими способами Катя может взять с собой в школу ручку, карандаш и тетрадь?
- Сколько различных пар, состоящих из гласной и согласной букв, можно выбрать из слова «комбинаторика»?
- В языке аборигенов далекого острова 10 прилагательных, 20 существительных и 15 глаголов. Предложением называется всякое сочетание либо существительного и глагола, либо прилагательного, существительного и глагола. Сколько всего предложений имеется в этом языке?
- Сколько различных четырехзначных чисел можно составить из цифр 1, 2, 3 и 4?
- Монету подбрасывают пять раз. Сколько различных последовательностей орлов и решек можно при этом получить?
- Каждую грань кубика можно покрасить в белый, красный или черный цвет. Сколько существует вариантов раскраски кубика?
- Сколько существует четырехзначных чисел, все цифры которых нечетны?
- Сколько существует а) семизначных чисел; б) четных трехзначных чисел?
- В футбольной команде 11 человек. Нужно выбрать капитана и его помощника. Сколькими способами это можно сделать?
- Король решил выдать замуж трех своих дочерей. Со всех концов света явились во дворец сто юношей. Сколькими способами дочери короля могут выбрать себе женихов?
- Сколько различных четырехзначных чисел можно составить из цифр 1, 2, 3, 4, 5 и 6, используя каждую из цифр ровно по одному разу?
- Сколько различных пятизначных чисел можно составить из цифр 1, 2, 3, 4 и 5, используя каждую из цифр ровно по одному разу?
- Сколько анаграмм имеют слова «цифра», «листок»?
- В некоторой гимназии, в некотором классе в понедельник семь уроков: математика, латынь, греческий, литература, история, английский и физкультура. Сколько вариантов расписания в этом классе можно составить на понедельник?
Источник
Элементы комбинаторики
Составитель преподаватель кафедры высшей математики Ищанов Т.Р.
Занятие №1. Элементы комбинаторики
Теория.
Правило умножения: если из некоторого конечного множества первый объект (элемент «a») можно выбрать n1 способами, а второй объект (элемент «b») — n2 способами, то оба объекта (a и b) в указанном порядке можно выбрать» width=»49
» style=»vertical-align: -4px;»/> способами.
» width=»49 Правило сложения: если некоторый объект «a» можно выбрать n1 способами, а объект «b» можно выбрать n2 способами, причем первые и вторые способы не пересекаются, то любой из объектов (a или b) можно выбрать 
» width=»58
» style=»vertical-align: -4px;»/> способами.
Практический материал.
1.(6.1.44. Л) Сколько различных трехзначных чисел можно составить из цифр 0; 1; 2; 3; 4 если:
а) цифры не могут повторяться;
б) цифры могут повториться;
в) числа должны быть четными (цифры могут повторяться);
г) число должно делиться на 5 (цифры не могут повторяться)
(Ответ: а) 48; б) 100; в) 60; г) 12)
2. (6.1.2.) Сколько чисел, содержащих не менее трех различных цифр, можно составить из цифр 3; 4; 5; 6; 7? (Ответ: 300.)
3. (6.1.39) Сколько можно составить четырехзначных чисел так, чтобы любые две соседние цифры были различными? (Ответ: 6561)
Теория. Пусть дано множество, состоящее из «n» различных элементов. Размещением из «n» элементов по «k» элементов (
» style=»vertical-align: -3px;»/>) называется любое упорядоченное подмножество данного множества, содержащее «k» элементов.
» width=»77 Два размещения различны, если они отличаются друг от друга либо составом элементов, либо порядком их следования. Число размещений из «n» элементов по «k» обозначаются символом 
» width=»21
» style=»vertical-align: -4px;»/> и вычисляется по формуле:
px;»> 
» width=»115
» alt=»\[A_n^k=\frac
Практический материал.
4. (6.1.9 Л.) Составить различные размещения по два элемента из элементов множества A= <3,4,5>и подсчитать их число. (Ответ: 6)
5. (6.1.3 Л) Сколькими способами могут быть распределены три призовых места среди 16 соревнующихся? (Ответ: 3360)
6. (6.1.11. Л) Сколько имеется пятизначных чисел, все цифры у которых различны? Указание: учесть тот факт, что цифры вида 02345, 09782 и т.д. не считаем пятизначными. (Ответ: 27 216)
7. (6.1.12.Л.) Сколькими способами можно составить трехцветный полосатый флаг (три горизонтальных полосы), если имеется материя 5 различных цветов? (Ответ: 60.)
Теория. Сочетанием из «n» элементов по «k» элементов (
» style=»vertical-align: -3px;»/>) называется любое подмножество данного множества, которое содержит «k» элементов.
Любые два сочетания отличаются друг от друга только составом элементов. Число сочетаний из «n» элементов по «k» обозначается символом
» style=»vertical-align: -4px;»/> и вычисляется по формуле:
» width=»21 px;»> 
» width=»129
» alt=»\[C_n^k=\frac
Практический материал.
8.(6.1.20.) Составить различные сочетания по два элемента из элементов множества A= <3,4,5>и подсчитать их число. (Ответ: 3.)
9. (6.1.25.) Группа туристов из 12 юношей и 7 девушек выбирает по жребию 5 человек для приготовления ужина. Сколько существует способов при которых в эту «пятерку» попадут:
а) одни девушки; б) 3 юноши и 2 девушки;
в) 1 юноша и 4 девушки; г) 5 юношей; д) туристы одного пола.
(Ответ: а) 21; б) 4620; в) 420; г) 792; д) 813.)
Теория. Перестановкой из «n» элементов называется размещение из «n» элементов по «n» элементов. Таким образом, указать ту или иную перестановку данного множества из «n» элементов значит выбрать определенный порядок этих элементов. Поэтому любые две перестановки отличаются друг от друга только порядком следования элементов. Число перестановок из «n» элементов обозначается символом
» style=»vertical-align: -3px;»/> и вычисляется по формуле:
» width=»19 px;»> 
» width=»105
» alt=»\[P_n=A_n^n=n!\]» title=»Rendered by QuickLaTeX.com»/>
10.(6.1.14.Л) Составить различные перестановки из элементов множества A=<5;8;9>. (Ответ: 6)
11.(6.1.15.Л) Сколькими способами можно расставить на книжной полке десятитомник произведений Д. Лондона, располагая их:
а) в произвольном порядке;
б) так, чтобы 1, 5, 9 тома стояли рядом (в любом порядке);
в) так, чтобы 1, 2, 3 тома не стояли рядом (в любом порядке).
(Ответ: а) 10! б) 8!?3! в) 
» width=»85
» style=»vertical-align: -4px;»/>)
12. (1.6.16.Л.) В комнате имеется 7 стульев. Сколькими способами можно разместить на них 7 гостей? 3 гостя? (Ответ: 5040; 210)
Схема выбора с возвращением.
Теория. Если при упорядоченной выборке «k» элементов из «n», элементы возвращаются обратно, то полученные выборки представляют собой размещения с повторениями. Число всех размещений с повторениями из «n» элементов по «k» обозначается символом
» style=»vertical-align: -4px;»/> и вычисляется по формуле:
» width=»21 px;»> 
» width=»69
» alt=»\[\bar A_n^k=n^k.\]» title=»Rendered by QuickLaTeX.com»/>
Если при выборке «k» элементов из «n», элементы возвращаются обратно без последующего упорядочивания (таким образом, одни и те же элементы могут выниматься по нескольку раз, т.е. повторяться), то полученные выборки есть сочетания с повторениями. Число всех сочетаний с повторениями из «n» элементов по «k» обозначается символом 
» width=»21
» style=»vertical-align: -4px;»/> и вычисляется по формуле:
px;»> 
» width=»102
» alt=»\[\bar C_n^k=C^k_
13.(6.1.29.) Из элементов (цифр) 2, 4, 5 составить все размещения и сочетания с повторениями по два элемента. (Ответ: 9; 6)
14. (6.1.31.Л.) Пять человек вошли в лифт на 1-м этаже девятиэтажного дома. Сколькими способами пассажиры могут выйти из лифта на нужных этажах? (Ответ: 
» width=»130
» style=»vertical-align: -5px;»/>)
15. (6.1.59.Л.) В кондитерской имеется 7 видов пирожных. Сколькими способами можно приобрести в ней: а) 3 пирожных одного вида; б) 5 пирожных? (Ответ: а) 7; б) 462)
Теория. Пусть в множестве из «n» элементов есть «k» различных типов элементов, при этом 1-й тип элементов повторяется n1 раз, 2-й — n2 раз, . . . , k-й — nk раз, причем
» style=»vertical-align: -4px;»/>. Тогда перестановки элементов данного множества представляют собой перестановки с повторениями.
Число перестановок с повторениями (иногда говорит о числе разбиений множества) из n элементов обозначается символом
» style=»vertical-align: -4px;»/> и вычисляется по формуле:
» width=»178 
» width=»135 px;»> 
» width=»300
» alt=»\[P_n (n_1,n_2,\cdot\cdot\cdot,n_k )=\frac
16.(6.1.32.) Сколько различных «слов» (под «словом» понимается любая комбинация букв) можно составить, переставляя буквы в слове АГА? MISSISSIPPI?
Решение.
Вообще из трех букв можно составить
» style=»vertical-align: -3px;»/> различных трехбуквенных «слов». В слове АГА буква «А» повторяется, а перестановка одинаковых букв не меняет «слова». Поэтому число перестановок с повторениями меньше числа перестановок без повторений во столько раз, сколько можно переставлять повторяющиеся буквы. В данном слове две буквы (1-я и 3-я) повторяются; поэтому различных перестановок трехбуквенных «слов» из букв слова АГА можно составить столько:
» width=»89 px;»> 
» width=»143
» alt=»\[P_3/P_2 =3!/2!=3.\]» title=»Rendered by QuickLaTeX.com»/>
Впрочем, ответ можно получить и проще: 
» width=»165
» style=»vertical-align: -5px;»/>. По этой же формуле найдем число одиннадцатибуквенных «слов» при перестановке букв в слове MISSISSIPPI. Здесь n=11; n1=1; n2=4 (4 буквы S); n3=4 (4 буквы I); n4=2, поэтому
px;»> 
» width=»438
» alt=»\[P_ <11>(1,4,4,2)=\frac<11!><1!4!4!2!>=\frac<5\cdot 6\cdot 7\cdot 8\cdot 9\cdot 10\cdot 11><1\cdot 24\cdot 2>=34 650.\]» title=»Rendered by QuickLaTeX.com»/>
17.(6.1.38.Л.) Сколько существует различных перестановок букв в слове ТРАКТАТ? А в «слове» АААУУАУУУУ? (Ответ: 420; 210)
Источник
