Размещения и сочетания без повторений

Часто приходится составлять из конечного числа элементов различные комбинации и производить подсчет числа всех возможных комбинаций, составленных по некоторому правилу. Такие задачи называются комбинаторными, а раздел математики, занимающийся их решением, называется комбинаторикой.

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

Допустим, что  разноцветных шариков распределены по двум ящикам: в первом ––  шаров, во втором –– . Произвольно из какого–нибудь ящика вынимаем один шарик. Сколькими разными способами можно это сделать? Из первого ящика шарик можно вынуть  разными способами, из второго ––  разными способами. Всего  способами.

Пришли к так называемому правилу суммы: если некоторый объект А можно выбрать  способами, а объект В ––  способами, причем любой способ выбора объекта А отличен от любого способа выбора В, то выбор
«А или В» можно сделать  способами.

Задачи, которые можно решить применением одного лишь правила суммы, по большей части тривиальны. Обычно правило суммы используют с правилом произведения.

Рассмотрим следующую задачу.

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

Решение. Число десятков двузначного числа может принимать одно из девяти значений: 1, 2, 3, 4, 5, 6, 7, 8, 9. Число единиц может принимать одно из десяти значений: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.

Если цифра десятков 1, цифра единиц может быть 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 –– всего 10 значений. Если цифра десятков 2, то вновь, цифра единиц может быть равна 0, 1, 2, …, 9. Всего получим 90 ( ) двузначных чисел.

Пришли к так называемому правилу произведения: пусть объект А можно выбрать  способами, а после каждого такого выбора другой объект В можно выбрать (независимо от объекта А)  способами, то пары объектов А и В можно выбрать  способами.

Тридцать три буквы русского алфавита принято располагать в таком порядке: А, Б, В, Г, Д, Е, Ё, Ж, З, И, Й, К, Л, М, Н, О, П, Р, С, Т, У, Ф, Х, Ц, Ч, Ш, Щ, Ъ, Ы, Ь, Э, Ю, Я.

При этом порядке расположения букв, буква А является первой,
Б –– второй, В –– третьей, и т.д. вплоть до тридцать третьей буквы Я. Мы имеем дело с упорядоченным множеством.

Определение 1. Множество называется упорядоченным, если каждому элементу этого множества поставлено в соответствие некоторое натуральное число (номер элемента) от 1 до , где  –– число элементов множества, так что различным элементам соответствуют различные числа.

Очевидно, что каждое множество, содержащее более одного элемента, можно упорядочить не единственным способом.

Определение 2. Различные упорядоченные множества, которые отличаются лишь порядком элементов (т.е. могут быть получены из того же самого множества), называются перестановками этого множества.

Множество из одного элемента можно упорядочить одним–единственным образом: единственный элемент множества приходится считать первым. Возьмем множество из двух элементов, для примера, из двух букв А и Б. Очевидно, что их можно расположить по порядку двумя способами:

АБ или БА.

Три буквы А, Б, В можно расположить по порядку шестью способами:

АБВ, АВБ, БАВ, БВА, ВАБ, ВБА.

Число перестановок из  элементов обозначают . Мы нашли, что

Докажем, что, вообще,  (число перестановок из элементов) равно произведению первых  натуральных чисел:

.

Будем последовательно выбирать элементы данного множества и размещать их в определенном порядке на  местах. На первое место можно поставить любой из  элементов. После того как заполнится первое место, на второе место можно поставить любой из оставшихся n–1 элементов. После того как заполнятся первое и второе места, на третье место можно поставить любой из оставшихся  элементов и т.д. По правилу умножения все  мест можно заполнить

способами. Таким образом, .

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

Решение.

Рис. 75

Ясно, что в этом случае на каждой горизонтали и каждой вертикали шахматной доски может быть расположено только по одной ладье. Число возможных позиций –– число перестановок из 8 элементов:

Рассмотрим теперь упорядоченные подмножества данного множества.

Определение 3. Конечные упорядоченные подмножества данного множества называются размещениями данного множества.

Число упорядоченных k–элементных подмножеств множества, состоящего из  элементов, т.е. число размещений из  по k обозначают .

Докажем, что .

Итак, пусть задано –элементное множество X. Упорядоченное
–элементное подмножество можно получить, выбирая из Х поочередно элементы  Но в качестве первого элемента х₁ можно выбрать любой из  элементов множества Х. Поэтому такой выбор может быть произведен  способами. После того как первый элемент выбран, второй элемент можно выбрать лишь способами (можно взять любой элемент, исключая уже выбранный). После выбора первых двух элементов остаются лишь  возможности выбрать третий элемент и т.д. Последний –й элемент можно выбрать  способами, так как до него уже выбраны  элемент, а , значит, осталось лишь  элементов.

По правилу произведения получаем, что число упорядоченных
–элементных подмножеств –элементного множества Х равно произведению чисел т.е.  Мы доказали таким образом, что

Произведение  можно записать в виде дроби

т.е. в виде . Итак, мы доказали, что .

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

Решение.

Если задано некоторое множество Х, то можно рассматривать новое множество М(Х) –– множество всех его подмножеств.

Рассмотрим все подмножества множества {А; Б; В}; их восемь:
Æ –– пустое множество; {А}, {Б}, {В} –– три множества по одному элементу в каждом; {А; В}, {А; Б}, {Б; В} –– три множества по два элемента в каждом; {А; Б; В} –– одно множество из трех элементов.

Естественно задать вопрос: сколько различных –элементных подмножеств имеет множество из  элементов?

Определение 4. Произвольное –элементное подмножество
–элементного множества называется сочетанием из элементов по .

Число сочетаний из элементов по  обозначается . Докажем, что

Чтобы образовать упорядоченное подмножество, содержащее  элементов из данных , надо:

1) выделить какие–либо  из этих  элементов, что можно сделать  способами;

2) выделенные  элементов упорядочить, что можно сделать  способами .

Всего получится  способов (упорядоченных подмножеств), т.е.

.

Отсюда

Пример 3. В девятом классе 35 учащихся. Из них нужно выбрать четыре делегата на конференцию. Сколько имеется возможностей такого выбора?

Решение.

Упражнения

1. Из элементов множества А составьте всевозможные перестановки, если:

а)   А={1}; в)   А={а; b; с};

б)   А={5; 6} г)   А= {m; n; p; q}.

2. Сколькими способами можно составить список из 9 учеников?

6. В кружке юных математиков 25 членов. Необходимо избрать председателя кружка, его заместителя, редактора стенгазеты и секретаря. Сколькими способами можно образовать эту руководящую четверку, если одно лицо может занимать только один пост?

7. В высшей лиге по футболу 18 команд. Борьба идет за золотые, серебряные и бронзовые медали. Сколькими способами медали могут быть распределены между командами?

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

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

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

11. В пассажирском поезде 14 вагонов. Сколькими способами можно распределить по вагонам 14 проводников, если за каждым вагоном закрепляется один проводник?

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

13. Некто забыл последние 4 цифры телефонного номера. Помнит, что все цифры разные и среди них есть 9. Какое максимальное число номеров ему придется перебрать, чтобы дозвониться до абонента?

14. Для полета на Марс необходимо укомплектовать следующий экипаж космического корабля: командир корабля, первый его помощник, второй помощник, два бортинженера и один врач. Командующая тройка может быть выбрана из 25 готовящихся к полету летчиков, два бортинженера – из числа 20 специалистов, в совершенстве знающих устройство космического корабля, и врач –– из числа 8 медиков. Сколькими способами можно укомплектовать экипаж исследователей космоса?

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

Поделиться: