Мегаобучалка Главная | О нас | Обратная связь

Основные правила комбинаторики





Условимся множество , содержащее элементов, называть, для краткости, -множеством. Напомним, что этот факт можно записать в виде .

1. Правило суммы. Рассмотрим следующую комбинаторную задачу: сколько элементов содержится в объединении m-множества и n-множества ? Ответ на этот вопрос очевиден в случае, когда множества и не пересекаются, т.е. . В этом случае множество содержит элементов. Таким образом, справедливо следующее утверждение: если множества и конечны, причем , то

(1)

В комбинаторике это очевидное утверждение называют правилом суммы иформулируют следующим образом:

Правило суммы.Если элемент а можно выбрать способами, а элемент b – m способами, причем любой способ выбора а отличается от любого способа выбора b, то выбор «а или b» можно сделать способами.

Сложнее обстоит дело, если пересечение множеств и не пусто. Например, объединение множеств = и = состоит из семи элементов: = , а не из 6 + 4 = 10 элементов. Это объясняется тем, что элементы принадлежат обоим множествам и , а в объединение входят лишь один раз. Поэтому из суммы 6 + 4 приходится вычесть число 3, т.е. число элементов пересечения . Вообще для любых конечных множеств и имеет место равенство:

. (2)

Таким образом, число элементов в объединении двух конечных множеств равно сумме чисел элементов в каждом из них, уменьшенной на число элементов в пересечении этих множеств.

Аналогично рассматривается вопрос о числе элементов в объединении нескольких конечных множеств . Если ограничимся только случаем, когда эти множества попарно не пересекаются (т.е. если при ), то с помощью математической индукции по числу к легко убедиться в справедливости равенства

(3)

Сложнее обстоит дело, если некоторые пары множества совокупности могут иметь непустые пересечения. Нам этот случай не понадобится и мы его опустим. Любопытный читатель может либо прочитать о нем в любой книге по комбинаторике, либо попытаться разобраться самостоятельно.

2. Правило произведения.Рассмотрим теперь следующую комбинаторную задачу: сколько элементов содержится в декартовом произведении m-множества A на n-множество В?



Ответ на этот вопрос дает следующее утверждение.

Т е о р е м а 1 (правило произведения). Если множество содержит элементов, а множество содержит n элементов, то их декартово произведение содержит элементов, т.е.

(4)

□ Пусть = и = .Выпишем элементы множества в виде прямоугольной таблицы:

, , …, ,

, , …, ,

…………………………………

, , …, .

В этой таблице m строк и n столбцов и поэтому число ее элементов равно , что и доказывает равенство (4).

В комбинаторике это утверждение называют правилом произведения иформулируют следующим образом:

Правило произведения.Если элемент можно выбрать способами, а элемент способами, то упорядоченную пару можно выбрать способами.

Теорема 1 обобщается на любое конечное число множителей в декартовом произведении.

Т е о р е м а 2 (обобщенное правило произведения).Если конечные множества содержат соответственно элементов, то множество имеет элементов, т.е.

. (5)

□ Применим индукцию по числу .

База индукции.При равенство (5) справедливо.

Шаг индукции.Предположим истинность равенства (5) для , т.е. что

, (6)

и рассмотрим . Легко видеть, что

= (7)

(это равенство вытекает из существования взаимно‑однозначного соответствия

между множествами и ). Используя теорему 1 и предположение индукции (6), отсюда получаем

= = . (8)

Из (7) и (8) следует теперь,

= .

Таким образом, мы доказали, что равенство (5) справедливо при .

Вывод.На основании обычного принципа математической индукции равенства (5) истинно при любом натуральном .





Читайте также:


Рекомендуемые страницы:


Читайте также:
Организация как механизм и форма жизни коллектива: Организация не сможет достичь поставленных целей без соответствующей внутренней...
Как построить свою речь (словесное оформление): При подготовке публичного выступления перед оратором возникает вопрос, как лучше словесно оформить свою...
Личность ребенка как объект и субъект в образовательной технологии: В настоящее время в России идет становление новой системы образования, ориентированного на вхождение...

©2015-2020 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (366)

Почему 1285321 студент выбрали МегаОбучалку...

Система поиска информации

Мобильная версия сайта

Удобная навигация

Нет шокирующей рекламы



(0.007 сек.)