Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 87
Текст из файла (страница 87)
Другой метод мог бы состоять в вычислении факториального многочлена в и + 1 точке, где и — степень многочлена, с последующей аппроксимацией этих значений многочленом степени п. Третий метод представляет собой обратную форму сокращенного деления. Чтобы показать, как работает этот метод, рассмотрим факториальный многочлен 3х(4) х(з) 2х(з) 476 ГЛАВА 11. Некоторые специальные вопросы теории рекурсии Раскрыв каждое слагаемое, имеем Зх(х — 1) (х — 2) (х — 3) — х(х — 1) (х — 2) — 2х(х — 1) — Зх — 5.
Раскрыв (х — 3) в первом члене, оставив х с первым членом и присоединив — 3 ко второму члену, получаем Зх~(х — 1) (х — 2) + (3( — 3) — 1) х(х — 1) (х — 2) — 2х(х — 1) — Зх — 5. Теперь, раскрыв (х — 2) во втором члене, оставив х со вторым членом и присоединив -2 к третьему члену, получаем Зхз(х — 1)(х — 2) — 10хз(х — 1) + (( — 10)( — 2) — 2)х(х — 1) — Зх — 5. Теперь раскрытие (х — 1) в третьем члене, присоединение х к третьему члену, а -1 — к четвертому члену дает З~з(~ — 1)(~ — 2) — 10~а(~ — 1) + 18ха + ( — 18 — 3) — 5 или Зх (х — 1)(х — 2) — 10х (х — 1) + 18х — 21х — 5, что совпадает с рассматриваемым многочленом после стадии 1. Заметим, что, используя приведенный ниже процесс, мы бы получили тот же самый результат в таблице Заметим, что числа в верхней строке являются коэффициентами факториального многочлена, а числа в первом столбце — целые числа, начинающиеся с 3, на единицу меньше, чем степень многочлена.
Переносим вниз 3, как при сокращенном делении, и умножаем на 3 первое число столбца. Но вместо сложения с — 1, следующим числом строки, вычитаем 9 из — 1, получая — 10. Теперь берем — 10, умножаем на 2, следующее число в столбце, и вычитаем из — 2, следующего числа в строке. Получаем 18. Продолжаем процесс, умножая 18 на 1 и вычитая результат из — 3, получаем — 21. Последнее число в строке не используется и остается неизменным.
Легко видеть, что числа в третьей строке вместе с последним числом в первой строке являются коэффициентами многочлена на стадии 1. Теперь берем многочлен на первой стадии Зхз(х — 1)(х — 2) — 10х~(х — 1) + 18хз — 21х — 5 РКЗДЕЛ 11.4. Фвкторовльные многочлены 477 и повторяем процесс.
Раскрываем х — 2, оставляем х с первым членом, присоединяем — 2 ко второму члену, после чего получаем Зхз(х — 1) + ((3)( — 2) — 10)хз(х — 1) + 18хз — 21х — 5. Теперь раскрываем х — 1 во втором члене, оставляя х со вторым членом, присоединяя — 1 к третьему члену, что дает Зхз(х — Ц вЂ” 16хз + (16+ 18)хз — 21х — 5 или Зх (х — 1) — 16хз(х — 1) + 34хз — 21х — 5 для многочлена второй стадии. Обратите внимание, что каждая стадия повышает степень х в том слагаемом, в котором раскрывается множитель. Снова, возвращаясь к таблице, повторяем процесс за исключением того, что сносим 3, первый элемент строки, умножаем на 2 и вычитаем результат из — 10, числа во втором столбце. Это дает — 16.
Умножаем — 16 на 1 и вычитаем результат из 18, получая 34. Опять — 21, последнее число в строке, не используется. Снова замечаем, что оставшаяся строка вместе с числами — 21 и — 5 формирует многочлен второй стадии: Теперь берем многочлен второй стадии Зхз(х — 1) — 16х + 34х~ — 21х — 5 и раскрываем х — 1 в первом члене.
Это дает Зх~ — 19х + 34х — 21х — 5, что является искомым многочленом. Снова, глядя на таблицу, сносим 3 и умножаем на 1. Вычитаем результат из — 16. Это оставляет неиспользованным — 19. Наконец, сносим 3. Замечаем, что 473 ГПАВА тт. некоторые специальные вопросы теории рекурсии числа в скобках являются искомыми коэффициентами. Продемонстрировав этот процесс, предоставляем читателю четко сформулировать алгоритм перехода от факториального многочлсна к обычному.
ПРИМЕР 11.30. Заменим многочлен х<е~ — 2х<з~ + 4хбб + 6х + 3 обычным много- членом. Используя обратное сокрашенное деление, имеем В результате получаем многочлен ~(х) = х4 — 8хз + 21хз — 8х+ 3. Было показано, что х~ "~ = х(х — 1) (х — 2) .. (х — (и — 1) + 1) (х — и + 1) = = (х — п + 1)х(х — 1) (х — 2) (х — (и — 1) + 1) = = (х — и + 1)х~" Решая относительно х~" '), имеем (и) х <„ц х х — и+1 Теперь имеется способ определить х<"), когда п — отрицательное целое число.
РАЗДЕЛ 17.4. Фанториальные много»лены 479 Положив п = 1, имеем х() = =1. х(1) х — 1+1 Положив п = О, имеем х( х-О+1 х+1 Теперь воспользуемся индукцией и соотношением ,(») (»-1) х — и+1 чтобы показать, что (-т] 1 (х + пт)('") для всех гп > 1, при которых знаменатель не равен нулю.
Было показано, что х( х + 1 (х + 1) (1) Предположим, что х( 1 (х+ Й)(ь) Тогда х( (+))=х( (-ь) х — ( — й)+1 1 1 (х + и)(") х + й + 1 1 (х+ЕИх+й — 1) .. (х+1)(х+й+1) 1 (х + й + 1их+ йих + й — 1) (х + 1)) 1 = (х+/„-+1)(ь+ )' Теперь необходимо найти Ь(х "). По определению 1 1 ~(.--) =л( 1 (х + п)(") / (х + п + 1)(") (х + п)(") 1 1 (х + и + 1)(х + п)(х + и — 1) ° (х + 2) (х + п)(х + п — 1) (х + 1) х+ 1 — (х+ п+ 1) — п (х + п + 1)(х + пИх + п — 1) (х + 1) (х + п + 1)("'"1) 480 ГПКВА 77. Некоторые специальные вопросы теории рекурсии поэтому для каждого целого числа и, не равного нулю, имеем Ь(х~">) = пх<" Ц.
Теперь есть возможность обобщить одну из комбинаторных теорем. Для положительного целого числа и пусть Когда х — целое число, это обычное определение числа сочетаний. Взяв разность, находим и и! (и — 1)! и — 1 Но поэтому имеем или Положив у = х+ 1, получаем в более привычной форме, которая ранее была доказана для случая, когда у— целое число. РАзяел 11.4. Фагтороальные многочлены 481 Покажем, что числа Стирлинга первого и второго рода могут быть описаны на основе многочленов. Числа Стирлинга первого рода равны абсолютным значениям коэффициентов многочлена, равного х(п), для и = 1, 2,3,...
ТЕОРЕМА 11.33. Пусть (и) (и) и (и) и-1 + (и) и-2 и Вп — 1Х Вп-2Х + ( 1)п-2 (и) 2 + ( 1)п — 1 (и) + ( 1)п (и) Коэффициенты в(п) являются числами Стирлинга первого рода. ДОКАЗАТЕЛЬСТВО. По определению, в(п) = О для всех п > 1 и в(п) = 1 для всех и > О. Чтобы показать, что в, — числа Стирлинга первого рода, требуется (и) ПОКаЗатЬ, ЧтО В(п ) = В(")1 + П В(п) дЛя 1 < 1 < П. По определению, х(п"1) = (х — п)х(п) = х х(п) — п. х(п). Следовательно, па1 и и ( 1)п — а (и) а и ~~ ( 1)п — ав(п) а=о а=о и и Х ~~( 1)п-а (и) а.)-1 Т «( 1)п-а ('а) а=о а=о и-~-1 и ( 1)п †(а — 1) (аа) а ~~;п~( 1)п — а (и) а а=1 а=о Увеличивая 1' на 1 в первой сумме, получаем п1-1 «( 1)п — аье1 (и) а + Х ~~( 1)п-ае1 (и) а Приравнивая коэффициенты при ха для 1 < 1 < п, имеем в(пе ) = в("), + пв( ), что и требовалось доказать.
Покажем, что числа Стирлинга второго рода есть не что иное, как коэффициенты факториальных многочленов, равных хп для п = 1,2,3, ТЕОРЕМА 11.34. Пусть и Х и-1Х и-2Х + . 2 Х + 1 Х + О и ~(п) (и) ~(п) (и-1) фп) (и — 2) фп) (2) ~(п) фп) Коэффициенты в(п) являются числами Стирлинга второго рода. 482 ГЛАВА 11. Некоторые специальные вопросы теории рекурсии ДОКАЗАТЕЛЬСТВО. По определению, оо" = О для всех п > 1 и о„" = 1 для (и) (и) всех и > О.
Требуется показать, что для 1 < 1 < п По определению, и-»1 о( )х(*) =хи+( =х.хи =х ~~» о~ )х(') = и (1+ х — 1) ) о'( )х(') = »=о + (х — 1) . ~~» о( )х(О »=о 1 ь о'( )х(') » Приравнивая коэффициенты при х' для 1 < ( < п, получаем о~ = г'.о» +о, (и-~-1) . (и) (и) что и требовалось доказать. 'Й ° УПРАЖНЕНИЯ 1. Найдите ()»з(Зх(з) — бх(з) + 4). 2. Найдите Ьс(4х(з) — Зх(4) + ОхОО + х(з) — Зх + 4.
3. Найдите уьз(х(в) + Зх(") — Зх<з) — 2х(з) + 4х — 1. 4. Найдите Ь(Зх(~) + 2х — 5)(х(~) + 4х<з) + 2х(з)) 5. Найдите»з(х(з) — 2х(з) — 4)(х(4) + 2х(з) — 6х(з) + х — 3). /х<з) + бх(з) + Зх1 6. Найдите Ь ( Г х(')-Зх(')+Зх ') 7. Найдите Ь ~ (4) (3) + 6 )). 8. Упростите выражение "»" м~., ) — ци.»» — Ь" ц~.
9. Найдите Ы((х — 3)(х — 5)(х — 7)). 10. Найдите Ы 1. ~» о'( )х(') »=о и 1 у о'( )х(О »=о и 1 Ея(и)х(() и + ~~ о',. (х — 1) . х(') »=о и + ~~» о'( )х(сь ) = »=о и-»-1 + С;- ~(и) х(») »=1 РАЗДЕЛ 11.5. Суммирование разностей 483 4 /х1 11. Найдите сз~ ~ ) при х = О. 1,5) 12. Преобразуйте х~ — 2хз + Зхз + 5 в факториальный многочлен. 13. Преобразуйте х4 — бхз + 4хз — 4х+ 5 в факториальный многочлен.
14. Преобразуйте х~ — хз + хз — х + 1 в факториальный многочлен. 15. Преобразуйте хз — х~ + хз — хз + х — 1 в факториальный многочлен. 16. Преобразуйте хОΠ— х~з> + хбй — х + 1 в обычный многочлен. 17. Преобразуйте хОО + Зх~з> — 4хби — 2х + 1 в обычный многочлен. 18. Преобразуйте 4хОΠ— 2х<з> + Зхби — 4х + 1 в обычный многочлен.
19. Преобразуйте хРΠ— хОО + хйи — хби + х — 1 в обычный многочлен. 20. Постройте алгоритм перехода от факториальных многочленов к обычным. з13' 21. Найдите Ы~ ), вычисленное при х = О. Ы 11.5. СУММИРОВАНИЕ РАЗНОСТЕЙ Мы знаем, что сзоЩх)) =1(х+и) — и.1(и — 1)+ . +( — 1) (Г(х+и — й))+ — 1(х). ',й/ Поэтому, если х принимает только целочисленные значения, любое разностное отношение может быть представлено в виде рекуррентного отношения. Например, ~з®х)) — З~з(Дх)) = 2Ь((х) может быть записано как 1" (х + 3) — 31" (х + 2) + 37'(х + 1) + 1 (х)— — ЗЩх + 2) — 21'(х + 1) + )'(х)) = 2(1'(х + 1) — 1'(х)), так что у(х + 3) = 67'(х + 2) — 7Щх + 1) — 4Дх), что является записью в рекурсивной форме.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
