К - сполучення й перестановки з необмеженими повтореннями

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

Приклад.Переставляючи букви слова «липень» одержимо 12 перестановок: ипеньл,пеньли...Переставляючи букви слова «мама» ми можемо одержати тільки 6 різних комбінацій: мама, амам, аамм, амма, ммаа, маам.

K-перестановкою з повторенням n-множини А або к-перестановкою з n елементів будемо називати впорядкований набір k елементів з множини М.

Приклад , , , , . Тоді 6-перестановки з повторенням з трьох елементів будуть: (a,b,c,a,a,a), (b,b,c,c,a,a,), (c,a,b,a,a,c) і т.д.

Дві такі к-перестановки рівні, якщо вони співпадають як за своїми елементами, так і порядком їх розташування; різними, якщо вони відмінні або елементами, або порядком їх розташування.

У загальному випадку постановка задачі така. Є множина М, що представляє собою об'єднання своїх підмножин, що не перетинаються.

, (7)

Потужність множини та підмножин дорівнює |M| = n _, |M_і| = n_і

Запишемо: кожна підмножина M_i містить елементи, що не розрізнюються в даній задачі. K – кількість типів елементів і у загальному випадку n ≠ k, якщо n = k, тоді кожен тип містить один елемент, і мова йде про множину М без елементів, що повторюються.

Приклад.

Нехай М - множина букв розрізної абетки М₁ = {а, а,…а} М₂ = {б, б,…б} … М₃₃ = {я, я,…я}

4-перестановки для цих підмножин є <а а а м>, <а а м м>, <м а а а> – різні 4 перестановки,

Число представників а класу М₁ у сполученні називається кратністю елемента а