Juk_Ilyenko_Moklyachuk_Orlovskiy_DM_praktikum

Отже, число всiх послiдовностей iз семи чисел, що задовольняють

умови задачi, буде рiвне

1!6!7! + 3!4!7! + 5!2!7! = 7 + 35 + 21 = 63.

Задачi для аудиторної та домашньої роботи

№9.4. Знайти експоненцiйну генератрису послiдовностi

1.= , = 0, 1, 2, . . ., ̸= 0;

2.= ( − 1), = 2, 3, . . ., 0 = 1 = 0;

3.= ( − 1)( − 2), = 3, 4, . . ., 0 = 1 = 2 = 0;

4.= 2, = 0, 1, 2, . . .;

5.= 3, = 0, 1, 2, . . .;

6.= !, = 0, 1, 2, . . .;

7.= (−1) !, = 0, 1, 2, . . .;

8.= ( − 1)!, = 0, 1, 2, . . .;

9.= (−1) ( − 1)!, = 0, 1, 2, . . .;

100

10.= ( + 1)!, = 0, 1, 2, . . .;

11.= (−1) ( + 1)!, = 0, 1, 2, . . .;

12.= ( ) , 0 = 1 = . . . = −1 = 0, = , + 1, + 2, . . .

№9.5. Довести рiвнiсть

∫ +∞

− = !, = 0, 1, 2, . . .

0

№ 9.6. Використовуючи попередню задачу, встановити зв’язок мiж звичайною ( ) та експоненцiйною ( ) генератрисою послiдовностi :

∫ +∞

( ) = − ( ) .

0

№9.7. Вiдновити послiдовнiсть за її експоненцiальною генератрисою

1.( ) = ;

2.( ) = 5 ;

3.( ) = 2 ;

4.( ) = 1−1 ;

5.( ) = 1+1 ;

6.( ) = ln(1 + );

7.( ) = ln(1 − );

8.( ) = sin ;

9.( ) = cos .

101

№ 9.8. Нехай ( ) , = ( − ) . . . ( − ( − 1) ), = 1, 2, . . ., ( )0, = 1. Побудувавши експоненцiйну генератрису, довести тотожнiсть

№9.9. Знайти експоненцiйну генератрису для числа способiв розмiщення чоловiк по кiмнатах за умови, що в кожнiй кiмнатi не менше 1 та не бiльше 10 чоловiк.

№9.10. Знайти експоненцiйну генератрису для числа способiв розмiщення чоловiк в трьох кiмнатах за умови, що кожна кiмната не буде порожньою, в першiй кiмнатi парна кiлькiсть гостей, а в другiй парна. Обчислити кiлькiсть всiх варiантiв розмiщення.

№9.11. Довести, що кiлькiсть варiантiв розмiщення рiзних об’єктiв в

рiзних ящиках за умови, що нi один iз ящикiв не порожнiй, дорiвнює

№ 9.12. Довести, що число варiантiв розмiщення рiзних об’єктiв в

ящиках, що не розрiзняються, дорiвнюють числам Стiрлiнга другого роду ( ), де

102

ЗАНЯТТЯ 10

Рекурентнi спiввiдношення

Навчальнi задачi

№ 10.1. Знайти загальний розв’язок рекурентного спiввiдношення 5 порядку

( + 5) = 4 ( + 4) − 4 ( + 3) − 2 ( + 2) + 5 ( + 1) − 2 ( )

Розв’язок. Запишемо характеристичне рiвняння даного спiввiдношення

5 − 4 4 + 4 3 + 2 2 − 5 + 2 = 0

Безпосередньою пiдстановкою знаходимо, що 1 = 1 - корiнь даного рiвняння. Понизимо степiнь рiвняння, подiливши характеристичний многочлен на − 1 за схемою Горнера.

Як результат отримаємо рiвняння четвертого степеня

4 − 3 3 + 2 + 3 − 2 = 0.

Значення 2 = 1 є коренем i цього рiвняння також, тому проведемо операцiю дiлення за схемою Горнера на − 1 ще раз.

103

Отримане рiвняння 3 −2 2 − +2 = 0 знову має корiнь 3 = 1, тому ще раз понижуємо степiнь.

В результатi отримуємо рiвняння 2 − − 2 = 0, котре має коренi

4 = −1 та 5 = 2.

За теоремою про загальний вигляд розв’язку лiнiйного однорiдного рекурентного спiввiдношення зi сталими коефiцiєнтами, записуємо загальний розв’язок задачi:

( ) = 1 · ( 1 + 2 + 2 3) + (−1) 4 + 5 · 2 =

=1 + 2 + 2 3 + (−1) · 4 + 2 · 5.

№10.2. Знайти загальний розв’язок рекурентного спiввiдношення 5-го порядку

√ √

( + 5) = 2 3 ( + 4) − 4 ( + 3) − 2 ( + 2) + 4 3 ( + 1) − 8 ( ).

Розв’язок. Запишемо характеристичне рiвняння даного спiввiдно-

шення:

Розкладемо лiву частину на множники. Для цього винесемо за дужки

√

( 2 − 2 3 + 4):

104

= 3 − 1 отримуємо пару комплексних спряжених чисел з модулями,

√

рiвними 3 2 та аргументами ± /3. Отже, вiдповiдна частина розв’язку буде мати вигляд

1(−√3 2) + (√3 2) ( 2 cos 3 + 3 sin 3 ).

√ √

Якщо ж 2 − 2 3 + 4 = 0, то отримаємо = 3 ± . Модуль даного

√ √

комплексного числа рiвний ( 3)2 + 12 = 2, а аргумент arcsin(1/2) =

/6. Вiдповiдна частина розв’язку буде мати вигляд

2 ( 4 cos 6 + 5 sin 6 ).

Тепер залишилося додати два отриманi вирази, i ми отримаємо вiдповiдь:

( ) = 1(−√3 2) +(√3 2) ( 2 cos 3 + 3 sin 3 )+2 ( 4 cos 6 + 5 sin 6 ).

№ 10.3. Знайти загальний вигляд розв’язку рекурентного спiввiдношення 4-го порядку при 0 = 0:

+4 − 3 +3 − 8 +1 + 24 = 0.

Розв’язок. Запишемо характеристичне рiвняння даного спiввiдношення:

4 − 3 3 − 8 + 24 = 0.

105

Пiдставляючи 1 = 2, бачимо, що дане значення буде розв’язком цього характеристичного рывняння. За схемою Горнера подiлимо характеристичний многочлен на − 2.

В результатi отримаємо рiвняння третього степеня 3 − 2 − 2 −

12 = 0. Бачимо, що у даного многочлена 2 = 3 є розв’язком, тому застосовуємо схему Горнера iще раз.

пару комплексних спряжених чисел з модулем 2 та аргументами ±2 /3. Остаточно, розв’язок заданого рекурентного спiввiдношення буде ма-

Врахуємо тепер початкову умови 0 = 0. Отримаємо, що

0 = 120 + 230 + 20 ( 3 cos 0 + 4 sin 0) = 1 + 2 + 3;

1 = − 2 − 3.

Пiдставляючи вираз для 1 у отриманий вище розв’язок, отримаємо

№ 10.4. Знайти загальний вигляд розв’язку рекурентного спiввiдношення 4-го порядку при (0) = 0, (1) = −6, (2) = −4, (3) = −34:

( + 4) = 6 ( + 2) + 8 ( + 1) + 3 ( ).

106

Розв’язок. Запишемо характеристичне рiвняння даного спiввiдношення:

4 − 6 2 − 8 − 3 = 0.

Пiдставляючи 1 = −1, бачимо, що дане значення є розв’язком цього рiвняння. Застосуємо сему Горнера та подiлимо характеристичний многочлен на + 1.

Отримаємо рiвняння 3 − 2 − 5 − 3 = 0, коренем якого також є

3. Отже, загальний вигляд заданого рекурентного спiввiдношення має

вигляд

( ) = (−1) ( + + 2) + 3 .

Врахувавши заданi початковi умови, отримаємо систему рiвнянь

Розв’язавши дану систему рiвнянь, отримаємо = 1, = 2, = 0,

= −1. Пiдставивши отриманi значення в формулу загального розв’яз-

ку, отримаємо

( ) = (−1) (1 + 2 + 0 2) − 1 · 3 = (−1) (1 + 2 ) − 3 .

107

Задачi для аудиторної та домашньої роботи

№ 10.5. Знайти загальний розв’язок рекурентного спiввiдношення 5 порядку

1.( + 5) = 2 ( + 4) + 10 ( + 3) −8 ( + 2) −33 ( + 1) −18 ( );

2.( +5) = −11 ( +4)−30 ( +3)+22 ( +2)+95 ( +1)−75 ( );

3.( + 5) = 2 ( + 4) + 6 ( + 3) − 4 ( + 2) − 13 ( + 1) − 6 ( );

4.( +5) = 9 ( +4)−26 ( +3)+20 ( +2)+24 ( +1)−32 ( );

5.( + 5) = 3 ( + 4) + 5 ( + 3) −27 ( + 2) + 32 ( + 1) −12 ( );

6.( + 5) = 6 ( + 4) − 11 ( + 3) + 2 ( + 2) + 12 ( + 1) − 8 ( );

7.( + 5) = 7 ( + 4) −7 ( + 3) −19 ( + 2) + 16 ( + 1) + 20 ( );

8.( +5) = 15 ( +4)−83 ( +3)+205 ( +2)−216 ( +1)+80 ( );

9.( + 5) = 5 ( + 4) − 2 ( + 3) − 14 ( + 2) + 3 ( + 1) + 9 ( );

10.( + 5) = 5 ( + 4) −4 ( + 3) −16 ( + 2) + 32 ( + 1) −16 ( );

11.( + 5) = −2 ( + 4) + 9 ( + 3) + 22 ( + 2) −4 ( + 1) −24 ( );

12.( +5) = −2 ( +4)+11 ( +3)+40 ( +2)+44 ( +1)+16 ( );

13.( +5) = −6 ( +4)−6 ( +3)+16 ( +2)+15 ( +1)−18 ( );

14.( + 5) = ( + 4) + 14 ( + 3) − 6 ( + 2) − 45 ( + 1) − 27 ( );

15.( +5) = 2 ( +4)+17 ( +3)−70 ( +2)+92 ( +1)−40 ( ).

108