Введение в прикладную комбинаторику, Кофман А. (984071), страница 11
Текст из файла (страница 11)
Полагаем М=Сагб А; (12.35) и!(0) = 1, ю (1) = ~2~ Саг!1 А!, !=! Деля. (12.20) на М, записываем 5о=1 — в1+ во — во+ ... +( — 1)" в„=(1+ в) в' — 'в„, г=1,2,...; в„.„~ — — О, 1> О. (12.39) Точно так же 5, = ~ (11г ((е) берется из (12.19)), (12.40) Яг (е) 5ь = во — Сь~е~вье1+ С~о+ вь„.о — ... -)- ( — 1)" ь Сев„')— =в (1+в), в" — 'в„г=1,2 в„;=О, 1> О, Й=О, 1,2, ..., п. (1241) Заметим, что величины 5м Й = О, 1, 2, . „п, можно рассматривать как вероятности того, что элемент обладает в точности й свойствами.
Перепишем формулу (10.88): р(й) = у,- С„,у,„, + С„,у„, — ... ... +( — 1)'Сьь,уьч,+ ..., 1=0,1,2, ° (12.42) Очевидно, вь — — ум 1=0,1,2, ..., п, (12.43) Итак, числа вь — биномиальные моменты распределения с ве. роятностями 5ь. В силу (10.67) вь — — Х С)50 )с=О, 1, 2, ..., и, (12.44) С=ь 1 2 вь = 5ь + Сь+15ьо ~ + Сьес5е+е + ... + Се+ь5е+г + ° ° ° (12.45) Пусть 5'(г) — производящая функция для 5„: 5*(г) = 5о + 5,г + 5,а~ + ...
+ 5„г". (12.46) Выписываем факториальные моменты ге для 5) (согласно (10.65)) ге= ~ п(п — 1) (п — 2) ... (и — Й+!) 5„(12.47) и производящую функцию для них г (3) = Го + г|х + гех + ... + гьа (12.48) В силу (10.80) 5" (г)=е""-", г' — 'го 1=1, 2, ..., и; г' — '1. (12.49) Введем производящую функцию для биномиальных моментов вь: в*(а)=во+ в1а+ зев~+ "+вез + ...~ в„+~=0, 1> О.
(1250) ~) Условие в„е~ О, ~>0, здесь сущестееиие. аа Тогда в силу (10.80) ( ) 3 (г 1) 30+31(г 1)+32(г 1) + . +з„(г — 1)" + . =[! — з(г — 1)] (з„ьз=О, з>0), 3' — '3„, к=1, 2, ..., п; зэ — '1. (12.51) Теперь найдем производящую функцию для (!т(й). Имеем (Р"' (г) = (Р'(О) + (Р' (1) г + (Р'(2) г' + ... ... +(зт(п)г" + ..., (р'(и+з)=0, з'>О, (12,52) и (Р'(Й) = А15а=Ы'"(г) = М5'(г).
(12. 53) Таким образом, производящая функция для (Р' (Й) представляется в виде (к'* (г) = А( [ 1 — 3 (г — 1)Г ' = Х А з (г — 1)' = Х (р' (й) ( — ц', в=о а=о 3' — '3„, г= 1, 2, ..., и; зо — '1. (12.54) Пример.
Вновь рассмотрим пример (см. (12.13)), В силу (12.21) в(0) = 11, нз(1) =15, нз(2) =5, тп(3) =0; (1т (г) н, (О) + ю ( 1) (г 1) + и, (2) (г 1)г = 11+ 15(г — 1)+ 5(г — 1)'=1+ 5г+ 5г' (12.55) Получаем коэффициенты полинома ((т" (г), уже найденные в (12.21). УПРАЖНЕНИЯ 12А. Дано множество А = (О, 1, 2, ..., 9) и свойства: Уз. Азы А кратно 3, У,: А ~ А кратно 3, Уз: А~А и 2(~А<7, Уа АзмА и Аз+А)4. Сколько элементов обладают свойствои: а) Уз Л Уз Л Уз; б) Уз Л Уз Л Уз' в) Уз Л Уз Л Уз Л Уз; г) Уз Ч (Уз Л У,), где Ч обозначает неисключазо- щее «или».
12Б. Сколько элементов из А в упражнении !2А обладают в точ- ности О, 1, 2, 3 илп 4 свойствами? Вычислить йт*(а). 123. Рассмотрим множество А, образованное парами (з, !), з, 1= 1, 2, 3, 4, б, и следующие свойства; УП 1+1 четко, Ун / нечетно, Уз: 1 четно, Уа 0<13, Уз: з =21. Сколько элементов обладает свойством; а) Ус Л Уз Л Уз, б) Ус Л э.з Л Ум в) Уз Л Уз Л Уз 12Г. Сколько элементов из А в упражнении 12В обладают в точности О, 1, 2, 3, 4 или 5 свойствами? Вычислить СР'"(г).
12Д. Рассмотрим множество простых чисел А = [2,3, 5, 7). Пока~ать, что количество целых чисел, не превосходяшнх й? и не деляюихсн на элементы из А, равно '-1~%+ ХБ) — Х~41+Х~ — „".1 ГУ1 где сг — ) — целая часть числа —, в ~ ~ —,) суммирование производцтся 'с х ] по всем элементам нз А, в т ! —,. ) — по всем парам [с, 11, 1 Ф й с, ] сы А, Ц %чгд? 1 1 в т ~ —,. ) — по всем триадам [1, ], й] без повторения и в лт ~ —.~ — по .?й ~ 1]й ! 24~ цл(] всем неупорядоченным четверкам [с, 1, й, 1] без повторения.
12Е. Обозначим через йс(п) количество натуральных чисел, меньших и и взаимно простых с ннм. Показать, что где пс, и„..., и„— простые делители п. В 13. Использование общего метода решета в теории чисел Рассмотрим применение формул предыдущего параграфа в элементарной теории чисел. Пусть х~ й+. Введем следующие обозначения: (х] — целая часть числа х; н. о. д. (аи а,), ао а? ~ Я, (а„ау) чь (О, 0), — наибольший общий делитель а; и ас (а, и а? взаимно простыч',='? н.
о. д, (аи а?) =1); а?[а, — ас делит ар ас ]' а? — а, не делит ар Тео рем а 1. Пусть А= [1, 2, ..., и) и а„а„..., а„, а;ен Х„Г= 1, 2, ..., т, попарно взаимно просты. Количество целых чисел й таких, что О < Ге(п, ас Г й, с = 1, 2, ..., и, равно и — )„' [ — ~ + )~~ ~ — ~ — ... +( — !)'~ ~. (13.1) с<с<с ' с<с<1<с До к а ватель ств о. Обозначим А; = (й ~ А: а;[й) (13.2) и выпишем формулу (12.7): Сагс1(А, П АзП ... П А„) = Сагс] А — Сагс[ А, — ... — Сагс[А„+ + Сагс[(А, Д А )+ ... + Сагс1 (А„, П А ) — ...
... +( — 1)'Сагс[(Ас[]А,[] ... [] А,). (13.3) По формуле (13.1) л %ч и у а <р(л) = л — ~ — +,à — — ( — 1) а Л1 а!а а,а, ... а, !<г<!<~ 1 ! 1 !<!<г ' !<1<1<г = (1 — — 'й1 — — ')... (1 — — '), (13!О) т. е. получаем (13.8). П р и м е р. Пусть л = 84, Простыми делителями 84 являются 2, 3, 7; поэтому ,р(84) = 84 (1 — — 2') (1 — — 3') (1 — 7 ) = 24. (13 11) Выписываем все числа, взаимно простые с 2, 3, 7 и не превосхо- дящие 84: 1, 5, 11, 13, 17, !9, 23, 25, 29, 31, 37, 41, 43, 47, 53, 55, 59, 61, 65, 67, 71, 73, 79, 83.
Функция Мебиуса. Представим (13.8) в другом виде, исполь- зуя функцию Мебиуса !!(л), определяемую следующим образом: р(1) =1; ц(л) =О, если л делится на квадрат простого числа; (13.12) р(а,а,... а,) =( — 1)', если а! — различные простые множители, !'=1, 2, ..., г. Тогда !р(л) =л~~! (13.13) где суммирование производится по всем л, делящим л (вклю- чая 1).
Пример на функцию Мебиуса. Имеем р (1) = 1, 14 (2) = ( — 1)' = — 1, 1! (3) = ( — 1)' = — 1, р(4)=р(2') =О, р(5) =(-Ц'=-1, р!(6) = ц (2 3) = ( — 1)' = 1, 1! (7) = (- 1)' = — 1 (13.14) Р (8) = р (2з) = о, 14 (9) 1! (3!) 0 !4 (30) р (2 . 3 . 5) ( 1)з При л=-84 формула (13.13) дает ! 1 ! ! 1 1 1 (р(84) = 84(1 — — — — — — — — + — + — — — 1=24, 2 3 4 6 14 37 237) (13. 15) Решето Эратосфена.
Известен следующий способ перечисле- ния простых чисел рь р! ( л: вычисляется с = ~У л~ и из по- следовательности 2, 3...,, л вычеркиваются последовательно 72 все числа, кратные 2, затем кратные 3, ..., кратные с. Оставшиеся числа и есть искомые. Используя теорему 11, можно получить следующую формулу пересчета. Если через М(п) обозначить количество простых чисел д таких, что )Уп(д(п, то в силу (13.1) М(и)= — !+и — ~ ~ — ~+ 1~! <г ~п, + )~~ ~ — ~ — ... +( — 1)'~ 1, (13.16) ~~1(!~~ где рь ! = 1, 2, ..., г,— простые числа, не превосходящие )/й( — 1 в правой части добавляется, так как 1 не считается простым). В силу (13.!3) М(п) =- !+и ~)', '~', (13.17) где суммирование в (13.17) производится по всем простым делителям и (включая 1). П р и м е р.
Сколько простых среди чисел 2, 3, ..., 84? Имеем !'у'84~ = 9. Простыми числами между 2 и 9 будут 2, 3, 5, 7. Согласно (13.!6) М(84)= — 1+84 — Ь~ — ~ 3] — Ц ~ 7 1+~2 3)+~2 51+ + 14+ 8+6+ 5+ 4+ 2 — 2 — 2 — 1 — 0+0= 19. (!3.!8) Таким образом, имеется всего 19+ 4 = 23 простых числа среди 2, 3, ..., 84. Решето Эратосфена перечисляет их: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83. й 14. Задача о встречах.
Беспорядки и совпадения Рассмотрим множество из п элементов А = (А„А„..., А„) (14.!) и множество и ячеек, в которые размещаются эти элементы: (4= (ао а,, ..., а„!. (14.2) Сколькими способами можно разместить п элементов в п ячейках (по одному в каждой) так, чтобы никакой элемент А; не попал в ячейку а;? Здесь речь идет о знаменитой задаче, 7З предложенной Монмором и называемой задачей о встречах.
Эта задача и ее обобщение, которое будет дано ниже, представляют интерес для различных приложений. Перестановка' ), обладающая указанным свойством, называется беспорядком и обозначается через 0„. Лля перечисленяя беспорядков из и элементов мы будем использовать формулы, установленные в 5 11. Рис. 9 дает пример беспорядка из 6 элементов. Обозначим через У, свойство; перестановка Р; ~ Р (Р— множество всех п! перестановок) и такова, что Л, =~ аь г = 1, 2, ..., и; через Уг — свойство: Р; обладает совпадением, т.
е. Аг Аг Аг Аа Аг Аг Аг Аг Аг Аг А аг ггг ег сг аг аг а аг а,, аг аг Рис. 9. Рнс 1О. А, = а, для одного н только одного значения г н Л; ~ а, для остальных: через У, — свойство; Рг обладает т совпадениями, т. е, А; = а; в точности для т значений г и А; Ф аг для остальных. Например, перестановка, изображенная на рис. 1О, обладает двумя совпадениями.
Следовательно, можно записать (1 4.3) Уо = Уг Л Ух Л ° Л Уч. Если нам известно Р„с: Р, соответствующее У„, то мы можем воспользоваться формулами (12.7) и (12.20). Имеем Сагд (РгПРвП ПР„)=Сагс1Р— ~аСагдРг+ + ~Саге( (Рг П Рг)+ ... +( — 1)н Саге( (Р, П Ре П... П Р„). (14.4) Если обозначим, как и раньше (см. (12.17)), и (т) = ~ Саге( (Рг, П Р;, П П Рс,), (14.5) то (Р (0) = иг (0) — ы (1) + в (2) — ... + ( — 1)" в (и). (! 4.6) Легко вычислить ш(т): ш(т) =С'„(и — т)! = —, с=О, 1, 2, ..., п.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
