AOP_Tom1 (1021736), страница 19
Текст из файла (страница 19)
23). Хотя Г(х) равна бесконечности для отрицательного целого или равного нулю х, функция 1/Г(х) корректно определяетси для всех комплексных х (см. упр. 1.2.7-24). Применяя гамма-функцию в теоретических исследованиях, часто прихсдится пользоваться интегральным представлением Германа Ганкеля (Негшапп Нап!се!): (17) прячем путь интегрирования в комплексной плоскости идет из — оо по отрицательной части действительной оси, затем огибает начало координат в положительном направлении (против часовой стрелки) и опять по отрицательной части оси Х возвращается в — оо.
[Хшйлсйпй Иг МаНь ши! Рйуш7с 9 (1864), 1-21.] Во многих формулах дискретной математики используются произведения факторнельного типа, которые называются фактлориальнмми сшепенями. Для положительного целого й величины хй и х" определяются следующим образом: *-'= (х — Ц...(х — Л+Ц=Ц(х-у); (18) х = х(х + 1)... (х + Л вЂ” 1) = П(х + 2).
Так, например, величина р е из (2) — зто просто пь. Заметим, что х = (х+ х — 1)- = ( — 1) ( — х)-. (26) Общие формулы УПРАЖНЕНИЯ 1. [00) Сколькими способами можно перетасовать колоду нз 52 карт? 2. [!О[ Используя обозначения из соотношения (2), покажите, что р„1„6 = р, и объясните, почему это так. х! 1 Г(х+ к) (21) (х — к)! Г(х) можно использовать лдя определения факториальных степеней для не целых значений Л. [Обозначение хе ввел А.
Кипении (А. Саре16) в работе Сюгпа!е Ж Маеетабсйе й' Вамаб!пп 31 (1893), 291 — 313.[ Захватывающая история изучения факториалов со времен Стирлинга до наших дней прослежена в статье Р. Л. ПауЬ "1.еопЬагс! Еп!ег'е ш!ейгай А Ыесобса! ргоб!е о1 спе бапппа Гипсе!оп" АММ 66 (1959), 849-869; см. также работу Л.
Ппс!са, Агс!пее Гог Н!а!осу оу Ехасг Бс!евсеи 31 (1984), 15-34. 3. [10] Какие перестановки чисел (1, 2, 3,4, 5] мол|но построить нз перестановки 3 1 2 4 с помощью методов 1 и 2 соответственно? 4. [15] Учитывая тот факт, что !об|о 1000! = 25б?.60464..., определите точно, скалько цифр содержится в числе 1000!. Какав цифра стоит в сяыршем разряде? Какая в ? б. [75] Оцените значение 8! с помощью следующей более точной прибляжеивой формулы Цтнрлишн: кй =,/2 ("-) (1+ — ').
6. [17] Используя формулу (8), запишите 20! в виде произведенив простык сомножи.- телей. 7. [М10] Покажите, что "обабщеннэл термиальная" функция, определенная формулой (10), удовлетворяет тов|деству х? = х + (х — 1)? длв всех действительных я. 8. [НМ15] Показ|иге, что предел в формуле (13) равен и! и в том случае, |тли и— неотрицательное целое число. 9. [М10] Определите значения Г(-') и Г( — -') на основании того, что (|)! = |/я/2. ь 10. [НМЗО] Справедливо лн тождество Г(к+ 1) = хГ(х) длв всех действительных чисел к (см. упр. 7)? 11. [М15] Пусть представление числа и в двоичной системе выгл|щнт следующим обра.- зом: и = 2" +2 |+...
+ 2', где е| > ет » -. е > Р. Покажите, что «! делитск на 2" но не делится на 2" 'т'. ь 12. [Мйй] (А. Лежандр, 1808.) Обобщим результат предыдущего упражнения. Пусть р — простое число и представление и в системе счисления с основанием р имеет вид и = аьр~ + аыр~ | + + а|р+ ао. Найдите простую формулу, выражающую число р из формулы (8) через и, р и коэффициенты ам 13.
[МЯЛ] (Теорема Вильсона (Игййвп/, на самом деле доказанная Лейбницем в 1682 г.) Если р — простое число, то (р — 1)! пкх1р = р — 1. Докажите это, разбивая элементы нз множества (1, 2,..., р — 1) на пары таких чисел, произведение которых по модулю р равно 1. ь 14. [Мдд] (Л. Штякепьбергер (1. Бс!с!се!Ьегбег)., 1890.) С помощью обозначений нз упр. 12 мо|кно определить и! шо|1р в виде представления в системе счисления с основанием р для любого положительного целого п, тем самым обобщив теорему Вильсона.
Докажите, что и!/р' = ( — 1)"ае!а|!...аь! (по модулю р). 13. [НМ15] Перманента квадратной матрицы вычисляется по той же формуле, что н определитель, на как|дому члену этой формулы присваявается знак "плюс", в то время как в формуле определителя чередуются знаки "плюс" н "минус". Таким образом, перманент матрицы (' ) равен ае|+ Ь/д+ ой+ две+ й/а+ !||Ь. Чему равен перманент матрацы 1х1 1х2 ... 1хп 2х1 2х2 ...
2хп пх1 пх2 ... пхп 16. [НМ15] Покажите, что бескоиечяал сумма в (11) расходится, если и не явлвется неот- рицательным целым числом. 1Т. )НМ20) Докажите, что бесконечное произведение Г? (и+ о!)... (и+ аь) 11 (и+0!) ... (и+Не) равно Г(1+0!) ... Г(1+ 0!)/Г(1+а!) ... Г(1+а!), если и!+ +аь = 0! + +Д, и ни одно из б! не является отрицательным целым числом. 18. (МЯ0) Предположим, что я/2 = з з -' зб "- е...
(Это "произведение Валлиса", полученное Дж. Валлисом (1. %а)5!в) в 1655 году; мы докажем его в упр. 1 2.6 — 43.) Используя предыдущее упражнение, докажите, что (-')! =,/я/2. 19. (НМ22) Обозначим величину, стоящую после "1пп„,," в формуле (15), через Г (х). Покажите, что г г , ь г! Г (х)=з/ ~1 — — ) ! 01=!а / (1 — !) Г* Й, еслих>О. е !в о 20. )НМИ) Учитывая тот факт, что 0 < е ' — (1 — !/т)'" < !~с '/гп, где 0 < ! < т, и предыдущее упражнение, покажите, что Г(х) = 1 е ~1* ' 01 при х > О. 21.
[НМЯб) (Л, Ф. А. Арбогаст (1. р. А. АгЬобаэ!), 1800.) Пусть Р~и — это Ь-я производная функции и по х. По правилу дифференцирования сложной функции В,ю = Р„ю.0„и. ! ! ! Применяя это правило при нахождении второй производной, получим 0зю = Рз ы(Р,'и) + В„в! Р, и. Покажите, что общая формула для производной и-го порядка имеет вид з Р."и = ~' !=о Р' Р! ы В" и Р„в! (,)ь, (Р и) ... (Р и) ь!+аз+" еь =! ь,+мг!--! ь = ь„ьз,...я >о +! —, < и! < —,, гдеп — целое,п>1. е" ! е" )указание. 1+ х < е* для всех действительных х, поэтому (Ь+ 1)/Й < еь а < 1/(Ь вЂ” 1).) 25.
(М20) Выполняется ли для факториальных степеней правило, аналогичное обычному правилу сложения показателей степеней хме" = х х"? 1.2.6. Биномиальные коэффициенты Сочетания из и обвея!лов по /с — зто возможные варианты выбора /с различных элементов из и объектов без учета порядка расположения этих элементов. Приведем пример сочетаний из пяти объектов (и, Ь, с,с(, е) по три: аЬс, аЬЫ, аЬе, асс(, асе, а!1е, Ьс0, Ьсе, Ьде, с!1е. (11 ь 22. )НМ20] Попробуйте поставить себя на место Эйлера, когда он искал способ обобщения понятия факториала и! для нецелых значений и. Так как (и+ !).'/и! умножить на ((и+ з) + з)!/(и+ -')! равно (н+ 1)!/и! = и+ 1, кажется естественным, что (и+ -')!/н! должно приближенно равняться !/ж Аналогично (и+ 1)!/и! должно приближенно равз з ияться !/ж Выдвиньте гипотезу о поведении отношения (и+я)!/и!, когда н стремится к бесконечности.
Будет ли ваша гипотеза справедлива для целых х? Можно ли с ее помощью найти приближенное значение х! для нецелого х? 23. (НМ20] Докажите формулу (16), исходя из того, что яз П~ !(1 — зз/и ) = э!и яз. ь 24. )НМ81] Докажите полезные неравенства Таблица 1 ТАБЛИЦА БИНОМИАЛЬНЫХ КОЭФФИЦИЕНТОВ (ТРЕУГОЛЬНИК ПАСКАЛЯ) Подсчитать общее число сочетаний из и объектов по й совсем несложно.
Соотношение (2) из предыдущего раздела говорит о том, что существует п(п — 1)... (и — й+ 1) способов выбора первых и объектов в перестановке, причем каждое сочетание из Й элементов встречается ровно Й! раз, так как для любого набора из Й объектов существует к( перестановок. Поэтому для числа сочетаний из и элементов по к, которое мы обозначим через(„"), получаем следующую формулу: и'1 п(п — 1)... (и — й+ 1) ()= й/ й(й - 1)...
(Ц (2) Например, т ~ т(т — 1) ...(г — Й + 1) т- ТТ т + 1 — 1 ()- ь/ ь(ь ц (ц И 11 (") =О, целое й < О. В частных случаях имеем: (т) т(т — 1) ( )=1, ( )=т, (4) В табл. 1 приведены значения биномиэльных коэффициентов для небольших целых величин т и и; биномиальные коэффициенты для О < т < 4 следует запомнить. Это число сочетаний, которые мы нашли в (1).
Величины (",) (читается "число сочетаний из и по к") называются биномиальнмми коэффициентами и имеют очень широкое применение. Вероятно, это самые важные величины, использующиеся в анализе алгоритмов, поэтому я настоятельно советую читателю познакомиться с ними. Формулу (2) можно использовать для определения ("„) даже в том случае, когда и не является целым числом. Точнее говоря, определим число сочетаний (") для всех действительных т и всех целых й следующим образом: Рмс. 8.
Геометрическая интер- претация ("+~), и = 4. Читатель, вероятно, уже заметил в табл. 1 несколько интересных закономерностей. Существуют буквально тысячи тождеств, в которых содержатся бнномиальные коэффициенты, и на протяжении многих веков не прекращалось изучение их замечательных свойств.
Соотношений, в которых используются биномиальные коэффициенты, так много, что открьггие нового тождества не волнует практически никого, кроме самого исследователя. Для работы с формулами, использующимися в анализе алгоритмов, умеяие обращаться с биномиальными коэффициентами является совершенно необходимым, поэтому в данном разделе я попытаюсь в доступной форме обьяснить, квк это делается.
Марк Твен однажды попьпался свести все шутки примерно к десяти основным типам (о дочери фермера, теще и т. д.), а мы попробуем свести тысячи тождеств к небольшому набору основных операций, позволяющих решить практически любую задачу, в которой фигурируют биномиальные коэффициенты. Числа г в й из („') в большинстве случаев будут целыми. Заметим, что отдельные методы, о которых пойдет речь, применимы только в подобной ситуации. Поэтому справа от каждого пронумерованного соотношения будем подробно перечислять все имеющиеся ограниченна на переменные.
Например, в соотношении (3) указано, что й — целое; в то же время для т никаких ограничений нет. Заметим, что самыми полезными являются те тождества, которые справедливы при наименьшем числе ограничениИ. Биномиальиые к<юффициеиты имеют продолжительную и интересную историю. Табл. 1 называется треугольником Паскаля, потому что она была приведена в работе Блеза Паскаля Т1 шйе 4п ТНап81е Апйшейк1пе, вышедшей в 1653 году. Этот трактат имел очень важное значение, так как он представлял собой одну из первых работ по теории вероятностей; но биномиальные коэффициенты были открыты не Паскалем (к этому времени они были уже хорошо известны в Европе).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
