Д. Кнут - Искусство программирования том 1 (1119450), страница 21
Текст из файла (страница 21)
(Эта формула не должна быть большой неожиданностью для студентов, изучающих численный анализ, так как 2 ь („") ( — 1)" ~у(х + Ь) — это "г-я разность" функции У(х).) Из (34) можно непосредственно получить многие другие соотношения, которые кажутся сложными на первый взгляд и часто сопровождаются очень длинными доказательствами, например В учебниках, подобных нашему, обычно приводится множество впечатляющих примеров использования хитроумных приемов, но никогда не упоминаются простые с виду задачи, в которых эти приемы не работают.
Приведенные выше примеры, возможно, создали у вас впечатление, что с бнномиальными коэффициентами можно делать все, что угодно. Но необходимо заметить, что, несмотря на формулы (10), (11) и (18), похоже, не существует простой формулы для аналогичной суммы при и < т. (При и = т существует простая формула. Как она выглядит, вы узнаете из упр. 36.) С другой стороны, эта сумма приобретает законченный вид функции от и, если пс — отрицательное целое число, например (37) Существует также простая формула для суммы, хотя, казалось бы, эта формула должна быть более сложной.
Как определить, что пора прекратить работу над суммой, которая не поддается дальнейшему упрощению? К счастью, теперь существует простой способ получения ответа на этот вопрос во многих важных случаях. Алгоритм Р, В. Госпера (К. ЪЧ. Созрей) и Д. Зейльбергера (П, Уе1!Ъегбег) позволяет получить замкнутые формы, если они существуют, выраженные через биномиальные коэффициенты, и доказать, что таких форм нет, если они не существуют. Рассмотрение алгоритма Госпера-Зейдельберга выходит за рамки этой книги, но о нем можно прочитать в журнале СМайЛ э5.8. (См. также книгу Петковшека (Рей)согяе1с), Вильфа (Ч7111) и Зейльбергера (Хе11Ъег8ег) А = В (1Че!!ея1еу, Мазал А. К.
Рейегя, 1996).) Главным инструментом выполнения преобразований над суммами биномиальных коэффициентов систематическим и механическим путем является использование свойств гипергеометрических функций, которые представляют собой бесконечные суммы, определенные через возрастающие факториальные степени следующим образом: (39) Вводная информация об этих важных функциях содержится в разделах 5.5 и 5.6 СМайЛ. Исторические сведения о данных функциях приводятся также в книге д.
1упй1са, АгсЛ!ге гог Нйяйогу ос Ехасй Яс!епсея 31 (1984), 15-34. Существует несколько важных обобщений понятия биномиальных коэффициентов, о которых мы сейчас вкратце поговорим. Во-первых, в качестве нижнего индекса lс в (,") можно рассмотреть произвольные действительные числа; см. упр. 40-45. Во-вторых, существует также обобщенная формула (),— г~ (1 — «')(1 — «)... (1 — «" + ) 94 (1 — «')(1 — «'-')... (1 — «') (40) которая принимает вид обычного биномиального коэффициента <'), = <'), если в (40) перейти к пределу при «, стремящемся к 1. Это станет очевидным, если разделить калсдьп$ сомножитель числителя и знаменателя на 1 — «. Основные свойства таких "«-номиальных коэффициентов" обсуждаются в упр.
58. Но для наших целей самым важным обобщением является палиномиальний каэффициеи1п < л1+лт+."+кт 1 (л1+л2+."+к 4)' 421 4 а2 4 ° ° ° 44444 а1 ° а2. ° ° ° 44444 ( Главное свойство полиномиальных коэффициентов выражается обобщением соотно- шения (13)1 (* 4* 4 4* )"= 2 < )*'*'...* . 4441 21+ив+-.+2 4 а 1 2 ' 444 ' Важно отметить, что любой полиномиальный коэффициент можно выразить через биномиальные коэффициенты й1 +Й2+ +й Й1 +Й2 Й1 +М2+Йз Й1 +12+ +й (43) и, следовательно, применить уже известные нам методы работы с биномиальны- ми коэффициентами. В обеих частях тождества (20) содержится триномиальный коэффициент И в завершение этого раздела дадим краткий анализ преобразования многочле. на, представленного в виде степеней переменной я, в многочлен4 выраженный через биномиальные коэффициенты.
Коэффициенты, фигурирующие в таком преобразовании, называются числами С1пирлинга; эти числа возникают при изучении самых разнообразных алгоритмов. Числа Стирлинга бывают двух видов. Числа Стирлинга первого рода обозначим через [„], а второго рода — через ("). Эти обозначения, введенные Йованом Кара- мата (3оъэл Кага1паса) (МагЬегаа11са (С!в)) 9 (1935), 164-178], имеют неоглорнмые преимущества над многими другими [см. В.
Е. КппгЬ, АММ 99 (1992), 403-422). Фигурные скобки в записи [1) легко запомнить потому, что они обычно обозначают множество, а [") — это число способов разбиения множества из и элементов на с л непересекающихся подмножеств (упр. 64). Числа Стнрлинга первого рода [Д также имеют комбинаторную интерпретацию, которая будет подробно рассмотрена в разделе 1.3.3: [,"] — это число перестановок п букв с к циклами.
В табл. 2 представлены треугольники Стнрлинга, в некоторых отношениях анало1 нчные треугольнику Паскаля. Таблица 2 ЧИСЛА СТИРЛИНГА ПЕРВОГО И ВТОРОГО РОДА й [".] ["1 ["1 ["1 [".] ["] [".] ° (".) (") (".) (") (") ("1 Ю Р (") 0 О О О О О 1 0 0 0 0 0 1 1 0 0 0 0 1 3 1 0 О О 1 7 6 0 О 0 1 15 25 0 О 0 1 31 90 1 0 0 1 63 301 21 1 0 1 127 966 266 28 1 0 0 0 О 0 0 0 0 1 0 10 1 65 15 350 140 1701 1050 Аппроксимация при больших и приведена в работе 1.Мовег,М.
Ъчутап, А Ьопдоп Маей. Яос. 33 (1958), 133 — 146; Вийе Мами А 25 (1958), 29-43; В. Е. Вагсоп, Р. )Ч. ВатЫ, М. Мегг(п5ьоп, В)отееггйа 47 (1960), 439 — 445; 50 (1963), 169-176; Х. М. Тепипе, Ягийгев гп Арр!гег( Ма15. 89 (1993), 233-243; Н. Б. ЪЪЛН, .7. СотЬгпаеогга7 Тьеогу А64 (1993), 344-349; Н.-К. Нгеап8, А СотЬта1ома7 ТЬеогу А71 (1995), 343-351. Числа Стирлинга первого рода используются для перехода от факториальных степеней к обычным: хп = х(х — 1)... (х — и + 1) и [ ] и-1+ +( цп[ ] = Е(- )"-'["„].". (44) Например, согласно табл.
2 имеем ( )= .= 5 ) = — = — (х — 10х + 35х —:50х +24х). х х- 1 5 4 3 2 5) 5! 120 0 0 1 0 1 1 2 3 б 11 24 50 120 274 720 1764 5040 13068 0 0 0 0 0 0 1 0 б 1 35 10 225 85 1624 735 13132 6769 0 0 О 0 0 1 15 175 1960 0 0 0 0 0 0 0 0 О О 0 0 1 0 21 1 322 28 Числа Стирлинга второго рода используются для перехода от обычных степеней к факториальным: х =( )х + +( )х1+( )хо=~~~ ( )х-. (45) Фактически именно эта формула послужила причиной того, что Стирлинг занялся изучением чисел (") в работе Меспоппв РНегепба11з (Ьопс1оп, 1730).
Например, из табл. 2 имеем хь = хй + 10хт + 25х1+ 15х4 + х-' = 120( ) + 240(4) + 150( ) + 30( ) + ( ) . Формулы сложения: [" ]=-[."] [." ] ("") =-(.").(." ) Формулы обращения (ср, с (33)): Ц( )(-1)"-'=б' „, Я„)[ ](-1)"-"=Б„„. Некоторые частные значения: ( )=[ ]=( )=со, ( )=[ ]=( (46) (47) (48) (49) [ ] = ( ) = О, [ ] = !, ( ) = 1, ( ) = 2" — 1, (50) Формулы разложения: [ ]( )=[ ], ~~ [ ]( )( — 1)ь =[ ]; (51) Ы')(") =("") й"")(")(-' "=(") ( )( — 1) Й" =тп!( (53) А теперь приведем наиболее важные тождества, в которых фигурируют числа Стирлинга. В этих тождествах переменные т и и всегда обозначают неотрицательные целые числа. (54) ~(.":~) ['3(-')ь - = (")' (55) к[."16= [.",1 ~( )(т+1)" "= ( ).
(56) Другие фундаментальные тождества, связанные с числами Стирлинга, приведены в упр. 1.2.6-61 и 1.2.7 — 6 и в разделе 1.2.9 (соотношения (23) и (26) — (28)). Тождество (49) — это только один пример общей закономерности: числа Стирлинга ~„" ~ и 1„" ) являются многочленами от п степени 2т, где т — неотрицательное целое число.
Например, для т = 2 и т = 3 получим следующие формулы: [." 3 =(") "("~') (." ) =("") "(") [ " ~=(")+8( 6 )+6С"+ )'( -з) С 6 )+8С 6 )+6(") Поэтому имеет смысл определить числа ~„' ~ и („' ) для произвольных ействительных (или комплексных) значений г. Используя это обобщение, получаем следующую интересную связь между числами Стирлинга двух родов: (и) [-т| (58) Такая связь называется законом двойственности, который содержался в неявной форме в оригинальных выкладках Стирлинга.
Более того, соотношение (45), в це- лом, остается справедливым в том смысле, что бесконечные ряды (о9) сходятся, когда дайствительная часть х положительна. Вторая формула, т. е. (44) аналогичным образом обобщается на случай асимптотических (но не сходящихся) рядов: '~'[ " ~( 1)ь,-а+О(,™1) «=а (60) (См. упр. 65.) В разделах 6.1, 6.2 и 6.5 СМа~Ь содержится дополнительная инфор- мация о числах Стирлинга и о том, как оперировать ими в формулах. См.
также упр. 4.7-21, в котором будет рассмотрено общее семейство тпезтольников, включа- ющее числа Стирлинга в качестве частного случая. УПРАЖНЕНИЯ 1. [00] Сколько существует сочетаний из п по п — 1? 2. [00] Чему равно ( )? 3. [00] Сколько существует различных способов сдать карты одному игроку во время игры в бридж (13 карт из колоды, состоящей из 52 карт)? 4. [10] Представьте ответ к задаче 3 в виде произведения простых чисел.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
