ЗАДАЧИ С РАЗБОРОМ
Задача. (Размещения) В футбольной команде 11 человек. Сколькими способами можно выбрать:
а) капитана и его ассистента;
б) капитана, первого ассистента и второго ассистента?
Решение.
а) Капитаном можно выбрать любого из 11 футболистов. Ассистентом — любого из 10 оставшихся. Поэтому капитана и ассистента можно выбрать 11 · 10 = 110 способами.
б) Капитана и первого ассистента мы уже выбрали 11 · 10 способами. Для выбора второго ассистента остаётся 9 способов. Поэтому капитана, первого ассистента и второго ассистента можно выбрать 11 · 10 · 9 = 990 способами.
Задача. (Перестановки) Сколько пятизначных чисел можно составить из цифр 1, 2, 3, 4, 5 при условии, что цифры не должны повторяться?
Решение. Для выбора первой цифры имеется пять способов, для выбора второй — четыре, для выбора третьей — три, для выбора второй — два, и для выбора последней цифры остаётся один способ. Всего чисел получается 5 · 4 · 3 · 2 · 1 = 5! = 120.
Задача. (Перестановки) Имеется n разноцветных шаров. Сколькими способами их можно выложить в ряд?
Решение. Первый шар можно выбрать n способами, второй шар можно выбрать n − 1 способами и т. д. Для выбора последнего, n-го шара остаётся один способ. Всего получается n · (n − 1) · . . . · 2 · 1 = n! способов выложить наши n шаров в ряд.
Задача. (Сочетания) В футбольной команде 11 человек. Сколькими способами можно выбрать из них двух игроков для прохождения допинг-контроля?
Решение. На первый взгляд кажется, что ситуация аналогична выбору капитана и ассистента: первого человека выбираем 11 способами, второго — 10 способами, так что всего имеется 11 · 10 способов. Однако в данном случае это не так.
В самом деле, пара «капитан и ассистент» является упорядоченной: выбрать Петю капитаном, а Васю ассистентом — это не то же самое, что выбрать Васю капитаном, а Петю ассистентом. С другой стороны, пара человек, отправленных на допинг-тест, является неупорядоченной: отправить Петю и Васю на тест — это ровно то же самое, что отправить Васю и Петю на тест. Соответственно, в данной задаче нас интересует именно число неупорядоченных пар футболистов, выбираемых из 11 человек.
Давайте представим себе, что неупорядоченная пара {Петя, Вася} как бы склеивается из двух упорядоченных пар (Петя, Вася) и (Вася, Петя). Иными словами, любые две упорядоченные пары, отличающиеся лишь порядком следования объектов, дают одну и ту же неупорядоченную пару. Следовательно, число неупорядоченных пар будет в два раза меньше числа упорядоченных пар и окажется равным (11 · 10) / 2 = 55.
Таким образом, двух футболистов можно выбрать для допинг-контроля 55 способами.
Задача. (Сочетания) Сколькими способами можно выбрать троих футболистов из 11 для прохождения допинг-контроля?
Решение. Произведение 11 · 10 · 9 (число способов выбора капитана, первого ассистента и второго ассистента) есть число упорядоченных троек футболистов. В данном же случае, как и в предыдущей задаче, порядок не важен, поэтому нам нужно найти число неупорядоченных троек фуболистов, выбираемых из 11 человек.
В одну неупорядоченную тройку склеиваются те и только те упорядоченные тройки, которые отличаются лишь порядком следования элементов. Число таких троек равно числу перестановок трёх элементов, то есть 3! = 6. Например, в одну неупорядоченную тройку
{Петя, Вася, Коля}
склеиваются ровно шесть упорядоченных троек
(Вася, Коля, Петя), (Вася, Петя, Коля), (Коля, Вася, Петя),
(Коля, Петя, Вася), (Петя, Вася, Коля), (Петя, Коля, Вася).
Следовательно, число неупорядоченных троек в 3! раз меньше числа упорядоченных троек. Соответственно, имеется
(11 · 10 · 9) / 3! = 165
способов выбрать троих человек для допинг-контроля.
ЗАДАЧИ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ
1. На прямой отметили 10 различных точек. Сколько при этом получилось отрезков?
45
2. На окружности отметили 12 различных точек. Сколько при этом получилось дуг?
132
3. Сколько диагоналей в выпуклом 12-угольнике?
54
4. На плоскости проведены 10 прямых так, что никакие две прямые не параллельны и никакие три прямые не пересекаются в одной точке.
а) Найдите число точек пересечения этих прямых.
б) Сколько треугольников образовано этими прямыми?
а) 45; б) 120
5. В классе 12 учеников. Их нужно разбить на две группы (первую и вторую), состоящие из чётного числа учеников. Сколькими способами это можно сделать?
2046
6. Сколькими способами тренер может скомплектовать хоккейную команду, состоящую из одного вратаря, двух защитников и трёх нападающих, если в его распоряжении есть два вратаря, 5 защитников и 8 нападающих?
1120
7. Из трёх математиков и десяти экономистов нужно составить комиссию, в состав которой войдёт семь человек. При этом в ней должен участвовать хотя бы один математик. Сколькими способами может быть составлена комиссия?
1596
8. Сколько существует делящихся на 9 одиннадцатизначных натуральных чисел, в записи которых участвуют только цифры 0 и 8?
45
9. Трамвайный билет состоит из шести цифр от 0 до 9. Сколько билетов содержат ровно 5 одинаковых цифр?
540
10. Сколько существует способов составить комиссию из семи человек, выбирая её членов из восьми супружеских пар, но так, чтобы члены одной семьи не входили в комиссию одновременно?
1024
11. У Миши есть пять банок с красками разного цвета. Сколькими различными способами он может покрасить забор, состоящий из 7 досок, так, чтобы любые две соседние доски были разных цветов и при этом он использовал краски не менее чем трёх цветов?
20460
12. У Васи есть семь книг по математике, а у Вани — девять. Все 16 книг разные. Сколькими способами они смогут обменяться тремя книгами (то есть дать три книги в обмен на три книги)?
2940
13. Сколько существует 23-значных чисел, сумма цифр которых равна четырём?
2300
14. Лёша принес в класс 36 орехов и решил разделить их между собой, Максом и Борей. Сколько способов существует это сделать, если у каждого в итоге должен оказаться хотя бы один орех?
595
15. Три пирата Джо, Билл и Том нашли клад, содержащий 80 одинаковых золотых монет, и хотят разделить их так, чтобы каждому из них досталось не менее 15 монет. Сколько существует способов это сделать?
666
16. Сколько 9-значных чисел, делящихся на 5, можно составить путём перестановки цифр числа 377 353 752?
1120
17. Старуха Шапокляк решила обзавестись коллекцией из 50 саквояжей. В магазине ей на выбор предложили оранжевые, зелёные, фиолетовые и голубые саквояжи. Сколькими способами она может сделать покупку? Саквояжи одного цвета считаются идентичными.
23426
18. У Игоря Горшкова есть все семь книг про Гарри Поттера. Сколькими способами Игорь может расставить эти семь томов на три различные книжные полки так, чтобы на каждой полке стояла хотя бы одна книга? (Расстановки, которые отличаются порядком книг на полке, считаются различными.)
75600
19. Найдите количество семизначных чисел, в десятичной записи которых могут встречаться только цифры 4, 5, 6, 7 и таких, что каждая цифра не меньше предыдущей.
120
20. Даны две параллельные прямые, расстояние между которыми равно 2 см, на каждой отмечено по 10 точек, идущих через 1 см. Нужно из этих 20 точек выбрать 9 таких точек, чтобы расстояние между любыми двумя из них было не менее 2 см. Сколькими способами это можно сделать?
420
21. а) В таблице 3 × 4 надо расставить числа от 1 до 12 так, чтобы разность любых двух чисел, стоящих в одной строке была кратна 3, а разность любых двух чисел в одном столбце — кратна 4. Пример такой расстановки приведён на рисунке. Сколькими способами можно это сделать?
1 4 7 10
5 8 11 2
9 12 3 6
б) Можно ли расставить числа от 1 до 24 в таблице 6×4 так, чтобы разность любых двух чисел в одной строке была кратна 6, а разность любых двух чисел в одном столбце была кратна 4?
а) 144; б) нет
Размещения, перестановки и сочетания
