Учебник. Правила решения комбинаторных задач




Правила решения комбинаторных задач

Пусть множество A состоит из p элементов, а множество B состоит из q элементов. Составим новое множество A × B, состоящее из всех упорядоченных пар (a, b), где a A и b B.

Множество A × B называется декартовым произведением множеств A и B.

Очевидно, что множество A × B содержит pq элементов.

Правило произведения: декартово произведение множеств A и B, содержащих p и q элементов соответственно, содержит pq элементов.

Для нас будет удобна следующая формулировка правила произведения.

Пусть некоторый объект a можно выбрать p способами, а объект b – q способами. Тогда количество способов, которыми можно выбрать упорядоченную пару (a, b), равно pq.

Правило произведения легко обобщается на большее число объектов.

Сколькими способами можно поставить на шахматную доску чёрную и белую ладью так, чтобы они не били друг друга?

Чёрную ладью можно поставить на шахматную доску p = 64 различными способами. Независимо от выбора поля чёрная ладья бьёт 15 полей, поэтому для второй ладьи остаётся 64 – 15 = 49 полей, то есть q = 49. Всего число возможных способов, по правилу произведения, равно pq = 64 ċ 49 = 3136.

Ответ. 3136.

Сколько решений в натуральных числах имеет система { x+y=10, u+v=5?

Число 10 можно представить в виде суммы двух слагаемых девятью различными способами: 1 + 9, 2 + 8, ..., 4 + 6, 5 + 5, 6 + 4, ..., 9 + 1. Заметим, что решения (a, b) и (b, a) мы считаем различными, и потому нам важен порядок, в каком число 10 представлено в виде суммы. Аналогично, число 5 можно представить в виде суммы двух натуральных слагаемых четырьмя различными способами. Каждому решению (x, y) можно выбрать в пару четыре решения (u, v). По правилу произведения, количество решений системы равно 9 ∙ 4 = 36.

Ответ. 36.

Пусть снова множество A состоит из p элементов, а множество B – из q элементов. Предположим, что множества A и B не пересекаются. В этом случае множество A ∪ B состоит из p + q элементов.

Это соображение и носит название правила суммы.

Обычно в задачах применяют оба правила вместе.

Встретились 6 друзей, и каждый пожал руку каждому. Сколько всего было рукопожатий?

Каждый пожал руку каждому, то есть каждый человек сделал 5 рукопожатий. Но общее количество рукопожатий получается по правилу суммы: n1 + n2 + ... + n6 = 6 × 5 = 30. Учтём теперь то, что каждое рукопожатие мы посчитали дважды, и получим в результате 15 рукопожатий.

Ответ. 15 рукопожатий.





 

Пластиковые окна в москве от производителя
Онлайн-расчет стоимости окна. Продажа пластиковых окон и дверей
ladokna.ru
© Физикон, 1999-2015