![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Добуток (1+ породжує r-сполучення, в яких кожен елемент із множини об'єктів {
} може з'являтися не більш одного разу. Очевидно, для інших типів сполучень варто підібрати й інший вид співмножників.
Якщо об'єкт може входити в сполучення 0, 1,...,k раз, то замість 1+
треба взяти співмножник 1+
(при k=0 співмножник дорівнює одиниці). Тоді при
коефіцієнти
багаточлена A(x)=1+
являють собою r-сполучення з n різних елементів з повтореннями.
Приклад. Для r-сполучення з трьох елементів a, b, c зі специфікацією {3, 1, 2} маємо (1+x+x +x
)(1+x)(1+x+x
)=1+3x+5x
+ +6
. Тут коефіцієнт при
дає шукане число r-сполучень. Так, є три 1-сполучення (aaa, aab, aac, abc, acc, bcc), п'ять 4-сполучень (aaab, aaac, aabc, aacc, abcc) і т.д.
Поліноміальна твірна функція (энумератор). Багаточлен вигляду називають поліноміальною функцією, або твірною (енумератором) для послідовності
Ця послідовність є r-сполученняз n елементів з повтореннями. Біном Ньютона є функцією, що виробляє для сполучення без повторення. Треба мати на увазі, що змінна x енумератора ніяк не визначена і вважається просто абстрактним символом. Його роль зводиться до того, щоб розрізняти елементи послідовності При цьому різні перетворення таких послідовностей заміняються відповідними операціями над твірними функціями.
Для сполучення з необмеженими повтореннями елементів n типів енумератор буде (1+х+ +...
. Вираження в дужках можна представити у вигляді
При розгляді виразу (1-х як бінома Ньютона з від’ємним показником –n, формально можна записати
,
що збігається з результатом, отриманим для сполучень. Звідси також слідує формальне відношення
Якщо зажадати, щоб кожен об'єкт входив у сполучення з необмеженими повтореннями парне число раз, то в якості энумератора варто прийняти (1 + x2 + x4 +...)n чи
,
тобто число r-сполучень при непарному r дорівнює нулю, а число
2r-сполучень визначається як число r-сполучень без прийнятого раніше обмеження.
Аналогічно визначається енумератор і при інших додаткових умовах. Нехай, наприклад, необхідно визначити число таких r-сполучень з п типів елементів з необмеженими повтореннями, що обов'язково містять хоча б по одному елементу кожного вигляду. Тоді
.
Тут при перетворенні суми зроблена заміна змінної n + r на r і використане відношення зі сполучень. Число шуканих сполучень дорівнює нулю при r < n. і дорівнює C(r — 1, n — 1) при
.
Приклад. Для трьох елементів а, b, з існує одне 3-сполучення (abc), число 4 cочетаний дорівнює С(3, 2) = 3 (aabc, abbc, abcc), число 5-сполучень дорівнює С(4, 2) = 6 (aaabc, aabbc, aabcc, abbbc, abbcc, abccc) і т.д.
Дата публикования: 2014-11-18; Прочитано: 1039 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!