WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

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

ГоловнаМатематика, Геометрія, Статистика → Початки комбінаторики - Реферат

Початки комбінаторики - Реферат

допомогою перестановок із повтореннями. Усі перестановки з повтореннями з елементів множини 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).
14243 14243 14243
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).
123 123 123
k1 k2 … kn
Як бачимо, множиною елементів, якими утворюється комбінація з повтореннями, тут є {1, 2, …, n}.
Комбінації по m елементів множини {a1, a2, …, an} з повтореннями складу (k1, k2, …, kn) можна взаємно однозначно поставити у відповідність послідовність довжини m+n-1 із m "1" і n-1 "0":
(1, …, 1, 0, 1, …, 1, 0, …, 1, …, 1).
123 123 123
k1 k2 … kn
Такій послідовності, у свою чергу, взаємно однозначно відповідає комбінація номерів місць у цій послідовності, на яких розташовані 1 (або 0). Кількість таких комбінацій є , що й є кількістю всіх можливих комбінацій по m елементів n-елементної множини з повтореннями.
6. Формули включень і виключень
Кількість елементів об'єднання двох множин, що не перетинаються, є сумою їх кількостей. Але якщо множини перетинаються, то елементи перетину при цьому додаванні кількостей враховуються двічі. Тому їх кількість треба один раз відняти:
|A B|=|A|+|B|-|A B|. (*)
При обчисленні |A B C| додавання |A|+|B|+|C| веде до того, що елементи кожного з перетинів |A B|+|B C|+|A C| враховуються двічі, тому їх треба по одному разу відняти. Якщо перетин A B C порожній, то в результаті кожний елемент об'єднання враховано по одному разу, і все гаразд. Якщо ні, то в результаті елементи цього перетину тричі додаються і тричі віднімаються, тобто у виразі
|A|+|B|+|C|-|A B|-|B C|-|A C|
не враховані. Отже, їх треба додати:
|A B|=|A|+|B|+|C|-|A B|-|B C|-|A C|+|A B C|. (**)
Вирази (*), (**) наводять на припущення, що в загальному випадку об'єднання n множин A1, A2, …, An
|A1 A2 … An|=|A1|+|A2|+…+|An|-|A1 A2|-|A1 A3|-…-|An-1 An|+
+|A1 A2 A3|+…+|An-2 An-1 An|-…+(-1)n+1|A1 A2 … An|. (1)
Як бачимо, кількості елементів усіх можливих перетинів непарної кількості множин додаються, а парної - віднімаються. Формула (1) називається формулою включень і виключень.
Доведення формули (1) можна провести з використанням індукції за n, але тут ми його не наводимо.
Ця формула дає змогу за кількостями елементів у кожній з множин, в усіх можливих їх перетинах по дві, по три і т.д. множини обчислити кількість елементів об'єднання.
Приклад. Є група студентів, серед яких каву п'ють 12 (це множина A), чай - 10 (множина B), йогурт - 8 (C), каву і чай - 5 (A B), каву і йогурт - 4 (A C), чай і йогурт - 3 (B C), усі три напої - 1 (A B C). Тоді всього студентів у групі 12+10+8-5-4-3+1=19.
За допомогою формули (1) можна обчислити кількість елементів деякої множини U, що не належать жодній з її підмножин A1, A2, …, An:
|U(A1 A2 … An)|=|U|-|A1|-|A2|-…-|An|+|A1 A2|+|A1 A3|+…+
+|An-1 An|-|A1 A2 A3|-…-|An-2 An-1 An|+…+(-1)n|A1 A2 … An|. (2)
Формулу (2) також називають формулою включень і виключень.
7. Біноміальні коефіцієнти
Означення. Біном Ньютона - це вираз вигляду (a+b)n.
Біном розкладається в суму одночленів, які є добутками деяких степенів його доданків a і b. Школярі-восьмикласники знають формули розкладу бінома Ньютона в многочлен із степенями a і b при n=2 та 3:
(a+b)2=a2+2ab+b2,
(a+b)3=a3+3a2b+3ab2+b3.
Спробуємо розкласти (a+b)n в многочлен у загальному випадку n. Запишемо його у вигляді, пронумерувавши дужки:
1 2 … n
(a+b)(a+b)…(a+b).
Очевидно, що кожний доданок містить n множників - k множників a і n-k множників b, тобто має вигляд akbn-k, де k n, k 0. Кожний такий доданок взаємно однозначно відповідає підмножині номерів дужок, з яких для утворення цього доданка ми брали множники a. Таким чином, доданків akbn-k рівно стільки, скільки таких підмножин, тобто = . Отже,
(a+b)n =
Коефіцієнти при akbn-k називаються біноміальними, оскільки записуються в розкладі бінома (a+b)n.
Біноміальні коефіцієнти мають очевидну властивість симетрії:
= =. .
Розглянемо окремі випадки бінома Ньютона:
при b=1 маємо (a+1)n = ,
при a=b=1 маємо (1+1)n = 2n = ,
при a= -1, b=1 маємо (-1+1)n = 0n = (-1)k.
За останньою рівністю, зокрема, природно означити 00 як 1, слідуючи за Доналдом Кнутом **** .
Запишемо біноміальні коефіцієнти для початкових значень n=0, 1, …, 5 у трикутну таблицю:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
З таблиці видно, що кожний елемент, який не є першим у своєму рядку, є сумою елемента над ним і елемента, розташованого над ним і ліворуч:
= +
Ця тотожність називається правилом додавання. Існує багато різних її доведень. Ось "лобове":
Доозначимо біноміальні коефіцієнти при kn як =0. Тоді правило додавання справджується за будь-яких значень k. Скористаємося цим доозначенням також і далі, розглядаючи суми, в яких додавання ведеться за нижнім коефіцієнтом k у виразах вигляду . Це дозволить не записувати межі, у яких змінюється k.
Доведемо ще одну тотожність, яка називається згорткою Вандермонда:
.
Якщо замінити k на k-m, а n - на n-m, то одержимо рівність
.
Вона має назву тотожності Коші. Доведемо спочатку цю рівність. Нехай є r дівчат і s юнаків. Праворуч маємо кількість способів вибрати з них усіх n осіб. Кожний доданок у сумі ліворуч задає кількість способів вибрати n осіб так, щоб серед них було k дівчат з r і n-k юнаків з s. Додавання цих кількостей по всіх можливих значеннях k дає кількість всіх способів вибрати з них усіх n осіб. Отже, вирази ліворуч і праворуч задають одну й ту саму кількість, тобто рівні. Якщо тепер замінити назад k на k+m, а n на n+m, одержимо початкову рівність.
Таблиця біноміальних коефіцієнтів зображається ще у вигляді так званого арифметичного трикутника, або трикутника Паскаля:
1
1 1
1 2 1
1 3 3 1

Розширимо поняття біноміальних коефіцієнтів на дійсні значення n. Згадаємо зв'язок між кількістю комбінацій з n елементів по k та кількістю їх розміщень без повторень: = (n)k/k!, де (n)k=n(n-1)…(n-k+1). Але останній добуток означений при будь-якому дійсному значенні n. Слідуючи Доналду Кнуту **** , замість цілого n розглянемо дійсне r: (r)k=r(r-1)…(r-k+1). Тоді за дійсних значень r означимо як (r)k/k!.
Loading...

 
 

Цікаве