Ещё одни лекции (1021740), страница 17

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 17)

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

Ярким примером эффективности комбинаторного подхода является теория бинома Ньютона. Все красивые результаты — различные соотношения между биномиальными коэффициентами — имеют простое комбинаторное истолкование.

Определение.

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

Если задана нумерация множества , то применяют следующие обозначения:

Теорема – правило суммы. Пусть и – конечные непересекающиеся множества, то есть , тогда

Доказательство.

Зафиксируем , нумерации и соответственно и рассмотрим отображение

,

заданное правилом:

Очевидно, – биективное отображение, тогда на основании основного принципа комбинаторики получаем

.

Теорема (следствие из предыдущей). Пусть и – конечные множества, тогда .

Доказательство.

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

. (*)

Очевидно, и множества , тогда из равенства правила суммы получаем

. (**)

Подставляя выражение для из (**) в (*), получаем

.

Теорема – правило включения-исключения.

Пусть – конечные множества, тогда

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

Доказательство.

Докажем формулу включения-исключения по индукции.

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

Здесь мы воспользовались равенствами

Теорема – правило суммы непересекающихся множеств.

Если – конечное попарно не пересекающиеся множества (т.е. , ), то

.

Ясно, что это тривиальное следствие из предыдущей теоремы.

56.Декартово произведение множеств.

Определение.

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

пусть

Теорема.

Если и – конечные множества, то – конечное множество и .

Доказательство.

Ясно, что в случае, когда одно из множеств , пусто, то и пусто и тривиально выполнено. Рассмотрим случай, когда и – непустые множества. Зафиксируем в нумерацию

.

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

(*).

Рассмотрим отображение , действующее по правилу

.

Ясно, что – биективное отображение, тогда по основному принципу комбинаторики получаем

(**).

Подставляя (**) в (*), получим:

.

Характеристики

Список файлов лекций