Реферат
на тему:
Елементи комбінаторики
Поняття множини. Операції над множинами
Поняття множини належить до первісних понять математики, якому не
дається означення Множину можна уявити собі як сукупність деяких
предметів, об’єднаних за довільною характеристичною ознакою Наприклад,
множина учнів класу, множина цифр десяткової нумерації (0, 1, 2, 3, 4,
5, 6, 7, 8, 9), множина натуральних чисел, множина зернин у даному
колосі, множина букв українського алфавіту, множина точок на прямій
Предмети, з яких складається множина, називаються її елементами і
позначаються малими буквами латинського алфавіту. Наприклад, а = 5 –
елемент множини цифр десяткової нумерації Для позначення множин
використовують великі букви латинського алфавіту або фігурні дужки,
всередині яких записуються елементи множини При цьому порядок запису
елементів не має значення Наприклад, множину цифр десяткової нумерації
можна позначити буквою М (чи будь-якою великою буквою латинського
алфавіту) або записати так {1, 3, 5, 2, 4, 6, 8, 7, 9, 0}
A.
Множини бувають скінченні і нескінченні. У скінченній множині міститься
певна кількість елементів, тобто кількість елементів скінченної множини
виражається натуральним числом Наприклад, множина М цифр десяткової
нумерації скінченна і містить десять елементів. У нескінченній множині –
нескінченна кількість елементів. Наприклад, множина натуральних чисел,
множина точок прямої – нескінченні множини.
. Наприклад, множина точок перетину двох паралельних прямих – порожня
множина
– знаком строгого включення.
А.
А.
Множину задають двома основними способами:
1) переліченням всіх її елементів;
,(} – множина, задана переліченням елементів; б) X – множина коренів
квадратного рівняння х2 = 25. Множина X задана характеристичною
властивістю елементів – бути коренем рівняння х2 = 25″. Цю саму множину
можна задати і переліченням її елементів: X = {-5; 5}.
Дві множини називаються рівними, якщо вони складаються з тих самих
елементів. Наприклад, множини коренів рівняння х2 = 25 і |x| = 5 рівні
між собою. Справді, X = {-5; 5} і Y = {-5; 5}, де Y – множина розв’язків
рівняння |x|-5. Отже, X = Y.
Над множинами виконуються певні операції (дії). Зазначимо три з них.
Переріз множин. Перерізом множин А і В називається множина С, яка
складається з усіх тих і тільки тих елементів, які належать коленій з
даних множин А і В.
Приклад 1. Нехай А – множина всіх дільників числа 32, тобто А = {І, 2,
4, 8, 16, 32), а В – множина всіх дільників числа 24, тобто В = {1, 2,
3, 4, 6, 8, 12, 24}. Тоді перерізом множин А і В є множина С = {1, 2, 4,
8}, яка складається зі спільних дільників чисел 32 і 24.
В і читається: “С є перерізом А і В”.
N – множина квадратів.
Об’єднання множин. Об’єднанням (або сумою) двох множин А і В називається
така множина С, яка складається з усіх елементів множин А і В, і тільки
з них.
В і читається: “С є об’єднанням А і В”.
0, то кожний з цих спільних елементів береться в множину С тільки один
раз.
Приклад 3. А ={1,2, 3,4}, В = {3, 4, 5, 6}, тоді С = {1,2,3,4,5,6}.
І.
Операції над множинами широко використовуються в математиці та інших
науках, а також у практиці. Наприклад, розв’язками системи рівнянь є
переріз множин розв’язків кожного рівняння, а об’єднання їх є множиною
розв’язків сукупності рівнянь.
Віднімання множин. Доповнення множини. Різницею двох множин А і В
називається така множина С, яка складається з усіх елементів множини А,
що не належать множині В.
Позначається це так: С = А \ В і читається: “С є різницею А і В”.
А, тоді С = А \ В= {8, 12};
б) А = {5, 6, 8, 12}, В = {8, 12, 1, 2}, тоді С = А\ В = {5, 6};
в) А = {5, 6, 12}, В = {1, 2}, тоді С = А \ В = {5, 6, 12};
.
В, то різниця С = А \ В називається доповненням множини В відносно
множини А і позначається САВ.
1. Принцип добутку і принцип суми. Розміщення з повтореннями
Двома основними правилами комбінаторики є:
Принцип суми. Якщо множина A містить m елементів, а множина B – n
елементів, і ці множини не перетинаються, то A(B містить m+n елементів.
Принцип добутку. Якщо множина A містить m елементів, а множина B – n
елементів, то A(B містить m(n елементів, тобто пар.
Кількість елементів множини A будемо далі позначати |A|.
Ці правила мають також вигляд:
Принцип суми. Якщо об’єкт A можна вибрати m способами, а об’єкт B – n
іншими способами, то вибір “або A, або B” можна здійснити m+n способами.
Принцип добутку. Якщо об’єкт A можна вибрати m способами і після кожного
такого вибору об’єкт B може бути вибраним n способами, то вибір “A і B”
в указаному порядку можна здійснити m(n способами.
Наведені правила очевидним чином узагальнюються на випадки довільних
скінченних об’єднань множин, що попарно не перетинаються, та на
скінченні декартові добутки.
Правило добутку застосовується для підрахунку кількості об’єктів, що
розглядаються як елементи декартових добутків відповідних множин. Отже,
ці об’єкти являють собою скінченні послідовності – пари, трійки тощо.
Нагадаємо, що з точки зору математики послідовність довжини m елементів
множини A – це функція, яка натуральним числам 1, 2, …, m ставить у
відповідність елементи з A.
Означення. Розміщення з повтореннями по m елементів n-елементної множини
A – це послідовність елементів множини A, що має довжину m.
Приклад. При A={a, b, c} розміщення з повтореннями по два елементи – це
пари (a,a), (a,b), (a,c), (b,a), (b,b), (b,c), (c,a), (c,b), (c,c).
Якщо |A|=n, то за правилом добутку множина всіх розміщень з
повтореннями, тобто множина Am=A(A(…(A, містить nm елементів. Зокрема,
якщо |A|=2, то розміщень з повтореннями 2m. Зауважимо, що ці розміщення
можна взаємно однозначно поставити у відповідність послідовностям з 0 і
1 довжини m.
a
a
a
??
dh^„T`„gd!”e
? – після того, як зафіксовано перші два і т.д. Обчислимо, наприклад,
кількість 7-цифрових телефонних номерів, у яких немає двох однакових
цифр поспіль. Якщо на першому місці в номері є, наприклад, 1, то на
другому може бути будь-яка з 9 інших цифр. І так само на подальших
сусідніх місцях. Таким чином, тут |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.
, і базу доведено.
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
Як бачимо, множиною елементів, якими утворюється комбінація з
повтореннями, тут є {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).
((( ((( (((
k1 k2 … kn
, що й є кількістю всіх можливих комбінацій по m елементів n-елементної
множини з повтореннями.
PAGE \* MERGEFORMAT 1
Нашли опечатку? Выделите и нажмите CTRL+Enter
