(0 голоса, среднее 0 из 5)

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

Пусть множество 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.

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

Пример 1

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

Решение

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

Ответ. 3136.

Пример 2

Сколько решений в натуральных числах имеет система 

Решение

Число 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 элементов.

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

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

Пример 3

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

Решение

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

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



Похожие статьи:
Следующие статьи:
Предыдущие статьи:

Комментарии
Добавить новый Поиск
Оставить комментарий
Имя:
Email:
 
Тема:
UBB-Код:
[b] [i] [u] [url] [quote] [code] [img] 
 
 
:angry::0:confused::cheer:B):evil::silly::dry::lol::kiss::D:pinch:
:(:shock::X:side::):P:unsure::woohoo::huh::whistle:;):s
:!::?::idea::arrow:
 
Пожалуйста, введите проверочный код, который Вы видите на картинке.

3.26 Copyright (C) 2008 Compojoom.com / Copyright (C) 2007 Alain Georgette / Copyright (C) 2006 Frantisek Hliva. All rights reserved."

Поиск по сайту

Голосование

Вы бы поддержали сайт новыми материалами за символическую плату?
 

Сейчас в чате



Нет пользователей online



Rambler's Top100