![]() |
Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
Размещения и сочетания без повторений
Часто приходится составлять из конечного числа элементов различные комбинации и производить подсчет числа всех возможных комбинаций, составленных по некоторому правилу. Такие задачи называются комбинаторными, а раздел математики, занимающийся их решением, называется комбинаторикой. Рассмотрим два основных правила, с помощью которых решается большинство задач комбинаторики. Допустим, что Пришли к так называемому правилу суммы: если некоторый объект А можно выбрать Задачи, которые можно решить применением одного лишь правила суммы, по большей части тривиальны. Обычно правило суммы используют с правилом произведения. Рассмотрим следующую задачу. Задача. Сколько можно записать двузначных чисел в десятичной системе счисления? Решение. Число десятков двузначного числа может принимать одно из девяти значений: 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. Различные упорядоченные множества, которые отличаются лишь порядком элементов (т.е. могут быть получены из того же самого множества), называются перестановками этого множества. Множество из одного элемента можно упорядочить одним–единственным образом: единственный элемент множества приходится считать первым. Возьмем множество из двух элементов, для примера, из двух букв А и Б. Очевидно, что их можно расположить по порядку двумя способами: АБ или БА. Три буквы А, Б, В можно расположить по порядку шестью способами: АБВ, АВБ, БАВ, БВА, ВАБ, ВБА. Число перестановок из Докажем, что, вообще,
Будем последовательно выбирать элементы данного множества и размещать их в определенном порядке на способами. Таким образом, Пример 1. Сколькими способами можно расположить на шахматной доске 8 ладей (рис.75) так, чтобы они не смогли взять друг друга?
Решение. Рис. 75 Ясно, что в этом случае на каждой горизонтали и каждой вертикали шахматной доски может быть расположено только по одной ладье. Число возможных позиций –– число перестановок из 8 элементов: Рассмотрим теперь упорядоченные подмножества данного множества. Определение 3. Конечные упорядоченные подмножества данного множества называются размещениями данного множества. Число упорядоченных k–элементных подмножеств множества, состоящего из Докажем, что Итак, пусть задано По правилу произведения получаем, что число упорядоченных Произведение т.е. в виде Пример 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 медиков. Сколькими способами можно укомплектовать экипаж исследователей космоса? |
Последнее изменение этой страницы: 2019-04-10; Просмотров: 345; Нарушение авторского права страницы