17. [НМ20] Докажите, что бесконечное произведение

n(n + Ql) ... (n + Qk) (п + 13г) ...{п + 0к)

равно r(l+j3i) ... r(l + j3ifc)/r(l +Qi) ... r(l+Qjfc), если ai + • = i3i+ +/Зк и ни одно из 0i не является отрицательным целым числом.

18. [М20] Предположим, что тг/2 = ff - •••• (Это "произведение Валли-са", полученное Дж. Валлисом (J. Wallis) в 1655 году; мы докажем его в упр. 1.2.6-43.) Используя предыдущее упражнение, докажите, что ()! = •\/7г/2.

19. [НМ22] Обозначим величину, стоящую после "limm-+cx)" в формуле (15), через Тт{х). Покажите, что

Г,„(х) = Jl- У" dt = J\l - t)"e- Ш, если х xiJ.

20. [НМ21] Учитывая тот факт, что О < е" - (1 - t/m)" < te-/m, где О < t < m, и предыдущее упражнение, покажите, что Г(х) = JJ" e~t~ dt при х > 0.

21. [НМ25] (Л. Ф. А. Арбогаст (L. F. А. Arbogast), 1800.) Пусть jDu -это к-я производная функции и по X. По правилу дифференцирования сложной функции Dl-w - Diw Du. Применяя это правило при нахождении второй производной, получим Dw = DIw{DIu) + DIw Du. Покажите, что общая формула для производной п-го порядка имеет вид

z.> = t Е >.,(1,).".,„,(п1).(--)-(»"-

*i+*2-t--l-=u=j

kl+2k2-t------njfcn=n

ki,k2.....*„>0

► 22. [HM20] Попробуйте поставить себя на место Эйлера, когда он искал способ обобщения понятия факториала п! для нецелых значений п. Так как (п + )!/п! умножить на ((п+ i) + )!/(п + )! равно (п + 1)!/п! = п + 1, кажется естественным, что (п + )!/п! должно приближенно равняться Уп. Аналогично (п + Dl/n! должно приближенно равняться и /п. Выдвиньте гипотезу о поведении отношения (п-Ьх)!/п!, когда п стремится к бесконечности. Будет ли ваша гипотеза справедлива для целых х? Можно ли с ее помощью найти приближенное значение х! для нецелого х?

23. [НМ20] Докажите формулу (16), исходя из того, что жг ni(l ~ /") = sin ттг.

► 24. [НМ21] Докажите полезные неравенства

-- < п! < --, где п - целое, п > 1.

gn - 1 gn - I

[Указание. 1 + х < е для всех действительных х, поэтому (к + 1)/к < е* < к/{к - 1).]

25. [М20] Выполняется ли для факториальных степеней правило, аналогичное обычному правилу сложения показателей степеней х™*" = хх"?

1.2.6. Биномиальные коэффициенты

Сочетания из п объектов по к - это возможные варианты выбора к различных элементов из п объектов без учета порядка расположения этих элементов. Приведем пример сочетаний из пяти объектов {а, Ь, с, d, е) по три:

аЬс, abd, abe, acd, асе, ade, bed, bee, bde, cde. {W

Таблица 1

таблица биномиальных коэффициентов (треугольник паскаля)

Подсчитать общее число сочетаний из п объектов по к совсем несложно. Соотношение (2) из предыдущего раздела говорит о том, что существует п(п - 1)... (п - /г-ь 1) способов выбора первых к объектов в перестановке, причем каждое сочетание из к элементов встречается ровно к\ раз, так как для любого набора из к объектов существует к\ перестановок. Поэтому для числа сочетаний из п элементов по к, которое мы обозначим через (), получаем следующую формулу:

п(п - 1)..-in - к + 1)

к{к-1)...{1)

Например,

5-4-3

= 10.

3-2-1

Это число сочетаний, которые мы нашли в (1).

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

Формулу (2) можно использовать для определения () даже в том случае, когда п не является целым числом. Точнее говоря, определим число сочетаний (j) для всех действительных г и всех целых к следующим образом:

* г -Ы - ?

-.-, целое к > 0;

r(r-l)...(r-fc + l)

fc(fc-l)...(l)

= 0,

В частных случаях имеем:

В табл. 1 приведены значения биномиальных коэффициентов для небольших целых величин г и fc; биномиальные коэффициенты для О < г < 4 следует запомнить.

целое fc < 0.

r(r - 1)

Биномиальные коэффициенты имеют продолжительнзю и интересную историю. Табл. 1 назьюс1ется треугольником Паскаля, потому что она была приведена в работе Блеза Паскаля Draite du Ttianje Aritbmetique, вьпиедшей в 1653 году. Этот трактат имел очень важное значение, так как он представлял собой одну из первых работ по теории вероятностей; но биномиальные коэффициенты были открыты не Паскалем (к этому времени они были уже хорошо известны в Европе). Табл. 1 приведена также в трактате Сы юань юй цзянь ("Яшмовое зеркало четырех элементов"), написанном китайским математиком Чжу Ши-Цзе (Shih-Chieh Chu) в 1303 году. В нем говорится, что биномиальные коэффициенты известны с давних времен. Самое раннее (из известных) подробное описание биномиальных коэффициентов встречается в комментарии, написанном в 10 веке Халаюдхой (Halayudha) к произведению древнеиндийской классики Чавда-сутра Пингала. [См. Г. Чакраварти (G. Chakravarti), BuU. Calcutta Math. Soc. 24 (1932), 79-88.] Примерно в 1150 году индийский математик Бхаскара Ачарья (Bhaskara Acharya) в книге Лалавати, ч. 6, 0Z 0\ гл. 4, дал очень четкое описание биномиальных коэффициентов. Для малых значений к эти коэффициенты были известны намного раньше; упоми- CJt--О:-"Ог

нание о них вместе с геометрической интерпрета- CiСм

дней встречалось в работах греческих и римских авторов (рис. 8). Обозначение (][) было введено Андреасом фон Эттингсхаузеном (Andreas von Ettingshausen) в книге Die combinatoriscbe Analy- Рис. 8. Геометрическая интер-sis (Vienna, 1826). претация ("+), п = 4.

Читатель, вероятно, уже заметил в табл. 1 несколько интересных закономерностей. Существуют буквально тысячи тождеств, в которых содержатся биномиальные коэффи1щенты, и на протяжении многих веков не прекращалось изучение их замечательных свойств. Соотношений, в которых используются биномиальные коэффициенты, так много, что открытие нового тождества не волнует практически никого, кроме самого исследователя. Для работы с формулами, использующимися в анализе алгоритмов, умение обращаться с биномиальными коэффициентами является совершенно необходимым, поэтому в данном разделе я попыталось в доступной форме объяснить, как это делается. Марк Твен однажды попытался свести все шутки примерно к десяти основным типам (о дочери фермера, теще и т. д.), а мы попробуем свести тысячи тождеств к небольшому набору основных операций, позволяющих решить практически любую задачу, в которой фигурируют биномиальные коэффициенты.

Числа г и А; из (][) в большинстве случаев будзт целыми. Заметим, что отдельные методы, о которых пойдет речь, применимы только в подобной ситуации. Поэтому справа от каждого пронумерованного соотношения будем подробно перечислять все имеющиеся ограничения на переменные. Например, в соотношении (3) указано, что к - целое; в то же время для г никаких ограничений нет. Заметим, что самыми полезными являются те тождества, которые справедливы при наименьшем числе ограничений.