|
|
МОДЕЛІ КОМБІНАТОРНИХ КОНФІГУРАЦІЙ
1.1 Мета заняття
Ознайомлення на практичних прикладах з основними поняттями комбінаторного аналізу. Вивчення основних правил розв’язання задач комбінаторики (правила суми і правила добутку). Вивчення і використання моделей комбінаторних конфігурацій (сполучення, розміщення, перестановка, композиція числа, розбиття числа). Вивчення поліноміальної формули, бінома Ньютона та їх використання. Аналіз властивостей біноміальних коефіцієнтів. Ознайомлення з комбінаторним принципом включення і виключення, використання формули включень та виключень. Ознайомлення з комбінаторними задачами, які пов’язані з теорією чисел (решето Ератосфена).
1.2 Методичні вказівки з організації самостійної роботи студентів
Під час підготовки до практичного заняття необхідно повторити лекційний матеріал, розділи літератури [1–12] з таких питань: комбінаторні задачі (задачі на перелік, задачі про існування та побудову, задачі про вибір); основні правила розв’язання задач комбінаторики (правило суми и правило добутку); приклади використання правила суми и правила добутку при розв’язанні комбінаторних задач; складний вибір предметів; перелік і визначення типових (елементарних) комбінаторних конфігурацій (перестановки, розміщення, сполучення, композиції; розбиття); властивості біноміальних коефіцієнтів (властивість симетрії, властивості додавання, властивості винесення за дужки); арифметичний трикутник (трикутник Паскаля) та правила його побудови; біноміальна формула (біном Ньютона) та її використання; поліноміальна формула та її використання; комбінаторний принцип включення і виключення (підрахування кількості предметів, позбавлених усіх без винятку властивостей); приклади використання формули включень і виключень; частковий випадок теореми включення і виключення; формула «повного безладдя» (субфакторіал), комбінаторні задачі та теорія чисел (решето Ератосфена). Підготовка і виконання практичного заняття проводиться у два етапи. Перший етап пов’язаний з вивченням на практичних прикладах таких основних понять і визначень комбінаторного аналізу: r-вибірка; правило суми; Виконуючи перший етап студент має запропонувати і записати індивідуальний приклад для кожного з розглянутих вище понять і визначень. Другий етап виконання практичного заняття пов’язаний з вирішенням практичних завдань, поданих у підрозділі 1.3, на основі запропонованих типових прикладів (див. підрозділ 1.4).
1.3 Контрольні запитання і завдання
1.3.1 Контрольні запитання 1. Дайте визначення комбінаториці. 2. Поясніть, що є задачами на перелік. 3. Які задачі є задачами про існування та побудову? 4. Поясніть, що є задачами про вибір. 5. Поясніть зв’язок астрології і комбінаторики. 6. Поясніть появу «задачі про кроликів». Як її розв’язував Леонардо Пізанський (Фібоначчі)? 7. Поясніть на прикладах комбінаторний зміст деяких задач генетики 8. Що є r-вибіркою? 9. Сформулюйте правило суми для комбінаторних задач. Поясніть на прикладі використання правила суми. 10. Сформулюйте правило добутку для комбінаторних задач. Яка формула використовується у правилі добутку? 11. Дайте визначення перестановці k -елементів. 12. Дайте визначення розміщенню з n по k елементів. 13. Що є розміщенням з повтореннями з n по k елементів? За якою формулою обчислюється кількість k -розміщень з повтореннями з n по 14. За якою формулою обчислюється кількість k -сполучень з n елементів по k елементів з повтореннями і без повторень? 15. Дайте визначення композиції числа. 16. За якою формулою визначається кількість усіх варіантів розбиття числа n на k частин? 17. Дайте визначення трикутнику Паскаля й поясніть принцип його побудови. 18. Які існують властивості трикутників Паскаля? 19. Що таке сполучення і біноміальні коефіцієнти? 20. У чому полягають властивості симетрії для біноміальних коефіцієнтів? 21. У чому полягають властивості додавання для біноміальних коефіцієнтів? 22. У чому полягають властивості винесення за дужки для біноміальних коефіцієнтів? 23. Наведіть формулу, яка називається «біном Ньютона». 24. Наведіть формулу, яка називається поліноміальною формулою. 25. Дайте загальну постановку задачі, для розв’язання якої використовують принцип включення і виключення. 26. Запишіть загальну формулу включень та виключень. 27. Наведіть приклади застосування принципу включення і виключення при розв’язанні комбінаторних задач. 28. У яких випадках використовується формула «повного безладдя» (субфакторіал)? 29. Поясніть розв’язання задачі розміщення простих чисел у натуральному ряді за допомогою використання решета Ератосфена.
1.3.2 Контрольні завдання Завдання 1. На денне чергування в студентському гуртожитку може піти або студент з кімнати 1, де проживають три студенти, або студент з кімнати 2, де проживають чотири студенти. Скількома способами можна вибрати одного студента на денне чергування в гуртожитку? Завдання 2. На денне чергування в студентському гуртожитку вибирається два студенти – один студент із трьох, що проживають у кімнаті 1, і один студент із чотирьох, що проживають у кімнаті 2. Скільки існує можливих способів формування різних пар із двох студентів для чергування в гуртожитку? Завдання 3. З 12 слів чоловічого роду 9 слів жіночого роду і 10 слів середнього роду. Треба відібрати по одному слову кожного роду. Скількома способами можна здійснити цей вибір? Завдання 4. Комутатор має Завдання 5. Телефонна мережа має Завдання 6. У магазині є 5 сортів цукерок у коробках і 4 сорти тортів. Якою кількістю способів можна купити коробку цукерок чи торт? Якою кількістю способів можна купити і те й інше? Завдання 7. Зі спортивного клубу, що нараховує 30 членів, треба вибрати 4 гімнастки для участі в особистих змаганнях з естетичної гімнастики Скількома способами це можна зробити? Завдання 8. Скільки трикнопочних комбінацій існує на кодовому замку (усі три кнопки натискаються одночасно), якщо на ньому всього 10 цифр? Завдання 9. У футбольному чемпіонаті беруть участь 17 команд. За умови, що 3 останні команди залишають вищу лігу, скільки варіантів такого завершення чемпіонату? Завдання 10. Скільки членів було в клубі, якщо при нумерації членських білетів використовувалися усі тризначні номери, в яких не було жодної цифри 8? Завдання 11. Скількома способами 7 книг різних авторів можна розставити на книжковій полці в один ряд? Завдання 12. Студенти вивчають 14 предметів. Скільки існує способів, якими можна скласти розклад занять на суботу, якщо в цей день має бути 5 різних занять? Завдання 13. Розглянемо множину Завдання 14. У поштовому відділенні продаються листівки 10 видів. Скількома способами можна купити в ньому 12 листівок? Скількома способами можна купити в ньому 8 листівок? Скількома способами можна купити в ньому 8 різних листівок? Завдання 15. На пошті є 5 видів листівок і 8 видів марок. Якою кількістю способів можна купити 12 листівок і 12 марок? Завдання 16. Скількома способами можна призначити на чергування з охорони суспільного порядку групу з п’яти студентів і одного викладача, якщо маємо 15 студентів і 4 викладачі? Завдання 17. Визначити коефіцієнт при Завдання 18. Знайти розклад виразу Завдання 19. Обчислити за допомогою бінома Ньютона вираз Завдання 20. Знайти розкладання за поліноміальною формулою Завдання 21. Записати формулу включень і виключень для випадку, коли число ознак, які нас цікавлять, дорівнює п’яти. Завдання 22. Скільки існує цілих чисел від 0 до 9999, що не поділяються ні на 3, ні на 4, ні на 5. Завдання 23. Знайти кількість цілих додатних чисел, які не перевищують 200 і не діляться на кожне з простих чисел: а) 2, 3, 5; б) 7, 11, 13. Завдання 24. Під час підведення підсумків сесії виявилося, що склали на «добре» і «відмінно» фізику – 60% студентів, вищу математику – 50%, дискретну математику – 50%, фізику і вищу математику – 30%, фізику і дискретну математику – 30%, вищу математику і дискретну математику – 20%, усі три предмети – 10%. Скільки студентів склали на «добре» і «відмінно» точно два предмети? Скільки відсотків студентів одержали оцінки нижче «добре» з усіх трьох предметів?
1.4 Приклади аудиторних і домашніх завдань
Завдання 1. З міста А в місто В відправляється 10 потягів, 5 літаків і Розв’язок. За правилом суми всього існує 10+5+3=18 способів. Завдання 2. На танцювальному майданчику є 17 юнаків і 21 дівчина. Скільки танцювальних пар вони можуть скласти? Розв’язок. Спочатку виберемо юнака. Це можна зробити 17 способами. Після цього кожний юнак вибере собі партнершу (21 спосіб). За правилом добутку вибір упорядкованої множини танцювальних пар (юнак, дівчина) становить Завдання 3. Скількома способами можна вибрати 3 різні фарби, якщо є п’ять різних фарб? Розв’язок. Порядок вибору фарб неважливий, тому кількість способів вибору можна обчислити за формулою Завдання 4. Нехай Розв’язок. 2-перестановками множини Їхня кількість дорівнює Завдання 5. Кілька людей сідають за круглий стіл. Вважатимемо, що два способи розміщення збігаються, якщо кожна людина має тих самих сусідів в обох випадках. Скількома різними способами можна розмістити за столом 11 осіб? Розв’язок. Якби місця за столом були нумеровані, то на перше місце можна було б посадити кожного з 11, тобто 11 способами, на друге місце – кожного з 10, що залишилися і т.д. Оскільки треба зайняти 11 місць і є 11 осіб, то за правилом добутку маємо (11!) способів. Але оскільки місця не нумеровані та при переміщенні усіх на одне місце за годинниковою стрілкою (чи проти її) сусідство зберігається, то кількість способів треба зменшити в 11 разів. Крім того, сусідство зберігається при симетричному відображенні щодо діаметра, отже, кількість треба зменшити ще вдвічі. Остаточна кількість способів розміщення виявляється рівною Завдання 6. У кімнаті студентського гуртожитку живуть троє студентів. У них є 4 чашки, 5 блюдець і 6 чайних ложок (усі чашки, блюдця і ложки відрізняються одне від одного). Скількома способами вони можуть накрити стіл для чаювання (кожний одержує одну чашку, одне блюдце й одну ложку)? Розв’язок. Чашки можна розставити Завдання 7. Рота складається з 3 офіцерів, 6 сержантів і 60 рядових. Скількома способами можна виділити з них загін, який складається з одного офіцера, двох сержантів і 20 рядових? Така ж задача, якщо в загін повинен увійти командир роти і старший з сержантів. Розв’язок. Офіцера можна вибрати Якщо в загін повинен увійти командир роти і старший із сержантів, то маємо Завдання 8. Розглянемо слово СТІЛ. Скільки слів із 4 букв можна скласти, якщо букви в словах повторюються? Розв’язок. Якщо можливі повторення букв, наприклад, СТТЛ, СІСЛ, ТТТТ та ін., тоді одержимо кількість слів Завдання 9. Розглянемо слово СТІЛ. Скільки слів із 3 букв можна скласти, якщо букви в словах повторюються? Розв’язок. Якщо можливі повторення букв, наприклад, СТТ, ССС, ІТІ, ЛЛТ та ін., тоді одержимо кількість слів Завдання 10. Скільки різних слів можна одержати, переставляючи літери слова «МАТЕМАТИКА»? Розв’язок. Слово «МАТЕМАТИКА» Різні слова з цих літер являють собою перестановки цих літер зі специфікацією Кількість таких перестановок дорівнює
Завдання 11. У кондитерській є тістечка 4 сортів. Якою кількістю способів можна купити 7 тістечок? Розв’язок. Порядок, у якому купуються тістечка, ролі не відіграє. Важливо лише, скільки тістечок кожного сорту в покупці. Тому покупку варто розглядати як сполучення з 4 по 7 з повтореннями. Кількість різних покупок дорівнює Завдання 12. Записати усі композиції числа 3. Розв’язок. Композиції мають вигляд 3=3, 3=2+1, 3=1+2, 3=1+1+1. Завдання 13. Обчислити за допомогою бінома Ньютона вираз Розв’язок. Використаємо загальну формулу бінома Ньютона
Завдання 14. Розкрити за поліноміальною формулою Розв’язок. Число доданків після розкриття дужок і приведення подібних дорівнюватиме
Завдання 15. Група студентів проходила практику в Німеччині та Франції. Половина студентів проходила практику у Франції. В обох країнах навчались 12 студентів, 39 студентів навчались у Німеччині. Скільки студентів в групі, якщо усі пройшли практику? Розв’язок. В цьому випадку є дві властивості (
де
Складемо рівняння: Завдання 16. Маємо деяку кількість куль, кожна з яких пофарбована одним, двома чи трьома кольорами: червоним, синім і жовтим. При цьому червоним пофарбовано 28 куль, синім – 23, жовтим – 23, червоним і синім – 12, синім і жовтим – 8, червоним і жовтим – 11, а всіма трьома – 5 куль. Скільки разом було пофарбовано куль? Розв’язок. Нехай Формула включення і виключення дає
Тоді Завдання 17. Задача про безладдя. Задано Розв’язок. Як початкову множину Використовуючи формулу включень і виключень, знаходимо, що кількість
Завдання 18. Скільки цілих додатних чисел у першій сотні не ділиться ні на одне із чисел 2, 3, 5? Розв’язок. Введемо наступні позначення для властивостей: За умови задачі:
Тоді число цілих чисел, яке не ділиться ні на одне із чисел 2, 3, 5, можна знайти, використовуючи формулу включень і виключень
  ЧТО ПРОИСХОДИТ, КОГДА МЫ ССОРИМСЯ Не понимая различий, существующих между мужчинами и женщинами, очень легко довести дело до ссоры...  ЧТО ПРОИСХОДИТ ВО ВЗРОСЛОЙ ЖИЗНИ? Если вы все еще «неправильно» связаны с матерью, вы избегаете отделения и независимого взрослого существования...  Что делать, если нет взаимности? А теперь спустимся с небес на землю. Приземлились? Продолжаем разговор...  Система охраняемых территорий в США Изучение особо охраняемых природных территорий(ООПТ) США представляет особый интерес по многим причинам... Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:
|
входів і 
виходів. Якою кількістю способів може бути обрана пара «вхід/вихід» для встановлення між ними з’єднання? Дві пари? К пар?
. Треба знайти число 
в розкладанні 
за біномом Ньютона.
на основі формули бінома Ньютона.
.
.
.
.
. Побудувати різні перестановки множини 
по 2 і по 3 елементи.
, 
, 
, 
, 
, 
. 3-перестановками множини 
, 
, 
, 
, 
, 
. Їхня кількість 
.
. У загальному випадку, коли за круглим столом треба розсадити 
.
способами, блюдця 
способами і чайні ложки 
способами. Усього за правилом добутку накрити стіл для чаювання можна 
способами.
способами, сержантів 
способами і рядових 
способами. Усього за правилом добутку маємо 
.
способів вибору.
.
.
містить 3 літери «А» 
, 2 літери «М» 
, 2 літери «Т»(
і по одній літері «Е» 
, «И» 
, «К» 
.
.
.
.
.
. Нехай 
, 
, 
. Тоді
.
.
.
,
.
– навчання в Німеччині, 
– навчання у Франції). Використовується загальна формула включення і виключення
,
– загальна кількість студентів, 
;
– кількість студентів, які проходили практику у Франції, 
; 
– кількість студентів, які проходили практику у Німеччині, 
; 
– кількість студентів, які проходили практику в обох країнах, 
;
– кількість студентів, які не проходили практику, 
.
. Розв’язавши його, отримаємо загальну кількість студентів, яка дорівнює 54.
– властивість кулі: у розфарбуванні кулі бере участь синій колір, 
– властивість кулі: у розфарбуванні кулі бере участь жовтий колір. Тоді умови задачі можна записати так: 
; 
; 
; 
; 
; 
; 
. 
тому, що всі кулі пофарбовані.
.
.
та 
. Скількома способами можна розмістити предмети по клітках так, щоб жоден предмет 
не потрапив у клітку 
?
візьмемо сукупність усіляких розміщень предметів по клітках. Тоді 
. Введемо властивості 
. Число 
розміщень, при якому предмет 
знаходиться в клітці 
, дорівнює 
. Однак тоді 
.
розміщень, при якому жодна з властивостей не виконується (тобто жоден із предметів 
не потрапив у клітку 
.
.
.