Размещено на http://www.allbest.ru/

Дипломна робота

Твірні функції

твірний функція ньютон задача

Вступ

Сучасне суспільство стрімко розвивається. Тому в зв'язку з цим люди змушені вирішувати безліч різноманітних проблем, зокрема, побутові, наукові, шукати засоби і способи їх вирішення. Будь-якому математику (і вченому взагалі) дуже часто доводиться зіштовхуватися з нескінченними послідовностями цілих додатніх чисел. Якщо послідовність проста, як наприклад, послідовність чисел, які збільшуються вдвічі (1, 2, 4, 8, 16,…) чи послідовність квадратів (1, 4, 9, 16, 25,…), то вона стане зрозумілою одразу ж. Не кожен математик не зможе дізнатися числа Фібоначчі (1, 1, 2, 3, 5, 8...) або трикутні числа (1, 3, 6, 10, 15, 21 ...).

Якщо ж послідовність не дуже відома, то можна витратити багато часу у пошуках рекурентного або не рекурентного закону, що задає її. (Закон є рекурентним, якщо обчислення наступного члена вимагає знання попередніх членів; не рекурентна формула дає п-й член, не вимагаючи знання попередніх.) Важко тому вірити, що тільки у 1973 році в США був виданий «Довідник числових послідовностей». У цій безцінній книзі складеною Н. Дж. А. Слоуном описано більше 2300 цілочисельних послідовностей, кожна з яких має свій номер.

В математиці можна виділити два основних напрями: один вивчає неперервні об'єкти, інший - дискретні. В реальному світі є місце і для другого підходу і часто до вивчення одного і того ж явища можна підійти з різних сторін, як, наприклад, задача про щасливі білети. Зрозуміло, що між цими напрямками існує багато зв'язків. Одним із методів є метод твірних функцій, який широко використовуються в математиці. Гармонійне поєднання теоретичного та прикладного аспектів робить ці функції однаково привабливими і цікавими як суто для математики, так і для тих хто займається застосуванням математики в різноманітних галузях знань.

Дана магістерська робота присвячена розгляду твірних функцій.

Актуальність теми полягає у використанні отриманих результатів при розв'язуванні певного класу задач, а саме з комбінаторики, теорії послідовностей.

Метою роботи є розкрити поняття твірної функції та її застосування.

Методи дослідження. При дослідженні даної теми використовуються загальні методи математичного аналізу.

Практичне значення одержаних результатів. Результати роботи носять теоретичний характер. Методика їх отримання може бути використана при дослідженні питань теорії функцій.

Апробація результатів. Результати магістерської роботи доповідались на Науковій конференції професорсько-викладацького складу та студентів ВНУ.

Робота складається з вступу, двох розділів, висновків, біографічних відомостей про математиків та літератури. У першому розділі особлива увага приділяється опису поняття твірної функції, її властивостей. Розглядаються дії над твірними функціями, їх диференціювання та інтегрування. Показано використання твірних функцій у теорії ймовірностей У другому розділі розглядаються практичні застосування твірної функції. Особливе місце відведене на розгляд запису твірних функцій для послідовностей чисел Каталана, Фібоначчі та циклів перестановок.

Твірні функції. Приклади

Ідея твірної функції дуже проста. Співставимо послідовності степеневий ряд . Вчинивши так ми використовуємо до вивчення дискретних об'єктів сильний арсенал засобів математичного аналізу . Зауважимо, що в розглянутих нижче прикладах степеневі ряди збігаються в деякому околі нуля, хоч існує теорія формальних степеневих рядів , яка і розглядає степеневі ряди , які збігаються тільки в точці 0. Справедлива теорема єдності : якщо при деякому додатному «с» функція f(х)представлена у вигляді степеневого ряду на інтервалі (-с;с), то коефіцієнти ряду знаходяться однозначно. Існують і інші конструкції твірної функції. Ми будемо використовувати відомі із базового курсу математичного аналізу властивості степеневих рядів без додаткових умов.

Метод твірних функцій дуже продуктивний, зокрема при розв'язуванні комбінаторних задач. Наведемо деякі приклади.

1. Найбільш відомим прикладом твірної функції, є звичайно, біном Ньютона

. (1)

Тут - біноміальні коефіцієнти ( число комбінацій із n по k, тобто число k- елементної підмножини n- елементної множини).

2. Можна розширити поняття біноміального коефіцієнта на випадок коли число n не є натуральним :



Відповідна твірна функція - це вже не многочлен, як (1), а степеневий ряд, сума якого на проміжку (-1;1) рівна , тобто справедлива рівність

(2)

При натуральних значеннях формула (2) перетворюється в (1)

3. Важливі одиничні випадки формули (2) одержимо при б=-1, б=-2.

Це формула суми нескінченно спадної геометричної прогресії зі знаменником -х.

Замінивши в цій формулі х на -х, одержимо, що твірною функцією послідовності 1, 2, 3… є функція .

4. Застосування твірних функцій дозволяє довести деякі комбінаторні формули, які в іншому випадку отримати було б важко. Наведемо приклад такого роду. Розклад функції в степеневий ряд має вигляд

.

Тому справедлива рівність

Прирівнюючи коефіцієнти при в лівій і правій частинах, одержимо

Ця формула має прозорий комбінаторний зміст, але довести її непросто. Ще в 80-ті роки ХХ століття з'явилися публікації, присвячені цьому сюжету.

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

.

Тобто, вивчаючи останню функцію, можемо дослідити властивості всіх біноміальних коефіцієнтів одночасно.

Задача про щасливі білети

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

Розіб'ємо всі щасливі білети на класи, в кожному з яких сума перших трьох цифр однакова. Ця сума може приймати значення від 0 (для трійки цифр 000 ) до 27 (для трійки 999 ). Тому число класів дорівнює 28. Позначимо через число різних трійок цифр з сумою цифр рівною . Перші декілька значень неважко обчислити:

(тобто лише одна трійка цифр 000 з сумою 0 );

( є три трійки 001, 010, 100 );

( трійки 002, 020, 200, 110, 011, 101) .

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

Розглянемо многочлен . Наприклад, добутку відповідає число 362 . Звідси видно , що є коефіцієнт при многочленна , тобто

.

Розглянемо тепер функцію (функція такого типу називається функцією Лорана ) , . Якщо розкрити дужки, то отримаємо, що

.

При цьому легко переконатися , що .

Покладемо . Тоді на підставі формули Муавра

.

Враховуючи, що при виконуються рівності

,

,

Одержимо

.

Отже,

.

Спростимо функцію :

,

Враховуючи , що

,

Маємо

Тут використана формула суми геометричної прогресії, формула Ейлера і формула косинуса подвійного кута .

Остаточно отримаємо формулу

. (3)

Напевно, раніше неможливо було уявити, що кількість щасливих білетів можна звести до обчислення інтегралу, до того ж з використанням теорії комплексного аналізу .

Число можна обчислити і по-іншому. Нехай - десятковий запис шестизначного числа . Розглянемо функцію, що ставить у відповідність числу число, що містить десятковий запис . Функція є взаємно однозначною, при чому і при всіх . Якщо число щасливе, то , звідси слідує, що сума цифр числа рівна 27. Навпаки: якщо сума цифр числа рівна 27, то число щасливе. Звідси випливає, що є кількістю шестизначних чисел, сума цифр яких рівна 27. Але тоді аналогічно попередньому є коефіцієнтом многочлена

при .

Другий співмножник можна подати у вигляді степеневого ряду (2) :

.

Звідси видно, що коефіцієнт при рівний

.

Зауважимо , що

.

Звідси отримуємо

. (4)

Порівняння формул (3) і (4) показує , наприклад , що за допомогою потрібних міркувань можна обчислити деякі інтеграли.

.

Задача про 100 кульок

Спочатку в урні знаходиться 100 білих кульок. Щокроку навмання вибирають кульку з урни, фарбують у чорний колір і повертають до урни. Кульку можна фарбувати кілька разів, причому кілька разів пофарбована кулька не відрізняється від пофарбованої один раз. Знайти закон розподілу білих кульок після п кроків.

Розв'язання

Скористаємось класичним означенням ймовірності: ;

- ймовірність того, що після кроків буде білих кульок.

- ймовірність того, що після кроків буде чорних кульок.

;

.

, якщо .

Таблица

.

;



;

.

.

; ;

;

.

.

,

.

Твірні функції та дії над ними

Означення. Нехай a₀, a₁, ..., a_n, ... - довільна (нескінченна) послідовність чисел. Твірною функцією (рядом) будемо називати ряд виду

A(s) = a₀ + a₁ s + a₂ s² + a₃ s³ + ... =

Означення. Нехай a₀, a₁, ..., a_n, ... - довільна (нескінченна) послідовність чисел. Експоненційною твірною функцією будемо називати ряд виду

A(s) =

До суми входять члени ряда з n ? 0, але іноді зручніше розширити діапазон сумування на всі цілі n. Для цього припускають a_-1 = a_-2 = a_-3 = … = 0, після чого сума може бути записана як .

Означення. Сумою двох твірних функцій

A(s) = a₀ + a₁ ?s + a₂ s² + a₃ ?s³ + ...

та

B(s) = b₀ + b₁ s + b₂ ?s² + b₃ s³ + ...

називається твірна функція

A(s) + B(s) = (a₀ + b₀) + (a₁ + b₁) ?s + (a₂ + b₂) ?s² + (a₃ + b₃) ?s³ + ...

Означення. Добутком двох твірних функцій A(s) та B(s) називається твірна функція

A(s) ?B(s) = (a₀ + a₁s + a₂s² + … ) . (b₀ + b₁s + b₂s² + … ) =

(a₀ . b₀) + (a₀ . b₁ + a₁ . b₀) .?s + (a₀ . b₂ + a₁ . b₁ + a₂ . b₀) .?s² + ... =

Суму h_n = можна записати як h_n = , оскільки a_k = 0 при k < 0, а b_n-k = 0 при k > n.

Означення. Нехай

і

-

- дві твірні функції, причому .

Підстановкою твірної функції В у твірну функцію називається твірна функція



Якщо, наприклад, , то

Означення. Згорткою двох послідовностей <a₀, a₁, a₂, … a_n> та <b₀, b₁, b₂, … b_n> називається послідовність <a₀b₀, a₀b₁ + a₁b₀, a₀b₂ + a₁b₁ + a₂b₀, …,>.

Лема. Згортці послідовностей відповідає добуток їх твірних функцій.

Нехай A(s) = 1 + s + s² + s³ + … = . Обчислимо її добуток на B(s) = :

= =

Лема. Множення твірної функції на дає твірну функцію для послідовності часткових сум вихідної послідовності.

Властивості твірних функцій

Диференціювання та інтегрування

Лінійність. Якщо та ?- константи, то послідовність c_n = a_n + . b_n має твірну функцію C(s) = ?. A(s) + B(s).

Зсув вправо. Нехай послідовність bn визначається через послідовність an зсувом вправо на m позицій:

b_n = <0, 0, …, 0, a₀, a₁, … > = a_n-m

Тоді

B(s) = = = s^m * = s^m * = s^m * A(s).

Через [<умова>] далі будемо позначати вираз, який дорівнює 1, якщо умова істина і 0, якщо хибна (позначення Д.Кнута [1]). Наприклад, вираз [n = 0] при n = 3 або n = 6 буде дорівнювати 0, а при n = 0 дорівнює 1.

Приклад. Послідовність <1, 0, 0, 0, 0…> має твірну функцію

A(s) = 1 * s⁰ + 0 * s¹ + 0 * s² + 0 * s³ + … = = 1,

Розглянемо послідовність <0, ..., 0, 1, 0, 0, …>, в якій лише на m - ому місті стоїть одиниця. Вона утворена з <1, 0, 0, 0, 0…> зсувом вправо на m позицій. Твірна функція послідовності <0, ..., 0, 1, 0, 0, …> має вигляд:

B(s) = s^m * A(s) = = s^m

Твірна функція A(s) може мати два вигляди у замкненому вигляді:

1. A(s) виражається через s у замкненому вигляді;

2. Задані значення a_n через n.

Приклад. Твірною функцією послідовності <1, 1, 1, … > буде

A(s) = = 1 + s + s² + s³ + … =

Замкнений вигляд твірної функції: A(s) = .

Значення коефіцієнтів послідовності: a_n = 1.

Множення на константу

A(c . s) = = - твірна функція послідовності

< cⁿa_n >

Приклад. Твірною функцією послідовності <1, 2, 4, 8, … > буде

B(s) = A(2 .?s),

де A(s) - твірна функція послідовності <1, 1, 1, … >.

B(s) = A(2 .?s) = =

Приклад. Твірною функцією послідовності <1, 4, 6, 4, 1, 0, 0 … > буде

A(s) = 1 + 4 .?s + 6 .?s² + 4 .?s³ + s⁴ = (1 + s)⁴

Зсув вліво. Нехай послідовність bn визначається через послідовність an зсувом вліво на m позицій:

b_n = <a_m , a_m+1 , a_m+2 ,… > = a_n+m

Для отримання твірної функції B(s) послідовності b_n із A(s) необхідно відняти перші m членів з A(s) та поділити на z^m:

B(s) = (A(s) - a₀ - a₁s - a₂s² - … - a_m-1s^m-1) / s^m = =

Останню суму не можна поширювати на всі значення n, якщо тільки не виконується a₀ = … = a_m-1 = 0.

Диференціювання. Обчислимо похідну твірної функції A(s):

A'(s) = a₁ + 2a₂ . s + 3a₃ . s² + … =

Виконаємо зсув на одну позицію вправо:

s .?A'(s) = = - твірна функція послідовності <na_n>

Приклад 5. Твірною функцію послідовності b_n = <1, 2, 3, 4, … > буде

B(s) = 1 + 2 .?s + 3 .?s² + 4 .?s³ + …

Знайдемо її замкнений вид. Відомо, що твірною функцією послідовності a_n = <1, 1, 1, … > буде

A(s) =

Тоді твірною функцією послідовності <na_n> = <0, 1, 2, 3, … > буде

s .?A'(s) =

Виконаємо зсув вліво на одну позицію:

B(s) = (s .?A'(s) - 0) / s =

Інтегрування. Інтегрування дає можливість поділити елементи послідовності на n. Нехай A(s) = a₀ + a₁ .?s + a₂ .?s² + a₃ .?s³ + ... . Тоді

= a₀ .?s + a₁ .?s² + a₂ .?s³ + a₃ .?s⁴ + ... = -

твірна функція послідовності <a_n-1 / n>. Якщо необхідно отримати твірну функцію для <a_n / n>, тоді необхідно перед інтегруванням зробити зсув на одну позицію вліво (замість A(s) інтегрувати (A(s) - a₀) / s).

Приклад. Знайдемо твірну функцію послідовності

<b_n> = <0, 1, , , , … >

Відомо, що твірною функцією <a_n> = <1, 1, 1, …> буде .

Тоді твірною функцією <b_n> = <a_n-1 / n> буде

= - = .

Вилучення членів з парними та непарними номерами. Нехай A(s) - твірна функція послідовності <a₀, a₁, a₂, a₃, a₄, … >. Знайдемо твірну функцію послідовностей <a₀, 0, a₂, 0, a₄, … > та <0, a₁, 0, a₃, 0, … >. Відомо, що

A(s) + A(-s) = + = =

2 .? = 2 .?

Звідси

=

Аналогічно можна вилучити члени з непарними номерами:

=

Приклад. Знайдемо твірну функцію послідовності b_n = <1, 0, 1, 0, … >. Для її знаходження необхідно вилучити члени з парними номерами із послідовності a_n = <1, 1, 1, 1, … >. Твірною функцією a_n є A(s) = . Тоді твірною функцією b_n буде = =

Приклад. Послідовність a_n = <1, 2, 3, 4, … > складається із часткових сум послідовності b_n = <1, 1, 1, 1, … >. Якщо твірною функцією b_n є , то твірною функцією a_n буде . = .

Застосування в теорії ймовірностей

Нехай дискретна випадкова величина, що приймає цілі невід'ємні значення 0, 1, 2, 3... з ймовірністю , .

Означення. Твірною функцією (генератрисою) цієї випадкової величини називають функцію

, , (1)

або (2)

Властивості твірної функції

1.

2.

Дійсно, згідно (2) .

3. Якшо , - незалежні випадкові величини, то

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

.

4. Між розподілом випадкової величини і твірною функцією існує взаємно однозначна відповідність.

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

Приклад. Геометричний розподіл , , тоді

Приклад. Біноміальний розподіл ,

, тоді

Означення. Функцію називають характеристичною функцією випадкової величини

Означення. Факторіальним моментом п-го порядку випадкової величини назвемо

(3)

З останньої формули будемо мати , , ....

Теорема. Якщо для випадкової величини існує факторіальний момент п-го порядку, то існує лівостороння похідна в точці 1 п-го порядкуцієї твірної функції .

Доведення. Оскільки степеневий ряд можна почленно диференціювати, то продиференціювавши (1) п раз отримаємо

(4)

За умовою існує факторіальний момент п-го порядку

(5)

Якщо підставити в формулу (4) , то ми отримаємо (5), тобто існує . Теорема доведена.

Зауваження. .

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

Доведення. Нехай , тоді

Для сум і будемо мати

Для довільного фіксованого виберемо таке N, щоб , аналогічно можна вибрати таке N, що .

Зафіксуємо більший з вибраних номерів N,

Якщо , то

Таким чином



.

За умовою , тому .

Перейшовши до границі при бачимо

Продиференціювавши обидва ряди аналогічно покажемо, що , . Теорема доведена.

Твірні функції відомих послідовностей. Твірна функція для чисел Каталана

Розглянемо який-небудь арифметичний вираз і витремо все, крім дужок. Одержимо деяку систему відкритих і закритих дужок. Якими властивостями вона володіє?



Рис.

По-перше, відкритих дужок рівно стільки, скільки і закритих. По-друге, ні в якому по початковому відрізку кількість закритих дужок не може виявитися більшою кількості відкритих дужок. Наприклад, розміщення )( і ((()))( неправильні. Не тяжко довести що ці дві умови не тільки необхідні, але і достатні.



Рис.

Розглянемо декілька прикладів. Одна пара дужок може виглядати єдиним способом: (). Дві пари - двома способами: ()() або (()). Три пари - п'ятьма способами: ()()(), ()(()),(())() або ((())). Чотири пари, в чому не тяжко переконатися, - чотирнадцятьма способами. Щоб зрозуміти, скількома способами можуть виглядати правильно розміщені п'ять пар дужок, розглянемо закриваючу дужку, парну до першої відкриваючої дужки. Останні чотири пари тоді розділяться на дві групи: розміщені в середині розглянутої пари і розміщеної справа від неї. (Розуміється, будь-яка із цих груп може складатися з нуль дужок.) Способів, коли всі чотири пари всередині або всі чотири справа, - по чотирнадцять в кожному випадку. Коли три пари всередині, а одна справа, - 5 способів. Стільки ж - коли одна всередині, а три справа. Нарешті, коли дві пари всередині, а дві справа, маємо способи. Отже, способи.

Приклад. Розглянемо добуток. Зітремо всі закриваючі дужки, після чого замінимо всі букви на закриваючі дужки і останню із них зітремо: Як бачимо одержимо правильне розміщення дужок. (На рисунках 1 і 2 показано і інші приклади.)

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

Нехай - твірна функція послідовності Каталана. Тоді

Звідси одержуємо квадратне рівняння відносно функції : .

Розв'язуючи його, одержуємо

.

Оскільки , розв'язком є функція

.

Розклавши функцію в ряд за формулою

Одержуємо

Ця формула цікава тим, що пряме доведення того, що при довільному п число ділиться на п+1, не є простим.

Числа Фібоначчі

Числа Фібоначчі знаходяться за наступним правилом: при . Спробуємо отримати формулу, що виражає безпосередньо через . Один із шляхів до розв'язання цієї задачі - побудова твірної функції. Нехай

(1)

Виділимо в (1) два перших доданки, а в решту підставимо вираз



Одержимо

Бачимо, що

Використовуючи ці рівності, одержимо

Ми отримали лінійне рівняння відносно функції .

(2)

Позначимо через та корені квадратного тричлена Маємо

Тоді

Як відомо, існують такі числа А і В, для яких



Перетворюючи вираз для функції , одержимо

(3)

Тут використані формула при б=-1 і заміна в першому доданку на , а в другому - на . За теоремою єдності, поданій у вступі, із (1) і (3) випливає рівність

(4)

Ми отримали просту формулу для обчислення чисел Фібоначчі. Участь в ній ірраціонального числа виглядає несподівано. При більших доданок стає надзвичайно малим, тобто справедлива наближена рівність

.

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

Звернемо увагу на те, як ми отримали формулу (4): ми почали зі степеневого ряду (1), потім ніби про степеневий ряд забули (2), але тільки для того, щоб знову вернутись до нього на новому рівні (3). Такий відступ дозволив отримати цю формулу.

Цикли перестановок

Перестановкою п-го порядку називається правило, яке кожному числу із множини співставляє одне із цих же чисел, причому різним числам співставляються різні числа. Теорія перестановок - найважливіший об'єкт теорії скінченних груп і комбінаторики. Перестановка зазвичай записується у вигляді рядка, в якому на перше місце ставиться число, співставлене двійці, …, на п-му місці - число, співставлень п. Наприклад, при п=5 перестановка може мати вигляд (5, 4, 1, 2, 3). Якщо прослідкувати ланцюжки, які породжує перестановка, одержимо 1-5-3-1, 2-4-2, тобто дана перестановка, розпадається на два цикли: один складається із трьох, другий - із двох чисел. Відомо [2, 3], що будь-яка перестановка розпадається на цикли. Позначимо через число перестановок п-го порядку, що мають циклів. Ці числа називаються числами Стірлінга першого роду.

Деякі із чисел Стірлінга легко обчислюються. , оскільки якщо число циклів дорівнює п, то кожен цикл складається із одного числа, тобто відповідна перестановка має вигляд (1, 2, ..., п). при , оскільки, як вже відмічалось, будь-яка перестановка має хоча б один цикл. Зручно рахувати, що .

Перевіримо справедливість рівності

(1)

при , .

Для ця рівність перевіряється безпосередньо. Нехай перестановка (п-1)-го порядку розпадається на циклів. Число п можна додати після будь-якого числа у відповідний цикл. Всі одержані перестановки різні, містять циклів, всього їх . Далі із будь якої перестановки (п-1)-го порядку, що розпадаються на цикл, можна побудувати єдину перестановку п порядку, що розпадаються на циклів, додавши цикл, що складається із одного числа п. Очевидно, що ця конструкція описує всі перестановки п-го порядку, що розпадається на циклів. Тим самим рівність (1) доведена.

Розглянемо тепер твірну функцію

. (2)

Цікаво, що, хоч нема простих формул для обчислення , многочлен має досить просту структуру:

. (3)

Доведемо цю формулу методом математичної індукції. Очевидно, що . Нехай при . Маємо



що і вимагалось перевірити. Тут використані одержані раніше рівності , .

Одержана твірна функція дозволяє легко обчислювати числа Стірлінга за (2), хоча, як вже відзначалося, простої формули для цього не існує.

Висновки

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

Перший розділ даної роботи присвячений основним теоретичним відомостям. Зокрема, було введено поняття твірної функції, а також розглянуто задачі, що приводять до цього поняття (біном Ньютона, задачі про щасливі білети, про 100 кульок). Розглянуто найважливіші властивості твірної функції: лінійність, зсуви вліво та вправо; операції інтегрування та диференціювання, застосування у теорії ймовірностей.

У другому розділі магістерсьської роботи розглядаються конкретні практичні застосування твірних функцій, а саме: послідовності чисел Каталана, Фібоначчі, цикли перестановок.

Було показано, що твірні функції дають змогу значно швидше отримати результат при знаходженні довільних членів відомих послідовностей чисел, при розв'язуванні задач з комбінаторики.

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

Біографічні відомості про математиків

Леонамрд Емйлер (нім. 15 квітня 1707, Базель, Швейцарія -- 18 вересня 1783, Санкт-Петербург, Росія), видатний швейцарський математик та фізик, який провів більшу частину свого життя в Росії та Німеччині. Традиційне написання "Ейлер" походить від рос. Леонард Эйлер.

Ейлер здійснив важливі відкриття в таких різних галузях математики, як математичний аналіз та теорія графів. Він також ввів велику частину сучасної математичної термінології і позначень, зокрема у математичному аналізі, як, наприклад, поняття математичної функції. Ейлер відомий також завдяки своїм роботам в механіці, динаміці рідини, оптиці та астрономії, інших прикладних науках.

Ейлер вважається найвидатнішим математиком 18-го століття, а, можливо, навіть усіх часів. Він також є одним із найбільш плідних -- збірка всіх його творів зайняла б 60-80 томів. Влив Ейлера на математику описує висловлювання "Читайте Ейлера, читайте Ейлера, він є метром усіх нас", яке приписується Лапласові.

Ейлер увічнений в шостій серії швейцарських 10 франків і на численних швейцарських, німецьких та російських поштових марках. На його честь названо астероїд 2002 Ейлер. Він також відзначений лютеранською церквою у церковному календарі (24 травня) - Ейлер був побожним християнином, вірив в біблійну непогрішність, рішуче виступав проти видатних атеїстів свого часу.

1707 у німецькомовній частині Швейцарії в сім'ї священника Пауля Ейлера та Маргарети Брукнер народився перший син -- Леонард Ейлер. У рідному Базелі він відвідує гімназію та одночасно бере приватні уроки у математика Йоганнеса Буркгардта.

З 1720 року навчається в університеті Базеля та слухає лекції у Йоганна Бернуллі. У 1723 отримує наукове звання магістра за порівняння латиною філософій Ньютона та Декарта. Від свого задуму студіювати також і теологію відмовляється в 1725. А 17 травня 1727 року на запрошення Даніеля Бернуллі приймає професуру в університеті Санкт-Петербургу, котра належала до того Ніколаусу II Бернуллі, померлому 1726 року. Тут він знайомиться з Крістіаном Ґольдбахом. 1730 Ейлер отримує професуру фізики, а 1733 отримує місце професора математики, котре до цього належало Даніелю Бернуллі.

У наступні роки Ейлер поступово втрачає зір, у 1740 році він осліп на одне око.

В 1741 приймає запрошення короля Пруссії Фрідріха Великого очолити Берлінську академію та відновити її репутацію, котра перебувала у занепаді після попереднього керівника -- придворного блазня. Ейлер продовжує листуватись з Крістіаном Ґольдбахом. Після 25 років у Берліні Ейлер повертається 1766 до Санкт-Петербургу. Причиною цього була також неприязність та приниження зі сторони деспотичного короля.

1771 Ейлер остаточно сліпне, незважаючи на це майже половина його праць виникла під час другого перебування у Санкт-Петербурзі. У цьому йому допомагають обидва його сини Йоганн Альбрехт та Крістоф.

1783 Ейлер помирає внаслідок крововиливу в мозок.

Ейлер є автором 866 наукових публікацій, зокрема у галузях математичного аналізу, диференціальної геометрії, теорії чисел, теорії графів, наближених обчислень, небесної механіки, математичної фізики, оптики, балістики, кораблебудуванні, теорії музики, що мали значний вплив на розвиток науки. Саме він ввів більшість математичних понять та символів у сучасну математику, наприклад: f(x), e, р (пі), уявна одиниця i, символ суми ? і багато інших.

Каталан, Ежен Шарль (30 травня 1814 - 14 лютого 1894) - бельгійський математик. Народився в м. Брюгге. Здобув освіту в Паризькій політехнічній школі. У 1856 Каталан дістав кафедру аналізу в Льєжському університеті і був обраний членом Брюссельської академії. Написав понад 200 мемуарів з різних питань математики. Зокрема, в диференціальній геометрії довів, що лінійчата поверхня тільки тоді може бути дійсною мінімальною, коли вона плоска або звичайна гвинтова. Поділив з М. В. Остроградським і Якобі заслугу розв'язання загальної задачі заміни змінних у кратних інтегралах; залишив помітний слід у теорії функцій і чисел Бернуллі тощо.

У 1842 Каталан висловив припущення, що рівняння немає розв'язків у натуральних числах x, y, z, t, більших за 1, крім тривіального . Ця проблема й досі не розв'язана.

Леонардо Пізанський, Фібоначчі (близько 1170 - після 1228) - італійський математик. Народився в м. Пізлі (Італія). Здобув освіту у м. Бугія (Алжир) під керівництвом місцевого вчителя, зокрема тут він опанував арифметику і алгебру арабів. У торговельних справах Леонардо відвідав багато країн Європи та Сходу і скрізь поповнював свої знання з математики. Леонардо видав дві книжки: з арифметики і алгебри «Liber abaci» («Книга про абак», 1202), де абак уже розглядався не стільки як прилад, скільки як числення взагалі, і з геометрії «Practica geometriae» («Практична геометрія», 1220). За першою книжкою навчалось багато поколінь європейських математиків, які, зокрема, вивчали за нею індійську позиційну систему числення. Виклад матеріалу і система його подання в цьому творі були цілком оригінальними і набагато зручнішими від арабських першоджерел. Леонардо належать і власні відкриття, зокрема він поклав початок розробці питань, пов'язаних з так званими числами Фібоначчі, і дав оригінальний прийом добування кубічного кореня.

Можна припустити, що знання і здібності Леонардо були настільки ширшими порівняно з його сучасниками, що він так і не залишив після себе учнів. Тільки цим можна пояснити і те, праці Леонардо не набули поширення аж до кінця ХV ст., поки Лука Пачіолі не переробив і не опублікував їх у своїй книжці «Сума» (Венеція, 1494).

Література

1.Бронштейн М. Е. Производящие функции. // Соросовский образовательный журнал. 2001. Том 7. № 2. С. 103 - 108.

2.Вейнштейн Ф.В. Разбиение чисел // Квант. 1988. № 11. С. 19 - 21.

3.Виленкин Н.Я. Комбинаторика. - Издат. «Москва», 1969. 191 с.

4.Виленкин Н.Я. Популярная комбинаторика. - М., «Наука», 1975. - 208 с.

5.Грэхем Р., Кнут Д., Поташник О. Конкретная математика. М.: Мир, 1998.704 с.

6.Ландо С.К. Лекции о производящих функциях. М.: Фазис, 1998. 192 с.

7.Риордан Дж. Комбинаторные тождества: Пер. с англ. - Н.: Наука, 1982. - 255 с.

8.С.М. Воронин, А.Г. Куланин Метод производящих функций // Квант. 1984. № 5. С. 11 - 13.

9.Сильвестров В.В. Степенные ряды и их приложения // Соросовский Образовательный Журнал. 1998. № 10. С. 124-127.

10.Спивак А. Числа Каталана. // Квант. 2004. № 3. С. 2 - 10.

11.Стенли Р. Перечислительная комбинаторика. М.: Мир, 1990. 440 с.

12.Холл М. Комбинаторика. Издательство «Москва», 1970. 424c.

Размещено на Allbest.ru