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

Всього в базі: 75843
останнє поновлення: 2016-12-04
за 7 днів додано 15

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

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

 

ПОШУК:   

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

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

цях. Таким чином, тут |A1|=10, |A2|=|A3|=…=|A7|=9, і

загальна кількість номерів є 10(96.

 

2. Розміщення та перестановки без повторень

 

Означення. Розміщення по m елементів n-елементної множини A, де m(n – це

послідовність елементів множини A, що має довжину m і попарно різні

члени.

 

Приклади.

 

1. При A={a, b, c} розміщення по два елементи – це пари (a,b), (a,c),

(b,a), (b,c), (c,a), (c,b).

 

2. Розподіл n різних кульок по одній на кожний з m різних ящиків, m(n.

Ящики можна пронумерувати від 1 до m, кульки – від 1 до n. Тоді кожному

розподілу взаємно однозначно відповідає послідовність довжини m попарно

різних номерів від 1 до n.

 

Неважко підрахувати кількість послідовностей з прикладу 2. На першому

місці може стояти будь-який із номерів 1, …, n. На другому – незалежно

від того, який саме був на першому, будь-який із n-1, що залишилися. І

так далі. За принципом добутку, таких послідовностей

 

n((n-1)(…((n-m+1),

 

або (n)m або nm.

 

Означення. Перестановка n елементів множини A без повторень – це

розміщення по n елементів, тобто послідовність елементів множини A, що

має довжину n і попарно різні члени.

 

Приклад. При A={a, b, c} усі перестановки –це трійки (a,b,c), (a,c,b),

(b,a,c), (b,c,a), (c,a,b), (c,b,a).

 

Очевидно, що кількість перестановок n елементів дорівнює кількості

розміщень по m при m=n, тобто n!. Отже, nn=n!.

 

3. Комбінації без повторень

 

Означення. Комбінація по m елементів n-елементної множини – це її

m-елементна підмножина.

 

Приклади.

 

1. При A={a, b, c} усі комбінації по два елементи – це підмножини {a,b},

{a,c}, {b,c}.

 

2. Розподіл n різних кульок по одній на кожний з m однакових ящиків,

m(n. Оскільки ящики однакові, то розподіл взаємно однозначно

визначається підмножиною з m кульок, що розкладаються.

 

.

 

4. Перестановки з повтореннями

 

Означення. Перестановка з повтореннями по m елементів множини A={a1, a2,

…, an} складу (k1, k2, …, kn) – це послідовність довжини m=k1+k2+…+kn, в

якій елементи a1, a2, …, an повторюються відповідно k1, k2, …, kn разів.

 

Приклади.

 

1. При A={a, b, c} перестановками з повтореннями складу (1, 0, 2) є

послідовності (a,c,c), (c,a,c), (c,c,a), складу (1, 1, 1) – (a,b,c),

(a,c,b), (b,a,c), (b,c,a), (c,a,b), (c,b,a).

 

2. Нехай m різних кульок розкладаються по n різних ящиках так, що в

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

причому m=k1+k2+…+kn. Пронумеруємо кульки від 1 до m, ящики – від 1 до

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

номеру кульки номер ящика, куди вона потрапила. Отже, маємо

послідовність довжини m=k1+k2+…+kn, в якій номери 1, 2, …, n

повторюються k1, k2, …, kn разів відповідно. Очевидно, що така функція

відповідає розкладу кульок взаємно однозначно. Таким чином, розклад

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

 

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

an} складу (k1, k2, …, kn) позначається P(k1, k2, …, kn) і виражається

формулою:

 

.

 

Доведемо її за допомогою математичної індукції за n.

-----> Page:

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

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