Клас: 5
У цій статті розглянемо один із уроків у курсі математики 5 класу, присвяченого знайомству з комбінаторикою.
Цілі уроку.
Освітні:
Ознайомити учнів із новим типом завдань (комбінаторні завдання), прийомами їх вирішення – перебір можливих варіантів, побудова дерева можливих варіантів, застосування правила множення;
Ввести нове поняття – факторіал, закріпити його під час вирішення завдань, прикладів, рівнянь.
Виховні:
Формування поваги до товаришів, уміння слухати та чути співрозмовника
Формування ставлення до дружби як однієї з найважливіших людських цінностей.
Розвиваючі:
формування інтересу до предмета;
формування обчислювальних навичок;
Розвиток логічного мислення;
Формування вміння доводити, доводити свою думку.
Хід уроку
1. Організаційний момент
Вчитель: Сьогодні у нас із вами незвичайний урок. Ми вирішуватимемо завдання, пов'язані з одним з найцікавіших розділів математики – комбінаторикою. У науці й у реальному житті часто доводиться вирішувати завдання, головним питанням яких є питання “Скількими способами це можна зробити?”. Наприклад:
Скільки способів можна поставити учневі оцінку на уроці?
Скільки способами можна призначити чергового в класі?
Скільки способами можна призначити двох чергових у класі?
Вирішуючи такі завдання, доводиться складати різні комбінації з кінцевого числа елементів та підраховувати кількість комбінацій. Такі завдання отримали назву комбінаторних задач, а розділ математики, у якому розглядаються такі завдання, називають комбінаторикою. А якій ще темі буде присвячено урок, ви дізнаєтесь, коли ми перевіримо, як ви впоралися з виконанням домашнього завдання.
2. Перевірка виконання домашнього завдання
(На попередньому уроці домашнє завдання складається таким чином, щоб завдань було рівно 6. Наприклад, у підручнику Віленкіна Н.Я. та ін це можуть бути № 693(а, в), 735(1), 765(а,б, в))
На дошці – таблиця та закріплені магнітами картки. На картках з одного боку – відповідь до завдання домашньої роботи, з іншого боку – буква.
Вчитель: Перевіримо домашню роботу. Відкрийте зошити, візьміть олівці. Знайдіть відповіді на номери домашньої роботи.
Учні виходять до дошці по одному, вибирають картку з відповіддю та прикріплюють її до осередку таблиці під номером завдання. Спочатку картки закріплюють у клітинах таблиці вгору стороною, де записана відповідь, щоб учні могли перевірити правильність виконання домашньої роботи. Інші перевіряють свої відповіді в зошитах.
| № вправ | 693(а) | 693(в) | 735(1) | 765(а) | 765(б) | 765(в) |
| Відповіді | 25 | 13 | 6 | 182 000 | 6 300 | 65 000 |
Варіанти відповідей (розташовуються на різних сторонах карток). Карток роблять свідомо надмірну кількість, щоб частина відповідей була неправильною.
| д | р | у | ж | б | а | м | п | про |
| 25 | 13 | 6 | 182 000 | 6 300 | 65 000 | 49 | 12 | 18 200 |
"5" - якщо все правильно
"4" - якщо одна помилка
"3" - 2-3 помилки
"2" - більше 3 помилок
Вчитель: Перевернемо картки, яке слово одержали? (ДРУЖБА). Дійсно, сьогодні на уроці ми не лише вирішуватимемо математичні завдання, удосконалюватимемо навички обчислень, а й говоритимемо про дружбу.
3. Новий матеріал.
Вчитель: Отже, ми вже сказали, що сьогодні вчитимемося вирішувати завдання, головним питанням яких є питання “Скількими способами...”.
Є три слова "ДРУЖБА", "СПРАВА", "ЛЮБИТЬ" (нарізати листочки з цими словами - по 7 карток на кожне слово). Скільки способами з цих слів можна скласти фразу?
Учні пропонують варіанти, ці варіанти становлять дошці.
Відповідь: 6 способів.
Вчитель: Як ви вважаєте, який варіант є вірним з погляду російської? (Дружба любить справу). Як ви розумієте цей вислів?
Вчитель: Тут був наведений повний перебір всіх можливих варіантів, або, як завжди, всіх можливих комбінацій. Тому це комбінаторне завдання. Давайте подумаємо, як можна записати, оформити вирішення цього завдання.
1 спосіб. Позначимо запропоновані слова великими літерами:
ДРУЖБА – Д
ЛЮБИТ - Л
СПРАВА – Е (візьмемо другу літеру цього слова)
Тоді всі названі вами способи можна просто перерахувати: ДЛЕ, СПРАВИ, ЛДЕ, ЛІД, ОДЛ, ЕЛД.
Виявляється, рішення можна оформити як моделі, яку називають деревом можливих варіантів. Вона, по-перше, наочна, як будь-яка картинка, і, по-друге, дозволяє все врахувати, нічого не пропустивши,
Учні під керівництвом вчителя становлять схему:
Спосіб 3 (міркування)
На першому місці може стояти одне з трьох слів: ДРУЖБА, ЛЮБИТ, СПРАВА. Якщо перше слово вибрано, то на другому місці може стояти одне з двох слів, а на третьому місці - тільки одне слово, що залишилося. Отже, всього варіантів: .
Зауважимо, що останній прийом називається правилом множення.
Кожен із цих трьох способів має свої переваги та свої недоліки (обговорити) Вибір рішення – за вами! Відзначимо все ж таки, що правило множення дозволяє в один крок вирішувати найрізноманітніші завдання.
У Ані 3 подруги, і вона кожною з них купила шоколадку і хоче подарувати їх до свята. Скільки способами вона може це зробити?
Рішення: Рішення виконують на дошці учні (рішення виконується 3 способами)
У компанії друзів – 6 осіб: Андрій, Борис, Вітя, Грицько, Діма, Єгор. У шкільній їдальні за столом 6 стільців. Друзі вирішили щодня, снідаючи, розсаджуватись на ці 6 стільців по-різному. Скільки разів вони зможуть зробити це без повторень?
Який спосіб ми виберемо? (Учні під керівництвом вчителя мають дійти висновку, що це третій спосіб – правило множення).
Рішення оформляє на дошці учень.
Для зручності міркувань вважатимемо, що друзі сідають за стіл по черзі. Вважатимемо, що першою сідає за стіл Андрій. Він має 6 варіантів вибору стільця. Другим сідає Борис, і незалежно вибирає стілець з 5, що залишилися. Вітя робить свій вибір третім і на вибір у нього буде 4 стільці. У Гриші буде вже 3 варіанти, у Діми – 2, у Єгора – 1. За правилом множення отримуємо:
Відповідь – 720 днів або майже 2 роки.
Вчитель: Як бачимо, умови завдань різні, а рішення, щодо справи, однакові. Зручно тому ввести й однакові позначення для цих відповідей.
Визначення: добуток усіх натуральних чисел від 1 до п включно називається п - факторіал і позначається символом п!
Знак п! читається “Ен факторіал”, що у дослівному перекладі з англійської мови означає “що складається з пмножників”. Відзначимо важливу особливість цієї величини – її швидке зростання.
Обчисліть:
а) 1!; б) 2!; у 3!; г) 4!; д) 5!; е)10!
Вважають, що 0! =1 (записати)
Завдання 5.
ВЧИТЕЛЬ: ДРУЖБА – одне з найважливіших багатств, що може бути у людини. Недарма про дружбу складаються вірші та пісні, складають прислів'я та приказки. Які прислів'я та приказки про дружбу ви знаєте?
Друзі пізнаються в біді.
Не май сто карбованців, а май сто друзів.
Один у полі не воїн.
Сам гинь, а товариша рятуй.
Старий друг краще нових двох.
Без друга у житті туго.
Молодці! Для кожної людини дуже важливо, щоб у неї були хороші справжні друзі. Давайте вирішимо кілька прикладів із застосуванням нового поняття - факторіал, і дізнаємося про нове прислів'я про дружбу.
| 7!+ | 8! – (13 - 5) 2 | 6! – 5! | ||
Картки з відповідями виконують із запасом (є картки з числами, що не є відповідями).
Таблиця після заповнення:
| 7!+ | 8! – (13 - 5) 2 | 6! – 5! | ||
| 5048 | 40256 | 600 | 24 | 7 |
| Ні | друга - | шукай, | а знайшов - | береги |
Завдання 6.
До Васі в гості прийшли 4 друзі, і вони збираються дивитися новий фільм. У Васі в кімнаті є крісло і ще він приніс 4 стільці з кухні. Крісло він, поза сумнівом, займе сам, а на стільцях розсадить своїх друзів. Вася підрахував, що розсадити друзів він зможе 24 способами.
Вчитель: Чи правильно розрахував Вася? (Так, з погляду математики)
Чи добре він вчинив? (обговорюється моральний аспект проблеми)
4. Фізкультурна хвилина.
Вчитель: А тепер давайте трохи відпочинемо, а для цього проведемо фізкультурну хвилину. Якщо я правильно прочитаю вираз, то ви встаєте і піднімаєте руки нагору, а якщо неправильно – сідайте, руки в бік.
Встали. Починаємо, будьте уважні.
| Вираз | Слова вчителя | Правильно / неправильно |
| 5! +3 | Сума 5! та 3 | + |
| 2 – 7! | Твір 2 та 7! | - |
| 4х: 2! | Приватне 4х та 2! | + |
| 5! + 7! + 3! | Сума 5!, 7! та 3! | + |
| 20! - 19! | Приватне 20! та 19! | - |
6. Самостійна робота.
Вчитель: Ну, а тепер, коли ми добре відпочили, перевіримо, що ми навчилися робити сьогодні на уроці. Для цього виконаємо самостійну роботу.
| Варіант 1 | Варіант 2 |
| 1. У 5 класі в середу 5 уроків: математика, російська мова, література, музика та праця. Скільки варіантів розкладу на день можна скласти? | 1. Шість різних листів розкладають у 6 різних конвертів. Скільки існує способів такого розкладання? |
| 2. Обчисліть: а) 6! - 2; б) 4! + (2+3) 2 |
2. Обчисліть: а) 3 2+5! б) (9-4) 2+4! |
| 3. Скільки способами 5 хлопчиків можуть зайняти чергу до квиткової каси, якщо першим все одно буде Толя? | 3. Скільки способами Даша може з'їсти обід, що складається з першого, другого, третього та тістечка, якщо першим вона напевно з'їсть тістечко? |
7. Домашнє завдання.
Придумати, записати умови та рішення 2 комбінаторних завдань на тему “Сім'я”. Оформити на листах А4, можна виконати малюнки до завдань.
8. Підсумок уроку.
Давайте підіб'ємо підсумки уроку.
Що нового дізналися? (Отримали правило множення, розглянули його геометричну модель – дерево варіантів, запровадили нове поняття – факторіал)
Що сподобалось?
Що запам'яталося?
Оцінки за урок.
Література:
- Є.А.Бунімович, В.А. Буличів. Імовірність та статистика в курсі математики загальноосвітньої школи: лекції 1-4, 5 - 8. - М.: Педагогічний університет "Перше вересня", 2006.
- Віленкін Н.Я. Математика. 5 клас: підручник для загальноосвіт. установ / Н.Я.Віленкін та ін - М.: Мнемозіна, 2009.
- Смикалова Є.В. Додаткові розділи математики для учнів 5 класу. СПб: ЗМІ. Прес, 2006.
- Мордкович О.Г. Події Можливості. Статистична обробка даних: Дод. Параграфи до курсу алгебри 7-9 кл. загальноосвітніх закладів/А.Г. Мордкович, П.В. Семенів. - М.: Мнемозіна, 2006.
План:
1. Елементи комбінаторики.
2. Загальні правила комбінаторики.
4. Застосування графів (схем) під час вирішення комбінаторних завдань.
1. Комбінаторика та її виникнення.Комбінаторика- це область математики, у якій вивчаються питання, скільки різних комбінацій, підпорядкованих тим чи іншим умовам, можна скласти з елементів, що належать даному безлічі.
Комбінаторика виникла XVI столітті. У житті привілейованих верств тогочасного суспільства велике місце займали азартні ігри (мапи, кістки). Широко поширені лотереї. Спочатку комбінаторні завдання стосувалися в основному азартних ігор: скількома способами можна отримати це число очок, кидаючи 2 або 3 кістки або скількома способами можна отримати двох королів у деякій картковій грі. Ці та інші проблеми азартних ігор були рушійною силою у розвитку комбінаторики і далі у розвитку теорії ймовірностей.
Одним із перших зайнявся підрахунком кількості різних комбінацій при грі в кістки італійський математик Тарталья. Він склав таблиці (кілька способів випадання k очок на r кістках). Однак, він не врахував, та сама сума очок може випасти різними способами, тому його таблиці містили велику кількість помилок.
Теоретичне дослідження питань комбінаторики зробили у XVII столітті французькі математики Блез Паскаль та Ферма. Вихідним пунктом їх досліджень були проблеми азартних ігор.
Подальший розвиток комбінаторики пов'язані з іменами Я. Бернуллі, Р. Лейбніца, Л. Ейлера. Проте, й у роботах основну роль грали докладання до різних ігор.
Сьогодні комбінаторні методи використовуються на вирішення транспортних завдань, зокрема завдань зі складання розкладів, упорядкування планів виробництва та реалізації продукції тощо.
2. Загальні правила комбінаторики.Правило суми:Якщо деякий об'єкт А може бути обраний m способами, а об'єкт-k способами, то об'єкт «або А, або В» можна вибрати m +k способами.
Приклади:
1. Допустимо, що в ящику знаходиться n різнокольорових кульок. Довільним чином виймається 1 кулька. Скільки способами це можна зробити?
Відповідь: n методами.
Розподілимо ці n кульок по двох ящиках: у першу-m кульок, у другій-k кульок. Довільним чином із довільно обраного ящика виймається 1 кулька. Скільки способами це можна зробити?
Рішення: З першого ящика кульку можна вийняти m способами, з другого-k способами. Тоді всього методів m+k=n .
2. Морський семафор.У морському семафорі кожній літері алфавіту відповідає певне положення щодо тіла сигнальника двох прапорців. Скільки таких сигналів може бути?
Рішення: Загальна кількість складається з положень, коли обидва прапорці розташовані по різні боки від тіла сигнальника та положень, коли вони розташовані по одну сторону від тіла сигнальника. При підрахунку числа можливих положень застосовується правило суми.
Правило твору:Якщо об'єкт А можна вибрати m способами, а після кожного такого вибору інший об'єкт можна вибрати (незалежно від вибору об'єкта А) k способами, то пари об'єктів «А і В» можна вибрати m *k способами.
Приклади:
1. Скільки двоцифрових чисел існує?Рішення: Число десятків може бути позначено будь-якою цифрою від 1 до 9. Число одиниць може бути позначено будь-якою цифрою від 0 до 9. Якщо число десятків дорівнює 1, то число одиниць може бути будь-яким (від 0 до 9). Таким чином, існує 10 двоцифрових чисел, з числом десятків-1. Аналогічно міркуємо і для будь-якого іншого числа десятків. Тоді можна порахувати, що існує 9 *10 = 90 двоцифрових чисел.
2. Є 2 ящики. В одному лежить m різнокольорових кубиків, а в іншому-k різнокольорових кульок. Скільки способами можна вибрати пару «Кубик-кулька»?
Рішення: Вибір кульки залежить від вибору кубика, і навпаки. Тому число способів, якими можна вибрати цю пару дорівнює m * k .
3. Генеральна сукупність без повторень та вибірки без повторень.Генеральна сукупність без повторень- Це набір деякого кінцевого числа різних елементів a 1, a 2, a 3, ..., a n.
Приклад:Набір з n різнокольорових клаптиків.
Вибіркою обсягуk (kn)називається група з m елементів цієї генеральної сукупності.
Приклад:Строката стрічка, зшита з m різнокольорових клаптиків, вибраних з даних n .
Розміщеннями зn елементів поkназиваються такі вибірки, які містять по k елементів, вибраних з даних n елементів генеральної сукупності без повторень, і відрізняються друг від друга або складом елементів, або порядком їх розташування.
- кількість розміщень з n по k.
Кількість розміщень з n по k можна визначити в такий спосіб: перший об'єкт вибірки можна вибрати n способами, далі другий об'єкт можна вибрати n -1 способом і т.д.
Перетворивши цю формулу, маємо:
Слід пам'ятати, що 0!=1.
Приклади:
1. У першій групі класу А першості з футболу беруть участь 17 команд. Розігруються медалі: золото, срібло та бронза. Скільки способами вони можуть бути розіграні?
Рішення:Комбінації команд-переможців відрізняються друг від друга складом і порядком прямування елементів, тобто. є розміщеннями з 17 до 3.
2. Наукове суспільство складається з 25 осіб. Необхідно обрати президента товариства, віце-президента, вченого секретаря та скарбника. Скільки способами це можна зробити?
Рішення:Комбінації керівного складу товариства відрізняються один від одного складом і порядком прямування елементів, тобто. є розміщеннями з 25 до 4.
Перестановками без повторень з nелементівназиваються розміщення без повторень з n елементів з n , тобто. Розміщення відрізняються один від одного лише порядком прямування елементів.
Число перестановок.
Приклади:
1. Скільки різних п'ятизначних чисел можна становити із цифр 1, 2, 3, 4, 5 за умови, що вони мають складатися з різних цифр?
Рішення:Маємо перестановки із 5 елементів.2. Скількими способами можна зібрати 6 різнокольорових клаптиків у строкату стрічку?Рішення:Маємо перестановки із 6 елементів.
Поєднаннями без повторень з nелементів поkназиваються такі вибірки, які містять по k елементів, вибраних з даних n елементів генеральної сукупності без повторень, і відрізняються друг від друга лише складом елементів.
- число поєднань з n по k
Елементи кожного зпоєднань можна розставитиметодами. ТодіПриклади:1. Якщо у півфіналі першості з шахів бере участь 20 осіб, а у фінал виходять лише троє, то скільки способів і можна визначити цю трійку?
Рішення:У разі порядок, у якому розташовується ця трійка, не суттєвий. Тому трійки, що вийшли у фінал, є поєднаннями із 20 по 3.
2. Скільки способів можна обрати трьох делегатів із десяти осіб на конференцію?Рішення:У разі порядок, у якому розташовується ця трійка, не суттєвий. Тому трійки делегатів є поєднаннями з 10 до 3.
Конспект:
4. Застосування графів (схем) під час вирішення комбінаторних завдань.
У разі коли кількість можливих виборів на кожному кроці залежить від того, які елементи були обрані раніше, можна зобразити процес складання комбінацій у вигляді «дерева». Спочатку з однієї точки проводять стільки відрізків, скільки різних виборів можна зробити на першому кроці. З кінця кожного відрізка проводять стільки відрізків, скільки можна зробити виборів на другому кроці, якщо на першому кроці було обрано цей елемент і т.д.
Завдання:
При складанні команд космічного корабля враховується питання психологічної сумісності учасників подорожі. Необхідно скласти команду космічного корабля з трьох осіб: командира, інженера та лікаря. На місце командира є 4 кандидати: a 1 , a 2 , a 3 , a 4 .На місце інженера-3:b 1 , b 2 , b 3 . На місце лікаря-3: c1, c2, c3. Проведена перевірка показала, що командирa 1 психологічно сумісний з інженерами b 1 та b 3та лікарями c 1 та c 3 . Командир a 2 – з інженерами b 1 та b 2 . та всіма лікарями. Командирa 3 – з інженерамиb 1 та b 2та лікарямиз 1 і з 3. Командир a 4 - з усіма інженерами та лікарем з 2 . Крім того, інженерb 1 не сумісний із лікарем c 3, b 2 - з лікарем з 1 і b 3 - з лікарем c 2 . Скільки способами за цих умов може бути складена команда корабля?
Рішення:
Складемо відповідне «дерево».
Відповідь: 10 комбінацій.
Таке дерево є графом і застосовується на вирішення комбінаторних завдань.
Комбінаторика – розділ математики. Основні поняття та формули комбінаторики як науки застосовуються у всіх сферах життя.
Не дивно, що вона включена в програму 11 класу, а також вступні випробування в багатьох ВНЗ РФ. Її основи лежать у прикладному мистецтві багатьох сфер діяльності.
Її історія налічує понад 6 століть. Перші комбінаторні завдання з'явилися у працях філософів та математиків Середньовіччя.
Представники того наукового світу намагалися знайти методи вирішення таких завдань, їхні базові правила та поняття, затвердити унікальні формули та рівняння для тих, хто ще не зустрічався з ними. Така інформація нині називається інформацією «для чайників».
Спробуємо розібратися в аспектах цієї галузі науки: які елементи, властивості, правила, методи та основне її застосування у нашому житті? Звісно, всю область у статті неможливо охопити. Тому нижче буде представлено найголовніше.
Що таке комбінаторика в математиці
Суть цього терміну дають книги минулих років: це розділ математики, що займається операціями з багатьма елементами.
В інтернеті є підручники з інформатики та математики для дітей, школярів, збірники матеріалів та завдань для початківців, де у доступному вигляді пояснена «цікава» комбінаторика. Потрібно твердо з'ясувати, як вирішувати такі завдання.
У молодших класах завдання з цієї теми вирішують на додаткових гуртках, а школах з поглибленим вивченням математики — на основних уроках. До того ж, завдання комбінаторики включені в олімпіади всіх рівнів.
Основні поняття
Їх декілька:
- Елемент- будь-який об'єкт або явище, що входить до безлічі, що шукається.
- Поєднання– підмножини, що у довільному порядку у вихідному множині.
- Перестановка- Елементи в безлічі знаходяться в строго визначеному порядку.
- Розміщення– упорядковані підмножини у вихідній множині.
Правило твору
Є одним з основних правил під час вирішення таких завдань і звучить так:
При виборі елемента Аnспособів і виборі елементаmспособів вірно твердження, що вибрати пару А та В одночасно можнаn* mметодами.
Розглянемо конкретні приклади.
Завдання №1.
У коробці лежить 2 м'ячі та 6 скакалок. Скільки існує способів дістати 1 м'яч та 1 скакалку?
Відповідь проста: 2 * 6 = 12.
Завдання №2.
Є 1 кубик, 2 кульки, 3 квітки та 4 цукерки. Скільки способами можна витягнути кубик, кульку, квітку і цукерку?
Рішення аналогічне: 1*2*3*4 = 24.
Причому ліву частину можна записати набагато простіше: 4!
! в даному випадку є не розділовим знаком, а факторіалом.За допомогою нього можна вирахувати складніші варіанти і вирішувати важкі завдання (існують різні формули, але про це пізніше).
Завдання №3.
Скільки двоцифрових чисел можна становити з 2 цифр?
Відповідь: 2! = 2.
Завдання №4.
Скільки десятицифрових чисел можна становити з 10 цифр?
Правило суми
Також є базовим правилом комбінаторики.
Якщо А можна вибратиnраз, а В -mраз, то А або В можна вибрати (n+ m) раз.
Завдання №5.
У коробці лежать 5 червоних, 3 жовті, 7 зелені, 9 чорних олівців. Скільки є способів витягти 1 будь-який олівець?
Відповідь: 5+3+7+9=24.
Поєднання з повтореннями та без повторень
Під цим терміном розуміють комбінації у довільному порядку з множини n по m елементів.
Число поєднань дорівнює кількості таких комбінацій.
Завдання №6.
У коробці знаходиться 4 різні фрукти. Скільки способами можна дістати одночасно 2 різних фрукти?
Рішення просте:
Де 4! - Комбінація з 4 елементів.
З повтореннямитрохи складніше, комбінації вважаються за такою формулою:
Завдання №7.
Візьмемо той самий випадок, але за умови, що один фрукт повертається в коробку.
В цьому випадку:
Розміщення з повтореннями та без повторень
Під цим визначенням розуміють набір m елементів із множини n елементів.
Завдання №8.
З 3 цифр треба вибрати 2, щоб виходили різні двоцифрові числа. Скільки варіантів?
Відповідь проста:
А як же бути із повтореннями?Тут кожен елемент може розміщуватись кілька разів! У такому разі загальна формула буде виглядати так:
Завдання №9.
З 12 літер латинського алфавіту та 10 цифр натурального ряду треба знайти всі варіанти складання автомобільного коду регіону.
Перестановки з повтореннями та без повторень
Під цим терміном розуміють усі можливі комбінації з n елементної множини.
Завдання №10.
Скільки можливих п'ятизначних чисел можна становити з 5цифр? А шестизначних із 6 цифр? Семизначних із 7 цифр?
Рішення, згідно з наведеною вище формулою, наступні:
А як же бути із повтореннями?Якщо в такій множині є однакові за своєю значимістю елементи, то перестановок буде менше!
Завдання №11.
У коробці є 3 однакові олівці та одна ручка. Скільки перестановок можна зробити?
Відповідь проста: 4! /(3!*1!) = 4.
Комбінаторні завдання із рішеннями
Приклади всіх можливих типів завдань із рішеннями були дані вище. Тут спробуємо розібратися з складнішими випадками, що зустрічаються у нашому житті.
| Типи завдань | Що потрібно знайти | Методи вирішення |
| Магічний квадрат | Фігура, в якій сума чисел у рядах і стовпцях має бути однаковою (його різновид – латинський квадрат). | Рекурентні співвідношення. Вирішується подібне завдання, але з набагато меншою безліччю елементів за відомими правилами і формулами. |
| Завдання розміщення | Стандартне виробниче завдання (наприклад, у клаптевій техніці) — знайти можливі способи розкладання кількості продуктів у комірки у певному порядку. | Увімкнення та виключення. Як правило, застосовується за доказом різних виразів. |
| Завдання про торговців | Суть - знайти всі можливі шляхи проходження людей з пункту А до пункту В. | Траєкторії. Для цього виду задач характерна геометрична побудова можливих способів розв'язання. |
Висновок
Варто вивчати цю науку, оскільки у вік швидкої модернізації технологій будуть потрібні фахівці, здатні надати різні рішення тих чи інших практичних завдань.
Реферат на тему:
Виконав учень 10 класу "В"
середньої школи №53
Глухів Михайло Олександрович
м. Набережні Човни
2002 р.
Зміст
| З історії комбінаторики_________________________________________ | 3 |
| Правило суми___________________________________________________ | 4 |
| - | |
| Правило твору_____________________________________________ | 4 |
| Приклади задач____________________________________________________ | - |
| Пересічні множини________________________________________ | 5 |
| Приклади задач____________________________________________________ | - |
| Кола Ейлера_____________________________________________________ | - |
| Розміщення без повторень________________________________________ | 6 |
| Приклади задач____________________________________________________ | - |
| Перестановки без повторень_______________________________________ | 7 |
| Приклади задач____________________________________________________ | - |
| Поєднання без повторень__________________________________________ | 8 |
| Приклади задач____________________________________________________ | - |
| Розміщення та поєднання без повторень______________________________ | 9 |
| Приклади задач____________________________________________________ | - |
| Перестановки із повтореннями_______________________________________ | 9 |
| Приклади задач____________________________________________________ | - |
| Завдання для самостійного вирішення________________________________ | 10 |
| Список використаної літератури___________________________________ | 11 |
З історії комбінаторики
Комбінаторика займається різного виду сполуками, які можна утворити з елементів кінцевої множини. Деякі елементи комбінаторики були відомі в Індії ще у ІІ. до зв. е. Нідійці вміли обчислювати числа, що зараз називають "поєднання". У ХІІ ст. Бхаскара обчислював деякі види поєднань та перестановок. Припускають, що індійські вчені вивчали з'єднання у зв'язку із застосуванням їх у поетиці, науці про структуру вірша та поетичні твори. Наприклад, у зв'язку з підрахунком можливих поєднань ударних (довгих) і ненаголошених (коротких) складів стопи з n складів. Як наукова дисципліна, комбінаторика сформувалася у XVII ст. У книзі "Теорія і практика арифметики" (1656) французький автор А. Також присвячує поєднанням і перестановкам цілий розділ.
Б. Паскаль у "Трактаті про арифметичний трикутник" і в "Трактаті про числові порядки" (1665 р.) виклав вчення про біноміальні коефіцієнти. П. Ферма знав зв'язки математичних квадратів і фігурних чисел з теорією з'єднань. Термін "комбінаторика" став вживатися після опублікування Лейбніцем в 1665 р. роботи "Міркування про комбінаторне мистецтво", в якій вперше дано наукове обґрунтування теорії поєднань та перестановок. Вивченням розміщень вперше займався Я. Бернуллі у другій частині своєї книги "Ars conjectandi" (мистецтво передбачання) у 1713 р. Сучасна символіка поєднань була запропонована різними авторами навчальних посібників лише у ХІХ ст.
Вся різноманітність комбінаторних формул може бути виведена з двох основних тверджень, що стосуються кінцевих множин – правило суми та правило твору.
Правило суми
Якщо кінцеві множини не перетинаються, число елементів X U Y (або) дорівнює сумі числа елементів множини X і числа елементів множини Y.
Тобто якщо на першій полиці стоїть X книг, а на другій Y, то вибрати книгу з першої або другої полиці, можна X+Y способами.
Приклади завдань
Учень має виконати практичну роботу з математики. Йому запропонували на вибір 17 тем з алгебри та 13 тем з геометрії. Скільки способів може вибрати одну тему для практичної роботи?
Рішення: X = 17, Y = 13
За правилом суми X U Y = 17 +13 = 30 тем.
Є 5 квитків грошово-речової лотереї, 6 квитків спортлото та 10 квитків автомотолотереї. Скільки способами можна вибрати один квиток зі спортлото або автомотолотереї?
Рішення: Оскільки грошово-речова лотерея у виборі не бере участі, то лише 6+10=16 варіантів.
Правило твору
Якщо елемент X можна вибрати k способами, а елемент Y-m способами, то пару (X,Y) можна вибрати k*m способами.
Тобто, якщо на першій полиці стоїть 5 книг, а на другій 10, то вибрати одну книгу з першої полиці та одну з другої можна 5*10=50 способами.
Приклади завдань
Палітурник повинен переплести 12 різних книг в червоний, зелений і коричневі плетіння. Скільки способами він може це зробити?
Рішення: Є 12 книг і 3 кольори, значить за правилом твору можливо 12 * 3 = 36 варіантів палітурки.
Скільки існує п'ятизначних чисел, які однаково читаються зліва направо та праворуч наліво?
Рішення: У таких числах остання цифра буде така сама, як і перша, а передостання - як і друга. Третя цифра буде будь-якою. Це можна уявити у вигляді XYZYX, де Y і Z - будь-які цифри, а X - не нуль. Значить за правилом добутку кількість цифр, що однаково читаються як зліва направо, так і справа наліво дорівнює 9*10*10=900 варіантів.
Пересічні множини
Але буває, що множини X і Y перетинаються, тоді користуються формулою
, де X і Y - множини, а - область перетину. Приклади завдань20 чоловік знають англійську і 10 - німецьку, з них 5 знають англійську, і німецьку. Скільки Людина всього?
Відповідь: 10 +20-5 = 25 чоловік.
Також часто для наочного вирішення задачі використовуються кола Ейлера. Наприклад:
Зі 100 туристів, що вирушають у закордонну подорож, німецькою мовою володіють 30 осіб, англійською – 28, французькою – 42. Англійською та німецькою одночасно володіють 8 осіб, англійською та французькою – 10, німецькою та французькою – 5, усіма трьома мовами – 3. туристів не володіють жодною мовою?Рішення:Висловимо умову цього завдання графічно. Позначимо колом тих, хто знає англійську, іншим колом – тих, хто знає французьку, і третім колом – тих, хто знає німецьку.
Всіми трьома мовами володіють три туристи, отже, у загальній частині кіл вписуємо число 3. Англійською та французькою мовами володіють 10 осіб, а 3 з них володіють ще й німецькою. Отже, лише англійською та французькою володіють 10-3=7 осіб.Аналогічно отримуємо, що тільки англійською та німецькою володіють 8-3=5 осіб, а німецькою та французькою 5-3=2 туристи. Вносимо ці дані до відповідних частин.
Визначимо тепер, скільки людей володіють лише однією з перелічених мов. Німецьку знають 30 осіб, але 5+3+2=10 з них володіють й іншими мовами, отже, лише німецьку знають 20 осіб. Аналогічно отримуємо, що однією англійською володіють 13 осіб, а однією французькою – 30 осіб.За умовою завдання лише 100 туристів. 20+13+30+5+7+2+3=80 туристів знають хоча б одну мову, отже, 20 людей не володіють жодною мовою.
Розміщення без повторень.
Скільки можна скласти телефонних номерів з 6 цифр кожен, щоб всі цифри були різні?
Це приклад завдання розміщення без повторень. Розміщуються тут 10 цифр по 6. А варіанти, за яких однакові цифри стоять у різному порядку, вважаються різними.
Якщо X-множина, що складаються з n елементів, m≤n, то розміщенням без повторень з n елементів множини X по m називається впорядкована множина X, що містить m елементів, називається впорядкована множина X, що містить m елементів.
Кількість всіх розміщень з n елементів m позначають
n! - n-факторіал (factorial анг. співмножник) добуток чисел натурального ряду від 1 до якого чи числа n Завдання
Скільки способами 4 юнаки можуть запросити чотирьох із шести дівчат на танець?
Рішення: два юнаки не можуть одночасно запросити одну й ту саму дівчину І варіанти, при яких одні й ті ж дівчата танцюють з різними юнаками, вважаються, різними, тому:
Можливо 360 варіантів.
Перестановки без повторень
У разі n=m (див. розміщення без повторень) з n елементів m називається перестановкою множини x.
Кількість всіх перестановок n елементів позначають P n.
Дійсно при n=m:
Приклади завдань
Скільки різних шестицифрових чисел можна скласти з цифр 0, 1, 2, 3, 4,5, якщо цифри в числі не повторюються?
1) Знайдемо кількість всіх перестановок із цих цифр: P 6 =6!=720
2) 0 не може стояти попереду числа, тому від цього числа необхідно відібрати кількість перестановок, при якому 0 стоїть попереду. І це P 5 =5!=120.
P 6 -P 5 = 720-120 = 600
Проказниця Мавпа
Так клишоногий Ведмедик
Затіяли грати квартет
Стій, брати стій! -
Кричить Мавпа, - зачекайте!
Як йти музиці?
Адже ви не так сидите.
І так, і так пересідали - знову музика на лад не йде.