Задача решения уравнений относительно Пк, подобных этому, называется задачей обращения. Метод, котдрым мы воспользуемся, применим для решения всех аналогичных задач.

Идея решения основана на частном случае тождества (23) для s = 0:

(I)(n)~~* = (n-r) целое n,целое г >0. (33)

Данная формула важна потому, что при п ф г сумма равна нулю. Это позволяет без труда решить задачу, поскольку многие члены суммы оказываются равными нулю, как в примере 3:

Е"С)(-)"-"=??(:)-ч:)(-г-" =Ei-E(:)(:)(-r-"

= YklokSkm = т\ат-

Обратите внимание на то, как нам удалось получить уравнение, в котором содержится только один неизвестный коэффициент - От- Для этого мы сложили равенства (32) для п = 0,1,..., умноженные на подходящие коэффициенты. В результате имеем

"n т\\п - Р (m-n)!~,/- n!

n>0 0<n<m 0<n<m

Таким образом, задача 5 решена. А теперь давайте более подробно рассмотрим, что означает соотношение (33). Для неотрицательных целых гит имеем

?a)<-)-(4S)

так как остальные члены после суммирования исчезают. Выбирая соответствующим образом коэффициенты с,-, можно представить любой многочлен от fc в виде суммы биномиальных коэффициентов с верхним индексом к. Поэтому

Y{l)i-V~ibo+hk + --- + brk) = r\br, целое г > О, (34)

где Ьо + + Ьгк - произвольный многочлен степени не выше т. (Эта формула не до.лжна быть большой неожиданностью для студентов, изучающих численный анализ, так как Ylk + )-™ "" разность" функции f(x).)

Из (34) можно непосредственно получить многие другие соотношения, которые кажутся сложными на первый взгляд и часто сопровождаются очень длинными доказательствами, например

в учебниках, подобных нашему, обычно приводится множество впечатляющих примеров использования хитроумных приемов, но никогда не упоминаются простые с виду задачи, в которых эти приемы не работают. Приведенные выше примеры, возможно, создали у вас впечатление, что с биномиальными коэффициентами можно делать все, что угодно. Но необходимо заметить, что, несмотря на формулы (10), (11) и (18), похоже, не существует простой формулы для аналогичной суммы

Ё(г)=(:)чт)-С)

при п < т. (При п = т существует простая формула. Как она выглядит, вы узнаете из упр. 36.)

С другой стороны, эта сумма приобретает законченный вид функции от п, если т - отрицательное целое число, например

:(")=<-:rm. (зг,

Существует также простая формула

£(:)(-?)=-?гг) <»»i

для суммы, хотя, казалось бы, эта формула должна быть более сложной.

Как определить, что пора прекратить работу над суммой, которая не поддается дальнейшему упрощению? К счастью, теперь существует простой способ получения ответа на этот вопрос во многих важных случаях. Алгоритм Р. В. Госпера (R. W. Gosper) и Д. Зейльбергера (D. Zeilberger) позволяет получить замкнутые формы, если они существуют, выраженные через биномиальные коэффициенты, и доказать, что таких форм нет, если они не существуют. Рассмотрение алгоритма Госпера-Зейдельберга выходит за рамки этой книги, но о нем можно прочитать в журнале CMath §5.8. (См. также книгу Петковшека (Petkovsek), Вильфа (Wilf) и Зейльбергера (Zeilberger) А = В (Wellesley, Mass.: А. К. Peters, 1996).)

Главным инструментом выполнения преобразований над суммами биномиальных коэффициентов систематическим и механическим путем является использование свойств гипергеометрических функций, которые представляют собой бесконечные суммы, определенные через возрастающие факториальные степени следующим образом:

= vi. (39)

bi, bn

Вводная информация об этих важных функциях содержится в разделах 5.5 и 5.6 CMath. Исторические сведения о данных функциях приводятся также в книге J. Dutka, Archive for History of Exact Sciences 31 (1984), 15-34.

Существует несколько важных обобщений понятия биномиальных коэффициентов, о которых мы сейчас вкратце поговорим. Во-первых, в качестве нижнего индекса к в () можно рассмотреть произвольные действительные числа; см. упр. 40-45.

Во-вторых, существует также обобщенная формула

ill-

которая принимает вид обычного биномиального коэффищ1ента (][) = (][), если в (40) перейти к пределу при q, стремящемся к 1. Это станет очевидным, если разделить каждый сомножитель числителя и знаменателя на 1 - д. Основные свойства таких "q-номиальных коэффициентов" обсуждаются в упр. 58.

Но для наших целей самым важным обобщением является полиномиальный коэффициент

+ (fc.-bA:.-b...-.M! ,0. (41)

\ fcl,*:2,...,Km J *:i!*:2!...fcm!

Главное свойство полиномиальных коэффициентов выражается обобщением соотношения (13):

в1-Ь*2Н-----l-tm=n

(42)

Важно отметить, что любой полиномиальный коэффициент можно выразить через биномиальные коэффициенты

rki+k2+-+km\ fki+кЛ Гк1+к2+кз\ (ki+k2+- Ч-кЛ . . \ ki,k2,...,km ) V *1 А *г+*2 J\ki+-+kr„.iJ

и, следовательно, применить уже известные нам методы работы с биномиальными коэффициентами. В обеих частях тождества (20) содержится триномиальный коэффициент

( " )

\к, т - к, г - т/

И в завершение этого раздела дадим краткий анализ преобразования многочлена, представленного в виде степеней переменной х, в многочлен, выраженный через биномиальные коэффициенты. Коэффициенты, фигурирующие в таком преобразовании, называются числами Стирлинга; эти числа возникают при изучении самых разнообразных алгоритмов.

Числа Стирлинга бывают двух видов. Числа Стирлинга первого рода обозначим через ["], а второго рода-через {}. Эти обозначения, введенные Йовано.м Кара-мата (Jovan Karamata) [Mathematica (Cluj) 9 (1935), 164-178], имеют неоспоримые преимущества над многими други.ми [см. D. Е. Knuth, AMM 99 (1992), 403-422]. Фигурные скобки в записи {]} легко запомнить потому, что они обычно обозначают множество, а {}-это число способов разбиения множества из п элементов на к непересекающихся подмножеств (упр. 64). Числа Стирлинга первого рода [] также имеют комбинаторную интерпретацию, которая будет подробно рассмотрена в разделе 1.3.3: [] -это число перестановок п букв с к циклами.

В табл. 2 представлены треугольники Стирлинга, в некоторых отношениях ана-ло1ичные треугольнику Паскаля.