AOP_Tom1 (1021736), страница 147
Текст из файла (страница 147)
~Р е — и)/е( = 1/(и+ 1)! — 1/(и + 2)! +, т. е. сумме знакопеременного ряда, члены которого убывают по модулю. Эта сумма меньше, чем 1/(и+ 1)! < -'. 20. Сущесгвует всего ад + аз -ь циклов, которые можно переставлять между собой, причем каждый отдельный т-цикл можно независимо от других записать т способами. Поэтому ответом будет (а~+аз+ ..)11 '2 '3 '.... 21. 1/(аП 1 'аз! 2 з... ), если и = а~ + 2аз+.; в противном случае вероятность равна О. Доказательство. Выпишите в ряд а~ циклов длины 1, аз циклов длины 2 и т.
д., вместо элементов вставив пробелы. Например, если а~ = 1, аз = 2, аз = аз = — — О, то получим "(-) ( — ) ( — )". Заполните пустые позиции всеми и) возможными способами. Тогда каждая перестановка нужного вида появится ровно а~) 1~'аз! 2~з... раз. 22. (а) Если )гз + 2)зз + = и, то вероятность в и. (О) равна П,>е/(ю, у,)зз), что по предположению равно (1 — ю)ю"/1Н 1"'йз! 2 "з....
Отсюда /(ю, т, )з -ь1) / = ~п/(ю,дйз)) Ц/(ю,), й +б-) = (5 +,). ю ,>е з>е Тогда по индукции получим »ф й /(ш,т,й) = —, ( — ) /(ш,т,б). Теперь из условия (1) следует, что /(ш,т,й) = —, ( — ) е [Другичи словами, о выбирается из распределения Пуассона; см.
упр. 1.2,10-15.] (П - "))ш ---. 01+222+" »»2'>О й,+гйг+--» й,,й,,...>о йг,йг," >О = (1 — ги)ш". фо„ф,,.. 12 1,=ф„=ф,, .1) »>а "й,йгйг+ -= = 0- 1т' т' 41ф,,ф,,,,11ффф"ффф'*. ). >О 21+242+ =» (о) Пуст' Ф(ог,сгю .. ) = юг +о4+ае+ .. Среднее значение линейной комбинации ф равно сумме средних значений аг, аф, ае,.... Среднее значение а равно й/(ш,т,к) = ~, ( — ) е й>о й>1 Следовательно, среднее значение ф равно 2 4 6 ш 1 — ш з 4 3 6 — + — + — + . = — (Нфш +Нфш + Нгги + Нгш + Нзги + ). 2 4 6 2 Искомым ответом будет 2 Н1 4гр (е) Положим ф(421,аг,...) = 2 и заметим, что среднее значение ф равно /(ш,т,й)з =~ —,( — ) е "1 =е 4 Н~=~ —,( — ) й>0 й>О >о - —.к"( к КЮ') »>а 0<2< 1 = (1 — ш) ~ ш"С„(з). »>О Отсюда 1 ( — 1/т)2 тй)41 0<1<»гш-й (ппп О, ате 1/т, игах (и/т], 41ет з/Г/т), где 6' »ф(2) = ~' —., ( — ); 0<1 <»1»ф Статистическими характеристиками будут и>2т.
Следовательно, вероятность того, что а1+ 2аг+ . < 21, равна (1 — ш)(1+ ш+ .. + ш") = 1 ш»+1 (с) Среднее ф равно 23. Постоянная Л равна („ехр( — ! — Е~(!)) 41, где Е~(х) = ), е 'пг/а (См. Тгалэ. Атег. Маг!с Яос. 121 (1966), 340 — 357, гйе докэзываетск множество других фактов, в частности, что средния длина самого корогпкого цикла приближенно равна г т !и и.] Следующие члены асимптотического представлення!„были найдены Ксавье Гордоном (Хач !ег Соагдоп). Первые члены ряда выглядят так: Ли+ 1Л вЂ” ~с~и ~ + ( ~ е~ — г(-1)")и г+ (ггг е~ + г( — Ц + Лег~ + г~ )и где ы = е~"ч~. Вильям Ч. Митчелл (ЧЧ!!!аш С М!ссЬе!!) с высокой точностью вычислил значение Л = .62432 99885 43550 87099 293б3 83100 83724 41796+ (Маг(ь Сотр, 22 (19б8), 411-415).
Пака неизвестны какие-либо соотношения, связывающие Л с классическими математическими константамк. Тем не менее эта же константа была вычислена в другом контексте Карлом Дикманом (Каг! Огс1апал) в работе АгЫг Гаг Маг., Аз!гоп. осб Руг. 22А, 10 (1930), 1-14. Но совпадение заметили только спустя много лет (ТЬсог Сошр. Яс!. 3 (1976), 373). 24. См. О Е КписЬ, Ргос. 1РГР Сапбгегэ (1971), 1, 19 — 27. 25. Одно доказательство (индукцией по Ф) основано на том, что когда №й элемент является членом г множеств, он добавляет к сумме в точности следующую величину; Другое доказательство (индукцией по М) основано на том, что число элементов, принадлежащих Бм, но не принадлежащих Я~ О О Ям и равно ~<г<ь<м ~<г<м 26. Пусть № = л! и ~<п« ы<м Тогда искомой формулой будет (г+ 1) (г+ 2) Это можно вывести из самого принципа включения и исключения либо воспользоваться формулой как в упр.
25. 27. Пусть 3г — это числа из заданного интервала, кратные т„, и пусть йг = атг... ть Тогда (3 С! Яь( = Х/т,ть и т. д. Поэтому ответом будет Это также будет решением упр. 1.2.4-30, если принять,что ты,.,,тс †прост числа, являющиеся делителями 5!. 29. Пропуская человека, присвойте ему новый номер (начиная с и+ 1). Тогда 7г-м казненным будет номер 2!с, а человек с номером 1 для 2 > и прежде имел номер (27) шоб (2и+ 1). 31. См. СМагб, раздел 3.3. 32.
(а) На самом деле й — 1 < яь < й+ 2, если й — четное, и й — 2 < яь < й+ 1, если й — нечетное. (Ь) Выбирайте йкспоненты слева направо, полагая еь = 1 тогда и только тогда, когда й и й + 1 пока еще находятся в разных циклах перестановки. ]8(ечеп А!регп, Х СотЬта!опа1 Тйеогу В25 (1978), 62 — 73.] 33. Для 1 = О положим (ао),аоз)))о),)уоз) = (крее) и (ам,амбал)1,)711) = (гцяр) где х = (1 4)(2 3), р = (1 5)(2 4) и е = (), Предположим, мы построили такую конструкцию для некоторого 1 > О, где а ь —— 1 )з)ь = () для О < 7 < гл и 1 < й < и. Тогда перестановки (А( +, >„...,А(, чз )(1„))В(„+, >„,,В( +, >(4„>) = (1т а)111,, а а„,а, т а1 1т,...,т с)1 „т, а )7)ьа,...,а В)1а, т В) т,,т )81 1т; а В))а,...,а )8)„а, т К')т,..., т В) „т, в' а).„а,..., а а))а, т ар„т,, .., т а,т) обладают свойством .4( )-1 )1В(1 +1 )1 .
А(1 .1. )(4„)В()т-); )((ч) = а (12345)ат (12345)та (54321)ат (54321)т, если 1 = 1 и 1' = 1', в противном случае произведение равно (). Выбирая а = (23)(45) и т = (345), получим искомое произведение (12345) при()в+ 1' = уж+1'. Метод построения от 1 к 1+ 1 предложен Давидом А. Вэррингтоном (1)ач!о А. Выт)ой!оп) (Х Соп1р. Яуэ!. Ясй 38 (1989), 150-164], который доказал общую теорему о том, что любую булеву функцию можно представить в виде произведения перестановок множества (1,2,3,4,5). С помощью аналогичной конструкции можно, например, найти последовательности перестановок (а)1,..., а,; В)1,, В)„), такие, что ! (12345), если) < у; О~ ,1! 2 для О < ),у < т = 2, где и = 6'+' — 4'+'. 34.
Пусть )1) = т + П. Если и) .ь и, существует только один цикл, так как каждый элемент можно записать в виде оп))ОО)! ))) дЛЯ нЕкоторогО ЦЕЛОГО а. В общем случае, если с( = бес!(и), и), то существует ровно )( циклов Св, С), ..., Св 1, где С, содержит элементы (1,1 + 11, -,2 + )Ч' — 11), расположенные в некотором порядке. Тогда, чтобы выполнить перестановку, необходимо действовать следующим образом для О < 7' < 1( (параллельно, если это удобно). присвоить ! +- х> и й +- 11 Зачем, до тех пор, пока (й + т) що(! х ~ 1, присваивать хь ( — х(ь+ >,ел и й+- (й+гл) що)!)().
И наконец присвоить хе +-1. В этом алгоритме неравенство (й+ и)) )оос) )1) ~ 2 будет выполняться тогда и только тогда, когда (й + т) то)!)ч > )(, поэтому можно использовать любой тест, который является более эффективным. (1Ч. Р!ессйег, Н. Я!!чег, САСМ 9 (1966), 326.] 35. Положим М = 1+ и>+ и и )ч' = 1+ 2щ + и. Циклы искомой перестановки получены из циклов такой перестановки на множестве (О, 1,..., ))) — Ц, которая переводит й в (й + 1+ т) що)! Ж, просто исключая все элементы каждого цикла, которые > М. (Сравните это с аналогичной ситуацией в упр. 29.) Двкоэвв)ельсщвв. Когда в результате предложенного в указании взаимного обмена будет выполнено присвоение хь (- хь и хь +- хь ° для некоторого й, где й = (11 + 1+ т) то)! ж, й" = (й' (-1+ )п) щог) ))) и й > м, получим, что хь — — хь .
Отсюда переход а)7 ) -+ 7)3а заменяет хь на хь Следовательно, существует ровно 4 = Ясб(1+ гл, гл+ и) циклов и можно испатьзовать алгоритм, аналогичный тому, который рассматривался в предыдущем упражнении. Заслуживает также вниьглиия несколько более простой способ сведения этой задачи к частному случаю из упр. 34, хотя он подразумевает больше случаев обращения к памяти. Предположим, 7 = 77, где )7 ! = )сг!.
Тогда можно заменить пд77 на 7 ф7п и выполнить взаимный обмен ~л с Г)7'. Аналогичный подход можно использовать и при (и( > Ц. (См. Л 1.. МоЬапипег), С. Б. ЯвЬ1, Х А!Яог)ййшл 8 (1987), 113-121.) РАЗДЕЛ 1.4.1 1. Последовательность вызова; )НР МАХИ; или )МР МАХ100, если и = 100. Состояния при входе: Для входа МАХИ г13 = и; предполагается, что и > 1. Состояние при выходе: Такие же, как в (4). 2. МАХБО БТ) ЕХ1Т ЕИТЗ БО )МР 2Г 3.
Состояние при входе: и = гП, если гП > 0; в противном случае и = 1. Состояние при выходе: гА и г12 такие же, как в (4); г11 не изменился; г13 = ппп(0, гП); гд = ЕХТТ + 1; С1 не меняется, если и = 1, в противном случае С1 будет больше, равен или меныпе прежнего значения, в зависимости от того, будет ли максимум больше Х(Ц, равен Х(Ц при г12 > 1 или равен Х[Ц при г12 = 1. (Аналогичное упражнение для (9), конечно, было бы немного более сложным.) 4. БМАХ1 ЕИТ1 1 г = 1 ЯМАХ БТ1 ЕХ1Т Произвольное г.
1МР 2Р Далее, как в прежней программе. ОЕСЗ 0,1 Уменьшить на г. )ЗР 18 ЕХ1Т )НР ь Выхо, д Последовательность вызова: )МР ЯНАХ; или )МР ЯНАХ1, если г = 1. Состояние при входе: г13 = и, предположительно положительному; для входа ЯНАХ гП = г, предположительно положительному. гА = шахе<в<„Г„СОИТЕИТЯ(Х+ и — )гг) = ООИТЕИТБ(1 + г12); и г13 = (и — 1) шоб г + 1 — г = -((-и) шоб г).
Б. Можно использовать любой другой регистр, например: Последовательность вызова: ЕИТА в+2, 1НР НАХ100. Состояние при входе; Нет. Состояние при выходе: Такие же, как в (4). Код аналогичен (1), но первая команда имеет вид "ИАХ100 ЯТА ЕХ1Т(0: 2) ". 6. (Решение предложено Джоэлом Голдбергом (Бее! Со!ИЬегб) и Роджером М, Ааронсом (Вояег М. Аагопв).) НОТЕ БТА ЗР БТА 4Р Сохранить гА и г12. БТ2 БР(0'.2) 002 ЗР(0:2) г12 +- адрес "ИОР А,Т(Р)".
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
