Вопросы и задания для повторения

• 1. Привести основные правила комбинаторики.
• 2. Что называется размещениями без повторений? Привести пример для совокупности из трех различных букв. Сформулировать теорему о размещениях.
• 3. Что называется перестановками? Привести пример для совокупности из трех различных букв. В чем их отличие от размещений?
• 4. Что называется сочетаниями? Привести пример для совокупности из трех различных букв. Сформулировать теорему о сочетаниях.
• 5. Перечислить и доказать свойства сочетаний.
• 6. Что называется размещениями с повторениями? Привести пример для совокупности из трех различных букв.
• 7. Что называется перестановками с повторениями? Привести пример для совокупности из трех различных букв. Сформулировать теорему о перестановках с повторениями.
• 8. Что называется сочетаниями с повторениями? Привести пример для совокупности из трех различных букв.

Примеры решения задач

Задача 1.1. Сколькими способами можно рассадить четырех студентов, явившихся на пересдачу, на 25 местах?

Решение. Искомое число способов равно числу размещений из 25 по 4:

Задача 1.2. Даны все нечетные цифры. Сколько трехзначных чисел можно из них составить?

Решение. На первом месте в числе стоит любая из пяти цифр, на втором — также любая из пяти и т. д. Всего комбинаций А| = 5 • 5 • 5 = 5³ = 125.

Задача 1.3. Даны цифры 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Сколько существует способов расстановки цифр так, чтобы четные цифры стояли на четных местах, а нечетные — на нечетных?

Решение. Пять четных цифр можно расставить на пяти четных местах 5! способами. Каждому способу размещения четных цифр на четных местах соответствует 5! способов размещения нечетных цифр на нечетных местах. Общее число перестановок оказывается равным 5! • 5! = = (5!)² = 14 400.

Задача 1.4. Сколько перестановок можно составить из пяти букв {а, б, в, г, д}, в которых не встречались бы комбинации аб и ба?

Решение. Число всех перестановок пяти букв равно 5! Рассмотрим варианты, когда буквы, а и б стоят рядом. Первый вариант: а стоит на первом месте, б на втором, остальные три буквы расставлены произвольно. Таких случаев будет 3! Второй вариант: а стоит на втором месте, б — на третьем, таких случаев также будет 3! и т. д. Последний вариант: а стоит на четвертом месте, б стоит на пятом месте. Эти варианты вместе дают 4−3! случаев. Возможно такое же число вариантов для комбинации ба. Следовательно, число способов размещения, а и б рядом равно 2 • (4 • 3!). Поэтому число перестановок без комбинаций аб и ба есть 5! — 2 • (4 • 3!) = 4! • 3 = 72.

Задача 1.5. Проводится шахматный турнир, в котором 16 участников. Из какого числа партий может состоять турнир, если:

• а) турнир проводится по системе плей-офф (участник выбывает из турнира после первого проигрыша);
• б) между любыми двумя участниками проводится одна игра;
• в) ничьи во внимание не принимаются.

Решение, а) В каждой партии участвуют два человека, один из которых выбывает. Вначале проводятся восемь партий, оставшиеся восемь человек проводят четыре партии, четыре победителя играют две партии, наконец, последняя партия выявляет чемпиона. Всего будет сыграно 8 + 4 + 2 + 1 = 15 партий.

• б) Каждая партия отличается от других составом участников. Число способов выбрать двух участников из 16 без учета последовательности
• 16!

их выбора есть число сочетаний из 16 по 2: С,²_Л =-— = 120.

¹⁶ 14!-2!

Задача 1.6. Студенту необходимо в течение недели пересдать четыре предмета. Сколькими способами это можно сделать, если в один день можно сдать один предмет? При этом:

• а) последовательность пересдачи предметов имеет значение;
• б) последовательность пересдачи предметов несуществена;
• в) при условии выполнения п. б) один предмет будет сдаваться в последний день;
• г) при условии выполнения п. а) один предмет будет сдаваться в последний день;
• д) при условии выполнения п. а) один предмет будет сдаваться в последний день, и это будет алгебра.

Решение. Из семи дней студент должен выбрать четыре дня, когда он будет сдавать экзамены или зачеты.

• а) Последовательность сдачи предметов представляет интерес.
• 7¹

Число способов описывается размещениями: =^j = 840.

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

7!

сочетания: С? =-= 35.

• 7 4!-3!
• в) Если последовательность сдачи не важна и дополнительно известно, что последний экзамен (один из четырех) будет сдаваться в последний день, то число способов равно

г) Если последовательность сдачи важна и дополнительно известно, что последний экзамен (один из четырех) будет сдаваться в последний день, то число способов равно

д) Если последовательность сдачи важна и дополнительно известно, что последним экзаменом в последний день будет алгебра, то число 6¹

способов равно Л| =— = 120.

Задача 1.7. Сколько различных слов можно получить, переставляя буквы в слове «мама»?

Решение. Задача может быть решена простым перебором перестановок букв. Их всего шесть: мама, ммаа, маам, аамм, амма, амам. Получим решение в общем виде, что позволит решать более сложные задачи. Перенумеруем места, на которых стоят буквы. Первой группой будут два места, на которых разместим букву «м». Второй группой будут места для размещения двух букв «а». Четыре места делятся на две группы по два места, т. е. имеем дело с разбиениями на группы. Число способов разбить четыре элемента на две группы по два есть.

Задача 1.8. Сколько различных слов можно получить, переставляя буквы в слове «экономика»?

Решение. В слове девять мест, на которые претендуют две буквы «к», две буквы «о», одна буква «э», одна буква «и», одна буква «н», одна буква «м» и одна буква «а». Разбиение на семь групп описывается формулой.

Задача 1.9. Сколько существует костей домино, каждая из которых содержит две цифры из семи: 0, 1, 2, 3, 4, 5, 6?

Решение. Кости домино можно рассматривать как сочетания с повторениями по два из семи цифр. Число таких комбинаций равно С²=С|=—= 28.

7 8 ₂,.

Задача 1.10. Руководитель подразделения должен написать десятистраничный отчет в течение недели. Сколькими способами он может распределить по дням работу, если:

• а) писать не менее одной странички в день;
• б) условием п. а) себя не ограничивать?

Решение, а) Используем так называемый принцип «шаров и перегородок» (рис. 1.2). Расположим 10 страниц в ряд и поставим между ними шесть перегородок, каждая из которых может стоять на одном из 9 мест. Число страниц между соседними перегородками автор должен написать в один из дней. Перегородки не должны совпадать, иначе в какой-то день не будет написана ни одна страница. Значит, надо выбрать шесть перегородок на девять мест, что описывается сочетани;

9'.

ями без повторений: С$ =-= 84.

Рис. 1.2. К задаче 1.10.

б) Поскольку могут возникнуть дни, когда не будет написана ни одна страница, перегородки (их всего шесть штук) могут совпадать. Мест для перегородок имеется 11 (до страниц, между ними и после). Значит, следует выбрать шесть перегородок на 11 мест, причем каждое место может быть выбрано вновь. Получили сочетания с повторениями:

Задача 1.11. Вдоль движения маршрутного такси девять остановок. Из шести пассажиров на одной остановке выходят четыре человека, на другой — остальные. Сколько вариантов покинуть такси имеют пассажиры?

Решение. Пассажиры разбились на группы, что описывается перестановками с повторениями Р₆(2,4). Из девяти остановок выбраны две. Число различных способов, которыми можно произвести последовательный выбор двух элементов без возвращения из совокупности объема девять, равно Л|. Таким образом, у пассажиров имеется Л| • Р₆ (2,4) = 6 1.

= 9−8—— = 1080 способов выйти из такси.

2 !• 4!