Так как

I - г

lim ( ) {г - Zk) - -1 при А; > О

и этот предел равен -2 при А; = О, функция

г> / \ г/ \ , 2 ,21 , гг 2:2 гг , Zm , Zm rm{z) = (г) н--н---1--г- н---1--:- н----н---ь

2-2о 2-21 2-21 Z-Z2 2-22 2-2 г - 2

не имеет особых точек на комплексной плоскости при \z\ < 2m+i- Значит, rm{z) можно разложить в степенной ряд Pkz, который сходится абсолютно при \z\ < 2m+i; отсюда следует, что ркМ -> О при А; -> оо, где М = 2m+i - е. Коэффициентами для L{z) служат коэффициенты разложения функции

2 1 1 1 1.4

1-2 1 - 2/21 1 - 2/21 1 - z/Zm 1 - Z/Zm

а именно

Ln = 2 + 2rf" cosni + 2r" cosna -I- • • • -b 2r-" cosn™ + 0(гД1), (29) если положить

Zkrke. (30)

Отсюда МОЖНО проследить асимптотическое поведение .Ln-

Имеем

п = 8.07556 64528 89526-, = 1.17830 39784 74668-ь;

Г2 = 14.35456 68997 62106-, 02 = 1.31268 53883 87636-f гз = 20.62073 15381 80628-, вз = 1.37427 90757 91688-Г4 = 26.88795 29424 54546-, Oi = 1.41049 72786 51865-; (31)

таким образом, главный вклад в L„ - 2 дают Гх и Oi, а ряд (29) сходится очень быстро. Дальнейший анализ [W. W. Hooker, С ACM 12 (1969), 411-413] показывает, что rmiz) -> -Z при m -> оо; следовательно, ряд 2.>д г" созпвк действительно сходится к L„ при п > 1.

Можно провести более тщательный анализ и полностью определить распределение вероятностей для длины А;-й серии и для общей длины первых к серий (см. упр. 9-11). Оказывается, сумма Li + • + Lk асимптотически приближается к 2А:- -fO(8-*).

В заключение этого раздела рассмотрим свойства серий в случае, когда в перестановке допускаются одинаковые элементы. Бесчисленные пасьянсы, которым посвящал свой досуг знаменитый американский астроном 19 в. Саймон Ньюкомб (Simon Newcomb), имеют непосредственное отношение к интересующему нас вопросу. Он брал колоду карт и складывал их в одну стопку до тех пор, пока они шли в порядке неубывания по старшинству; как только следующая карта оказывалась младше предыдущей, он начинал новую стопку. Он хотел найти такую вероятность, при которой вся колода окажется разложенной на заданное количество стопок. Задача Саймона Ньюкомба состоит, следовательно, в нахождении распределения вероятностей для серий случайной перестановки мультимножества. В общем случае ответ довольно сложен (см. упр. 12), хотя мы уже видели, как решать задачу в частном случае, когда все карты различны по старшинству. Мы удовлетворимся здесь выводом формулы для среднего числа стопок в этом пасьянсе.

Пусть имеется т различных типов карт и каждая встречается ровно р раз. Например, в обычной колоде для бриджа m = 13, а р = 4, если пренебрегать различием масти. Замечательную симметрию обнаружил в этом случае П. А. Мак-Магон [см. Combinatory Analysis 1 (Cambridge, 1915, 212-213)]: число перестановок с к+1 сериями равно числу перестановок с тр -р~к+1 сериями. Это соотношение легко проверить при р = 1 (формула (7)), однако при р > 1 оно кажется довольно неожиданным.

Можно доказать свойство симметрии, установив взаимно однозначное соответствие между перестановками, такое, что каждой перестановке с А; + 1 сериями соответствует перестановка с тр - р - к + 1 сериями. Мы настойчиво рекомендуем читателю постараться самостоятельно найти такое соответствие, прежде чем двигаться дальше.

Какое-нибудь очень простое соответствие на ум не приходит; доказательство Мак-Магона основано на производящих функциях, а не на комбинаторном построении. Однако установленное Фоатой соответствие (теорема 5.1.2В) позволяет упростить задачу, так как в нем утверждается существование взаимно однозначного соответствия между перестановками с к+1 сериями и перестановками, в двухстрочном представлении которых содержится ровно к столбцов %, таких, что х < у.

Пусть дано мультимножество {р-1, р-2,..., р-т}. Рассмотрим перестановку в двухстрочном представлении

/ 1 ... 1 2 ... 2 ... т ... т \

Хп Xip Х21 ... Х2р ... Х„г1 ... Хр j

Сопоставим с ней другую перестановку того же мультимножества: /1 ... 1 2 ... 2 ... т ... т\

(32)

Vii ... Хр Ху ... Хр ... Х21 ... Х2р J

(33)

где х = т + 1 - X. Если перестановка (32) содержит к столбцов вида , таких, что X < у, то (33) содержит (т - 1)р - к таких столбцов, потому что необходимо рассмотреть лишь случай «/ > 1, а неравенство х < у эквивалентно х > т + 2 - у. Поскольку (32) соответствует перестановке с к + 1 сериями, а (33) - перестановке стр- р - к + 1 сериями и преобразование, переводящее (32) в (33), обратимо (оно же переводит (33) в (32)), то тем самым доказано условие симметрии Мак-Магона. Пример этого построения содержится в упр. 14.

В силу свойства симметрии среднее число серий в случайной перестановке должно равняться [{к+1) + (тр-рк + 1)) - 1 + \р(т-1). Например, для стандартной колоды среднее число стопок в пасьянсе Ньюкомба равно 25 (так что раскладывание этого пасьянса вряд ли покажется столь уж увлекательным занятием).

На самом деле после несложных рассуждений можно определить среднее число серий в общем случае для любого данного мультимножества \п\ • Zj, П2 - Х2,..., п,п х„г}, где все Xk различны. Пусть п = пг + П2 + • + Пщ и все перестановки ai 02 ... On этого мультимножества выписаны в явном виде. Посмотрим, как часто at оказывается больше Oj+j при каждом фиксированном значении i, 1 < i < п. Число случаев, когда Oj > Oj+i, равно в точности половине числа случаев, когда Oj Oj+i, и нетрудно видеть, что Oj = Oj+j = Xj ровно в Nnj(nj - 1)/п(п - 1) случаях, где N - общее число перестановок. Следовательно, о; = Oj+i ровно в

случаях, a fli > Oj+i в

2n{n - 1)

случаях. Суммируя по г и прибавляя Л, потому что в каждой перестановке одна серия заканчивается элементом а„, получим общее число серий во всех перестановках:

+ + + (34)

Выполнив деление на Л, получим искомое среднее число серий.

Поскольку серии играют весьма важную роль в изучении "порядковых статистик", имеется весьма обширный список работ, посвященных этой теме, включая некоторые типы серий, не рассмотренные здесь. Дополнительную, информацию можно найти в книге F. N. David, D. Е. Barton, Combinatorial Chance (London: Griffin 1962, гл. 10) и в обзорной статье С. L. Mallows, Annals of Math. Statistics 36 (1965), 236-260.

УПРАЖНЕНИЯ

1. {M26] Выведите формулу Эйлера (13).

► 2. [М22] (а) Попытайтесь развить Идею, использованную в тексте при доказательстве тождества (8). Рассмотрите последовательности ai a-z . .. an, содержащие ровно q различных элементов, и докажите, что

qj

(b) Используя это тождество, докажите, что

>(,) ] = { , ) (п - ту. при п> т.

3. [НМ25] Вычислите сумму Х:.(;;)(-!)*.

4. [М21] Чему равна сумма T.ki-)4l] ("m*) ?

5. [М20] Найдите значение () modp, если р - простое число.

• 6. [М21] Мистер Далл заметил, что из формул (4) и (13) можно получить

кУО" к>0 j>0

Он обнаружил, что Х<.>о(~1)* (llj) = О при всех j > О, выполнив суммирование сначала, по к, а затем по j > 0; отсюда п! = О при любом n > 0. Не допустил ли он какой-нибудь ошибки?

7. [НМ40] Является ли распределение вероятностей для серий, задаваемое формулой (14), асимптотически нормальным? (Ср. с упр. 1,2,10-13.)

8. [М24] (П. А. Мак-К1агон.) Покажите, что вероятность того, что длина первой серии достаточно длинной перестановки есть li, длина второй есть I2, ..., а. длина к-й серии > Ц равна