Головна

виробляють функції

  1. II. ФУНКЦІЇ
  2. II. функції
  3. II. ФУНКЦІЇ
  4. II. функції ІТС
  5. II. ФУНКЦІЇ ЦУП
  6. Адвокат і його функції
  7. активаційні функції

У комбінаторних задачах на підрахунок числа об'єктів при наявності деяких обмежень шуканим рішенням часто є послідовність виду

a0, a1, a2, ..., Ak, ..., (4)

де ak (K = 0, 1 ...) - число шуканих об'єктів «розмірності» k. Наприклад, якщо ми шукаємо число підмножин n-елементного безлічі, то  Зручним поданням цієї послідовності є формальний ряд

 (5)
=

Зауваження. Фраза «формальний ряд» означає, що (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. Який вигляд має виробляє функція для розміщень з трьох різних елементів, в яких кожен елемент зустрічається не менше двох разів?

Рішення: Відомо, що .



Попередня   8   9   10   11   12   13   14   15   16   17   18   19   20   21   22   23   Наступна

Безлічі і операції над ними | алгебра множин | Розбиття множини на підмножини | Кортежі і декартовій твір множин | відносини | Властивості бінарних відносин | алгебра підмножин | Завдання для самостійної роботи | Різні комбінаторні співвідношення | Принцип включення і виключення |

© 2016-2022  um.co.ua - учбові матеріали та реферати