Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 162
Текст из файла (страница 162)
9. ()Р 11. Число, которое делится на 7, 2 или 5, есть 2730+ 1092+ 780 — 546 — 390 — 156+ 78 = 3588. Число, взаимно простое с 700, равно 5640 — 3588 = 1872. 906 Ответы к упражнениям 9. В(х, С) и 1 + Вх + 15хз + бхз. 11. В(х, С) = (1+ 2х)(1+ х)(1+ 4х+ 2хз). 13. В(х, С) = 1+ 4х+ 68хз+ 148хз + 14424 + 48хз количество размещений равно 8! — 14 ° 7! + 68. 6! — 148 5)+ 144 4! — 48. 3! = 4128.
15 В(х С) — 1+бх+11хз+бхз количество размещений равно 5! — 6 4! + 11 3! — 6 2! = 30. 17. В(х,С) = 1+ 12х+ 54хз 4-112х~ 4-108х~+ 48хз +Вхе, количество размещений равно 6! — 112 5! + 54 4! — 112. 3! + 108 2! — 48 1! + В О! = 80. 19 В(х С) = 1 + 82 + 20хз + 16хз 4- 4х4 количество размещений равно 4! — 8 . 3! + 20 2! — 16 1! + 4 О! = 4. 21. В(х, С) = 1 + 13х + 59хз + 115хз + 100х4 + 32хз, количество размещений равно 6! — 13 5! + 59 4! — 115 3! + 100 2! — 32 = 54. 23 В(х С) = 1+Вх+20хз ! 16хз+4х4 количество размещений равно 4! — 8 3!+ 20 2! — 16.
1! 4-4 = 4. 25 В(х С) = 1 + 102 + 35хз + 5022 + 2624 + 424 количество размещений равно 5! — 10 4! + 35 3! — 50 2! + 26. 1! — 4 = 12. 27. В(х, С) = 1 + 10х + 35хз + 50хз + 25х4 + 2хз, количество размещений равно 5! — 10 4! +35 3! — 50 2! + 25 1! — 2 = 13. Раздел 13.2. — 1 1 — 1 3 1.
а) — + —; 6) — + —: в+4 х+3' х — 2 х — 3' 2 14 г) 2 + 3 д) + х — 1 х — 2 (х — 3)' х — 1 3. а) 4(1 — 4х+ —,'ех 44х + +( — -,)"х" +..); б) 14(1+ .Ч- $х'+-зх'+."+( — )х" +" ): в) — 1 — Зх — 6х — 10х г з и(и+ 1) х" — "; 2 г) -х+ -х + -х + + — х" +. ззтз2" — 1 2 4 З 29 2 13 А) — - — -х — — х — ° ° ° — (4и — 6+ — )х 2 4 З 2"+4 5. а) а = 3"+' — 2"+', б)о = 43 — 2и — 4! г) а„= 2" — и2"; д) а„=2" +3.
и +и+2 7. а)а 2 в) а = (и+ З)2" — и — 2; -10 6 11 в)— + (х 1)2 х 2' 4 14 13 (х — 1)2 х — 2 (х — 2)2 ' + в) а = 6 3" + 2(-1)"; б) а„= -2 2" +4 3"; г) а = (Зи — 3)3" + 4 . 2". Раздел 13.3. 1. а)(1+х+х + . ) (1+х+х)(1+х+х +х +х); б) (1+х ! 2 ! )2(1 ! !,2 ! .2)(1 ! 2 ! 4+ е ! ). в) (х+х +хе+ х + )(1+х +х4+х + )(1+х+х + . )(х +х +х +х + .); г) (х + х + хз + ) (х + х + х4 + .. ) (х + х4 + х + . ) (х4 + х + х -!- х" + ); д) (1+х+х + ° )(1+х +х4+...)(1+х +х + . )(1+х4+х Ч- .
). 3. а) (1+х+ х + хе + х4)(1+ х+хе + ха)(1+х+ хз+ .. +хе)(1+х+хе); 6) (х+х~)(х+ хе+ х +х4+х'Их+ха+ха+ 4)( +,г+ 2). в) (1+х+х + +х )(х +х + +х ')(1+х+х + +х )(1+х +х4+ х ); г) (х +х4++х )((х+х +х ++х' )(х+х +х +х )(х +х4+ х ). Ответы к упражнениям 907 5 (1+х+х + ..)(1+х +х' + )(1+х' +х + )((1+х +хз + ). 7 (1+ з+ 4+,.)(1+ з+ 1о+,.) д (1+ ! 2+ 3+ 4+ з+ 6)ь и. (';). 13.
1. С) 17. 51. (14) 5ьз 21. а) Зб; б) ЗО. 25. (,';) -з(';)+з(,'). 25. г(х) — хг(х) — х Г(х) = = ао+ а1Х+азх +азх + а4х + азх + 2 3 4 З вЂ” аох — агх — азх — азх — а4х + " 2 3 4 3 — аох — агх — азх — азх + = ао+ (аг — ао)х = поскольку во = О и аг = 1. Следовательно,(1 — х — х~)Г(х) = х, так что х х Р(х) = 1 — х — хз 1 — (х + хз) Воспользовавшись разложением, получаем Р(х) =х(1+(х+хз)+(х+ х)'+(х+Х)'+(х+х')'+".= = х + х (1 + х) + х (1 + х) + х (1 + х) + х (1 + х) + Коэффициент при х"+' в выражении хь+г(! + х)", если существует, то равен („"„). Суммируя по к = и, и — 1,а — 2,..., имеем Раздел 13,4 .
1. 15. 1 1 1 1 1 1 1 — х ! — Х2 1 — ха ! — х4 ! — Х5 ! — хе 1 1 1 1 1 .4 ! 4 1 з 1 ю 7. В строках, начиная с верхней, представим каждую часть разбиения на четные величины. Теперь, глядя на столбцы, видим, что представленные части разбиения присутствуют парами и убывают по размеру. Поскольку рост в строке влечет за собой увеличение четного числа, в столбцах это порождает пару или пары одного размера. ° ° ° ° ° Ф ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° 908 Ответы к упражнениям 9. Пусть столбцы изображают разбиение 2о обьектов на и частей.
° ° ° ° Ф ° ° ° ° ° ° ° ° ° ° 1 1 1 1 1 1 1 4 Раздел 73.Б. б) ( 1+ — *,1+ т' + 101) ( + 11+ 21 + 21) ( с 11+ 21 + 3' + 4')' ( +1'+ 2'+ 10')( + 3'+ ' т' э')( 2' 4' 1о')' 3. е*. 5. Производящая функция ез — 2е4* + ез*, количество способов 5" — 2 4" + 3". 7. Производящая функция е'* — Зег* + Зе* + 1, количество способов 3'о — 3 2'о -Ь 3. 9. Производящая функция -' (е4 — 2ез + ег* — 1+ 2е * — Зе г ), количество способов 2(424 2 Згз + 224 + 2( цгз ( 2)гз) П 4 з 10 гак 41 13. (е* — 1)(ег* — 1)(ез — 1) (е" — 1).
х х 2 15. а) (е — 1) = (1+ — + — + ..) — 1 = 1! 2! х х' = — + — + 1! 2! е+е 1 х х 1 х х х б) = -(1+ — + — + )+-(1 — — + — — — ) = 2 2 И 2! 2 1! 2! 3! хг х = -(2+2 — +2 — ) = 2 2! 4! 2 4 =1+ — + — +...; 2! 4! е — е * 1 х х 1 х х х в) = -(1+ — + — + ".) — -(1 — — + — — — ".) = 2 2 1! 2! 2 1! 2! 3! 1 х' х' = -(2х+2 — +2 — ) = 2 3! 5! х' х' = х+ — + — + ° 3! 5! Поскольку ни одна из этих частей не пуста, то нижняя строка содержит и элементов. Если отбросить эту строку, то легко увидеть, что другие строки образуют разбиение и элементов.
Ответы к упрагкнениям 909 б) гомоморфизм не сушествует; в) У(вз) = с; П 2)=6; Пв1) = У( 4) = а; г) У(вз) = У(вз) = У(вз) = а; У(вг) У(в4) У(вз) 61 д) Пш) = Пвз) = с; Пвз) = У(ве) = 6; У(вг) = У(в4) = а; е) У(в1) = У(вз) = У(вз) = У( т) = с; У(вз) — У(в4) = а; У(вг) = Пвз) = Ь. д) графы не изоморфны, вершина Н имеет степень 4, ни одна из вершин первого графа не имеет степень 4; е) графы не изоморфны, первый граф несвязный, второй граф — связный.
б) объединение; а Ь пересечение; Ь с пересечение; :П Раздел 14.1. 1. а) У(вз) = Пвг) = а; У(вз) = Пвз) = 6; Пвз) = с' 3. а) графы не изоморфны б) У(вз) = а; У(вг) = 6; У(вз) = с; У(в4) =4 б. (а), (с). 7. (а), (с), (е). 9. а) объединение; разное количество вершин; в) Пве) = а; У(вг) = )1 У(вз) = е; Пв4) = Ь; Пвг) = с; Пвз) =У; г) У(вз) = е; У( 4) =У; У(вг) = а; У(вз) = Ь; У(ве) = 2; Пвз) = с; 910 Ответы к упражнениям в) объединение; а Ь с г) объединение; д) объединение; Н с / пересечение; пересечение; пересечение. се 11.
а) с б) в) се ° Ф г) д) е) Уз Уг сз Уз мз и ° ° !3. (а); (Ь). 15. С имеет еид С' имеет вид У: С вЂ” С' задана соотношениями Да) = с; 1(Ь) = о. 17. Пусть/: С С'. Пусть а,ЬЕ ДЪ'). Тогда а = Дх),Ь = Ду) для некоторых х,у Е Г. По- [! :1 с а ь ° ° ;1 ;1 ае — е е — еС ь с Ь Огпеегпы я упрвжненцям 91 1 скольку граф С полный, то существует е = (я, у). Поэтому 7(е) = (а, Ь), Следовательно, между двумя любыми вершинами графа г'(У) имеется ребро, и граф /(С) — полный.
19. Пусть о б У. Имеется наибольший связный граф, содержащий о. Поэтому е принадлежит компоненте. Пусть е б Е. Имеется наибольший связный граф, содержащий е. Поэтому е принадлежит компоненте. Следовательно, граф С(Е, У) — объединение компонент, и, по теореме 12.17, они являются попарно непересекающимися. 21.
Эквивалентно показать, что если С'(Е', У') — расширение графа С(Е, У), то один является связным тогда и только тогда, когда связным является второй. Предположим, что граф С связный и ребро а6 заменено путем асЬ. Пусть ш и оз — вершины в графе С. Поскольку С связный, то существует путь из оз в оз. Если ребро аЬ входит в путь, заменим его на асЬ, и еы оз остаются связанными в графе С'.
Обратно, если С' связный и ш, оз б С', то в графе С' существует путь из о~ в оз. По определению расширения, только ребра, инцидентные вершине с, являются инцидентными вершинам а и 6. Следовательно, любой путь, включающий с, должен включать путь асЬ или 6са. В графе С путь асЬ можно заменить на а6, а путь Ьса можно заменить на Ьа, так что путь из сч в оз по-прежнему существует. 23. Если 7; С(Е, У) - С'(Е', У') — изоморфизм, то он задает взаимно однозначное отображение из Е на Е' и взаимно однозначное отображениее из У на У'.
Таким образом, С и С' содержат одинаковое количество ребер и вершин. 2$. Пусть 7: С(Е, У) — С'(Е', У') — изоморфизм. Вершины а и Ь принадлежат одной и той же компоненте графа С тогда и только тогда, когда существует путь аогее сь ~Ь из а в Ь, тогда и только тогда, когда существует путь /(а)/(о~Щиз) ..7(се ~ЩЬ) из 1(а) в /(Ь), тогда и только тогда, когда 7"(а) и /(6) принадлежат одной и той же компоненте. 27. Пусть У; С(Е, У) — С'(Е', У') — изоморфнзм. Поскольку с1ек(о) = бек(/(о)) для всех о б У, то все вершины в У имеют четную степень тогда и только тогда, когда все вершины в 7'(У) имеют четную степень.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
