Теорія множин Теорія множин Комбінаторика. Поняття множини є первинним поняттям математики, якому не дається означення. Поняття множини є первинним поняттям. - презентация

1 Теорія множин Теорія множин Комбінаторика

2

3 Поняття множини є первинним поняттям математики, якому не дається означення. Поняття множини є первинним поняттям математики, якому не дається означення. Множину можна уявити, як сукупність зібрання деяких предметів, обєднаних за певною характеристичною ознакою. Приклади: м ножина учнів класу; множина букв латинського алфавіту; множина чисел, які використовують при лічбі, її називають множиною натуральних чисел N. Множина. Її елементи

4 Множина зазвичай позначається будь-якою великою буквою латинського алфавіту, при заданні множини переліком елементів – елементи беруться у фігурні дужки. Множина зазвичай позначається будь-якою великою буквою латинського алфавіту, при заданні множини переліком елементів – елементи беруться у фігурні дужки. B ={,,, } – множина задана переліком елементів. Множина, яка не має жодного елемента, називається порожньою і позначається Множина, яка не має жодного елемента, називається порожньою і позначається множина всіх натуральних чисел – літерою N; множина всіх цілих чисел – Z; множинавсіх раціональних чисел – Q; множина всіх раціональних чисел – Q; множинавсіх ірраціональних чисел – I; множина всіх ірраціональних чисел – I; множинавсіх дійсних чисел R; множина всіх дійсних чисел R; множина всіх комплексних чисел C. Для деяких множин існують спеціальні позначення:

5 Предмети, що утворюють множину, називаються елементами множини. Предмети, що утворюють множину, називаються елементами множини. Належність елемента до множини позначається. Неналежність елемента до множини позначається,. Приклади: Нехай А – множина чисел першого десятка, тоді Нехай L – множина букв латинського алфавіту, тоді

6 Порівняння множин Дві множини вважаються рівними, якщо вони складаються з одних і тих самих елементів.

7 Поняття підмножини Якщо кожен елемент множини А є елементом іншої множини В, то кажуть, що А є підмножиною В і записують:, якщо при цьому допускається, що множина А включає у себе всі елементи множини В, то записують. Таким чином:

8 Інколи співвідношення між множинами зручно ілюструвати за допомогою кругів (які часто називають кругами Ейлера-Венна). А – підмножина В. Співвідношення між множинами N, Z, Q, R.

9 Множини бувають скінченними і нескінченними. Скінченна множина містить певну кількість елементів. Наприклад: А={1; 5; 8; 17}. B - множина учнів в класі. Нескінченна множина містить безліч елементів. Наприклад: N, Z, Q, I, R, C. B - множина точок на прямій.

10 Приклад : 1. А – множина всіх дільників числа 32; В – множина всіх дільників числа 24; А={1; 2; 3; 8; 16; 32}; B={1; 2; 3; 4; 6; 8; 12; 24}; C=AB; 2. А – множина всіх прямокутників; В – множина всіх ромбів; C=AB – множина всіх квадратів. Перетин (переріз, добуток) множин Перетином множин А і В називається множина С, що складається з усіх тих і лише тих елементів, які входять до складу кожної з даних множин А і В і є спільною частиною множин А і В. Приклад : 1. А – множина всіх дільників числа 32; В – множина всіх дільників числа 24; А={1; 2; 3; 8; 16; 32}; B={1; 2; 3; 4; 6; 8; 12; 24}; C=AB; C={1; 2; 3; 8}.

11 Приклад: 1) А={1; 2;3; 4} B={3; 4; 5; 6} C=A U B = {1; 2; 3; 4; 5; 6}. 2) А і B-множини точок двох трикутників зі спільною стороною. C=A U B – множина точок опуклого многокутника. Обєднання (сума) множин Обєднанням двох множин А і В називається така множина С, яка складається з усіх елементів множин А і В і лише з них.

12 Приклад: 1.A={5; 6; 8; 12} B={5; 8} C=A\B={8; 12} C=B\A=Ø 2. A={10; 12; 14; 50; 78} B={3; 14; 78; 100} C=A\B={10; 12; 50} C=B\A={3; 100} Різниця множин Різницею двох множин А і В називається така множина С, яка складається з усіх елементів множини А, які не належать множині В. С=А\В С=В\А

13 1.A={1;5;8;15}; B={3;5;7;15;18}; C=A U B; D=A B Знайдіть C і D. 2. Чи існують такі множини А, В і С, для яких виконуються усі 3 умови AB Ø ; AC= Ø ; (AB)\C= Ø. 3. A={3;19;125}; B={7;13;125}; C= A B; Зі скількох елементів складається множина С. 4. A={хліб, молоко, цукерки, печиво, кава} – множина товарів у магазині. В 1 ={масло, печиво, цукор} – множина товарів, які хоче придбати перший покупець. В 2 ={молоко, хліб, печиво} – множина товарів, які хоче придбати другий покупець. Який із двох покупців зможе задовольнити свої потреби у магазині? 5. Яка із множин A={1; 3.5; 9;}; B={1;7;8;9;19}; C={-1; 0; 7; 8; 15;} є підмножиною множини натуральних чисел N. 6.А- множина квадратів усіх цілих чисел. Які із чисел 1; 16; 5; -4; 0.3; 8; 25 є елементами цієї множини. 7.Нехай А – множина коренів рівняння х 2 3х + 2 = 0, а В = {0; 2}. Знайти A B, АUВ. 8. Яка із двох множин є підмножиною іншої (QØ): а) Р та Р Q ; б) Р та PUQ. Завдання з теми Множини

14

15

16 При розвязуванні багатьох практичних задач доводиться вибирати з деякої сукупності обєктів елементи, що мають ту або іншу властивість, розміщуватися ці елементи в певному порядку, зясовувати скількома способами можна це зробити і т.ін. оскільки в таких задачах мова іде про ті або інші комбінації обєктів то такі задачі називають комбінаторними. Розділ математики, в якому вивчають комбінаторні задачі, називають комбінаторикою. У комбінаториці розглядається вибір і розміщення елементів деякої скінченної множини на основі якихось умов.

17 В основі розвязування багатьох комбінаторних задач лежать два основних правила – правило суми і правило добутку.

18 Правило суми У загальному вигляді має місце таке твердження: Якщо елемент множини А можна вибрати m способами, а елемент множини В – n способами, то елемент множини А або В можна вибрати m+n способами. Приклад: Якщо на тарілці лежить 3 груші та 2 яблука, то вибрати один фрукт (тобто грушу або яблуко) можна 2+3=5 способами.

19 Правило добутку В загальному вигляді має місце таке твердження: Якщо елемент множини А можна вибрати m способами, а після цього елемент множини В – n способами, то А і В можна вибрати (m n) способами. Приклад: Якщо на одній тарілці лежать 3 яблука, а на другій - 2 груші, то вибрати пару груша і яблуко можна 3 2 = 6 способами.

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

21 У комбінаториці розглядається вибір і розміщення елементів деякої скінченної множини на основі якихось умов.

22 Впорядкована множина Множина, кожному елементу якої поставлений у відповідність певний номер називаеться впорядкованою. Будь-яку впорядковану множину, що містить більше одного елемента можна впорядкувати декількома способами. Впорядковані множини вважаються різними, якщо вони складаються з різних елементів або мають різний порядок одних і тих же елементів. Різні впорядковані множини, що відрізняються лише порядком елементів (тобто можуть бути отримані з однієї множини) називаються перестановками цієї множини.

23 Будь-яка впорядкована множина, яка складається з n елементів, називаеться перестановкою з n елементів. Отже перестановки з n елементів відрізняються одна від одної лише порядком елементів. Число перестановок з n елементів позначається P. Перестановки можна утворювати з елементыв будь-якої скінченної множини. Множину з одного елемента можна впорядкувати одним- єдиним способом: єдиний елемент множини доводиться вважати першим, тобто P=1. Перестановки Візьмемо множину з двох елементів, для прикладу, з двох літер А і Б. Зрозуміло, що їх можна розташувати по порядку двома способами: АБ або БА, тобто P=2=12. Три літери можна розташувати по порядку шістьма способами: АБВ, АВБ, БАВ, БВА, ВАБ, ВБА, тобто P=6=123. Взагалі,P (число перестановок з n елементів) дорівнює добутку перших n натуральних чисел P=123...n. Для добутку перших n натуральних чисел прийнято спеціальне позначення:n! (читається "n-факторіал"). Користуючись цим позначенням можна записати P=n! Як вже зазначалося, множину з одного елемента можна впорядкувати єдиним способом. Для подальшого зручно вважати, що порожню множину теж можна впорядкувати лише одним способом, тобто домовитися вважати, що P1=1!=1 і P0=0!=1.

24 Розміщення Розміщенням з n елементів по k називається будь- яка впорядкована множина з k елементів, складена з елементів n-елементної множини. Наприклад із множини з трьох цифр {1; 5; 7} можна скласти такі розміщення з двох елементів: (1;5), (1;7), (5;7), (5;1), (7;1), (7;5). Ще однією класичною задачею на розміщення є задача на складання розкладу, наприклад: скількома сппособами можна скласти даний розклад з 5 різних уроків, якщо у класі вивчають девять навчальних предметів? Отже, розміщення відрізняються одне від одного або елементами, або порядком елементів. Характеристичні ознаки розміщень: 1) предмети і місця різні; 2) 0 k n; 3) усі k місць треба зайняти; 4) порядок елементів важливий. Очевидно, що коли k = n, матимемо перестамовки з k елементів, тобто перестановка є окремим випадком розміщення за умови, що k = n. Кількість розміщень з n елементів по k позначається (читається: "А з ен по ка") і розраховується за формулою

25 Сполучення Властивості Якщо при розвязуванні комбінаторної задачі з елементів даної множини треба скласти підмножини, які різняться складом елементів, а порядок розташування вибраних елементів є не істотним, то говорять, що маємо задачу на сполучення. Сполученням з n елементів по k називаеться будь-яка k - елементна підмножина n - елементної множини. Характеристичні ознаки сполучень: 1) предмети різні; 2) 0 k n; 3) порядок елементів не має значення. Кількість комбінацій з n елементів по k позначається і розраховується за формулою:

26 Вибір формули Чи враховується порядок?(Чи є множина впорядкованою?) Усі елементи приймають участь? ТакНі ТакНі ПерестановкиРозміщенняСполучення

27 Біном Ньютона Двочлен a+b називається біномом. З шкільного курсу алгебри відомі квадрат і куб двочлена: Для довільного натурального n має місце формула: Властивості: 1.Кількість членів розкладу бінома на одиницю більше за показник степеня. 2.Показники одного з членів зменшуються від n до 0, а показники другого збільшуються від 0 до n. 3.Біномінальні коефіцієнти, рівновіддалені від кінців розкраду рівні між собою: 4. Сума усіх біномінальних коефіціентів дорівнює 2 n, де n показник бінома.

28 Комбінаторика – розділ дискретної математики, присвячений розвязанню задач про вибір та розміщення елементів скінченної множини, згідно з заданими правилами, для створення певних комбінаторних конфігурацій.

29 В основі розвязування багатьох комбінаторних задач лежать два основних правила – правило суми і правило добутку.

30 Правило суми Правило суми стверджує: якщо множина А складається з n елементів, а множина В з k, то вибрати елемент множини А або В можна n+k способами. Приклад: Маємо 2 урни. У першій – n куль, а у другій – k. Отже з першої урни можна вибрати кулю n способами, а з другої – k способами. І тоді існує n+k способів, щоб вибрати кулю з будь-якої із обох урн.

31 Правило добутку Правило добутку стверджує: Якщо елемент множини А можна обрати n способами, а елемент множини В – k способами, то існує nk способів сформувати комбінацію з двох елементів, взявши один із них з множини А, а другий з множини В. Приклад: Маємо 2 урни. У першій – n жовтих куль, а у другій – k синіх. Отже з першої урни можна вибрати кулю n способами, а з другої – k способами. І тоді існує nk способів, щоб скласти набір з однієї синьої і одної жовтої кулі.

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

33 У комбінаториці розглядається вибір і розміщення елементів деякої скінченної множини на основі якихось умов.

34 Впорядкована множина Множина, кожному елементу якої поставлений у відповідність певний номер називаеться впорядкованою. Будь-яку впорядковану множину, що містить більше одного елемента можна впорядкувати декількома способами. Впорядковані множини вважаються різними, якщо вони складаються з різних елементів або мають різний порядок одних і тих же елементів. Різні впорядковані множини, що відрізняються лише порядком елементів (тобто можуть бути отримані з однієї множини) називаються перестановками цієї множини.

35 Перестановки P n =n! (n! читається ен факторіал n!=123…n=n(n-1)(n-2)…1) Доведення: Нехай А – множина з n елементів. Номер 1 можна присвоїти будь-якому з n елементів, номер 2 будь-якому з (n-1) елементів (бо один вже пронумеровано), номер 3 будь-якому з (n-2) елементів що залишилися і т.д. Отже P n =n(n-1)(n-2)…1=n! Перестановки множини А (позначається P n ) – це множини, що складаються з тих самих елементів, що й А, але розставлених у різному порядку.

36 Розміщення Будь-яка впорядкована підмножина з k елементів даної n-елементної множини називається розміщенням з n елементів по k. Будь-яка впорядкована підмножина з k елементів даної n-елементної множини називається розміщенням з n елементів по k. Розміщення відрізняються одне від одного або складом або порядком елементів. Доведення: Нехай існує множина А, що містить n елементів і деяка послідовність, що може бути заповнена будь-якими k елементами з n, kn. Отже, як і у випадку з перестановками, першим елементом послідовності може стати один із n елементів, другим – один із (n-1) і т.д. але ми маємо k місць для розміщення елементів з множини А і тому послідовність n(n-1)(n-2)… буде на (n-k) множників коротшою, а добуток у (n-k)! разів меншим за n! Отже.

37 Сполученням з n елементів по k називається будь-яка невпорядкована, k - елементна підмножина даної n - елементної множини. Сполучення Доведення: Нехай існує множина А, що містить n елементів і деяка послідовність(невпорядкована множина), що містить k елементів, вибраних із А. Якщо існує, можливих способів заповнити k – елементну послідовність, що є впорядкованою множиною, то дану послідовність можна заповнити способами. Властивості

38 Біном Ньютона Двочлен a+b називається біномом. З шкільного курсу алгебри відомі квадрат і куб двочлена: Для довільного натурального n має місце формула: Властивості: 1.Кількість членів розкладу бінома на одиницю більше за показник степеня. 2.Показники одного з членів зменшуються від n до 0, а показники другого збільшуються від 0 до n. 3.Біномінальні коефіцієнти, рівновіддалені від кінців розкраду рівні між собою: 4. Сума усіх біномінальних коефіціентів дорівнює 2 n, де n показник бінома.

39 Тести З 30 учасників зборів треба вибрати голову і секретаря. Скількома способами це можна зробити? інша відповідь 30! 15

40 Тести Скількома способами можна вибрати трьох чергових з групи в 20 чоловік? інша відповідь !

41 Тести Скількома способами можна вісім учнів вишикувати в колону по одному? інша відповідь

42 Тести У коробці знаходяться 10 білих і 6 чорних куль. Скількома способами з коробки можна витягти одну кулю будь-якого кольору? інша відповідь 60 16

43 Тести Маємо чотири різні конверти без марок і 3 різні марки. Скількома способами можна вибрати конверт і марку для відправки листа? інша відповідь

44 Тести Многочлен x 4 +8x 3 +24x 2 +32x+16 є біномінальним розкладом степеня (х+1) 4 (х+1) 4 (х+2) 4 (х+2) 4 інша відповідь (х-2) 4 (х-2) 4 (х-4) 4 (х-4) 4

45 Тести Скільки різних звукосплучень можна взяти на десяти вибраних клавішах роялю, якщо кожне звукосполучення може містити від трьох до десяти звуків? інша відповідь

46 Тести Скількома способами можна розмістити на шаховій дошці дві тури, щоб одна не змогла побити іншу? (одна тура може побити іншу, якщо вони знаходяться з нею на одній горизонталі або на одній вертикалі шахової дошки) інша відповідь

47 Тести Учасники шахового турніру грають в залі, де є 8 столиків. Скількома способами можна розмістити шахістів, якщо учасники всіх партій відомі? 16! 16 інша відповідь 8! 8888

48 Тести Скільки існує правильних дробів, чисельник і знаменник яких прості числа, не більші за 20? інша відповідь

49 Тести Яку мінімальну кількість елементів повинна містити множина, щоб число усіх перестановок з елементів цієї множини було не менше 500? інша відповідь

50 Тести Знайдіть показник степеня бінома, якщо шостий член розкладу (a -3/4 -a -3/5 ) n не залежить від a інша відповідь

51 Дякуємо за увагу! На початок На початок Завершити