Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 88
Текст из файла (страница 88)
Поэтому для решения этого отношения можно использовать результаты первых трех разделов данной главы. В этом разделе мы используем несколько иной подход. Определим 2; как оператор, обратный разностному. То есть, желательно, чтобы из ЬГ(х) = Г'(х) следовало 1 7'(х) = Г(Х). Мы установим, однако, что на самом деле, если ЬГ(х) = 1(х), то 1 )(х) = х'(Х) + с, где с — константа, так как Ь(Г(х) + с) = ЬР(х) + Ь(с) = ЬГ(х). Те, кто знаком с математическим анализом, без труда узнают в этом аналог первообразной функции или неопределенного интеграла. Из того, что Ь(Е(х)) = О, вообще говоря, не следует, что Е(х) — константа.
Рассмотрим, например, Г(х) = зш(2згх): сз.г(х) = ьбп(2я(х+ 1)) — сйп(2ях) = 484 ГЛЛВА 1ъ Некоторые специальные вопросы теории рекурсии = гйп(2хх + 2х) — з>п(2ях) = = Ип(2ях) — з>п(2ях) = О. (х("+>>) ,(з1(х) = (>, Ь(х("т'>) = и+1 1 = — (и + 1)х(") = п+ 1 — х(п) по теореме 11.23 поскольку Ь(х(">) = пх(" так что х("+>> х(") = +с. п+ 1 Пусть Ь('(х) = 15х(~> + 8х(з) + бх(з> + 4х()> + 5, тогда 15х(з> 8х(е> 6х(з> 4х(з> Пх) — + + + +ох+с= 5 4 3 2 = 3*'з) -(- 2*(4) + 2х(з) + 2х(з) + „.- +, / а" Далее, мы видим, что если )'(х) = ~ — ), то 'Х а — 1) Ь((х) = Ь 1 Ьа а — 1 1 (а*) (а — 1) = (а*), по теореме 11.23 показано в предыдущем разделе l а* так что 2 (а*) = ~ — ) + с.
1а — 1) ПРИМЕР 11.36. Пусть Ь1(х) = 15х(4> + Зх(з> + 2 + 8 . 5*. Тогда 15х(з) Зх(з> 8 бе г(х) = + +2 + +с= Это объясняется тем, что ейп(х) — периодическая функция. Но в дальнейшем мы ограничимся рассмотрением многочленов, рациональных и экспоненциальных функций. Для таких функций, если Ь(с (х)) = О, то с (х) — константа. ПРИМЕР 11.36.
Используя разностные формулы предыдущего раздела, находим, х("+)> что если 1(х) =, то п+1 РяадЕЛ 11.5 Суммироеаное разностей 485 = Зх(б) + х(з) + 2' + 2 . 5' + с. Также пусть 1(х) =, тогда (з Г" (х) = как показано в предыдущем разделе, так что ПРИМЕР 11.37. Пусть 2з)"(х) = 5х(4) + 6 4 + 6 ('з). Тогда Дх) = х(з) + 2. 4*+ 6.
~ ) + с. /10'( 1 Наконец, рассмотрим 1(х) = х( 1 — и х( "+') ,(1('(х) = Ь 1 — и — д ( — +1) 1 — и 1 (-и+1)х(-"+1-1) = х(-"). 1 — и по теореме П.23 х( "+1) Следовательно, 2,х( ") = — + с. -и+ 1 ПРИМЕР 11.38. Пусть Ь)'(х) = х(2) + 2* + 5* + х( з) + х( т), тогда ,((х) = -х +2*+ — 5* — — х + — х ) +с. (3) х 1 а 1 ( — 2) 1 (-б 3 4 2 6 ~Уд) =Х ~Ь)+е(д) ~У) Ь()'д) = ~ )' Ь(д) + ~ Е(д) . с1((), ~,1.~(д) =(,Ы вЂ” ~.Е(д) ~10).
Поэтому так что Теперь рассмотрим метод, который называется суммированием ио частям. ТЕОРЕМА 11.39. 2 1'(х)(1д(х) = г(х)д(х) — 2' Е(д(х))Ь) (х) + с. ДОКАЗАТЕЛЬСТВО. Из теоремы 11.25 имеем 486 ГЛАВНА 76 Некоторые слециельные вопросы теории рекурсии Рассмотрим теперь суммы, которые являются аналогом определенных интегралов в математическом анализе. Пусть Дх) = ЬР(х) = Р(х + 1) — Г(х), тогда и и 'у Дх) = ,'> (тт(х+1) — Е(х)) = Г(п+1) — Г(1).
х=1 х=1 Обозначим с(п+ 1) — с(1) через Г(х)>1~ . ПРИМЕР 11.40. Пусть 1(х) = х1з> + 3* + х! ~>, тогда 7 г 7( ) = г х .~ з* ~.*<-и = ( — ~ -з* — — <-и) [, 4 2 3 х=1 х=1 + Зв 81-з> ~ + 3 + 3<-з>) в 1 -з ~~ 1 1 -з~ 4 2 3 ~, 4 2 3 ПРИМЕР 11.41. Найти сумму 1г + 2г + Зг + + пг. и 1г + 2г + Зг + + пг Х~~~ хг =1 и <г> + х=1 = — (2х1~> + Зх!~>) ) 6 1 = — (2х — Зх + х)> = -(2(п+ 1) — 3(п + 1) + (и + 1)) 6 1 = -п(п+1)(2п+1).
6 Г* ~ Го+1 — 1 ПРИМЕР 11.42. ~; гх = хо ' 1о ПРИМЕР 11.43. 2' х =— х!'> х(х — 1 (и + 1)п 2, 2, 2 ПРИМЕР 11А4. Как упоминалось выше, 44(1д) = 1' 4з(д) + Е(д) сз(1). Поэтому и и и Е,Щх)д(х)) = ~ г(х) Й(д(х)) + ~~! Е(д(х)) Ь(г(х)) х=1 х=1 х=1 или и и (1(х)д(х))~, = ~~! Дх) Ь(д(х)) + У д(х+1) . Й(7(х)). х=1 х=1 Следовательно, и и Дх) Й(д(х)) = (г(х)д(х)) ~ — у д(х + 1) Ь(г(х)).
х=1 х=1 ПРИМЕР 11.45. 3* ~ х,5,— = 2 х=1 и хЗ* = х=1 (и + 1) 3" 4 ! 3*аз — Ьх = 2 2 (и+ 1)Зи+' (2и — 1)Зи+' + 3 ° УПРАЖНЕНИЯ сумму разностей первого порядка для функции 3* — ха+ха — х+ 5 до х = 9. сумму разностей первого порядка для функции 2* — Зхз + 2хз от х = 5.
в ~ ' 2. — 12х1з1 1о ~' 3* + 10х14! — Зх1з1. 1. Найдите от х = 1 2. Найдите х = 1 до /х'~ ~ + 4'+ 12х1в1. ~=4 2 11 /х; ~ + 3 ° 5*+ 14х1в! , в1,4„~ 6. Найдите 3. Найдите 4. Найдите 5. Найдите РДЗДЕЛ 155. Суммороеение разностей 487 488 Глядел тт. некоторые слечивльные вопросы теории рекурсии 7. Покажите, что ',> (=1 8. Покажите, что 2 з=1 п 9. Покажите, что 2, 1=1 п 10. Покажите, что 2 1=1 21 = п(п+ 1). ,з пз(п + 1)2 4 п(п+ 1)(п+ 2) г((+1) = 3 41 — 2 = 2пз. что Ь 2 ((1) = ('(х+ 1). (=с что Ь 2', У(() = — Пх) 20. Докажите 21.
Докажите 11. Используя суммирование по частям, найдите 12. Используя суммирование по частям, найдите 13. Используя суммирование по частям, найдите 14. Используя суммирование по частям, найдите 15. Используя суммирование по частям, найдите 16. Используя суммирование по частям, найдите 17.
Используя суммирование по частям, найдите 18. Используя суммирование по частям, найдите 19. Используя суммирование по частям, найдите 8 2; (2х+ З)3*. с=1 1О 4(Зх — 6)4 . к=2 в ХС И*-1) * в=о з 2 ' (х)(х — 1)2*. к=о в х2 2*. к=о 1О х(2) 2' в=о 1О 2 ' х(4)4*. в=о (4) .(О) с=о 9 ~., х(2) х(з) . 490 ГЛЛВА 12. Снова о комбинвторных подсчетах Задача значительно усложняется в ситуации, когда ни один ящик не может быть пустым, поэтому мы отложим ее рассмотрение на потом.
В разделе 8.6 было показано, что число способов размещения и неразличимых объектов в й различимых ящиках, некоторые из которых могут быть пустыми, равно (и ч- )с — 1)! С(и+к — 1,п) = С(и+0 — 1,к — 1) = и)(й — 1)! Кроме того, показано, что число способов размещения и неразличимых объектов в й различимых ящиках, ни один из которых не может быть пустым, равно (и — 1)! С(п — 1,п — lс) = С(п — 1,9 — 1) = (и — й) )()с — 1)! Подсчитаем теперь количество способов размещения и различимых шаров в )с неразличимых ящиках.
Сначала рассмотрим случай, когда ни один из ящиков не может быть пустым. Это также будет числом способов разбиения множества, содержащего и объекгпов на й непересекающихся подмножеств. ТЕОРЕМА 12.2. Существуют Я~я"~ способов размещения и различимых шаров в к неразличимых ящиках, когда ни один из ящиков не может быть пустым, где (Я~Ь'О; 0 < к < п) — множество чисел Стирлинга второго рода. ДОКАЗАТЕЛЬСТВО.
Требуется показать, что если 1(п, й) — количество способов размещения и различимых шаров в й неразличимых ящиках, когда ни один из ящиков не может быть пустым, то 1'(п,п) = 1 для всех и > О, г"(п,О) = 0 для всех п > 1 и г(п+1,0) = г(п,й — 1)+к1(п,й). Очевидно, что для и > 1 имеется только один способ размещения и шаров в и ящиках, так что ни один из ящиков не будет пуст. Поэтому 1(п,и) = 1 для всех п > 1.
Случай и = 0 несколько надуманный, но представляется разумным предположить, что существует только один способ разместить 0 объектов в 0 ящиках. Поэтому положим У'(0,0) = 1. Очевидно, что для и > 1 не существует способа разместить 0 объектов в и ящиках и не оставить ни один ящик пустым, поэтому 1(п, 0) = 0 для всех и > 1. Чтобы доказать соотношение г"(п+ 1, й) = 1(п, й — 1) + к1(п, й), предположим, что и объектов размещены в й ящиках и нужно поместить в ящик (и+1)-ый объект. Имеются две возможности: либо положить объект в пустой ящик, либо— в уже занятый.
В первом случае остальные и объектов должны быть размещены в оставшихся ящиках. Поскольку имеется 1с — 1 таких ящиков, то п объектов следует поместить в й — 1 ящик. Существует Дп, й — 1) способов такого размещения. Если (и+ 1)-ый объект помещается в уже занятый ящик, то предыдущие и объектов были размещены в й ящиках. Это возможно сделать г'(п, й) способами.
Следующий, (и+ 1)-ый, объект может быть помещен только в один из й ящиков, поэтому существуют й 1(п, й) способов размещения объектов при условии, что ни один из й ящиков не пуст. Следовательно, существуют 1"(п,к — 1) +)с1(и,к) способов разместить и + 1 объектов в й ящиках, и у(п+1,9) = ((п,й-1)+ ц(п,й). Отсюда, 1(п,й) = Яь"~, где (Яь"~: 0 < к < и) — множество чисел Стирлинга второго рода. РАздеп 12.1. Задачи о размещении 491 Теперь, используя свойство Я„= 5„1 + йЯ„, можно сформировать (пм1) (и) (и) таблицу чисел Стирлинга второго рода аналогично тому, как это было сделано в случае треугольника Паскаля.
Треугольник для чисел Стирлинга второго рода ТЕОРЕМА 12.3. Снимем ограничение на то, что ни один из ящиков не может быть пустым. Возможны ситуации; (1) все п объектов помещены в один ящик, что можно осуществить 51(") способами; (2) все п объектов помещены в два ящика, что можно осуществить Яз") способами, ..., (9) все п объектов помещены в й ящиков, что можно осуществить Яь(") способами, и т.д. Итого, имеется о(а) о(п) + о(п) о(п) г з ''' ь способов размещения и объектов в й ящиках при условии, что ящики могут быть пустыми.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
