Основи комбінаторики. Робота студентів економічного факультету II курсу, 9 групи: Кислюк Аліни, Сімончук Марини, Федоренко Катерини, Цибори Аліни. 2011. - презентация

1 Основи комбінаторики. Робота студентів економічного факультету II курсу, 9 групи: Кислюк Аліни, Сімончук Марини, Федоренко Катерини, Цибори Аліни р р.

2 План : План : Скінченні множини та операції над ними.Скінченні множини та операції над ними. Предмет комбінаторики.Предмет комбінаторики. Перестановки, розміщення та комбінації.Перестановки, розміщення та комбінації. Сполуки з повторенням.Сполуки з повторенням.

3 Скінченні множини та операції над ними Всяка сукупність довільних елементів утворює множину. Всяка сукупність довільних елементів утворює множину. Множина вважається визначеною, якщо відомі всі її елементи. Множина вважається визначеною, якщо відомі всі її елементи. Якщо кількість елементів множини скінченна, то множина називається скінченною. Якщо кількість елементів множини скінченна, то множина називається скінченною.

4 Сумою або об'єднанням множин А та В називається множина: Сумою або об'єднанням множин А та В називається множина: С = А U В = А + В, С = А U В = А + В, яка складається з елементів, що належать хоча б одній з цих множин (рис.1.2). яка складається з елементів, що належать хоча б одній з цих множин (рис.1.2). Рис.1.2. Діаграма Ейлера-Венна для суми множин. Рис.1.2. Діаграма Ейлера-Венна для суми множин. Приклад. Для множини А = {1;2;3} і В = {2;3;4} сумою буде множина А + В = {1;2;3;4}. Приклад. Для множини А = {1;2;3} і В = {2;3;4} сумою буде множина А + В = {1;2;3;4}.

5 Добутком або перерізом множин А та В називається множина: Добутком або перерізом множин А та В називається множина: С = А В= А В, С = А В= А В, якій належать лише спільні для обох множин елементи (рис.1.2). якій належать лише спільні для обох множин елементи (рис.1.2). С = А В= А В С = А В= А В Рис.1.2. Діаграма Ейлера-Венна для перетину множин. Рис.1.2. Діаграма Ейлера-Венна для перетину множин. Приклад. Для множин А = {1;2;3} і В = {2;3;4} перерізом буде множина С = {2;3} Приклад. Для множин А = {1;2;3} і В = {2;3;4} перерізом буде множина С = {2;3}

6 Комбінаторика - розділ математики, в якому розглядаються задачі вибору і розміщення елементів деякої, зазвичай скінченної, множини у відповідності до заданих правил. Комбінаторика - розділ математики, в якому розглядаються задачі вибору і розміщення елементів деякої, зазвичай скінченної, множини у відповідності до заданих правил. Комбінаторику розглядають як вступ до теорії ймовірностей, тому що методи комбінаторики допомагають в теорії ймовірностей виконати підрахунок числа можливих результатів. Комбінаторику розглядають як вступ до теорії ймовірностей, тому що методи комбінаторики допомагають в теорії ймовірностей виконати підрахунок числа можливих результатів. Предмет комбінаторики

7 Якщо множина А містить n елементів, а множина В – m елементів, і множини не перетинаються, то множина A U В вміщує m + n елементів – принцип суми. Принцип суми Принцип суми

8 Для створення підприємства необхідно вибрати місто. У східній Україні було запропоновано 5 міст, у західній – 4, у північній і південній - жодного. Скількома способами можна вибрати місто для створення підприємства? Розв'язання. Вибір А (із східної України) можна вибрати п'ятьма способами, а вибір В (із західної) – чотирма способами. Загальна кількість способів А + В = = 9. Приклад Приклад

9 Для множин А={a 1, а 2,..., a n } і В={b 1, b 2,..., b n } множина С всіх можливих пар з елементів обох множин містить n · m – принцип добутку. Принцип добутку Принцип добутку

10 Для перевезення товарів з Києва до Львову існує шість шляхів, а з Львову до Тетієва – чотири шляхи. Скількома способами можна проїхати з Києва до Тетієва? Розв'язання. Для кожного, наприклад, із шести шляхів з Києва до Львову існує чотири шляхи (способи) потрапити з Львова до Тетієва. Тому на підставі правила добутку маємо: 6 · 4 = 24. Приклад Приклад

11 Перестановки, розміщення та комбінації. Комбінаторна математика оперує поняттями перестановка, розміщення та комбінації (сполучення). Комбінаторна математика оперує поняттями перестановка, розміщення та комбінації (сполучення). Множини, для яких істотним є порядок розташування елементів, називаються упорядкованими. Дві упорядковані множини називають рівними, якщо вони складаються з однакових і однаково розташованих елементів. Тому множини {a, b, c} і {b, c, a} – це різні упорядковані множини. Множини, для яких істотним є порядок розташування елементів, називаються упорядкованими. Дві упорядковані множини називають рівними, якщо вони складаються з однакових і однаково розташованих елементів. Тому множини {a, b, c} і {b, c, a} – це різні упорядковані множини.

12 Нехай нескінченна впорядкована множина Ω складається з n пронумерованих елементів. Будь-який спосіб розташування цих елементів складає результат дослідження. Будь-яка впорядкована множина, яка складається з n елементів називається перестановкою. Число перестановок позначається Рn і визначається за формулою: Рn = n !, де n ! є добутком натуральних чисел від 1 до n, ( 0! = 1). Перестановка Перестановка

13 Розміщення Розміщення Розібємо множину Ω, що складається з n елементів, що упорядковані підмножини, які складаються з m елементів кожна, так, щоб підмножини відрізнялись одна від одної або порядком розташування елементів, або самими елементами. Отримуємо певне елементарне розміщення елементів у підгрупах як результат досліду. Розміщенням з n елементів по m називається будь-яка впорядкована підмножина, що складається з m елементів, які вибрані з n елементів. Число розміщень знаходиться за формулою:

14 Комбінація (сполучення) Будь-яка підмножина з m елементів даної множини Ω, яка містить n елементів, називається комбінацією або сполученням з n елементів по m, де m n. Число всіх можливих комбінацій (сполучень) обчислюється за формулою:

15 Сполуки з повторенням Розміщення з повторенням. Розміщенням з повторенням з n елементів по k, взятих із множини, складеної з n елементів, називається будь-яка упорядкована підмножина, що вміщує k елементів, серед яких можуть бути однакові. Розміщенням з повторенням з n елементів по k, взятих із множини, складеної з n елементів, називається будь-яка упорядкована підмножина, що вміщує k елементів, серед яких можуть бути однакові. Число розміщень з повтореннями позначається через і обчислюється за формулою: Число розміщень з повтореннями позначається через і обчислюється за формулою:

16 Перестановки з повтореннями. Перестановки з повтореннями. Перестановкою з повтореннями називається будь-яке упорядкування з n елементів, серед яких є однакові. Перестановкою з повтореннями називається будь-яке упорядкування з n елементів, серед яких є однакові. Якщо серед n елементів множин є n 1 елементів I – типу, n 2 елементів II типу і т.д., тобто n 1 + n 2 …+ n k = n, то число всіх перестановок повторенням такої множини позначається через Р n (n 1, n 2,…, n k ) і обчислюється за формулою: Якщо серед n елементів множин є n 1 елементів I – типу, n 2 елементів II типу і т.д., тобто n 1 + n 2 …+ n k = n, то число всіх перестановок повторенням такої множини позначається через Р n (n 1, n 2,…, n k ) і обчислюється за формулою:

17 Комбінація (сполучення) з повтореннями. Комбінацією з повтореннями з n елементів по k називається множина, що складається з k елементів, взятих із даних n елементів, серед яких є однакові. Комбінацією з повтореннями з n елементів по k називається множина, що складається з k елементів, взятих із даних n елементів, серед яких є однакові. Число всіх комбінацій з повтореннями позначається через і обчислюється за формулою: Число всіх комбінацій з повтореннями позначається через і обчислюється за формулою: