Д. Кнут - Искусство программирования том 1 (1119450), страница 20
Текст из файла (страница 20)
Эта формула позволяет представлять комбинации факториалов в виде биномиаль- ных коэффициентов, и наоборот. В. Свойство симметрии. Из соотношений (3) и (5) получаем ( ) = ( ), целое и > О,.целое к. (6) Эта формула справедлива для всех целых Й.
Если Й отрицательно нлн больше, чем и, то блломлгльный коэффициент равен пулю (при условии, что и — неотрицательное целое число). С. Внесение-вынесение. В силу определения (3) имеем ) = — ( ), целоекфО. (7) Эта формула очень полезна для комбинирования биномиального коэффициента с другими частями выражения. Выполнив элементарные преобразования, получаем правила причем первое из них справедливо для всех целых Й, а второе - — если Й и г не равны нулю. Мы имеем также еще одно аналогичное соотношение: ) = — ( ), целое(гфг.
(8) Давайте продемонстрируем эти преобразования на примере доказательства формулы (8), используя поочередно формулы (6) и (7): для бесконечного ггпожестеа значений г. Обе части этого равенства являются мнагачленами от г. Ненулевой многочлен степени и может иметь максимум и различных корней. Поэтому, если два многочлена степени < и совладают в и+ 1 или более различных точках, то, вычцтая лх один яз другого, получим, что этн (Замечание. Данное доказательство имеет силу только в случае, когда г — положительное целое число ф (г, так как этого требуют ограничения, наложенные на соотношения (6) и (7).
Утверждается, что формула (8) справедлива для произвольного т ф )г. Доказать это можно с помощью простого, но важного приема. Мы убедились в том, что многочлены тождественно равны. Данный принцип можно использовать для дока- зательства того, что многие тождества, верные для целых чисел, справедливы для всех действительных чисел.] В.
Формула сложения. Очевидно, что основное соотношение ( ) =( )+( ), целое1с, (9) выполняется для табл. 1 (каждое значение равно сумме двух значений из преды- дущего ряда, причем одно находится в том же столбце, а другое — в ближайшем столбце слева) и его можно легко вывести из соотношения (3). Но есть и другой способ. Из формул (7) и (8) получаем т( )+т( ) (т Й)( )+Й( ) т( ) Формула (9) часто используется в доказательствах индукцией по т, когда т — целое число. Е. Формулы суммирования. Повторное применение формулы (9) дает Таким образом, получаем две важные формулы суммирования, которые можно выразить следующим образом: целое и > 0; (10) целое тп > О, целое п > О.
(11) Формулу (11) можно легко доказать нндукцией по и, но давайте посмотрим, как вывести ее из формулы (10) в результате двукратного применения соотношения (б), ( ~( — )+1) ( 1) в предположении, что и > тп. Если и ( тп, то (11) очевидно. Формула (11) применяется очень часто; фактически мы уже вывели ее частные случаи в предыдущих разделах. Например, при т = 1 получаем старую добрую формулу суммы арифметической прогрессии: ( )+( )+" +( ) О+1+ +и ( ) Предположим, нам нужна простая формула для суммы 1э + 2~ + ..
+ иэ. Ее можно вывести, если заметить, что к~ = 2(") + (~); отсюда Эту формулу, выраженную через биномиальные коэффициенты, при желании мож- но снова записать в виде многочлена: 1~ + 2~ + . + иэ — 2 + — 1и(и+ 1)(и + 1). (12) (и+1)и(и — 1) (и+1)и Аналогично можно получить формулу для суммы 1з + 2э+ . + и', и вообще, любой многочлен типа ао + а1Ь + атЬ~ + . + а„,й™ можно представить в виде Ьо(е) + Ь! (",) + . + Ь („",), где Ьо,..., Ьч, — соответствующим образом подобранные коэффициенты. Мы вернемся к этому вопросу несколько позже. Р. Биномиальная теорема. Сформулируем биномиальную теорему, которая, без сомнения, является одним из наших главных инструментов: (х+у)" = ~~~ ( )х~у™, целое г > О.
(13) (14) которое принимается по определению. Мы везде будем следовать этому соглаше- нию. Например, (х+у)' = х~+4хзу+бх~у~+4хуз+у~. (Наконец-то мы можем назакопных основаниях использовать термин "биномиальные коэффициенты" для чисел („')!) Важно отметить, что в формуле (13) мы записали сумму вида 2 „, а не С„ как можно было ожидать. Если на й не наложено никаких ограничений, то суммирование производится по всем целым Ь, — со < Ь < +со. В данном случае две приведенные записи эквивалентны, так как для Ь < О или Ь > г соответствующие члены суммы из формулы (13) обращаются в нуль. Но форма записи 2 „более предпочтительна, так как все операции с суммами выполняются проще, когда утловия суммирования являются более простыми.
Мы существенно сэкономим время и силы, если не будем следить за верхним н/или нижним пределом суммирования; поэтому, по возможности, данные пределы имеет смысл оставлять неопределенными. Выбранный нами тип записи имеет еще одно преимущество: если г не является неотрицательным целым числом, то сумма в формуле (13) становится бесконечной и бииолаиельная теорема математического анализа утверждает, что соотяошен»с (13) с»равеля»во дл» всех г, если ~х/у) < 1.
Следует отметить, чтр формула (13) не противоречит равенству Для целого т можно получить еще одно важное следствие формулы (17): ( ( )! ) = (-1)" 1 (!, целое и > О,целое т. (19) (Положите в (17) г = и и к = п — т и воспользуйтесь формулой (б).) Таким образом, мы переместили и из верхней позиции в нижнюю. Н. Упрощение произведений. Произведения бииомиальиых коэффициентов можно выразить несколькими различными способами, расписывая их через факториалы по формуле (5) и снова возвращаясь к записи для бииомиальиых коэффициентов. Например, ( ) (™) = („) ( „), целое т, целое Й.
(20) Формулу (20) достаточно доказать для т — иелого > т (см. примечания после формулы (8)) и 0 < й ( т. Тогда ( Н )-....— .. — ..-()( -) т! т! т'. (т — Й)! (тй(т — Й1 т ) (. й г! т! (т — т) ! И (т — й) ! к! (т — !с) ! (т — 1) ! (т — т)! ~ й.l ( т — кг! Формула (20) очень полезна в случаях, когда ицдекс (а именно — т) находится и в верхней, и в нижней позициях, а иам нужно, чтобы ои был только в одном месте. Обратите внимание, что (7) является частным случаем (20) при !с = 1. (21) целое т,целое п,целое г > 0; (22) ( ) ( )( — 1)' ~ = ( ), целое п,целое т > 0; (23) целое ! > О,целое т > О,целое гп > 0; (24) целое и > целое е > О, целое гп > О, целое т > 0; (25) 1.
Суммы произведений. Чтобы набор операций с бииомиальиыми коэффициентами был полным, приведем следующие общие тождества, которые доказываются в конце данного раздела. Эти формулы показывают, чему равны суммы произведения двух бииомиальиых коэффициентов при различных положениях индекса суммирования Й: Е( — оу) ( — ф — Е) г ыао Самым важным из этих тождеств является соотношение (21). Чтобы облегчить его запоминание, можно интерпретировать правую часть как количество способов выбора и человек среди т мужчин и э женщин, а каждый член суммы слева— как количество способов выбора й мужчин и и — й женщин.
Тождество (21) обычно называют сверткой Вандермонда, поскольку А. Вандермонд (А. Напс1егшопс)е) опубликовал его в журнале Меш. Асад. Воу. Яс)евсея Раг1э (1772), 489 — 498. Но на самом деле это тождество уже было приведено в трактате Чжу Ш1-Цзз от 1303 года, о котором упоминалось выше (см. 3. 1чеесйаш, Яс~епсе апс( Сл йяайоп ш С)ппа 3 (СашЬг1с(8е 1)пттегэ11у Ргеээ, 1959), 138 — 139]. Если в тождестве (26) т = гас, то мы избегаем появления нуля в знаменателе, сокращая на (т — М) и числитель, и знаменатель.
Поэтому (26) является полиномиальным тождеством от переменных т, э, 1. Очевидно, что (21) — это частный случай (26) при 1 = О. Следует отметить не совсем очевидные способы применения тождеств (23) и (25). Часто бывает полезно заменить простой биномиальный коэффициент в правой части тождества более сложным выражением из левой части, изменить порядок суммирования и упростить его. Левые части тождеств можно рассматривать как разложения Тождество (23) используется для отрицательных а, а формула (25) — для положительных а.
На этом наше изучение "науки о биномиальных коэффициентах" заканчивается. Советую читателю внимательно разобраться в приведенных формулах; особенно это касается тождеств (5)-(7), (9), (13), (17), (20) и (21). Обведите их своим любимым маркером! Имея в своем распоряжении все эти методы, мы сможем решить практически любую возникшую задачу по меньшей мере тремя различными способами. Приведем несколько примеров. Пример 1. Чему равна сумма ~( ) ( ) й, где т — положительное целое число? 2-Ы Ы Решение. Формула (7) позволяет избавиться от "внешнего" 1с: ~(.")(')"=~-(")(' ) = ~(")(' ) Теперь применим формулу (22) при и = -1. В результате получим ( ) ( ) й = ( ) э, целое т > О.
Задача решения уравнений относительно аы подобных этому, называется задачей обрап!екал. Метод, которым мы воспользуемся, применим для решения всех аналогичных задач. Идея решения основана на частном случае тождества (23) для э = 0: („)( )( — 1) = ( ) =б„„, целое п,целоег>0. (33) Данная формула важна потому, что при и ф г сумма равна нулю. Это позволяет без труда решить задачу, поскольку многие члены суммы оказываются равными нулю, как в примере 3: ='~ Ь!пью~ =ш)а~.
ь Обратите внимание на то, как нам удалось получить уравнение, в котором содер- жится только один неизвестный коэффипиент — а . Для этого мы сложили равен- ства (32) для и = О, 1,..., умноженные на подходящие коэффициенты. В результате имеем а =~ ( — 1) "—,( )= ь>0 0<п<ы ( ) 0<чйпь Таким образом, задача 5 решена. А теперь давайте более подробно рассмотрим, что означает соотношение (33). Для неотрицательных целых г и т имеем так как остальные члены после суммирования исчезают. Выбирая соответствующим образом коэффициенты со можно представить любой многочлен от /с в виде с~ ммы биномиальных коэффициентов с верхним индексом Ь. Поэтому ( 1!( — 1)" ь(Ьо+Ь|К+ +Ь„!с") = г!Ь„, целое г >О, (34) ~Й/ ( )( )( — 1)ь=с", целоег>0. (35) где Ьо + + Ь„Ь' — произвольный многочлен степени не выше г.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
