Практическое занятие 4 «Комбинаторика»

1. Размещения с повторениями

Задача 1. Для запирания сейфов и автоматических камер хранения применяют секретные замки, которые открываются лишь тогда, когда набрано некоторое «тайное слово». Это слово набирают с помощью одного или нескольких дисков, на которых нанесены буквы (или цифры). Пусть на диск нанесены 12 букв, а секретное слово состоит из 5 букв. Сколько неудачных попыток может быть сделано человеком, не знающим секретного слова?

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

Задача 2. Найти количество всех пятизначных чисел.

Решение. Введем пять множеств: ,. Согласно правилу прямого произведения получаем.

Задача 3. При игре в кости бросаются две кости и выпавшие на верхних гранях очки скла­дываются. Какова вероятность выбросить 12 очков?

Решение. Всего возможно различных исходов. Из них только один (6 + 6) дает двенадцать очков. Вероятность 1/36.

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

Задача 1. Сколькими способами можно рассадить 4 учащихся на 25 местах?

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

.

Задача 2. Учащемуся необходимо сдать 4 экзамена на протяжении 8 дней. Сколькими спосо­бами это можно сделать?

Решение. Искомое число способов равно числу 4-элементных последовательностей (дни сдачи экзаменов) множества из 8 элементов, то есть способов. Если известно, что по­следний экзамен будет сдаваться на восьмой день, то число способов равно.

Задача 3. В хоккейном турнире участвуют 17 команд. Разыгрываются золотые, серебряные и бронзовые медали. Сколькими способами могут быть распределены медали.

Решение. 17 команд претендуют на 3 места. Тогда тройку призеров можно выбрать способами .

3. Перестановки без повторений

Задача 1. Сколькими способами можно разме­стить на полке 4 книги?

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

Задача 2. Сколькими способами можно упоря­дочить множество так, чтобы каждое четное число имело четный номер?

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

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

Решение. Определим число перестановок, в ко­торых данные два элемента истоят рядом. Могут быть следующие случаи:стоит на первом месте,стоит на втором месте, ...,стоит на-м ме­сте, астоит правее; число таких случаев равно. Кроме того,иможно поменять местами, и, следовательно, существуетспособов разме­щенияирядом. Каждому из этих способов соот­ветствуетперестановок других элементов. Следовательно, число перестановок, в которыхистоят рядом, равно. Поэтому искомое число перестановок равно.

Задача 4. Сколькими способами можно распо­ложить на шахматной доске 8 ладей так, чтобы они не могли бить друг друга?

Решение. При указанном расположении ладей на каждой вертикали и каждой горизонтали стоит лишь одна ладья. Рассмотрим одно из таких располо­жений ладей. Пусть — номер вертикали, в которой стоит ладья из первой горизонтали,— номер верти­кали, в которой стоит ладья из второй горизонта­ли, ...,— номер вертикали, в которой стоит ладья из последней, восьмой, горизонтали. Тогдаесть некоторая перестановка чисел 1, ..., 8. Среди чи­селнет ни одной пары равных, иначе 2 ла­дьи попали бы в одну вертикаль. Следовательно, каж­дому расположению ладей соответствует определен­ная перестановка чисел 1, ..., 8. Наоборот, каждой перестановке чисел 1, ..., 8 соответствует такое рас­положение ладей, при котором они не бьют друг дру­га. Следовательно, число искомых расположений ла­дей равно.