В.Н. Нефедов, В.А. Осипова - Курс дискретной математики (1127083), страница 30
Текст из файла (страница 30)
!ж Вен! 3.1.7. формула включений н исключений Пусть Х«, Хв — лва конечных множества. Тогда, если Х ПХз О. то (Х«ЦХ«(=(Х«)+(Хв!. Пусзь теперь Х«ПХ«~8. Тогда и )Х«)+)Хз! каждый элемент из Х«ПХ, будет учтен иье раза. Поэтому (ХЦХ,(=(Х,(+(Х,! — )ХПХ,), (330) т. е. мы выразнля котичество элементов е объединении множеств через количество элементов в их пересечении.
Получим соответствующую формулу лля произэальнсео чясла множеств, которая называется формулой включений и исключений Утверждение Д!1. Пусте Х,— конечные множестеа, 1=1, 2 ..., л, л~у Тогда )х Ц...Цх.!-Пх,)+...+(х.!)-Пх Пх.)+(х Пхз)-... ...+)К„«ПХ !)+((Х«ПХ«ПХ«(+...+)Х„«ПХ «ПХ,!) —... ...+( — !)«ы)х«П...ПХ,!. (3.1!) Доказательство будем проводить нндукцней по л.
Пре л=2 формула (3.1!) совпадает с (3.!0). Предположим. чка доказываемая формула верна для случая л — ! подмножеств, тле л:3. Докажем ее справедливость для л подмножеств. Разобьем множества Х«, ..., Х на две группы: Хь ..., Х„и Х„. Тогда согласнс (Э.10) получаем (хц...цх.! =! (хц...цх,) цх.(- =)хц...цх (+)х ! — )<хц...цх -)пх (= =(Хц...цх (+(Х )-)АЦ...ЦА — (, (ЭЛ23 гдеА, Х«ПХ,« !,...,п — 1. Используя индунтнвное предположение, имеем: а) )ХЦ-.ЦХ «)=()Х«)+ +(Х «!) — ()Х«ПХ«(+-.
-..+)Х -«ПХ «!)+((ХПХ«ПХ«)+...+(Х «ПХ «П ПХ» «!)-...+(-1)"(ХП..ПХ «): б) )А,Ц..ЦА.,(-()А,)+...+)А.,!) — ((А,ПА,(+ +(АПА«)+...+)А -«ПА в!)+.-.+( — 1)")АП...ПА «)= =((Х ПХ.)+...+(Х,ПХ !) — ПХ ПХ,ПХ.)+(Х ПХ«П ПХ»(+...+)Х -«ПХ «ПХ !)+--+( — Ц"!»(«П- Пх.! Иэ (3.12), учитывая «з». «б», получаем (3 11). 1Ео бдедсгене. Пусть Х вЂ” понечное множество, Хг, ..., Х вЂ” подмножества Х. Тогда (Хч(хгЦ..ЦК.)(=(К! — ЦК,(+...+(Х !)+((Хб)хо(+... ...+(Х ! —...+( — 1 "(Х ...
Х !. (3.13) Действительно. ':! В,(Х ц...цК.) )Ц(К Ц...ЦХ.) =К, Л,(ХгЦ...ЦК.ЦП(ХгЦ...ЦХ.) =а, откуда (Хь (Х,Ц...ЦХ„) (+(К,Ц ..ЦХ (=(Х(, а следовательно. ! Хч(Х Ц...ЦК.) ! = ! К! — (К Ц...цК.!. (3.14) Для получения (3.13) остаегся только в (Зцв) применить рмулу (3.!». Приведем теперь еше одну (наиболее распространенную) форму записи формулы включений и исключений. Пусть Х— конечное мпожество, состоящее ив И элементов, аь ... а — не- каюрые свойства (одноместные предвкаты, определенные на К), которыми могут обладать или пе обладать элементы из Х.
ОбозначниТ1«н(1, 2, .... а) Хг (хгмХ(ги(х)) — множество эле- менюв в Х, обладающих свойством а,. Обозначим также И(агг ...,«ь)=(Ха()...ПХ1, (=((хщХ(аб (х)6...6«1,(х)) ! — ко- личество элементов в Х, облалающих одновременно свойствами аа, ..., аи; Ио= (Хч(Х1Ц...ЦК ) ! — количество элементов в Х, не обааллющих ви одним из свойств аь ..., а,. Тогда по формуле (3.13) получим Ио И вЂ” Юг+ус —... +( — »"5, (3. 16) тзе Л( ,..., ог ), а 1, Э,...
о. Х 1ЩЬ«... С! Що Пэоокэ З.14. Пусть о 3.. о. висовсо рв свовсгоог аь о„с, Тогда ю (З 1Е) И, И вЂ” И(а,) — И(ао) — И(щ)+И(лг, ас)+И(аь ао)+ +И(аь ао! — И(аь аь «о). (3.16) Пример 3.13. Пусть Х= (О,1, ..., 10); а, (х): «х четное»; ос(х)1 «х)бж ао(х): «2<х(8». Подсчитаем количество Ио элементов а Х, не обладающих свобствами ль ас, ао.
Исполщуя формулу (3.16), получаем Ио=11 — 6 — 4 — 6+2+2+1 — 0=! (нетрудно ввлеть, что единственным элементом в К, не обладаюоким свойствами аь аь аз, является число». И! Пример 818. Применяя формулу включений и исключений, задачу оаределения количества целочисленных решышй системы хэ+кэ.!....+к =г, а;<кг<Ьэ, 1=1, 2, ..., и, (38 7) где аэ, Ьь г — целые числа; аэ<Ьь 1=1.
2, ..., л, легко свести к совокупности задач определения количества целочисленных ре- шений систем вида (3.1). Для этого необходимо воснольэоваж ся свойствамн а;(х); «хт>бэ+1», где х=<хь ..., к >, 1=1, 2... ., л, а зз исходное множества Х взять совокупность целочислен. ных решений х системы (3.!). Пусть Ьг — количество целочислен. ных решений системы (3.1).
Тогда Ь ю определяемое яо формуле (3.13), и будет выражать количество целочисленных решений системы (3.17). Прюлер 8.17. Определим количество трекэначных чисел, м которых сумма цифр равнястси 20. Если через кь хэ, х, обозначить соотвеютвенно первую, вто- рую и третью цифры в произвольном трсяэначном числе а= =х, ° 10'+хэ 1О+кэ, то для решения задачи достаточно опре- делить количество целочисленных решений системы кэ+к,.(.кэ 20, 1<к,<9, 0<хэ<9 0<хэ<9. (3.18» Пусть Х вЂ” множество целочисленных решений х=<хь х,„ к,> снстемм хэ+хэ+кэ=й(, кэ.'Ю1. хэВтО. хэ>О, й( — количество элементов в Х.
Введем следуюшие три свойства: аэ(х)г «хэ>10»; аэ(х): «хэ>10»; аэ(к): гхэ 10». Используя теперь формулу включений н исключений (3.16), а также формулу (3.3) для подсчета ноличесгва целочисленных решений в системе вида (3.1), определим число Ьээ целочислен- ных решений системы (3.18): Ыэ Сэы-э ('э о — эо ('ээо-ээ-э Сэпо-ээ-э ( С то-э™ 1 +Сэпо 'э 'э+Π— О=Стгы — С~ээо — 2Сэр-1-2= =-210 — 86 — 110+2=36. Пример 818 (задача о беспорядках). Имеется л различных нредмеюв аэ, а„..., а, н л различных ячеек Ьь Ь, Ь,. Сколь- кими сиособвмн можно разместить аредметы ло ячейкам так.
чтобы никакой предмет аг не повал в ячейку ЬП В пвчсствс яскодяого вожсствв Х воээпсл совокгмюсть эссвоэиожямк рвсяоложсяяа пред стон ло ячсвкэм. тогда л !х! лэ Ввод« слов«тая ас э лэходлмв в сакс ьэь 1 1. ц..., л, чвсло х(о ., оэ! рвс- иоложсяяа, лря катарах предлог о,, явждп ся в ячейке Ьэ„, 1,... а. рвало (л — Э)1 Но ж дв 1(Э ггг 6,- ~~~~ и( Ч,...,ом1-0*.( ЬИ- — „, . 1<г « ... г.< Иепольеу» мперь формулу ммючеппа л пе чючеплз (ЗЛВ], по учмж.
чге члсло я р о олмп А, прп «о ормл пп олею пл зовете ле емполплеюл (ч. е по олпе и прел ееоа и, гм попел е и «Зпу И], тлело лг я+ х ( — цьх.- ег+ х ( — ц» — =- пг х ( — гр —. Зиаачн и упражнения 1. Сколькими способами можно дать клички четырем щенкам, имея семь возможных вариантов (щенки названм по-рва.ному)? 2. Сколькнмн способами можно раскрасить квадрат, разделенный иа девать частей (см.
рис 3.2), пятью цветами, допуская окрашиаанне разных частей в один цвет? 3. Сколькггми способами можно разместить 03 различных шаров по трем различным урнам? 4. Обосновать (без испольвования формул) С",=Сл ,+ +Сь-г., 5. Спределвть количество прямоупгльных матриц размерности гиХл с злементама из (0,1) с попарно равличнымн строкамн (зг<2"]. 6. Ив колоды, состоящей из 52 карт, выбрали 1О карт. Оп. ределпть„ в скольких случаях среди них окажутся: а) пиковая дама; б) все четыре дамы; в) все карты одной масти; г) ни одного туза; д) ровно один туз; е) хотя бы один туз; ж) ровно два туза.
7. Имеются монеты по 1, 2 и 3 конейки; всего 20 монет. Сколько существует различных комбинаций монет? 6. Сколькими способами можно разложить 20 одинаиовых шаров по четырем различным урнам? 9. Определить количество целочисленных решений системы .«г+хе+ге=40, хг~З, ле)0. хе~2. 1О. Сколькнмн способами можно разложить 20 различных шаров по трем различным урнам тан, ччобм в первой, второй н трспмй урнах находилось соответственно 5, 3 н 12 шаров? 11. Сколькими способами группу из 25 человек можно разбить нв семь коалиций: 2 — по 5 человек, 1 — 7 человек, 4— па 2 человеиа? 12. Определить коэффициент й в следующих членах много- члена (с приведенными подобными членами), получаемого из алгебоанческого выражения (а+Ь+с]'(а*.(-Ь*-]-с') ° г а) йа'Ьес', 5) йиейгсь, в) Ьлейег г) Ьогбзсе. 13.
Определить количество целочисленных решений системы хе+хе+хе=40, 4<хе<15, 9<хе<16, 5<хе<16. ггз !4. Определить ьоаичаство шестизначных чисел, в когорык сумма первых трех цифр ажпааает с суммой последних трех цифр. 1б Найти количество целых щшохщгсльных чисел, не превосходящих 2)0 и ис делящихса ии иа одно нз простых чисел- а) 2,3,3; б) 7, 11, 13. 3.2. РЕШЕНИЕ ЗАДАЧ ПЕРЕСЧЕТА МЕТОДОМ ПОИЛ 3.2.1. Реализация труним Пусть Х вЂ” некоторое конечное множество элементов, 3(Х)— группа всех биехтпвпых отображений множеспга Х в себя, 0— неюипрая группа.
Под реалиапйией С в 5(К) будем понимать любой гомозюрфизм тгС-эЯ(Х). Дл» простоты обозначений вместо т(й), где йщС, пишем тг, а вместо тг(х), где хщК,— йк Нример 339. Пусть К=1Р— множество точек иа плоскости. 5 (31*) — группа бисхтивиих отображений йу в себя, 0 — группа вращений на плоскости вокруг начальной точна 0(00). Элементы группы С будем обозначать угламн вращений, при этом в качестве положительного выберем направление против часовой стреляи.
Пусть, например, 6 (пщй[0«и«шг). Бинарной операцией па 6 является последовательное выполнение вращений. Обозначим указанную операцию символом Ю. Тогда, очевидно, выполнястс» равенство нш()нц [ н+й. ы. и+О«2 ц ( и+3 — 2и, сслн а+3~2и. Единичным элемантом в группе 0 является вращение иа угол О н УпщСч,(0) а-'=Ул — а. Под рсализзписй введеиной группы С будем попинать отображение, ставящее в соответствие каждому вращению и биекцию тл 1Р йг такую, что для любой точки Мщйг точка т.
(М) есть результат перемыпения точки М после поворота вектора бМ на угол с против часовой стрелки. Тогда, например, я)2(1, 0) =т п[(1, О)) = (О, 1) (рис. 33). 144 3.2.2. Действие групгпг па ииожесгве Пусть сохраняемся условия, описаивые в разд. 3.2.1, и т — некоторая реализапия С в 5(Х). Заметим.
что поскольку прв гомомарфизме едиивчпый элемент отображается иа единичный элемент, то УМВХ ех х, (3.19) где е — едвипчпый элемент из С. Кроме того, по определению гомоморфизма ТхевХ. Ц йспа т,ь(х] (щ(х])=2( ), откуда Тгхгых, Тгй, йгжС (ЗЛ)х йг(йх), (320] Всякий раз, когда имсетсе отображение ~2, х)-ьйх прямого произведения С)(Х в Х, удовлетворяющее свойствам (3. 19), (3.20).
будем говорить, что группа С действует па миожесгве Х. В определении действия группы С иа миожестве Х явным образом пе используется гомоморфизм т, а следовательно, действие группы яа множестве можно вводить иепосредствепио, без прелварительяого указания гомоморфизма т. Тем ие менее в последнем случае можно по формуле тз(х)=-йх, хщХ, (3.21) для каждого йюС однозначно овределвть отображение тз; Х-ь К, и при этом отображение т:Х тг будет гомоморфизмом группы С в 8(Х). Дсйствитсльио, используя (3.19), (ЗМ), пот лучаем, что для любого влемеита ЗщС выполпяются условия УхепХ те г(те(х))=й Г(йх)=(у 2)х=ек=х; (322) ТгхспХ чз (те ~(х) ) 2(й '.т) ( йй-г]х ех х, (Зло) атвуда следует, что ТгйгыС та — биекющ из Х в Х (ив (3.23) по.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
