КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Принцип включения и исключенияПусть 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)= S n,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]
Дата добавления: 2014-01-06; Просмотров: 456; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |