А. Гурвиц (А. Hurwitz) [Acta Mathematica 26 (1902), 199-203] еще больше обобщил теорему Абеля следующим образом:

х{х + eizi + + е„г„)+•+«"-(у - eiZi-----е„г„)"-- = (х + у)",

где сумма берется по всем 2" наборам ei,...,e„, независимо принимающим значения О или 1. Это тождество по х,у, zi,... ,z„, а формула Абеля - частный случай, когда zi = Z2 = ~ Zn- Формула Гурвица следует из результата упр. 2.3.4.4-30.

52. 2ц,>о(* + 1)~ = т/б. [М. Л. И. Хаутус (М. L. J. Hautus) заметил, что эта сумма абсолютно сходится для всех комплексных х, у, г, п, когда z ф О, так как для больших к члены суммы всегда имеют порядок 1/к. На ограниченных областях эта сходимость является равномерной, поэтому можно продифференцировать ряд почлекно. Обозначив через f{x,y,n) значение суммы при г = 1, находим {d/dy)f{x,y,n) = nf(x,y,n-l) и {d/dx)f{x,y,n) = nf{x - l,y+l,n-l). Эти формулы не противоречат тому, что f{x,y,n) = (ж + у)". Но на самом деле последнее равенство, видимо, выполняется редко (если выполняется вообще), если только сумма не является конечной. К тому же производная по z почти всегда является ненулевой.]

53. Для доказательства п. (Ь) в формуле из п. (а) положите г = и« = -.

54. Вставьте знаки "минус" в шахматном порядке, как показано ниже.

/1-0 О -О \ -1 1-0 О 1-2 1-0 \-1 3-3 1/

Это эквивалентно умножению a,j на (-I)""-. Согласно (33) это и есть искомая обратная матрица.

55. Вставив знаки "минус" в один треугольник (как в предыдущем упражнении), получим обратную матрицу другого треугольника. (Соотношение (47).)

56. 012 013 023 123 014 024 124 034 134 234 015 025 125 035 135 235 045 145 245 345 016. Если зафиксировать с, то пара а, b пробегает комбинации из с чисел по два; если зафиксировать с и Ь, то а пробегает комбинации из b чисел по одному.

Аналогично можно представить все числа в виде п = (") 4- () + (з) + (4), где О < а < Ь < с < d. Эта последовательность начинается с 0123 0124 0134 0234 1234 0125 0135 0235 .... Комбинаторное представление можно найти по принципу максимализма: сначала выбрать наибольшее возможное d, затем - наибольшее возможное с для п - (4) и т. д. [Другие свойства этого представления обсуждаются в разделе 7.2.1.]

58. Проведем доказательство по индукции, так как

Отсюда получаем, что обобщение соотношения (21) на случай, когда q не равно 1, выглядит следующим образом:

E(i).(„!j/-*"-"=E(i).(„!j/-=г:г

и с помощью тождества 1 - q* = -g*(l - g") можно легко обобщить (17):

а).=<-"("г),«"-"*-""

д-номиальные коэффициенты имеют много различных применений; см., например, раздел 5.1.2 и авторские примечания в J. Combinatoriai Theory AID (1971), 178-180.

Полезные факты. Если п - неотрицательное целое число, то (") -многочлен степени к{п - к) от g с неотрицательными целыми коэффициентами, удовлетворяющий рефлексивному закону:

{к), (n-fc), *(а:),-1

Для д( < 1 и ж( < 1 д-номиальная теорема справедлива для произвольного действительного числа п, если заменить левую часть выражением П*>о((9*)/(-9"*))- Благодаря свойствам степенных рядов это необходимо проверить только для положительного целого п, так как можно положить q" = у; затем можно проверить тождество для бесконечного числа значений у. Если теперь обратить верхний индекс в д-номиальной теореме, получится

Эта формула была получена Кощи [Comptes Rendus Acad. Sci. Paris 17 (1843), 523] и Гейне (Heine) [Crelle 34 (1847), 285-328]. Дополнительную информацию можно найти в работе G. Gasper, М. Rahman, Basic Hypergeometric Series (Cambridge Univ. Press, 1990).

59. in+l){l)~i,l,).

* ( " fc ) Я™У формулу легко запомнить, так как это

п{п + 1)...{п + к-1) fc(fc-l)...l

что аналогично (2), но в числителе идет возрастание, а не убывание значений. С\ществует остроумный способ доказательства рассматриваемой формулы: достаточно заметить, что нужно подсчитать число целых рещений (ai,..., ajt) неравенств 1 < ai < 02 < • • • < а* < п. А это равносильно соотнощениям 0<ai<a2 + l<--<ajt-t-fc - l<7i + fc. Число решений неравенств

0<bi<b2<-<bit<n + fc

равно числу выборов к различных элементов из множества {1, 2,...., п 4- fc - 1}. (Идея этого доказательства принадлежит Г. Ф. Шерку (Н. F. Scherk), Creiie 3 (1828), 97. Но самое интересное, что в этом же журнале, 13 (1835), 237, описанный метод был вновь предложен В. А. Ферстеманном (W. А. Forstemaim), который заявил: "Можно не сомневаться, что это доказательство известно уже давно, но, как ни странно, я нигде его не нашел, хотя и просмотрел множество работ".)

61. Если Птп -нужная величина, то из соотношений (46) и (47) имеем атп = nam(n-i) + бтп- Поэтому в результате получаем [п > т] п\/гп\. Эту же формулу легко получить путем обращения соотношения (56).

62. Используйте тождество из упр. 31, выполнив замену (т, п, г, s, к) <- (m+fc, 1-к, т + п, п + 1, j):

=Е<-.)(,:г)(Г)(,:;-,)(-::г)

jm+n + jy.

Z > {lj + kj {2l-2jyj\{m-l + jyin + j-iy

(мы поменяли знаки факториалов). Теперь сумма по к обратится в нуль (исключение составляет случай i = l)r

Частный случай данного тождества при I = т = п был опубликован А. К. Диксоном (А. С. Dixon) [Mes.sengerW Math. 20 (1891), 79-80], который через 12 лет обобщил эту формулу [Proc. London Math. Soc. 35 (1903), 285-289]. Но тем временем Л. Дж. Роджерс (L. J. Rogers) уже опубликовал гораздо более общую формулу [Proc. London Math. Soc. 26 (1895), 15-32, §8]. См. также статьи П. А. Мак-Магона (Р. А. MacMahon), Quarterly Journal of Pure and Applied Math. 33 (1902), 274-288, и Джона Дугалла (John Dougall), Proc. Edinburgh Math. Society 25 (1907), 114-132. Соответствующие д-номиальные тождества выглядят следующим образом:

y-/m-r + s\ rn + r-s\ Гг + к\ ,m-r+s-k)(n-k) /г\ /s\ \ к /,\ п-к )д\т + п), \mjq\njq

Y \1 + к )q\m + k)q\n + k)q /!,т!,п!,

гдеп!, = ПLl(l + 9 + •••+9*-)• 63. См. CMath, упр. 5.83 и 5.106.

64. Пусть /(п, то) - это число разбиений множества {1,2,..., п) на то частей. Ясно, что /(1,то) = 5\т. Если п > 1, то существует два вида разбиения: (а) элемент п образует одно из множеств разбиения; существует /(п - 1, то - 1) способов построить разбиения такого типа; (Ь) элемент п появляется в разбиении вместе с другим элементом; существует то способов вставить элемент п в любое то-разбиение множества {1, 2, ...,п - 1}. Следовательно, существует rnf{n~\, тп) способов построения подобных разбиений. Отсюда можно заключить, что /(п, то) = /(п - 1, m - 1) -Ь mf{n - 1, то) и по индукции /(п, т) - { }•

65. См. АММ 99 (1992), 410-422.

66. Сначала обратите внимание, что („i) < i+i)- Это очевидно, если z > п, так как Z < у; в противном случае п - l<z<nn, следовательно, („i) < О < („!J.i). Поэтому

i:X\) = LU) + С) < Ш + С) = Ш и мы имеем x>z + l. Теперь можно доказать, что каждый член суммы

(„:,)-(„:.)=Е(г-> --nvn-iTA*)

является неотрицательным Коэффициент (ij) неотрицателен, так как z >п-1; неотрицателен и ("+5*), так как х > z + 1. Поэтому пз z < у < х следует, что (""+1*) -

/x-z-l+k\

\ к+1 )•

Нужный результат очевиден при ж = уиг = п - 1. В противном случае

(:)-(:)-(„1,)=Е(„!7!>-м=Е,(:::)<.-«.

что меньше или равно

Е1(::>-м-;4((„:,)-(л.)-а))-»

так как fo - 1 = ж - у - 1 < 0. [L. Lovasz, Combinatoriai Problems and Exercises, Problem 13.31(a).]