32.
Задачи по комбинаторике
Наука, изучающая способы составления и количество множеств и их подмножеств, называется комбинаторикой.Каждое конкретное подмножество, составленное из элементов данного конечного множества, называется соединениемили выборкой.Если во множестве определено, какой элемент множества за каким следует или какому предшествует, то множество называется упорядоченным. Если в упорядоченном множестве изменить расположение элементов, то мы получим другое, отличное от первого множество.Выборка — результат отбора, извлечение предпочитаемого из наличного.Комбинаторная задача состоит в подсчете числа выборок из конечного основного множества элементов M = {a1, а2, а3, ..., аn}.Выборки отличаются объемом (т.е. числом элементов, которые надо выбрать), порядком (т.е. упорядоченные или неупорядоченные выборки) и повторениями (есть или нет в выборке повторяющиеся элементы).Мы знаем три основных вида соединений: размещения, перестановки и сочетания.Упорядоченные выборки. (Поочередный выбор). Размещения с повторениямиПример 1.Сколько трехзначных чисел можно составить из 4 цифр: 1, 2, 3, 4?Решение.Перечислим с помощью схемы все возможные числа:Видим, что всего данных чисел 43 = 64, где 4 — количество элементов исходного множества, а 3 — число выбранных элементов.Данный пример является иллюстрацией к следующему понятию:Размещениями из n элементов по k называются упорядоченные выборки, каждое из которых содержит k элементов из n данного множества. Размещения отличаются друг от друга либо порядком элементов, либо самими элементами.Если некоторые элементы данного множества могут повторяться в размещении, то такие размещения называются кортежами или размещениями с повторениями. Число элементов в размещении называют его длиной.Размещениями с повторениями называют упорядоченную выборку, состоящую из n не обязательно различных элементов.Пусть дано множество M = {a1, а2, а3, ..., аn}. Сколько кортежей длины k можно составить из n элементов этого множества?Решение.Первый элемент каждого кортежа мы можем выбрать n способами, записав на первое место любой из n элементов. Второй элемент тоже можно выбрать n способами и т.д. Значит, общее число кортежей из множества n элементов, по k элементов в каждом, будет равно nk. Число кортежей из n по k с учетом их порядка обозначается , и называют числом размещений с повторениями из n элементов по k: .В примере 1: .Перестановки с повторениямиПример 2.Сколько четырехзначных чисел можно составить из 4 цифр: 1, 2, 3, 4?Решение.Перечислим с помощью схемы все возможные числа:Видим, что всего данных чисел 44 = 256.Данный пример является иллюстрацией к следующему понятию, которое является частным случаем, когда наше основное множество состоит из различных элементов:Размещения с повторениями из n не обязательно различных элементов основного множества по n принято называть перестановками с повторениями. Число перестановок с повторениями обозначают .Заметим, . Общее число перестановок с повторениями из n элементов равно .В примере 2: .Пример 3.Сколько семизначных чисел можно составить из 7 цифр: 1; 1; 2; 2; 2; 3; 4?Решение.Заметим, что «1» повторяется 2 раза, «3» — три раза, а «3» и «4» — по одному. На этот случай существует другая формула перестановок с повторениями.В общем случае, когда в нашем основном множестве какие-то элементы могут повторяться используют понятие:Размещения без повторений (Размещения)Пример 4.Сколько трехзначных чисел, в которых цифры не повторяются, можно составить из 4 цифр: 1, 2, 3, 4?Решение.Перечислим с помощью схемы все возможные числа:Видим, что всего данных чисел 4·3·2 = 24.Данный пример является иллюстрацией к следующему понятию:Пусть множество M = {a1, а2, а3, ..., аn}. Сколько размещений без повторения элементов, по k элементов в каждом, можно составить из элементов этого множества?Решение.На первое место можно записать любой элемент из М. Значит, имеем n возможностей. На второе место — любой элемент, кроме выбранного на первое место. Итак, при каждом выборе первого элемента для выбора второго имеем n - 1 возможностей, т. е. для выбора двух элементов имеем n(n — 1) возможностей. При каждом выборе первых двух элементов для выбора третьего элемента имеем n — 2 возможностей и т. д. На послед нее k-е место можно записать любой элемент, кроме выбранных k — 1 элементов на предыдущие места, т.е. для его выбора имеем n — (k — 1 ) = n — k + 1 возможностей. Следовательно, всего размещений из n по k элементов будетAnk = n(n — 1)(n — 2)…(n — k + 1). Полученное выражение состоит из k последовательных натуральных множителей, наибольший из которых равен n. Умножив и разделив полученное выражение на (n — k)! получим:Размещениями называют упорядоченную выборку k элементов, из n различных элементов основного множества.Число всех выборов k элементов из n различных элементов данного множества с учетом их порядка обозначают Аnk и называют числом размещений из n элементов по k.В примере 4: A43 = 4! / (4-3)! = 4·3·2 = 24.Перестановки без повторений (Перестановки)Пример 5.Сколько четырехзначных чисел, в которых цифры не повторяются, можно составить из 4 цифр: 1, 2, 3, 4?Решение.Перечислим с помощью схемы все возможные числа:Видим, что всего данных чисел 4 · 3 · 2 · 1 = 24.Данный пример является иллюстрацией к следующему понятию:Размещения из n элементов по n принято называть перестановками. Иначе, перестановки — это упорядоченные множества из n различных элементов основного множества по n. Перестановки отличаются друг от друга только порядком элементов. Число перестановок принято обозначать Рn. Общее число перестановок из n элементов равно Pn = n!.В примере 5: P4 = 4! = 4·2·3·1 = 24.Неупорядоченные выборки.(Одновременный выбор). Сочетания без повторений. (Сочетания)Пример 6.Сколько трехэлементных подмножеств, различающихся хотя бы одним элементом друг от друга и без учета порядка в подмножестве, можно составить из 4 цифр: 1, 2, 3, 4?Решение.Перечислим все полученные подмножества:(1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4).Видим, что всего получилось 4 подмножества.Данный пример является иллюстрацией к следующему понятию:Сочетания. Сочетаниями из n элементов по k называются соединения, каждое из которых содержит k элементов из данного множества n элементов и отличается от других хотя бы одним элементом. В сочетаниях нас интересуют только сами элементы множества и не интересует их порядок. Важно, какие конкретно элементы множества входят в каждое соединение.Число сочетаний, т.е. число всех различных подмножеств длины k из данного множества, содержащего n элементов, обозначается Сnk . Легко видеть, что если мы возьмем все сочетания из n по k и в каждом из них упорядочим элементы всеми возможными способами, т.е. из каждого сочетания получим все возможные перестановки, то получим все размещения из n элементов по k. Значит,Ank = Сnk·Pk. Отсюда или . Иначе В примере 6: .Пример 7.Сколькими способами можно выбрать к предметов из n?Например:Сочетания с повторениямиСочетания с повторениями — неупорядоченная выборка, состоящая из n необязательно различных элементов. Обозначается .,где n — количество необязательно различных элементов основного множества, k — количество выбираемых.Пример 8.Сколько будет костей в игре домино, если использовать, только четыре цифры 1, 2, 3, 4?Решение.Используем формулу сочетаний с повторениями:Ответ: Задачи для тренировкиПример 9.Сколько четырехзначных чисел можно составить из 9 цифр: 1, 2, 3, 4, 5, 6, 7, 8, 9?Решение.Цифры в числах могут повторяться, и число зависит от порядка цифр в его записи. Значит, это размещения с повторениями, т.е. кортежи. Их число .Ответ: Пример 10.В чемпионате участвует 12 команд. Сколькими различными способами могут быть распределены три различные медали?Решение.Это размещения без повторения, т.к. одна команда не может занять два или три места сразу. А123 = 12 · 11 · 10 = 1320.Ответ: Пример 11.В семье 6 человек. За столом 6 стульев. В семье решили каждый вечер рассаживаться на эти 6 стульев по-новому. Сколько дней члены семьи смогут делать это без повторений?Решение.Одного человека мы можем посадить только один раз. Значит, имеем перестановки без повторений. Одно размещение от другого может отличаться только порядком размещения людей, т.е. имеем перестановки 6 элементов: P6= 6! = 720.Ответ: Пример 12.Сколькими способами из класса, в котором учатся 30 школьников, можно выбрать капитана команды для математических соревнований и его заместителя?Решение.Ответ: Пример 13.Сколькими способами из класса, в котором учатся 30 школьников, можно выбрать двоих для участия в математической олимпиаде?Решение.Ответ: Пример 14.Сколько трехкнопочных комбинаций существует на кодовом замке (все три кнопки нажимаются одновременно), если на нем всего 10 цифр?Решение.Так как кнопки нажимаются одновременно, то выбор этих кнопок — сочетание. Отсюда возможно вариантов.Ответ: Пример 15.Три медведя выбегают из дома, догоняя девочку. Сколькими способами они смогут это сделать?Решение.Порядок выбегания из дома задает нумерацию трех медведей числами 1 2 3. Таких нумераций 3! = 6.Ответ: Пример 16.Сколькими способами можно построить пятерых человек в шеренгу?Решение.По формуле числа перестановок имеем Р5 = 5 · 4 · 3 · 2 · 1 = 120.Ответ: Пример 17.Сколькими способами 4 вора могут по одному разбежаться на все 4 стороны?Решение.Стороны фиксированы, например юг, север, запад, восток или для простоты 1, 2, 3, 4. Порядок разбегания по ним задает нумерацию 4-х воров числами 1, 2, 3, 4. Таких нумераций имеется 4! = 24.Ответ: Пример 18.11 футболистов строятся перед началом матча. 1-м — обязательно капитан, 2-м — обязательно вратарь, а остальные — случайным образом. Сколько существует способов построения?Решение.Капитана и вратаря строить не надо, т.к. их места фиксированы. 9 футболистов (все, кроме капитана и вратаря) надо расставить на 9 мест — с 3-го по 11-е. Всего имеется 9! = 362 880 таких перестановок.Ответ: Пример 19.В классе 27 учеников, из которых нужно выбрать троих. Сколькими способами это можно сделать, если:
    а) 1-й ученик должен решить задачу, 2-й — сходить за мелом, 3-й — пойти дежурить в столовую;б) им следует спеть хором?
Решение.
Ответ: Пример 20.В коридоре 3 лампочки. Сколько существует различных способов освещения коридора? (включая случай, когда все три не горят)Решение.Пример 21.У бармена есть 6 сортов зеленого чая. Для проведения чайной церемонии требуется подать зеленый чай ровно 3 различных сортов. Сколькими способами бармен может выполнить заказ?Решение.Тут все просто: есть n = 6 сортов, из которых надо выбрать k = 3 сорта. Число сочетаний можно найти по формуле: Ответ: Пример 22.В чемпионате по футболу 7 команд. Каждая команда играла с каждой один раз. Сколько всего было игр?Решение.Порядок выбора не имеет значения, т.е. если выбраны две команды, то неважно, какая из них первая, а какая — вторая: .Ответ: Пример 23.Сколько всего исходов, если друг за другом из колоды вынимают две карты, не возвращая карту обратно (выбор без возвращения)?Решение.Ответ: Пример 24.Сколько существует всего исходов, если из колоды вынимают две карты одновременно?Решение.Порядок не важен, значит:Ответ:  Видеолекция «Задачи по комбинаторике»: