UkrReferat.com
найбільша колекція україномовних рефератів

Всього в базі: 75850
останнє поновлення: 2016-12-08
за 7 днів додано 17

Реферати на українській
Реферати на російській
Українські підручники

$ Робота на замовлення
Реклама на сайті
Зворотній зв'язок

 

ПОШУК:   

реферати, курсові, дипломні:

Українські рефератиРусские рефератыКниги
НазваЕлементи комбінаторики (реферат)
АвторРоман
РозділМатематика, алгебра, геометрія, статистика
ФорматWord Doc
Тип документуРеферат
Продивилось6246
Скачало739
Опис
ЗАКАЧКА
Замовити оригінальну роботу

укції за n.

 

, і базу доведено.

 

2. Індукційний перехід. За припущенням індукції,

 

.

 

Поставимо довільній перестановці складу (k1, k2, …, kn, kn+1) у

відповідність пару вигляду

 

(підмножина номерів місць, де розташовано елементи an+1,

 

перестановка з повтореннями решти елементів по інших місцях).

 

За принципом добутку та за припущенням індукції, кількість таких пар є

 

 

Оскільки очевидно, що відповідність між перестановками складу (k1, k2,

…, kn, kn+1) та наведеними парами є взаємно однозначною, то правильність

формули для P(k1, k2, …, kn) доведено.

 

За означенням, перестановки складу (k1, k2, …, kn) є послідовностями

довжини m=k1+k2+…+kn, тобто розміщеннями з повтореннями окремого

вигляду, а саме, з фіксованими кількостями елементів a1, a2, …, an.

Таким чином, послідовності чисел (k1, k2, …, kn), таких, що

k1+k2+…+kn=m, взаємно однозначно відповідає підмножина множини

розміщень. Перебираючи всі можливі послідовності чисел (k1, k2, …, kn),

ми перебираємо всі можливі розміщення.

 

Наведені неформальні міркування демонструють зв'язок між перестановками

й розміщеннями з повтореннями та обгрунтовують формулу:

 

.

 

5. Комбінації з повтореннями

 

Комбінації елементів якоїсь множини – це її підмножини. Але у множинах

елементи не повторюються, тому термін "комбінації з повтореннями", що

склався в математиці, не можна вважати вдалим.

 

Розглянемо це поняття за допомогою перестановок із повтореннями. Усі

перестановки з повтореннями з елементів множини A={a1, a2, …, an} з тим

самим складом (k1, k2, …, kn), де k1+k2+…+kn=m, будемо вважати

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

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

можливим складам (k1, k2, …, kn). Кожний такий клас еквівалентності й

називається комбінацією по m елементів з повтореннями складу (k1, k2, …,

kn) [1].

 

Можна означити комбінації з повтореннями дещо інакше. Серед усіх

еквівалентних перестановок складу (k1, k2, …, kn) є перестановка вигляду

 

(a1, a1, …, a1, a2, a2, …, a2, …, an, an, …, an).

 

((((( ((((( (((((

 

k1 k2 … kn

 

Цю перестановку також будемо називати комбінацією по m елементів множини

{a1, a2, …, an} з повтореннями складу (k1, k2, …, 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 різних ящиках так, що у

першому ящику k1 кульок, у другому – k2 кульок, …, у n-му – kn кульок,

причому m=k1+k2+…+kn. Пронумеруємо ящики від 1 до n. Задамо розподілення

кульок як функцію, яка ставить у відповідність номеру ящика кількість

кульок у ньому. Отже, маємо послідовність (k1, k2, …, kn), що є складом.

Припишемо кожній кульці номер її ящика і утворимо послідовність номерів

вигляду

 

(1, …, 1, 2, …, 2, …, n, …, n).

 

((( ((( (((

 

k1 k2 … kn

 

Як бачимо, множиною елементів, якими утворюється комбінація з

-----> Page:

[0] [1] [2] 3 [4]

ЗАМОВИТИ ОРИГІНАЛЬНУ РОБОТУ