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, используя каждую из цифр ровно по одному разу?
- Сколько анаграмм имеют слова «цифра», «листок»?
- В некоторой гимназии, в некотором классе в понедельник семь уроков: математика, латынь, греческий, литература, история, английский и физкультура. Сколько вариантов расписания в этом классе можно составить на понедельник?
Источник
