Поєднання

План:

1 Число сполучень
2 Сполучення з повтореннями

Введення

В комбінаториці поєднанням з 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}.$

Примітки

Дивовижний трикутник великого француза. - www.arbuz.uz / u_treug.html