Основные правила комбинаторики
Условимся множество , содержащее элементов, называть, для краткости, -множеством. Напомним, что этот факт можно записать в виде . 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-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (600)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |