ОБЩИЕ ПРАВИЛА СЛОЖЕНИЯ И УМНОЖЕНИЯ

​АННОТАЦИЯ

Комбинаторика - раздел математики, в котором изучаются задачи выбора элементов из заданного множества и расположения их в группы по заданным правилам, в частности задачи о подсчете числа комбинаций (выборок), получаемых из элементов заданного конечного множества. В каждой из них требуется подсчитать число возможных вариантов осуществления некоторого действия, ответить на вопрос «сколькими способами?».  Многие комбинаторные задачи могут быть решены с помощью следующих двух важных правил, называемых соответственно правилами умножения и сложения.

Ключевые слова: правила умножения, правила сложения, принцип индукции, множество.

Правило сложения для двух множеств выражает основное свойство числа элементов конечного множества. Это правило можно принять в качестве аксиомы. Интуитивно оно представляется очевидным.

Условимся число элементов конечного множество  обозначать символом .

Правило сложения. Число  элементов суммы  не пересекающихся конечных множеств  и  равно сумме  чисел  и  элементов этих множеств.

Правило сложения можно записать коротко следующим образом:

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

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

Общее правило сложения. Число  элементов суммы  попарно не пересекающихся конечных множеств  равно сумме  чисел  элементов этих множеств.

Рассмотрим множество  всех номеров  таких, что общее правило сложения верно для всех семейств  попарно не пересекающихся конечных частей  множеств , имеющих множеств индексов , составленное из  элементов.

1. . Это вытекает из определений. В самом деле, если множество  имеет 0 элементов (то есть является пустым множеством  ), то, по определению, сумма  пустого семейства множеств  равна пустому множеству , а сумма  пустого семейства чисел  - числу 0. И следовательно,

 .

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

.

Множество  состоит из  элементов. Поэтому, если , то

,

и, следовательно,

,

то есть, .

Таким образом, условия 1 и 2 принципа индукции выполнены значит, множество  совпадает с множеством  всех натуральных чисел. Общее правило сложения верно.

Из общего правило сложения выводится правило умножения.

Рассмотрим произвольные множества  и . Каждые элементы  и  определяют упорядоченную пару . Множество всех таких пар образует декартово произведение  множеств  и .

Правило умножения. Число  элементов декартова произведения  конечных множеств  и  равно произведению  чисел  и  элементов этих множеств.

Для каждого элемента  обозначим символом  множеств всех упорядоченных пар , составленных из элемента  и произвольного элемента :

Эти множества попарно не пересекаются, и число элементов в каждом из них равно числу элементов множества :

.

Сумма всех множество  равна декартову произведению  множеств  и :

.

По правилу сложения из сказанного следует, что

.

Правило умножения доказано.

Общее правило умножения. Используя принцип индукции, легко вывести из правила умножения общее правило умножения для конечного семейства множеств.

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

.

В частности, если , то единственным элементом множества  является пустая часть множества .

Если  для каждого индекса , то декартово произведение семейства  называется декартовой степенью  множества  и обозначается символом . Это множество образовано всеми отображениями множества  в множество  или, что эквивалентно, всеми семействами элементов множества , имеющими множество индексов .

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

Рассмотрим семейство  конечных частей  множества , имеющее конечное множество индексов .

Число  элементов декартова произведения  конечных множеств  равно произведению  чисел  элементов этих множеств.

Рассмотрим множеств  всех номеров  таких, что общее правило сложения верно для всех семейств  конечных частей  множества , имеющих множество индексов , составленное из  элементов.

1. . В самом деле, если  и, следовательно, , то единственным элементом произведения  является пустое семейство. В то же время произведение , по определению, равно единице. Значит,

.

2. Для каждого натурального числа , , то . В самом деле, рассмотрим семейство  конечных частей  множества , имеющее множество индексов , составленное из  элементов. Рассмотрим также произвольный элемент  и множество  остальных элементов. Отображение

является изоморфизм множества  на множество . Следовательно, число элементов в этих множествах одинаково:

.

Из правила умножения вытекает, что

.

Множество  состоит из  элементов. Поэтому, если , то

и, следовательно,

,

то есть .

Таким образом, условия 1 и 2 принципа индукции выполнены и, значит, множество  совпадает с множеством  всех натуральных чисел. Общее правило умножения верно.

Список литературы:

1. Виленкин Н. Я. Комбинаторика. М., «Наука», 1969.
2. Риордан Дж. Введение в комбинаторный анализ. М., ИЛ, 1963.