Курсова робота на тему: «ТВІРНІ ФУНЦІЇ, ЇХ ЗАСТОСУВАННЯ ДЛЯ РОЗВ’ЯЗАННЯ КОМБІНАТОРНИХ ПРОБЛЕМ»

Зміст

1. Вступ.

2. Степеневі ряди, та їхні властивості.

3. Поняття твірної функції.

4. Твірні функції для сполучень.

5. Твірні функції для розміщень.

6. Поліномні твірні функції.

7. Застосування твірних функцій до розв’язування рекурентних рівнянь.

8.
Розкладання на елементарні дроби.

9. Про єдине нелінійне рекурентне співвідношення.

10. Висновок.

11. Список використаної ітератури.

Вступ

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

Трапляються також задачі, коли на початковій скінченній множині елементів означено деяку цільову функцію, причому інтерес становлять елементи множин, що забезпечують, мінімальне (або максимальне) значення цієї функції. У цьому разі
маємо окремий випадок задачі оптимізації. Тут під її розв’язком у сильному значенні
розуміють, знаходження сукупності всіх елементів, які забезпечують, мінімальне (або максимальне) значення цільової функції, а під розв’язком у слабкому значенні — відшукання довільного елемента, що забезпечує мінімальне (або максимальне) значення цільової функції. Іноді цікавляться лише мінімальним (або максимальним) значенням функції.

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

Метод твірних функцій — один із найуніверсальніших методів комбінаторики. Строге його обгрунтування спирається на поняття й результати математичного аналізу. Щоб краще зрозуміти цей метод, ми спочатку ознайомимось з поняттям степеневого ряду і розглянем його властивості.

 

1.Степеневі ряди та їхні властивості

Степеневим називають ряд

а0 + a1х + а2х2+ а3х3+ … + аnхn+ …,

де а0, а1, а2, а, … – дійсні числа. Суму ряду позначатимемо як f(x).

Степеневі ряди мають такі важливі властивості.

1.    Область збіжності ряду – множина {х| |х| < r}, до якої іноді можуть долучатися точки х=r та х= –r або одна з цих точок. Число r називають радіусом збіжності ряду.

2.    Нехай f(x) = та φ(x) = – степеневі ряди; r1
r2 – радіуси їх збіжності, а r0= min{r1, r2}. Тоді для |х|< r0 ці ряди можна почленно додавати й множити:

(1.1)

  1. Якщо два степеневі ряди збігаються в області {х ||х|< r}і мають однакову суму для всіх х
    із цієї області, то коефіцієнти при відповідних степенях х
    цих рядів однакові.
  2. Сума ряду f(x) =
    в області {х ||х|< r}, де r – радіус збіжності, має похідні всіх порядків, причому


    зокрема,


    Ця властивість дає змогу визначати окремі члени ряду, якщо є аналітичний вираз для його суми f(x).

    Ньютон узагальнив формулу (1
    + х)n для ненатуральних показників. Якщо |x|<1, то для будь-якого дійсного значення υ справджується рівність

    (1.2)

    Рівність (1.2) називають біноміальним рядом Ньютона. Нам потрібні два випадки формули (1.2) – для υ = –n (де n — натуральне) та υ = 1/2:







    (1.4)

    2 Поняття твірної функції

    Нехай задано послідовність чисел а0, а1 а2 аn, … . Утворимо степеневий ряд а0 + а1х + а2х2 + а3х3 + … + anxn +…. Якщо він збігається в якійсь області до функції f(х), то її називають твірною для послідовності чисел а0, а1
    а2
    аn, …. Якщо послідовність а0, а1
    а2
    аn скінченна, то твірна функція для цієї послідовності — поліном а0 + а1х + а2х2 + а3х3 + … + anxn

    Нас цікавитимуть твірі функції для послідовностей а0, а1 .. ., аn
    . .., так або інакше пов’язаних з комбінаторними завданнями. За допомогою цих функцій вдається набувати самих різних властивостей цих послідовностей. Крім того, ми розглянемо, як зв’язані твірні функції з вирішенням рекурентних співвідношень.

    ЗАВАНТАЖИТИ

    Для скачування файлів необхідно або Зареєструватись

    Tvirni Funkc Jih Zastos (131.5 KiB, Завантажень: 12)

    ЗАВАНТАЖИТИ

    Для скачування файлів необхідно або Зареєструватись

    Tvirni Funkc Jih Zastos (949.0 KiB, Завантажень: 4)

Сторінка: 1 2 3 4 5 6 7 8
завантаження...
WordPress: 23.39MB | MySQL:26 | 0,371sec