Дискретная математика

п о поселения, как легко видеть, равно числу возможных разбиений 10 - элементного множества на подмножества с 5, 3 и с 2 элементами. Следовательно, искомое число равно: PflO,5,3,2J = - ^ = ^ ' ^ ' 8 ' ^ ' 1 0 = 2520. 5/3/2/ 2.3-2 2. Чему равно число различных расположений пяти букв А,А,В,В,В1 Это число определяем, как число возможных разбиений 5-ти элементного множества на подмножества с 2 и с 3 элементами. Следовательно, искомое число равно: Р(5,3,2)=~ = \0. 3/2/ § 6. Метод включения и исключения Этот метод применяется к важной задаче разбиения множеств на подмножества в зависимости от того, обладают ли их элементы определенной совокупностью свойств или нет. Пусть дано й-множество S некоторых элементов и т - множество свойств Pi, р2,-;Рт, которыми элементы множества S могут как обладать, так и не обладать. Выделим какую - либо г выборку свойств (рц, раPir)- Число элементов seS, каждый из которых обладает всеми г свойствами, обозначим через n(pii, Pi2,-, p t j . Отсутствие у элементов какого - либо свойства, например /?,•, будем обозначать через Таким образом, число элементов, обладающих, скажем, свойствами pi, рз, р^ и не обладающих свойствами/?2,/?^./'б. запишется как ръРз, Р4,Р5,Рб)- Сначала рассмотрим два простых случая, 1. Имеется только одно свойство, например, р. Тогда очевидно, что п( р)=п-п(р). 2. Имеется конечное число несовместимых друг с другом свойств pi, Р2,--,Рт (например, быть сферическими, кубическими, К0ничес1сими и т.п.). Снова очевидно, что п( pi, р2,, p j = п - En(pi). Перейдем теперь к общему случаю, когда элементы множества S обладают комбинациями совместимых свойств. Теорема 4.2. Пусть даны п - множество элементов и множество свойств Pi (\<i <т), совместимых между собой. Тогда число элементов, не обладающих ни одним из этих свойств р/, р2, ..., рт, равно; п( Pi , Р2,.... р^)=п- En(pi) + Y. n(pi, pj) - « j (4.7) - Z n(Pi, P J , Pt) + ... +(-1)'" n(Pl, P2,..., P,„). i<j<k