§4. Элементы комбинаторики

Комбинаторные задачи:

^{Магический квадрат. Одна из классических задач, фигурирующей еще в мифах Древнего Востока, является построение магического квадрата, т.е. расположение первых n2 натуральных чисел в квадрате nn так, чтобы все суммы по строкам, столбцам и диагоналям были одинаковы. Например, магический квадрат при n = 3:}

4	9	2
3	5	7
8	1	6

Определение числа магических квадратов для n > 4 – еще нерешенная задача.

Задача о 36 офицерах: 36 офицеров 6 различных воинских званий и из 6 различных полков так расположить в ячейках квадрата 66 , чтобы каждая колонна и каждая шеренга содержала только одного офицера каждого звания и из каждого полка.

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

Задача о 15 школьницах. Пятнадцать школьниц должны были гулять ежедневно пятью группами по три в каждой группе. Необходимо составить расписание для их прогулок так, чтобы каждая школьница в течение семи дней смогла только один раз попасть в одну группу с каждой из остальных.

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

Задача о размещении. Определить число размещений m различных предметов в n различных ячейках с заданным числом k пустых ячеек.

Комбинаторика – раздел математики, посвященный решению задач выбора и расположения элементов некоторого конечного множества в соответствии с заданными правилами. Каждое такое расположение элементов называется соединением. Простейшими примерами соединений являются размещения, перестановки и сочетания.

Размещением из n по m называется соединение по m элементов из

n-элементного множества, в котором важен порядок расположения элементов.

Число размещений из n по m обозначается через и вычисляется по формуле:

При n = m размещение из n по n называется перестановкой n элементов. Число таких перестановок обозначается через (последнее выражение читается «эн факториал»), и вычисляется так:

Сочетанием из n по m называется соединение по m элементов из

n-элементного множества, в котором не важен порядок расположения элементов. Число сочетаний из n по m обозначается через и вычисляется по формуле:

Имеют место следующие соотношения:

1.

2. - свойство симметрии.

3.

4.

5. - формула бинома Ньютона.

Пример. 1) Вычислить

2) Проверить

3)

4)

5)

1. Из пункта А в пункт В ведут 3 дороги, из пункта В в пункт С ведут 4 дороги. Сколько различных путей имеется из А в С?

2. На вершину горы ведут 4 дороги. а). Сколькими способами турист может подняться и спуститься с нее? б). Сколькими способами турист может подняться и спуститься с нее, если спуск и подъем должен происходить по разным дорогам?

3. Имеется четыре различных конвертов и пять видов марок. Сколькими способами можно составить письмо, если а) на конверт должна наклеиваться одна марка; б) на конверт надо наклеивать две марки ?

4. Для запирания автоматической камеры хранения применяется замок с числовым шифром, который открывается лишь тогда, когда набрано некоторое «тайное число». Пусть «тайное число» состоит из 4 цифр от 0 до 9. Сколько наибольшее число неудачных попыток может сделать человек, не знающий «тайного числа»?

5. Автомобильный номер состоит из 3 букв латинского алфавита и трех цифр от 0 до 9. Сколько можно составить различных автомобильных номеров?

6. Экзаменационный билет содержит 2 вопроса из 20. Студент выучил только 10 вопросов. Сколько можно составить различных билетов, и сколько из них могут оказаться «счастливыми» для этого студента?

7. В ящике находится 4 белых и 5 черных шаров. а). Сколькими способами можно извлечь 2 шара любого цвета? б). Сколькими способами можно извлечь 2 белых шара? в). Сколькими способами можно извлечь 3 черных шара?

г). Сколькими способами можно извлечь 2 шара разных цветов? д). Сколькими способами можно извлечь 1 белый и 2 черных шара ?

8. В первом ящике находится 4 белых и 5 черных шаров, во втором ящике находится 3 белых и 2 черных шаров. Из каждого ящика извлекают по 1 шару. а). Сколькими способами можно извлечь только белые шары? б). Сколькими способами можно извлечь только черные шары ? в). Сколькими способами можно извлечь шары разных цветов?

9. В первом ящике находится 4 белых и 5 черных шаров, во втором ящике находится 3 белых и 2 черных шаров. Из каждого ящика извлекают по 2 шара. а). Сколькими способами можно извлечь только белые шары? б). Сколькими способами можно извлечь только черные шары? д). Сколькими способами можно извлечь 2 белых и 2 черных шара?

10). В студенческой группе 20 человек. Необходимо выбрать старосту группы и его заместителя. Сколькими способами это можно сделать?

11). В студенческой группе 20 человек. Необходимо выбрать трех делегатов на конференцию. Сколькими способами это можно сделать?

12). Двум студентам подарили 15 яблок. Сколькими способами они могут поделить эти яблоки между собой?

13). Трем студентам подарили 20 яблок. Сколькими способами они могут поделить эти яблоки между собой?

Правило сложения. Если некоторое событие А может наступить в m случаях, а другое событие В может наступить в n cлучаях, то событие «А или В» может наступить в m + n случаях.

Правило умножения. Если событие А может наступить в m случаях, и в каждом из этих случаев событие В может наступить в n cлучаях, то событие «А и В» может наступить в mn случаях.

Примеры