Главная страница Случайная страница
Разделы сайта
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Комбінації з повтореннями
|
|
Комбінації елементів якоїсь множини – це її підмножини. Але у множинах елементи не повторюються, тому термін " комбінації з повтореннями", що склався в математиці, не можна вважати вдалим.
Розглянемо це поняття за допомогою перестановок із повтореннями. Усі перестановки з повтореннями з елементів множини A ={ a 1, a 2, …, an } з тим самим складом (k 1, k 2, …, kn), де k 1+ k 2+…+ kn = m, будемо вважати еквівалентними між собою. Таким чином, множина перестановок розбивається на класи еквівалентності, які взаємно однозначно відповідають усім можливим складам (k 1, k 2, …, kn). Кожний такий клас еквівалентності й називається комбінацією по m елементів з повтореннями складу (k 1, k 2, …, kn) [1].
Можна означити комбінації з повтореннями дещо інакше. Серед усіх еквівалентних перестановок складу (k 1, k 2, …, kn) є перестановка вигляду
(a 1, a 1, …, a 1, a 2, a 2, …, a 2, …, an, an, …, an).
14243 14243 14243
k 1 k 2 … kn
Цю перестановку також будемо називати комбінацією по m елементів множини { a 1, a 2, …, an } з повтореннями складу (k 1, k 2, …, kn).
Приклади.
1. При A ={ a, b, c } усіма комбінаціями по 2 з повтореннями є послідовності (a, a), (a, b), (a, c), (b, b), (b, c), (c, c). Їм відповідають усі можливі склади (2, 0, 0), (1, 1, 0), (1, 0, 1), (0, 2, 0), (0, 1, 1), (0, 0, 2).
2. Нехай m однакових кульок розкладаються по n різних ящиках так, що у першому ящику k 1 кульок, у другому – k 2 кульок, …, у n -му – kn кульок, причому m = k 1+ k 2+…+ kn. Пронумеруємо ящики від 1 до n. Задамо розподілення кульок як функцію, яка ставить у відповідність номеру ящика кількість кульок у ньому. Отже, маємо послідовність (k 1, k 2, …, kn), що є складом. Припишемо кожній кульці номер її ящика і утворимо послідовність номерів вигляду
(1, …, 1, 2, …, 2, …, n, …, n).
123 123 123
k 1 k 2 … kn
Як бачимо, множиною елементів, якими утворюється комбінація з повтореннями, тут є {1, 2, …, n }.
Комбінації по m елементів множини { a 1, a 2, …, an } з повтореннями складу (k 1, k 2, …, kn) можна взаємно однозначно поставити у відповідність послідовність довжини m + n -1 із m " 1" і n -1 " 0":
(1, …, 1, 0, 1, …, 1, 0, …, 1, …, 1).
123 123 123
k 1 k 2 … kn
Такій послідовності, у свою чергу, взаємно однозначно відповідає комбінація номерів місць у цій послідовності, на яких розташовані 1 (або 0). Кількість таких комбінацій є 
, що й є кількістю всіх можливих комбінацій по m елементів n -елементної множини з повтореннями.
|
|