Д. Кнут - Искусство программирования том 1 (1119450), страница 19
Текст из файла (страница 19)
также работу Л. Ппсйа, АгсЬ1те уог Нийогу оу Ехас1 Яс[епссн 31 (1984), 15-34. 3. [10] Какие перестановка чисел (1, 2,3,4, 6) моною построить из перестановки 3 1 2 4 с помощью методов 1 и 2 соответственно? 4. [13) Учитывая тот факт, что !об, 1000! = 2567.60464..., определите точно, сколько цифр содержится в числе 1000!. Какая цифра стоит в сягарогсм разряде? Какая в ла0 е? 6. [15) Оцените значение 8! с помощью следующей более точной прибляженной формулы Цтирлинга: "'ж'""Р) ("ж) 6.
[17) Используя формулу (8), запиппгге 20! в виде произведении простых сомножителей. 7. [М10) Покажите, что "обобщенная термнальная" функщгя, апределениал формулой (10), удовлетворяет тождеству х? = х + (х — 1)? для всех действительных х. 8. [НМ15) Покажите, что предел в формуле (13) равен и! и в том случае, если и— неотряпательное целое число. О. [М10] Определите значения Г(г) и Г( — 1) на основании того, что (1)! = Щ2, ° 10. [ВМ30] Справедливо ли тождество Г(к+1) = яГ(к) для всех действительных чисел к (см. упр. 7)? 11.
[М15] Пусть представление числа и в двоичной системе выглядит следующим абразом: и = 2" +2'*+-..+2'", где ег > ег » .. е„> О. Покажите, что и! делитглна 2" ' но не делится на 2" '+~. ь 12. [М88] (А. Лежандр, 1808.) Обобщим результат предыдущего упражнения. Пусть р — просгое число и прецставпение и в системе счисления с основанием р имеет вид и = агр + аь ~р~ ~ + ... + а~р + ао. Найдите простую формулу, выражающую число ?г из формулы (8) через и, р и коэффициенты аг. 13.
[МЙЗ] (7еорема Вильсона (ИггЬои), на самом деле даказаннал Лейбницем в 1682 г.) Если р — простое число, то (р — 1)! шеар = р — 1. Докажите это, разбивая элементы из множества (1, 2,..., р — 1) на пары таких чисел, произведение которых по модулю р равно 1. ь 14. [Мйй! (Л. Штикельбергер (1,. Бс!оке!Ьегбег)., 1890.) С помощью обозначений из упр. 12 можно определить и! гаобр в виде представления в системе счисления с основанием р для любого положительного целого и, тем самым обобщив теорему Вильсона. Докажите, что и!10" = ( — 1)"ао!а~!...аь! (по модулю р).
16. [ВМ15] Нерггапсит квадратной матрицы вычисляется по той же формуле, что я определитель, ио кюкдому члену этой формулы присваивается знак "плюс", в то время как в формуле определителя чередуются знаки "плюс" и "минус". Таким образом, перманент матрицы (" ) равен ае1+ Ь10+ спй+ усе+ й?а+ (пв. ~(ему равен перманент матрицы 1х1 1х2 ... 1хи 2х1 2х2 ...
2хи их1 их2 ... ггхи 16. [НМ15) Покахпгте, что бесконечнгл сумма в (11) расходится, если и не являегса неотрицательным целым числом. 1Т. [НМ20] Докажите, что бесконечное произведение 1 1 (и+ а!) ... (и+ о!) 11 (и+ 0!) ... (и-~ 04) равно Г(1+0!) ... Г(1+ 02)/Г(1+о!) ... Г(1+о!), если он+ .+аг =0!+..+04 пни одно из О! не является отрицательным целым числом.
18. [м20] предположим, что !г/2 = 2 2 4 4 "- 4 .. (это "произведение Валлиса", полученное Дж. Валлисом (Л. %а)йэ) в 1655 году; мы докажем его в упр. 1.2.6 — 43.) Используя предыдущее упражнение, докажите, что (-')! ш г/к/2. 19. [НМхв) Обозначим величину, стоящую после "1пп " в формуле (15), через Г (х). Покажите, что г '! г! Г (х) =4[ ~1 — — ) ! 02=ш /! (1 — 2) 1* ~Ж, еслих>'О. о о 20. [ЛМ21) Учитывая тот факт, что 0 < е ' — (1 — 2/пг) < 1 е '/гл, где 0 < 2 < пг, и предыдущее упражнение, покажите, что Г(х) = ) е М* '01 при х > О. 21.
[НМхб] (Л. Ф. А. Арбогаст (1. Р. А. АгЪобаэг), 1600.) Пусть Вги — это Ь-я производная функции и по х. По правилу дифференцирования сложной функции Р ш = В„ш Р! и, 1 1 Применяя это правило при нахождении второй производной, получим Р ш = В„ш(Р,и) + 2 2 1 2 Р„ш В,и. Покажите, что обигал формула для производной и-го порядка имеет вцд 1 2 и и'. Р"ш= ~ ~ В!ш,, „,,„(Р и) '...(В,"и) ". !=о г, г,+, 244242+ 4- Ц= г,,г,,,г„йо ь 22. [НМЯО] Попробуйте поставить себя на место Эйлера, когда он искал способ обобщения понятия факториала и! для нецелых значений и. Так как (и+ 1)!/и! умножить на 2 1 ((и+ -') + 2)!/(и + 2)! равно (и + 1)!/и! = п + 1, кажетси естественным, что (и+ -)!/и! должно приближенно равняться,,/и. Аналогично (и+ -')!/и! должно приближенно равняться 1/й.
Выдвиньте гипотезу о поведении отношения (и+к)!/и!, когда и стремится к бесконечности. Будет ли ваша гипотеза справедлива для целых ху Можно ли с ее помощью найти приближенное значение х! для нецелого хУ 23. [НМ20) Докажите формулу (16), исходя из того, что кх П„,(1 — 22/п2) = сйпкх. ь 24. [НМ31] Докажите полезные неравенства -1- ! — < и! < —, где и — целое, и > 1. е е — 1 ' — 1' [Указание. 1+ х < е для всех действительных х, поэтому (Ь+ 1)/Ь < е!12 < Ь/(Ь вЂ” 1).) 25. [М00) Выполняется ли для факториальных степеней правило, аналогичное обычному правилу сложения показателей степеней х +" = х х" у 1.2.6. Биномиальные коэффициенты Сочеглаиил из и обаекпгов по Ь вЂ” -это возможные варианты выбора )2 различных элементов из и объектов без учета порядка расположения этих элементов.
Приведем пример сочетаний из пяти объектов (а, Ь, с, гг, е) по три: аЬс, аЫ, абе, асг), асс, аг)е, Ьсг), бее, Ые, сг(е. (41 Таблица 1 ТАБЛИЦА БИНОМИАЛЬНЫХ КОЭФФИЦИЕНТОВ (ТРЕУГОЛЬНИК ПАСКАЛЯ) Подсчитать общее число сочетаний из и объектов по й совсем несложно. Соотношение (2) из предыдущего раздела говорит о том, что существует и(п — 1)... (и — к+ 1) способов выбора первых )с объектов в перестановке, причем каждое сочетание из )с элементов встречается ровно )с! раз, так как для любого набора из )с объектов существует к! перестановок, Поэтому для числа сочетаний из п элементов по к, которое мы обозначим через("), получаем следующую формулу: (2) Например, Это число сочетаний, которые мы нашли в (1).
Величины (ь) (читаетсЯ "число сочетаний из и по кь) называютсЯ биномиальными коаффициеигнами и имеют очень широкое применение. Вероятно, это самые важные величины, использующиеся в анализе алгоритмов, поэтому я настоятельно советую читателю познакомиться с ними. Формулу (2) можно использовать для определения ("„) даже в том случае, когда н не является целым числом. Точнее говоря, определим число сочетаний („") для всех действительных г и всех целых Й следующим образом: целое х > О; целое й < О. В частных случаях имеем: (г) г(г — 1) (4) В табл.
1 приведены значения биномиальных коэффициентов для небольших целых величин г и !с; биномиальные коэффициенты для О < г < 4 следует запомнить. Бяномиальные коэффипленты имеют продолжительную и интересную историю. Табл. 1 называется треугольником Паскаля, потому что она была приведена в работе Блеза Паскаля Тгшйе дн ТНаи81е Апййшейк1пе, вышедшей в 1653 году. Этот трактат имел очень важное значение, так как он представлял собой сдну из первых работ по теории вероятностей; но биномиалъпые коэффяциенты были открыты не Паскалем (к этому времени оня были уже хорошо известны в Европе). Табл. 1 приведена также в трактате Сы юэль юй цзянь (кЯшмовое зеркало четырех элементов" ), написанном китайским математиком Чжу Ши-Цзе (81пЬ-СЬ1еЬ СЬп) в 1303 гаду.
В нем говорятся, что биномиальные коэффициенты известны с давних времен. Самое раннее (из известных) шдробное описание биномиэльных коэффициентов встречается в комментарии, написанном в 10 веке Халаюдхой (На(аунбЬа) к произведению древнеиндийской классики Чаяда-сутра Пингала.
(См. Г. Чакравартн (С. СЬайгатэгг1), ВпИ. Са1сис1а МагЬ. 8ос. 24 (1932)„79 — 88.] Прямерно в 1150 году индийский математик Бхаскара Ачарья (ВЬакйага АсЬагуа) в книге Лилавлти, ч. 6, гл. 4, дал очень четкое описание биномиальных коэффициентов. Для малых значений Ь эти коэффициенты быля известны намного раньше; упоминание о них вместе с геометрической интерпреш- -',о цяей встречалась в работах греческих и римских авторов (рис. 8). Обозначение („') было введено Андреасом фон Этгингсхаузеном (Апдгеаз топ ЕррпйэЬапэеп) в княге Вйе сотЬшагагшсйе Апа1уяз (Иеппа, 1826). Ряс. 6. Геометрическая ивтер- прешция ("+~), и = 4.
Читатель, вероятно, уже заметил в табл. 1 несколько янтересных закономерностей. Существуют буквально тысячи тождеств, в которых содержатся биномиальные коэффициенты, и на протяжении многих веков не прекращалось изучение их замечательных свойств. Соотношений, в которых используются бнномиальные коэффициенты, так много, что открытие нового тождества не волнует практически някого, кроме самою исследователя.
Для работы с формулами, использующимися в анализе алгоритмов, умение абрапшться с биномиальнымн коэффициентами является совершенно необходимым, поэтому в данном разделе я попьггаюсь в доступной форме объяснить, как это делается. Марк Твен однажды попытался свести все шутки примерно к десяти основным тяпам (о дочери фермера, теще и т. д.), а мы попробуем свести тысячи тождеств к небольпюму набору основных операций, позволяющих решать практически любую задачу, в которой фигурируют бяномнальные коэффкцненты. Числа г и Ь из (;,) в большинстве случаев будут целымя.
Заметим, что отдельные методы, о которых пойдет речь, применимы только в подобной ситуации. Поэтому справа от каждого пронумерованного соотношения будем подробно перечислять все имеющиеся ограничения на переменные. Например, в соотношения (3) указано, что Ь вЂ” целое; в то же время для г никаких ограничений нет. Заметим, что самыми полезными являются те тождества, которые справедливы при наименьшем числе ограничений. А теперь давайте изучим основные методы работы с биномиальными коэффициентами. А. Факторнальное представление. Из соотношения (3) непосредственно полу- чаем ()=.(. ). и~ и.' ) =,, целое и > целого lг > О..
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
