Головна |
У комбінаторних задачах на підрахунок числа об'єктів при наявності деяких обмежень шуканим рішенням часто є послідовність виду
a0, a1, a2, ..., Ak, ..., (4)
де ak (K = 0, 1 ...) - число шуканих об'єктів «розмірності» k. Наприклад, якщо ми шукаємо число підмножин n-елементного безлічі, то Зручним поданням цієї послідовності є формальний ряд
|
Зауваження. Фраза «формальний ряд» означає, що (5) розглядається просто як вид (або форма) записи послідовності (4), і ніякий інший сенс в цю запису не вкладається.
Визначення. Формальний ряд (5) називається виробляє функцією послідовності (4).
Виробляють функції набули широкого поширення в комбінаторики в силу наступних обставин.
По-перше, вони дозволяють, не обчислюючи кожне з чисел
a0, a1, a2, ..., Ak... Окремо, отримати всі ці рішення в «збиральної» формі. У той же час для будь-якого фіксованого k (k = 0, 1, ...) число може бути обчислено аналітичними методами. Дійсно, з курсу математичного аналізу відомо, що при виконанні певних вимог функція f (x) може бути розкладена в ряд Маклорена (окремий випадок ряду Тейлора, відповідний розкладання в околиці точки 0),
(6)
де аi = (I = 0,1, ...).
Порівняння (6) і (5) дає підставу вважати, що в запису (5) , І трактувати A (x) як значення функції A в точці x.
По-друге, що виробляють функції дозволяють в явному вигляді знаходити функцію, що визначає послідовність (4), встановлювати співвідношення між числами a0, a1, a2, ..., Ak, ..., А також отримувати різні тотожності. Це досягається за допомогою використання ряду стандартних методів, які використовують операції, визначені над виробляють функціями. Розглянемо деякі з таких операцій.
Нехай задані виробляють функції
=
и
.
Сумою виробляють функцій A (x) и B (x) називається виробляє функція
A (x) + B (x) = (a0+ b0) + (A1+ b1) X + ... + (ak+ bk) xk+ ...=
Твором виробляє функції A (x) на число p називається виробляє функція
Твором виробляють функцій A (x) и B (x) (Воно також називається твором Коші) Називається виробляє функція
A (x) B (x) = з0+ з1x + ... + зkxk+ ...= ,
де ck = a0bk + a1bk-1 + ... + Ak-1b1 + akb0 = для всіх k = 0, 1 ...
похідною від виробляє функції A (x) називається виробляє функція
Приклад 15. Знайти виробляє функцію послідовності, яка визначається функцією f (k) = 1 для всіх k = 0, 1, ...
Рішення: Задана послідовність має вигляд
1, 1, ..., 1, ...
З (5) випливає, що виробляє функція A (x) = 1 + x + x2+ ... + Xk+ ...
при |x| <1 права частина цієї рівності є нескінченно спадаючу геометричну прогресію. Вважаючи, що умова |x| <1 виконується і замінюючи прогресію її сумою, отримаємо, що
.
Приклад 16. Знайти виробляє функцію послідовності, яка визначається функцією для всіх k = 0, 1, ... (n фіксоване).
Рішення. З (5) випливає, що
Приклад 17. довести тотожність
. (*)
Рішення: Диференціюючи рівність
отримаємо .
Підставивши в цю рівність x = 1, отримаємо (*).
2.7. Виробляють функції числа основних
комбінаторних об'єктів
Яка Виробляє функція є пристроєм, почасти нагадує мішок. Замість того щоб нести окремо багато предметів, що могло б виявитися скрутним, ми збираємо їх разом, і тоді нам потрібно нести лише один предмет - мішок.
Д. Пойа
Біноміальна теорема вказує на те, що (1 + z)n - Це виробляє функція для послідовності . дійсно,
Часто буває зручно замість ряду (5) розглядати ряд виду
, (7)
який ми будемо називати експоненційної виробляє функцією послідовності (4).
Виробляють функції числа основних комбінаторних об'єктів:
1) виробляє функція для
2) виробляє функції числа сполучень з безлічі
E = {e1, e2, ..., En}, Заданих умовами, згідно з якими кратність кожного елемента ei може бути одним з чисел є функція
+ ...),
а коефіцієнт при xk , Отриманий після розкриття дужок, дорівнює числу таких поєднань.
3) Знайти число поєднань з повтореннями з n елементів по k без будь-яких обмежень на кратність елементів в даному поєднанні (тобто кратність кожного елемента може бути будь-яким цілим невід'ємним числом), таким чином,
В даному випадку виробляє функція виглядає наступним чином:
.
4) Знайти число поєднань з повтореннями з n елементів по k, В яких кожен елемент зустрічається не менш r раз (тобто кратність кожного елемента може бути одним з чисел r, r + 1, r + 2, ...). Виробляє функцією для числа сполучень такого виду є функція
|
5)
- Експоненціальна виробляє функція числа розміщень Ank.
6)
- Експоненціальна виробляє функція числа nk (Тобто числа k-перестановок з повторенням елементів в n-елементному безлічі).
Приклад 18.Який вигляд має виробляє функція для поєднань з трьох елементів, в яких кожен елемент зустрічається не менше ніж один раз?
Рішення: n = 3, r = 1, тоді
Приклад 19. Є безліч M = {a, b, c}, з елементів якого будуються п'ятимісні розміщення з наступними обмеженнями на частоту повторення елементів:
1) елемент a може входити в розміщення не більше одного разу;
2) елемент b може входити в розміщення один або два рази;
3) елемент c може входити в розміщення необмежену кількість разів.
Знайти число розміщень описаного типу.
Рішення: Як відомо, число k-розміщень з повторенням елементів в n-елементом безлічі дорівнює nk.
Яка Виробляє функція для розміщень з повтореннями виглядає так:
коефіцієнт при дорівнює .
Згідно з умовами вихідної задачі виробляє функція виглядає наступним чином:
.
Тепер, перемноживши дужки, шукаємо коефіцієнт перед , Він і є рішення вихідної завдання.
отримуємо
|
|
Число розміщень дорівнює 65.
приклад 20. Який вигляд має виробляє функція для розміщень з трьох різних елементів, в яких кожен елемент зустрічається не менше двох разів?
Рішення: Відомо, що .
Безлічі і операції над ними | алгебра множин | Розбиття множини на підмножини | Кортежі і декартовій твір множин | відносини | Властивості бінарних відносин | алгебра підмножин | Завдання для самостійної роботи | Різні комбінаторні співвідношення | Принцип включення і виключення |