Читайте также:
|
|
Пусть A1,…,An некоторые подмножества (необязательно различные) конечного множества Х.
Теорема 1.(Принцип включения и исключения).
- + -…(-1)n-1| |
Доказательство
Применим математическую индукцию по n.
Для n=1 терема очевидно справедлива!
Предположим, что для произвольных A1,…,An-1 выполняется
| |= - + -…(-1)n-2| |
Применяя эту формулу к сумме
,
получаем
| |= - +…(-1)n-2| |,
а отсюда
| |= = +|An|-| |=
- + -…(-1)n-1| |.
Покажем несколько применений принципа включения и исключения
Теорема 2. Пусть |X|=n, |Y|=k, то число всех функций f:X®Y и f(X)=Y, равно
S n,k=
Доказательство
Пусть У={y1,…,yk} и Ai={f: f:X®Y & yiÏf(X)}, тогда
f(X)¹YÛfÎ
Множество всех f:X®Y имеет мощность kn. Определим , пусть 1£p1£…£pi£k пересечение есть множество всех функций f:X®Y таких, f(X), a, следовательно, мощность этого пересечения ровно (m-i)n. Согласно теоремы 1 имеем
S n,k=kn-| |=kn- =
Эта формула дает простое выражение для вычисления чисел Стирлинга 2го рода
S(n,k)= Sn,k =
Рассмотрим вопрос об определении числа “беспорядков” на множестве {1,…,n}
Определение. Под беспорядком на множестве {1,…,n} будем понимать произвольную перестановку f этого множества, такую что f(i)¹i для 1£i£n.
Пусть Dn – множество всех беспорядков на {1,…,n} и
Ai={fÎSn: f(i)=i}, i=1,…,n.
Заметим, что fÎDn ÛfÏ Ai для "iÎ{1,…,n}, следовательно
|Dn|=|Sn|- + - +…(-1)n-1| |
Для произвольной последовательности 1£p1£…£pi£n пересечение является множеством таких перестановок f, для которых f(pj)=pj для 1£j£n, и значит, | |=(n-i)!. Заметив, что последовательность 1£p1£…£pi£n можно выбрать способами, получаем в итоге
|Dn|= = =n!()
Отметим, что сумма в скобках является начальным членом ряда е-1= . Это означает, что беспорядки составляют е-1=0.36788… всех перестановок.
Перечисление графов [5]
Дата добавления: 2015-09-11; просмотров: 28 | Поможем написать вашу работу | Нарушение авторских прав |