Сполучення

Визначимо число r-сполучень з n різних елементів.

r-сполучення з n різних елементів: З кожного такого сполучення можна утворити r! перестановок, тому число r-сполучень з
n різних елементів буде в r! раз менше числа r-перестановок з
n елементів:

C(n, r) = = =

Приклад. З чотирьох різних об'єктів, що позначаються 1, 2, 3, 4, можна скласти таки шість сполучень по два елементи (n=4, r=2): 12, 13, 14, 23, 24, 34.

Число r-сполучень з n різних елементів позначається через чи . Заміна r на n-r дозволяє одержати C(n,r) = C(n, n-r) чи .

Формулу для числа r-сполучень з необмеженими повтореннями з
n елементів можна одержати в такому способі.

r-сполучення з необмеженими повтореннями з n елементів. Кожному сполученню ставиться у відповідність перестановка, у якій всі елементи даного сполучення закодовані одиницями, причому всі різні класи елементів розділяються нулем навіть і у випадку, якщо елементи яких-небудь класів не ввійшли в сполучення.

Приклад. Для сполучення abbce з елементів множині {a,b,c,d,e} перестановка буде 101101001, для сполучення bbbee – перестановка 011100011 і т.д.

Очевидно, перестановка для r-сполучення з n елементів з повтореннями містить r одиниць і n-1 нулів. Шукане число r-сполучень збігається з числом перестановок з обмеженими повтореннями з r+n-1 елементів і специфікацією {r,n-1} відповідно до формули перестановок з r-повтореннями з n різних елементів, що наведена вище. Отже

F(n, r) = = = C(r+n-1, r).

Приклад. Число сполучень з повтореннями по 2 з 4 елементів, що позначаються 1, 2, 3, 4, дорівнює C(5,2)=10, що утворюються такими вибірками: 11, 12, 13, 14, 22, 23, 24, 33, 34, 44.

Розглянутий спосіб заснований на заміні однієї множині іншою множиною, елементи яких знаходяться у взаємно однозначній відповідності, і, отже, їхнє число в цих множинах однаково.