Добавил:

Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.

Вуз:

Киевский национальный университет им. Т. Шевченко

Предмет:

[НЕСОРТИРОВАННОЕ]

Файл:

Metodichka2012.doc

Скачиваний:

Добавлен:

01.07.2025

Размер:

5 Мб

Скачать

☆

<<< < Предыдущая 1 2 3 4 5 6 78 / 138 9 10 11 12 13 > Следующая >>>

2.6. Рекурентні співвідношення.

Рекурентним співвідношенням -го порядку називається співвідношення виду . Таке співвідношення дає можливість обчислити його -й елемент, якщо відомі попередні елементи  .

Вважають, що послідовність є розв’язком рекурентного співвідношення, якщо при підстановці її членів в це співвідношення воно перетворюється в тотожність при будь-якому .

Будь-якому рекурентному співвідношенню відповідає нескінченна кількість розв’язків, оскільки перші елементи розв’язку можна задати довільним чином (між ними не існує ніяких співвідношень). Але якщо перших елементів задано, то решта елементів визначається однозначно: елемент виражається внаслідок залежності через елементи , елемент  через елементи і т.д. Використовуючи рекурентне співвідношення і початкові члени, можна один за одним отримувати інші члени розв’язку, причому рано чи пізно ми отримаємо будь-який його член. Але на практиці найчастіше треба знайти тільки один конкретний член послідовності, а інші нас не цікавлять. В цих випадках зручно мати формулу для -го члена розв’язку.

Розв’язок рекурентного співвідношення -го порядку називається загальним, якщо він залежить від довільних сталих . Із загального розв’язку можна одержати частинний, якщо підібрати такі значення сталих , які відповідають значенням його початковим членам.

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

Спочатку розглянемо лінійні рекурентні співвідношення другого порядку, тобто співвідношення вигляду , причому . Для розв’язку таких співвідношень використовуються наступні два твердження.

Лема 2.1. Якщо та є розв’язками рекурентного співвідношення , то для будь-яких чисел та послідовність також є розв’язком цього співвідношення.

Доведення. Дійсно, за умовою маємо, що та . Першу з цих рівностей помножимо на , другу  на та складемо рівності. Одержали

, а це і означає, що послідовність є розв’язком рекурентного співвідношення . ■

Рівняння виду називається характеристичним рівнянням рекурентного співвідношення .

Лема 2.2. Якщо  корінь характеристичного рівняння рекурентного співвідношення , то послідовність є розв’язком цього співвідношення.

Доведення. Дійсно, якщо , то та . При підстановці цих значень у рекурентне співвідношення одержимо рівність . Ця рівність справедлива, оскільки за умовою маємо, що . ■

Тепер ми можемо розглянути процедуру розв’язку будь-якого лінійного рекурентного співвідношення другого порядку.

Твердження 2.10. Нехай характеристичне рівняння рекурентного співвідношення має корені та . Якщо , то загальний розв’язок рекурентного співвідношення має вигляд . Якщо ж , то загальний розв’язок рекурентного співвідношення має вигляд .

Доведення. Розглянемо перший випадок. За лемою 2.2 та є розв’язками даного рекурентного співвідношення. За лемою 2.1 також є його розв’язком. Покажемо, що будь-який розв’язок рекурентного співвідношення може бути записаним у цьому вигляді. Для цього достатньо показати, що при будь-яких початкових умовах та можна однозначно знайти константи та . Нехай та . Підставимо ці значення у розв’язок. Одержали та . Тоді система рівнянь

має єдиний розв’язок, оскільки її визначник

за умовою не дорівнює нулю, а саме та , тому перша частина твердження доведена.

Розглянемо другий випадок. Ясно, що коли , то вираз не буде загальним розв’язком, оскільки , і ми не можемо завжди так обрати єдину сталу, щоб задовольнити дві початкові умови та . Тому треба знайти будь-який інший розв’язок, який відрізняється від . Покажемо, що таким розв’язком є .

Дійсно, за теоремою Вієта та . Після підстановки цих значень у рекурентне співвідношення одержимо

(*).

Перевіримо, чи є розв’язком рекурентного співвідношення (*). Ліва частина цього рекурентного співвідношення: . Розглянемо праву частину.

Оскільки ліва частина дорівнює правій, то є розв’язком рекурентного співвідношення. За лемою 2.1 загальний розв’язок рекурентного співвідношення має вигляд .

Покажемо, що будь-який розв’язок рекурентного співвідношення може бути записаним у цьому вигляді. Для цього достатньо показати, що при будь-яких початкових умовах та можна однозначно знайти константи та . Одержали та . Тоді система рівнянь

має єдиний розв’язок, оскільки її визначник

за умовою не дорівнює нулю, а саме та . ■

Лінійні рекурентні співвідношення с постійними коефіцієнтами, порядок яких більше двох, можна розв’язати в той же спосіб, що і лінійні рекурентні співвідношення другого порядку.

Нехай задано лінійне рекурентне співвідношення -го порядку . Складемо для цього співвідношення характеристичне рівняння . Якщо всі корені цього рівняння різні, то загальний розв’язок рекурентного співвідношення має вигляд . Якщо ж, наприклад,  корінь степеня , то цьому кореневі відповідають такі розв’язки : , , , ..., . Тоді в загальному розв’язку рекурентного співвідношення цьому кореневі відповідає частина . Складаючи такі вирази для всіх коренів та додаючи їх один до одного одержимо загальний розв’язок рекурентного співвідношення.

Приклад 2.8. Знайти загальний та частинний розв’язок рекурентного співвідношення при початкових умовах , , , .

Характеристичне рівняння цього співвідношення має корінь кратності 3 та корінь кратності 1. Тоді загальний розв’язок заданого рекурентного співвідношення має вигляд .

Знайдемо частинний розв’язок для цього підставимо початкові умови у загальний розв’язок. Одержали систему з чотирьох лінійних рівнянь з чотирма невідомими:

Розв’яжемо цю систему рівнянь та одержимо відповіді: , , , . Тому частинний розв’язок заданого рекурентного співвідношення має вигляд . ■

Завдання до розділу 2.

2.1. Визначити кількість всіх -значних натуральних чисел в запису яких відсутні такі цифри:

1. 1 і 5;

2. 0 і 5;

3. 2,4 і 5;

4. 0, 3 і 7;

5. 0, 2, 5 і 9;

6. 1, 5, 7 і 8;

7. 1, 2, 6, 8 і 9;

8. 0, 3, 4, 7 і 8.

2.2. У просторі взято „чорних” та „зелених” точок, причому будь-які три з них не лежать на одній прямій, а будь-які чотири з них не лежать в одній площині. Знайти кількість:

1. Відрізків, у яких один кінець  чорна точка, а другий  зелена;

2. Відрізків, у яких хоча б один кінець  чорна точка;

3. Трикутників, у яких одна вершина  чорна точка, а дві інші  зелені;

4. Трикутників, у яких хоча б одна вершина  чорна точка;

5. Трикутників, у яких хоча б дві вершини  чорні точки;

6. Тетраедрів, у яких одна вершина  чорна точка, а інші три  зелені;

7. Тетраедрів, у яких хоча б одна вершина  чорна точка;

8. Тетраедрів, у яких хоча б три вершини  чорні точки.

2.3. Визначити, скільки підмножин множини задовольняють таким умовам:

1. і ;

2. , і ;

3. , і ;

4. , і ;

5. складається з трьох парних та двох непарних чисел;

6. містить не менше семи елементів;

7. та містить не менше трьох парних чисел;

8. містить рівно чотири парних числа.

2.4. Визначити, скільки існує -значних натуральних чисел, які:

1. закінчуються на три цифри 5;

2. починаються з трьох однакових цифр;

3. мають різні цифри у сусідніх розрядах;

4. не мають у запису цифри 4;

5. не мають у запису цифр 0 та 2;

6. мають у запису рівно одну цифру 8;

7. мають у запису принаймні одну цифру 8;

8. мають у запису принаймні одну парну цифру.

2.5. Визначити, скільки існує -значних натуральних чисел, які діляться на 2 та мають у своєму запису:

1. принаймні одну цифру 4;

2. рівно одну цифру 4;

3. принаймні дві цифри 4;

4. рівно дві цифри 7 та рівно одну цифру 6;

5. рівно три цифри 5 та рівно дві цифри 3;

6. принаймні одну цифру 5 та рівно дві цифри 0;

7. рівно дві цифри 8 та принаймні одну цифру 0;

8. принаймні одну цифру 8 та принаймні одну цифру 9.

2.6. Із колоди, що складається з 36 карт вибрали 5 карт. Визначити кількість випадків, коли серед цих карт є:

1. рівно одна дама;	5. більше однієї дами;
2. рівно дві дами;	6. хоча б одна дама;
3. немає жодної дами;	7. більше двох дам;
4. чотири дами;	8. хоч дві дами.

2.7. Із колоди, що складається з 36 карт вибрали 6 карт. Визначити кількість випадків, коли серед цих карт є:

1. рівно одна дама та рівно один туз;	5. рівно дві дами та рівно один туз;
2. немає жодної дами та туза;	6. хоча б дві дами та хоч один туз;
3. рівно одна дама та хоч один туз;	7. рівно три дами та хоча б два туза;
4. рівно одна дама та немає жодного туза	8. рівно дві дами та хоча б два туза .

2.8. Із колоди, що складається з 52 карт вибрали 7 карт. Визначити кількість випадків, коли серед цих карт є:

1. Рівно одна бубна, рівно одна пика та рівно дві дами;

2. Рівно одна бубна, рівно дві пики та рівно три дами;

3. Рівно одна бубна, рівно дві пики та принаймні одна дама;

4. Рівно одна бубна, рівно дві пики та рівно одна дама;

5. Рівно дві бубни, рівно дві пики та рівно дві дами;

6. Рівно дві бубни, рівно дві пики та рівно одна пара карт;

7. Рівно одна бубна, рівно дві дами та рівно три туза;

8. Рівно дві бубни, рівно дві дами та рівно три туза.

2.9. Із колоди, що складається з 52 карт вибрали 7 карт. Визначити кількість випадків, коли серед цих карт є:

1. Рівно одна бубна, рівно одна пика та рівно дві дами (інші карти не повторюються за назвами);

2. Рівно одна бубна, рівно дві пики та рівно одна пара карт (інші карти не повторюються за назвами);

3. Рівно одна бубна, рівно дві пики та принаймні одна дама (інші карти не повторюються за назвами);

4. Рівно одна бубна, рівно дві пики та рівно одна дама (інші карти не повторюються за назвами);

5. Рівно дві бубни, рівно дві пики та рівно дві дами (інші карти не повторюються за назвами);

6. Рівно дві бубни, рівно дві пики та рівно одна пара карт (інші карти не повторюються за назвами);

7. Рівно одна бубна, рівно дві дами та рівно три туза (інші карти не повторюються за назвами);

8. Рівно дві бубни, рівно дві дами та рівно три туза (інші карти не повторюються за назвами).

2.10. Колода з карт містить чотири масті по карт у кожній. Карти кожної масті занумеровані числами . Визначити, скількома способами можна вибрати з колоди п’ять карт так, щоб серед них виявилось:

1. дві карти однієї масті, а три  іншої;

2. дві карти одного номеру, а три  іншого („фулл хаус”);

3. п’ять карт однієї масті („флеш”);

4. усі карти з різними номерами;

5. дві карти з одним номером, а інші  з різними номерами („пара”);

6. п’ять послідовно занумерованих карт („стріт”);

7. п’ять послідовно занумерованих карт однієї масті(„флеш - стріт”);

8. чотири карти з однаковим номером („каре”).

2.11. Визначити кількість дільників числа:

1. ;

2. ;

3. ;

4. ;

5. ;

6. ;

7. ;

2.12. В науковому інституті працює 100 співробітників, з яких володіє англійською мовою,  французькою та  німецькою. Також відомо, що співробітників інституту володіє одночасно англійською та французькою мовами,  англійською та німецькою,  французькою й німецькою та  англійською, французькою та німецькою мовами одночасно. Знайти кількість співробітників, які:

а) не володіють жодною іноземною мовою з наведених вище;

б) володіють рівно двома мовами з наведених вище;

в) володіють англійською мовою та не володіють французькою й німецькою.

1. ; ; ; ; ; ; .

2. ; ; ; ; ; ; .

3. ; ; ; ; ; ; .

4. ; ; ; ; ; ; .

5. ; ; ; ; ; ; .

6. ; ; ; ; ; ; .

7. ; ; ; ; ; ; .

8. ; ; ; ; ; ; .

2.13. Знайти кількість і суму натуральних чисел, що не перевищують 1000 і які:

1. не діляться на числа 4, 7, 9;	5. діляться на 5 та не діляться на 8, 9;
2. не діляться на числа 5, 8, 11;	6. діляться на 4 та не діляться на 7, 15;
3. не діляться на числа 6, 9, 11;	7. діляться на 6 та не діляться на 9, 10;
4. не діляться на числа 8, 12, 21;	8. діляться на 5 та не діляться на 8, 10.

2.14. Визначити скількома способами червоних, жовтих та зелених предметів можна розмістити у різних коробок, якщо предмети одного кольору не розрізняються між собою та порядок предметів у коробках неважливий, за таких умов:

1. , , , ;	5. , , , ;
2. , , , ;	6. , , , ;
3. , , , ;	7. , , , ;
4. , , , ;	8. , , , .

2.15.

1. Скількома способами можна розкласти різних предметів на три групи так, щоб у першій групі було предметів, у другій  , у третій  предметів.

2. Є однакових та ще різних предметів. Скількома способами можна вибрати з них предметів.

3. Є по предметів чотирьох сортів. Скількома способами їх можна розділити на 2 групи по предметів.

4. Скількома способами можна розподілити між трьома людьми різних предметів так, щоб кожний одержав предметів.

5. Скількома способами можна розподілити різних книг між трьома особами так, щоб числа отриманих ними книг утворювали арифметичну прогресію.

6. Скількома способами можна вибрати три „кістки” з гри «доміно» так, щоб їх можна було з’єднати між собою за правилами цієї гри.

7. Скількома способами можна з множини вибрати три числа так, щоб їх сума ділилася на 3.

8. Є елементів. Скількома способами можна розбити ці елементи на пари, якщо не розрізняти випадки з різним порядком пар та випадки з різним порядком елементів у парах.

2.16. Знайти коефіцієнт при у розкладі виразу:

1. , ;

2. , ;

3. , ;

4. , ;

5. , ;

6. , ;

7. , ;

8. , .

2.17. Визначити скільки раціональних доданків містить розклад виразу:

1. ;

2. ;

3. ;

4. ;

5. ;

6. ;

7. ;

2.18. Знайти коефіцієнт при у розкладі поліному:

1. , ;	5. , ;
2. , ;	6. , ;
3. , ;	7. , ;
4. , ;	8. , .

2.19. Розв’язати рівняння:

1. ;	5. ;
2. ;	6. ;
3. ;	7. ;
4. ;	8. .

2.20. Розв’язати систему рівнянь:

1. ;	5. ;
2. ;	6. ;
3. ;	7. ;
4. ;	8. .

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

1. , , ;

2. , , ;

3. , , , ;

4. , , , ;

5. , , , ;

6. , , , ;

7. , , , , ;

8. , , , , .

2.22. Знайти кількість композицій:

1. числа 17 на частини 7, 4, 2;	5. числа 16 на частини 7, 4, 2;
2. числа 17 на частини 7, 5, 4;	6. числа 16 на частини 7, 4, 3;
3. числа 17 на частини 6, 5, 3;	7. числа 16 на частини 6, 5, 2;
4. числа 18 на частини 7, 6, 4;	8. числа 18 на частини 6, 5, 4.

2.23. Знайти кількість розбиттів:

1. числа 27 на частини 7, 6, 4;	5. числа 27 на частини 8, 5, 3;
2. числа 28 на частини 7, 6, 4;	6. числа 28 на частини 8, 5, 3;
3. числа 29 на частини 8, 6, 5;	7. числа 29 на частини 7, 5, 4;
4. числа 30 на частини 9, 5, 4;	8. числа 30 на частини 7, 6, 3.

2.24. Знайти кількість варіантів покупки 6 хлібобулочних виробів, якщо сірий хліб у покупці може зустрічатися разів, чорний хліб  разів, батон  разів, багет  разів, булка  разів та тістечко  разів (порядок купівлі хлібобулочних виробів не є важливим, вироби одного виду не розрізняються між собою):