INFONKO.RU

МОДЕЛІ КОМБІНАТОРНИХ КОНФІГУРАЦІЙ

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 по
k елементів?

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.Розглянемо множину . Треба знайти число
2-сполучень із чотирьох елементів із необмеженими повтореннями.

Завдання 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 літаків і
3 автобуси. Скількома способами однієї людині можна дібратися з міста А
в місто В?

Розв’язок.За правилом суми всього існує 10+5+3=18 способів.

Завдання 2.На танцювальному майданчику є 17 юнаків і 21 дівчина. Скільки танцювальних пар вони можуть скласти?

Розв’язок.Спочатку виберемо юнака. Це можна зробити 17 способами. Після цього кожний юнак вибере собі партнершу (21 спосіб). За правилом добутку вибір упорядкованої множини танцювальних пар (юнак, дівчина) становить .


Завдання 3.Скількома способами можна вибрати 3 різні фарби, якщо є п’ять різних фарб?

Розв’язок.Порядок вибору фарб неважливий, тому кількість способів вибору можна обчислити за формулою .

Завдання 4. Нехай . Побудувати різні перестановки множини по 2 і по 3 елементи.

Розв’язок.2-перестановками множини є , , , , , . Їхня кількість . 3-перестановками множини є , , , , , . Їхня кількість .

Їхня кількість дорівнює .

Завдання 5. Кілька людей сідають за круглий стіл. Вважатимемо, що два способи розміщення збігаються, якщо кожна людина має тих самих сусідів в обох випадках. Скількома різними способами можна розмістити за столом 11 осіб?

Розв’язок.Якби місця за столом були нумеровані, то на перше місце можна було б посадити кожного з 11, тобто 11 способами, на друге місце – кожного з 10, що залишилися і т.д. Оскільки треба зайняти 11 місць і є 11 осіб, то за правилом добутку маємо (11!) способів. Але оскільки місця не нумеровані та при переміщенні усіх на одне місце за годинниковою стрілкою (чи проти її) сусідство зберігається, то кількість способів треба зменшити в 11 разів. Крім того, сусідство зберігається при симетричному відображенні щодо діаметра, отже, кількість треба зменшити ще вдвічі.

Остаточна кількість способів розміщення виявляється рівною . У загальному випадку, коли за круглим столом треба розсадити людин, кількість способів дорівнює .

Завдання 6. У кімнаті студентського гуртожитку живуть троє студентів. У них є 4 чашки, 5 блюдець і 6 чайних ложок (усі чашки, блюдця і ложки відрізняються одне від одного). Скількома способами вони можуть накрити стіл для чаювання (кожний одержує одну чашку, одне блюдце й одну ложку)?

Розв’язок.Чашки можна розставити способами, блюдця способами і чайні ложки способами. Усього за правилом добутку накрити стіл для чаювання можна способами.

Завдання 7. Рота складається з 3 офіцерів, 6 сержантів і 60 рядових. Скількома способами можна виділити з них загін, який складається з одного офіцера, двох сержантів і 20 рядових? Така ж задача, якщо в загін повинен увійти командир роти і старший з сержантів.

Розв’язок.Офіцера можна вибрати способами, сержантів способами і рядових способами. Усього за правилом добутку маємо .

Якщо в загін повинен увійти командир роти і старший із сержантів, то маємо способів вибору.

Завдання 8. Розглянемо слово СТІЛ. Скільки слів із 4 букв можна скласти, якщо букви в словах повторюються?

Розв’язок.Якщо можливі повторення букв, наприклад, СТТЛ, СІСЛ, ТТТТ та ін., тоді одержимо кількість слів .

Завдання 9. Розглянемо слово СТІЛ. Скільки слів із 3 букв можна скласти, якщо букви в словах повторюються?

Розв’язок.Якщо можливі повторення букв, наприклад, СТТ, ССС, ІТІ, ЛЛТ та ін., тоді одержимо кількість слів .

Завдання 10. Скільки різних слів можна одержати, переставляючи літери слова «МАТЕМАТИКА»?

Розв’язок.Слово «МАТЕМАТИКА» містить 3 літери «А» , 2 літери «М» , 2 літери «Т»( і по одній літері «Е» , «И» , «К» .

Різні слова з цих літер являють собою перестановки цих літер зі специфікацією .

Кількість таких перестановок дорівнює

.

Завдання 11. У кондитерській є тістечка 4 сортів. Якою кількістю способів можна купити 7 тістечок?

Розв’язок.Порядок, у якому купуються тістечка, ролі не відіграє. Важливо лише, скільки тістечок кожного сорту в покупці. Тому покупку варто розглядати як сполучення з 4 по 7 з повтореннями. Кількість різних покупок дорівнює .

Завдання 12.Записати усі композиції числа 3.

Розв’язок.Композиції мають вигляд 3=3, 3=2+1, 3=1+2, 3=1+1+1.

Завдання 13.Обчислити за допомогою бінома Ньютона вираз .

Розв’язок.Використаємо загальну формулу бінома Ньютона . Нехай , , . Тоді

.

.

Завдання 14.Розкрити за поліноміальною формулою .

Розв’язок.Число доданків після розкриття дужок і приведення подібних дорівнюватиме ,

.

Завдання 15.Група студентів проходила практику в Німеччині та Франції. Половина студентів проходила практику у Франції. В обох країнах навчались 12 студентів, 39 студентів навчались у Німеччині. Скільки студентів в групі, якщо усі пройшли практику?

Розв’язок. В цьому випадку є дві властивості ( – навчання в Німеччині, – навчання у Франції). Використовується загальна формула включення і виключення

,

де – загальна кількість студентів, ;

– кількість студентів, які проходили практику у Франції, ; – кількість студентів, які проходили практику у Німеччині, ; – кількість студентів, які проходили практику в обох країнах, ;

– кількість студентів, які не проходили практику, .

Складемо рівняння: . Розв’язавши його, отримаємо загальну кількість студентів, яка дорівнює 54.

Завдання 16.Маємо деяку кількість куль, кожна з яких пофарбована одним, двома чи трьома кольорами: червоним, синім і жовтим. При цьому червоним пофарбовано 28 куль, синім – 23, жовтим – 23, червоним і синім – 12, синім і жовтим – 8, червоним і жовтим – 11, а всіма трьома – 5 куль. Скільки разом було пофарбовано куль?

Розв’язок.Нехай – властивість кулі: у розфарбуванні кулі бере участь червоний колір, – властивість кулі: у розфарбуванні кулі бере участь синій колір, – властивість кулі: у розфарбуванні кулі бере участь жовтий колір. Тоді умови задачі можна записати так: ; ; ; ; ; ; . тому, що всі кулі пофарбовані.

Формула включення і виключення дає

.

Тоді .

Завдання 17. Задача про безладдя.

Задано різних предметів та різних кліток . Скількома способами можна розмістити предмети по клітках так, щоб жоден предмет не потрапив у клітку ?

Розв’язок.Як початкову множину візьмемо сукупність усіляких розміщень предметів по клітках. Тоді . Введемо властивості : « знаходиться в клітці », . Число розміщень, при якому предмет знаходиться в клітці , дорівнює . Однак тоді .

Використовуючи формулу включень і виключень, знаходимо, що кількість розміщень, при якому жодна з властивостей не виконується (тобто жоден із предметів не потрапив у клітку ), становить

.

Завдання 18. Скільки цілих додатних чисел у першій сотні не ділиться ні на одне із чисел 2, 3, 5?

Розв’язок.Введемо наступні позначення для властивостей: – число ділиться на 2; – число ділиться на 3; – число ділиться на 5.

За умови задачі:

.

Тоді число цілих чисел, яке не ділиться ні на одне із чисел 2, 3, 5, можна знайти, використовуючи формулу включень і виключень

.



infonko.ru/klassifikaciya-gosudarstvennih-organov.html infonko.ru/klassifikaciya-gosudarstvennih-vnutrennih-i-vneshnih-dolgov.html infonko.ru/klassifikaciya-grafikov-i-usloviya-ih-primeneniya.html infonko.ru/klassifikaciya-grupp-malaya-gruppa-i-ee-vidi.html infonko.ru/klassifikaciya-gruppovih-konfliktov-puti-razresheniya-konfliktov-mezhdu-lichnostyu-i-gruppoj.html infonko.ru/klassifikaciya-gruppovih-norm.html infonko.ru/klassifikaciya-harakteristika-assortimenta-identifikaciya-i-ekspertiza-neprodovolstvennih-tovarov-v-tamozhennih-celyah-na-primere-grupp-tovarov.html infonko.ru/klassifikaciya-himicheskih-soedinenij.html infonko.ru/klassifikaciya-hozyajstvennih-processov.html infonko.ru/klassifikaciya-hronicheskoj-bolezni-pochek.html infonko.ru/klassifikaciya-hronicheskoj-pochechnoj-nedostatochnosti.html infonko.ru/klassifikaciya-i-assortiment-kozhanoj-galanterei.html infonko.ru/klassifikaciya-i-assortiment-krup.html infonko.ru/klassifikaciya-i-assortiment-majoneza.html infonko.ru/klassifikaciya-i-assortiment-molochnih-produktov.html infonko.ru/klassifikaciya-i-funkcionirovanie-organizacij.html infonko.ru/klassifikaciya-i-harakteristicheskie-parametri-uchs.html infonko.ru/klassifikaciya-i-harakteristika-assortimenta-gazirovannoj-vodi-po-gost-ok-005-93-i-tn-ved.html infonko.ru/klassifikaciya-i-harakteristika-assortimenta-metallicheskoj-posudi.html infonko.ru/klassifikaciya-i-harakteristika-fizicheskih-uprazhnenij-primenyaemih-v-lfk.html