(1 - z* N" ---j . [Обратите внимание на случай г = оо.]

ZV A; fc(fc-l)...l "A.

zw/kl.

к к .. , . . .

(Есть и другой способ: записать эту функцию в виде е""" и разложить сначала по степеням w.)

18. (а) Для фиксированного п и переменного г согласно (27) производящая функция равна Gn{z) = (1 + z){l + 2г)... (1 + nz) = z"+ Q + 1) Q + 2) ... + n)

n + 1 A;

n + l-k

(cm. формулу (27)). Отсюда получаем ответ: (*) Аналогично согласно (28)

производящая функция равна

1 - г 1 - 2г

поэтому получаем ответ: С*}.

19. i:„>i(l/"-l/(n+P/9))x+" = EU"*l4(l-*x)-xPln(l-x) + fxP = f{x)+9(x), где ш = е"» и

/(х) = Е"*М1 - *з;), у(х) = (1 - х)1п(1 - х) + хР - хПп ""

Теперь получим limi ,i д{х) = q/p - Inq. Из тождества

е--j = In 2 + \г{в - тг) + Insin

можно записать /(х) = А + В, где

А = Е- Ч-Y + v)- + T"к

9-1 , ,

4 = 1 0<*:<9/2

Окончательно получаем

„ 2рк , fc

= 2 > cos-Trlnsin-TT.

q q

1 г i /1 +aP\ i /aP + oP \ 1 p

2" (w-p-1) ~ 2 ll-шР/ ~ 2 1шР/2-ш-Р/2у ~ 2°S

[Гаусс вывел эту формулу в §33 своей монографии, посвященной гипергеометрическим рядам (соотношение [75]), но доказательство было недостаточно строгим; Абель обосновал данный результат в работе Crelle 1 (1826), 314-315.]

20. стк КТ} согласно соотношению 1.2.б-(45).

21. Находим zG{z) + zG{z) = G{z)- 1. Решением этого дифференциального уравнения будет G(z) = {-llz)e-{Ei{-\/z) + С), где Ег{х) = e-t/t, а С -константа. Эта функция "очень плохо себя ведет" в -окрестности точки г = О, и G{z) нельзя разложить в степенной ряд. Действительно, так как функция УтЛ к п/е не ограничена, ряд в представлении производящей функции расходится. Однако при г < О для данной функции существует асимптотическое представление. [См. К. Кпорр, InSnite Sequences and Series (Dover, 1956), Section 66.]

22. G(z) = {l + zУ{l + zУ{l+zУ{l + zУ ... = {I - zy. Отсюда следует, что исходная сумма равна С"")-

23. При т = 1 получаем биномиальную теорему, где fi (г) = г, а (г) = 1 4- z. При m > 1 можно увеличить m на 1, если заменить z на Zn, (l+z+i) и положить fm+i (zi,..., Zm+i) =

Zrn+lfm{zi, . . . , Zm-l,Zm{l+Zm+\)), ym+l(zi, . . . , ) = m+lm (1, . . . , Zm-l, Zm (1++1))

Тогда (?3(zi, za) = zi + za + 21Z2 и

ffm(zi,...,Zm)

/m(Zl, . . . , Zm)

l + z-J

Оба многочлена, fm и , удовлетворяют одному и тому же рекуррентному соотношению

fm = Zm/m-1 + 2m-l/m-2, Qm = Zm9m-1 + Zm-l9m-2 С НачаЛЬНЫМИ УСЛОВИЯМИ f-l = О,

/о = д-\ = QQ = ZQ = \. Отсюда следует, что дт -сумма всех членов, которые можно получить, начиная с zi... Zm и вычеркивая нули или несоседние коэффициенты; существует Fm+2 способов сделать это. Точно так же можно интерпретировать fm, только zi должно остаться. В п. (Ь) мы будем иметь дело с многочленом hm = zgm-i + Zm-ifm-2- Это сумма всех членов, получаемых из zi ... Zm путем вычеркивания коэффициентов, которые не являются соседними циклически. Например, /13 = Z1Z3Z3 + z\z2 + z1z3 + z2z3.

(b) Согласно п. (а) Sn{zx,... ,Zm-x,z) = [z;] Er=o т"/ГУт- Отсюда

Szu---,zm)= Е [[)V~/)abed--\

0<s<r<n

где о = Zmgm-l, Ь = Zm-igm-2, С = Zmfm-1, d = Zm-lfm--2- УмНОжаЯ ЭТО равеНСТВО на

z" и суммируя сначала по п, затем по г и наконец по s, получим выражение в замкнутом виде:

1 р"+ - (7"+ S„(Z1, . ..,Zm) = [z"]-------J = -,

(1 - oz)(l - dz) - bcz p-a

где 1 - {a + d)z + {ad - bc)z = (1 -pz)(l -az). Здесь a + d = hm,aad - bc можно упростить до вида (-l)"2i ... z„. [Дополнительно мы получили рекуррентное соотношение S„ = hmSn-i - {~l)"zi ... ZmSn-2, которое нс так просто вывести без помощи производящих функций]

(c) Пусть Pi = (г -f л/г -f 4z)/2 и (Ti = (2 - л/г + 42)/2 -корни при m = 1; тогда

Рт = рГ и (Тш = (тГ-

Карлитц использовал этот результат для вывода следующего удивительного факта. Характеристический многочлен det(x/ - А) матрицы размера пх п

состоящей из "расположерных по правой стороне биномиальных коэффициентов", равен 5* (к) (~-)""** Д (t):F-фибономиальные коэффициенты (см. упр. 1.2.8-30). Используя аналогичные методы, он также показал, что

. .oV kl )[ к, )[ km

2*"

kl,.. ,fc„>0

zl...zl, hmi-Zi -Zf -4zi...Zm

[Collectanea Math. 27 (1965), 281-296.]

24. Обе части тождества равны Е* {k)W]iG{)) Для G{z) = 1/(1 - z) тождество принимает вид kCk)C-k) = (""Г") (м- соотношение 1.2.6-(21)), а для G(z) = (е - l)lz - Y,k ""{*} = (см. соотношение 1.2.6-(45)).

25. «1(1 - 2и;)" [г"] 2*=(1 + г)""" = [z"] (1 + г)" EJ"*] (1 " 2«)"(/(l + )). а это равно [г"] (1 + zf{l - 2г/(1 + zfY = [•г"] (1 + «)" = („/г)!" четное]. Аналогично находим Et (fc)(n-D(~1)"(п)- Множество примеров применения этого метода суммирования можно найти в книге Г. П. Егорычева Интегральное представление и вычисление комбинаторных сумм (Новосибирск: Наука, 1977), 284 с. (G. Р. Egorychev, Integral Representation and the Computation of Combinatorial Sums (Amer. Math. Soc, 1984)).

26. [F{z)]G{z) обозначает постоянный член F{z~)G{z). Этот вопрос обсуждается в работе D. Е. Knuth, А Classical Mind (Prentice-Hall, 1994), 247-258.

РАЗДЕЛ 1.2.10

1. Gn{0) = 1/n; это вероятность того, что Х[п] имеет наибольшее значение.

2. G"(l) = Ek - 1)Рь Gil) = Е* крк.

3. (min О, ave 6.49, max 999, dev 2 42). Обратите внимание, что Н приближенно равно л-7б; см. 1.2.7-(7).

4. iDpq-".

5. Среднее равно 36/5 = 7.2, а среднее квадратичное отклонение - 6V2/5 « 1.697.

6. Для (18) формула

ln(g+pe)=ln(l+p« + + + ...) =pt + p(l-p)+p(l-p)(l 2p) + .-.

говорит о том, что кз/п = р(1 -р)(1 - 2р) = pq(q-p). (Но эта схема не распространяется на коэффициент при t"*.) Полагая р = к~, получим кз = Et=2 к~{1 - ")(1 - 2к~) = Н„- гНп + 2Н1 для случая распределения (8). И для (20) имеем InG(e) = t -Ь H(nt) - H{t), гдеЯ(г) = ln((e-l)/t). Поскольку Я(г) e7(e-l)-l/t, в этом случае Кг = (п-1)Вг/г для всех г > 2, в частности кз = 0.

7. Вероятность того, что А - к, равна Ртк- Можно считать, что мы рассматриваем величины 1,2, ...,тп. Для любого заданного разбиения п элементов на m непересекающихся множеств существует тп! способов присвоения этим множествам чисел 1,...,тп. Алгоритм М работает с данными величинами так, как будто присутствуют только крайние справа элементы каждого множества Поэтому рт - среднее для любого фиксированного разбиения. Например, если п = 5, тп = 3, то одно из разбиений выглядит так:

{Х[1],Л[4]} {А[2],Х[5]} {Л[3]};