AOP_Tom1 (1021736), страница 21
Текст из файла (страница 21)
) целое и > целое з > О, целое т > О, целое г > 0; (25) 1. Суммы произведений. Чтобы набор операций с биномиальными коэффициентами был полным, приведем следующие общие тождества, которые доказываются в конце данного раздела. Эти формулы показывают, чему равны суммы произведения двух биномиальных коэффициентов при различных положениях индекса суммирования 1г: Самым важным из этих тождеств является соотношение (21). Чтобы облегчить его запоминание, можно интерпретировать правую часть как количество способов выбора и человек среди т мужчин и э женщин, а каждый член суммы слева— как количество способов выбора к мужчин и и — к женщин.
Тождество (21) обычно называют сверткой Вандермонда, поскольку А. Вандермонд (А. Уапоегшопйе) опубликовал его в журнале Меш. Асас1. Иоу Яс1епсев Раг1з (1772), 489 — 498. Но на самом деле это тождество уже было приведено в трактате Чжу Ши-Цзе от 1303 года, о котором упоминалось выше [см. 1.
Хееопаш, Яс1елсе алс( С1и)1гаСюл 1п СЛ1па 3 (СашЬг1ойе Цп1тегЫу Ргеээ, 1959), 138 — 139]. Если в тождестве (26) т = гк, то мы избегаем появления нуля в знаменателе, сокращая на (г — И) и числитель, и знаменатель. Поэтому (26) является полиномиальным тождеством от переменных г, э, 1. Очевидно, что (21) — это частный случай (26) при 1 = О. Следует отметить не совсем очевидные способы применения тождеств (23) и (25).
Часто бывает полезно заменить простой биномиэльный коэффициент в правой части тождества более сложным выражением из левой части, изменить порядок суммирования и упростить его. Левые части тождеств можно рассматривать как разложения Тождество (23) используется для отрицательных а, а формула (25) — для положительнь|х а. На этом наше изучение "науки о биномиальных коэффициентах" заканчивается. Советую читателю внимательно разобраться в приведенных формулах; особенно это касается тождеств (5)-(7), (9), (13)., (17), (20) и (21).
Обведите их своим любимым маркером! Имея в своем распоряжении все эти методы, мы сможем решить практически любую возникшую задачу по меньшей мере тремя различными способами. Приведем несколько примеров. Пример 1. Чему равна сумма ~ ( ) ( ) й, где г — положительное целое числа? 2-~~) Ь) Решение. Формула (7) позволяет избавиться от "внешнего" й: ~:("Н')"=~:(."Н':~) = ~:(")(' ) Теперь применим формулу (22) при п = -1. В результате получим ( ) ( ) к = ( )э, целое г > О. т / и+й 1/2й1( — 1)ь Пример 3. Чему равна сумма ~ ) ( ), если т и и — положителя ные целые числа? ь ~т+2й) ~ й ) й+1' Решение. Если бы т было равно нулю, мы получили бы ту же сумму с которой имели дело в примере 2. Но присутствие ненулевого т означает, что мы не можем воспользоваться методом из предыдущего примера, так как уже на первом шаге формулу (20) применить нельзя.
В этой ситуации имеет смысл усложнить задачу, заменив нежелательный коэффи иент ( "~~ ь) суммой членов вида (*зь ). В результате задача сведется к ряду задач, решать которые мы уже умеем. Итак, воспользуемся формулой (25), положив г=и+й — 1, п1=2й, е=О, и=т — 1 В результате получим Е Е (п+ й — 1 — у') (2й) ( у ) (-1)е ь о<~< ве-1 (29) ( ) 3( -1-0о. О<1<в Все члены этой суммы, за исключением того, который соответствует у = и — 1, обращаются в нуль. Таким образом, окончательно получаем (" ) Эта задача оказалась довольно сложной, но все-таки вполне разрешимой; все наши действия были обоснованы. Советую вам внимательно изучить решение, так как в нем продемонстрированы тонкие моменты, связанные с ограничениями, которые наложены на тождества.
Но на самом деле существует более оптимальный метод решения этой задачи; читателю предоставляется самостоятельно найти способ преобразования исходной суммы таким образом, чтобы к ней можно было применить формулу (26) (см. упр. 30). Пример 4. Докажите, что Аь(г,1)А„, ь(е,1) = А„(г+ е,1), целое п > О, ь (30) где А„(х,1) — многочлен степени и по х, такой, что 'х — и1х х А„(х,1) = ( ) для хаий и х — п1 Мы хотим выполнить суммирование сначала по й, но для изменения порядка сумо мирования требуется, чтобы суммирование происходило по тем й, которые > 0 и > у — и + 1. К сожалению, последнее условие вызывает проблемы, так как при у > и сумма не определена.
Попытаемся спасти ситуацию. Для начала заметим, что члены суммы (29) равны нулю при и < у < и+ й — 1. Отсюда следует, что й > 1; таким образом, 0 < п+ й — 1 — у < й — 1 < 2й и первый биномиальный коэффициент в формуле (29) обращается в нуль. Следовательно, во второй сумме можно выполнять суммирование по 0 < у < и и теперь с изменением порядка суммирования никаких проблем не будет.
Суммируя по й согласно (28), получим ( )( )( — 1)" "= ( ) = д„„, целое п,целое т > О. (33) Данная формула важна потому, что при п ф г сумма равна нулю. Это позволяет без труда решить задачу, поскольку многие члены суммы оказываются равными нулю, как в примере 3: Ыаь ~~~ ( ) (™)( — 1) ь ь = ~~~ ' Ь! аьбм, = т! ат.
ь Обратите внимание на то, как нам удалось получить уравнение, в котором содер- жится только один неизвестный коэффициент — а . Для этого мы сложили равен- ства (32) для п = О, 1,.... умноженные на подходящие коэффициенты. В результате имеем в>0 0<пят ( ) 0<п<т Таким образом, задача 5 решена. А теперь давайте более подробно рассмотрим, что означает соотношение (33). Для неотрицательных целых г и гп имеем твк как остальные члены после суммирования исчезают.
Выбирая соответствующим образом коэффициенты с;, можно представить любой многочлен от Ь в виде суммы биномивльных коэффициентов с верхним индексом Ь. Поэтому 1( — 1)" ~(Ье+Ь~Ь+. +Ь„Ь') = г! Ь„, целое т > О, (34) (Й) где Ье + . + Ь,й" — произвольный многочлен степени не выше т. (Эта формула не должна быть большой неожиданностью для студентов, изучающих численный анализ, так как ~„(„") ( — 1)" ьу(х + й) — это "г-я разность" функции у(х).) Из (34) можно непосредственно получить многие другие соотношения, которые кажутся сложными на первый взгляд и часто сопровождаются очень длинными доказательствами, например ( )( )( — 1)"=1', целоет>О. (35) Задача решения уравнений относительно аы подобных этому, называется задачей обращения. Метод, которым мы воспользуемся, применим для решения всех аналогичных задач.
Идея решения основана на частном случае тождества (23) для з = О: В учебниках, подобных нашему, обычно приводится множество впечатляющих примеров использования хитроумных приемов, но никогда не упоминаются простые с виду задачи, в которых эти приемы не работают. Приведенные выше примеры, возможно, создали у вас впечатление, что с биномиальными коэффициентами можно делать все, что угодно. Но необходимо заметить, что, несмотря на формулы (10), (11) и (18), похоже, не существует простой формулы для аналогичной суммы при и < гп.
(При а = т существует простая формула. Как она выглядит, вы узнаете из упр. 36.) С другой стороны, эта сумма приобретает законченный внд функции от и, если гп — отрицательное целое число, например (37) Существует также простая формула для суммы, хотя, казалось бы, эта формула должна быть более сложной. Как определить, что пора прекратить работу нгд суммой, которая не поддается дальнейшему упрощению? К счастью, теперь существует простой способ получения ответа на этот вопрос во многих важных случаях. Алгоритм Р.
В. Госпера (?1. %. Соврет) и Д. Зейльбергера (В. Ее!!Ьегйег) позволяет получить замкнутые формы, если они существуют, выраженные через биномиальные коэффициенты, и доказать, что таких форм нет, если они не существуют. Рассмотрение алгоритма Госпера-Зейдельберга выходит за рамки этой книги, но о нем можно прочитать в журнале СМасЛ 55.8. (См. также книгу Петковшека (Рейоъве)г), Вильфа (%!!?) и Зейльбергера (Уе!!Ьегйег) А = В (Ч~е!!еэ!еу, Маге.: А. К. Ре?егэ, 1996).) Главным инструментом выполнения преобразований над суммами биномиальных коэффициентов систематическим и механическим путем является использование свойств гипергеометрическия функций, которые представляют собой бесконечные суммы, определенные через возрастающие факториальные степени следующим образом: (39) Вводная информация об этих важных функциях содержится в разделах 5.5 и 5.6 СМагй. Исторические сведения о данных функциях приводятся также в книге ,?.
Эп!ка, АгсЛпге Еог Н!аготу оЕ Ехасг Бс!евсее 31 (1984), 15 — 34. Существует несколько важных обобщений понятия биномнальных коэффициентов, о которых мы сейчас вкратце поговорим. Во-первых, в качестве нижнего индекса Л в („") можно рассмотреть произвольные действительные числа; см. упр. 40 — 45. Во-вторых, существует также обобщенная формула (40) которая принимает вид обычного биномиального коэффициента ('), = (;,), если в (40) перейти к пределу при д, стремящемся к 1. Это станет очевидным, если разделить каждый сомнолаггель числителя и знаменателя на 1 — 9. Основные свойства таких "д-номиальных коэффициентов" обсуждаются в упр.
58. Но для наших целей самым важным обобщением является полинамиальнмй коэффицигтгш < й~ + йг + - -. + й ~ (й, + йг + "+ й )! й1 йг ° ° ° 1 ив йг йг... йт. Главное свойство полиномиальных коэффициентов выражается обобщением соотно- шения (13): (хг+хг+. +х,ч)" = ~~~ х гяг*...хг . (42) 1й„й„...,й У Ь1+ь*+-.+г гя Важно отметить, что любой полиномиальный коэффициент можно выразить через биномивльные коэффициенты с й1+йг+" +й~~ (й1+й21 (й1+йг+йг~ (й1+йг+.-.+йв~ йг йг - ° й~а ~ йг / ~ й1+йг / ~ й1+'''+йт — 1 и, следовательно, применить уже известные нам методы работы с биномиальными коэффициентами. В обеих частях тождества (20) содержится триномивльный коэффициент И в завершение этого раздела дадим краткий анализ преобразования многочлена, представленного в виде степеней переменной х, в многочлен, выраженный череэ биномиальные коэффициенты.
Коэффициенты, фигурирующие в таком преобразовании, называются чпсламп Сгпирлинга; эти числа возникают при изучении самых разнообразных алгоритмов. Числа Стирлинга бывают двух видов. Числа Стирлинга первого рода обозначим через (ь), а второго рода — через ("). Эти обозначения, введенные Йованом Кара- мата (Логан Кагашаса) [Магйешабса (С1н)) 9 (1935), 164-178), имеют неоспоримые преимущества над многими другими (см. В. Е. Кппгп, АЛЫХ 99 (1992), 403-422]. Фигурные скобки в записи (") легко запомнить потому, что они обычно обозначают множество, а Я вЂ” это число способов разбиения множества из и элементов на й непересекающихся подмножеств (упр. б4).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
