Главная страница | Контакты | Случайная страница Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Принцип включения и исключения.

Пусть A₁,…,A_n некоторые подмножества (необязательно различные) конечного множества Х.

Теорема 1.(Принцип включения и исключения).

- + -…(-1)^n-1| |

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

Применим математическую индукцию по n.

Для n=1 терема очевидно справедлива!

Предположим, что для произвольных A₁,…,A_n-1 выполняется

| |= - + -…(-1)^n-2| |

Применяя эту формулу к сумме

,

получаем

| |= - +…(-1)^n-2| |,

а отсюда

| |= = +|A_n|-| |=

- + -…(-1)^n-1| |.

Покажем несколько применений принципа включения и исключения

Теорема 2. Пусть |X|=n, |Y|=k, то число всех функций f:X®Y и f(X)=Y, равно

S _n,k=

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

Пусть У={y₁,…,y_k} и A_i={f: f:X®Y & y_iÏf(X)}, тогда

f(X)¹YÛfÎ

Множество всех f:X®Y имеет мощность kⁿ. Определим , пусть 1£p₁£…£p_i£k пересечение есть множество всех функций f:X®Y таких, f(X), a, следовательно, мощность этого пересечения ровно (m-i)ⁿ. Согласно теоремы 1 имеем

S _n,k=kⁿ-| |=kⁿ- =

Эта формула дает простое выражение для вычисления чисел Стирлинга 2^го рода

S(n,k)= S_n,k =

Рассмотрим вопрос об определении числа “беспорядков” на множестве {1,…,n}

Определение. Под беспорядком на множестве {1,…,n} будем понимать произвольную перестановку f этого множества, такую что f(i)¹i для 1£i£n.

Пусть D_n – множество всех беспорядков на {1,…,n} и

A_i={fÎS_n: f(i)=i}, i=1,…,n.

Заметим, что fÎD_n ÛfÏ A_i для "iÎ{1,…,n}, следовательно

|D_n|=|S_n|- + - +…(-1)^n-1| |

Для произвольной последовательности 1£p₁£…£p_i£n пересечение является множеством таких перестановок f, для которых f(p_j)=p_j для 1£j£n, и значит, | |=(n-i)!. Заметив, что последовательность 1£p₁£…£p_i£n можно выбрать способами, получаем в итоге

|D_n|= = =n!()

Отметим, что сумма в скобках является начальным членом ряда е^-1= . Это означает, что беспорядки составляют е^-1=0.36788… всех перестановок.

Перечисление графов [5]