Знаймо

Додати знання

приховати рекламу

Цей текст може містити помилки.

Поєднання



План:


Введення

В комбінаториці поєднанням з n по k називається набір k елементів, вибраних з даних n елементів. Набори, що відрізняються тільки порядком проходження елементів (але не складом), вважаються однаковими, цим поєднання відрізняються від розміщень.

Так, наприклад, набори (3-елементні поєднання, підмножини, k = 3 ) {2, 1, 3} і {3, 2, 1} 6-елементного безлічі {1, 2, 3, 4, 5, 6} ( n = 6 ) Є однаковими (проте, як розміщення були б різними) і складаються з одних і тих же елементів {1,2,3}.

У загальному випадку число, яке показує, скількома способами можна вибрати k елементів з безлічі, що містить n різних елементів, стоїть на перетині k -Й діагоналі і n -Й рядки трикутника Паскаля. [1]


1. Число сполучень

Число сполучень з n по k одно біноміальним коефіцієнту

{N \ choose k} = C_n ^ k = \ frac {n!} {k! \ left (nk \ right)!}.

При фіксованому n виробляє функцією послідовності чисел сполучень {N \ choose 0} , {N \ choose 1} , {N \ choose 2} , ... Є:

\ Sum_ {k = 0} ^ n {n \ choose k} x ^ k = (1 + x) ^ n.

Двовимірної виробляє функцією чисел сполучень є

\ Sum_ {n = 0} ^ {\ infty} \ sum_ {k = 0} ^ n {n \ choose k} x ^ ky ^ n = \ sum_ {n = 0} ^ {\ infty} (1 + x) ^ ny ^ n = \ frac {1} {1-y-xy}.

2. 2. Сполучення з повтореннями

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

Число сполучень з повтореннями з n по k одно біноміальним коефіцієнту

{N + k-1 \ choose k} = (-1) ^ k {-n \ choose k}.

При фіксованому n виробляє функцією чисел сполучень з повтореннями з n по k є:

\ Sum_ {k = 0} ^ {\ infty} (-1) ^ k {-n \ choose k} x ^ k = (1-x) ^ {-n}.

Двовимірної виробляє функцією чисел сполучень з повтореннями є:

\ Sum_ {n = 0} ^ {\ infty} \ sum_ {k = 0} ^ {\ infty} (-1) ^ k {-n \ choose k} x ^ ky ^ n = \ sum_ {n = 0} ^ {\ infty} (1-x) ^ {-n} y ^ n = \ frac {1-x} {1-xy}.

Примітки


Цей текст може містити помилки.

Схожі роботи | скачати

Схожі роботи:
Поєднання клавіш
© Усі права захищені
написати до нас
Рейтинг@Mail.ru