УРНОВІ СХЕМИ ВИРІШЕННЯ КОМБІНАТОРНИХ ЗАДАЧ

2.1 Мета заняття

Ознайомлення з методами аналізу змісту комбінаторних задач про розміщення (розподіл предметів за урнами). Ознайомлення на практичних прикладах з основними поняттями розподілу предметів за урнами. Вивчення основних способів розв’язання задач про розміщення.

2.2 Методичні вказівки з організації самостійної роботи студентів

Під час підготовки до практичного заняття необхідно повторити лекційний матеріал, розділи літератури [1–12] з таких питань: аналіз фізичних властивостей предметів під час розв’язання задач про розміщення (розподіл предметів за урнами); аналіз і опис змісту комбінаторних задач про розподіл предметів за урнами; розподіл n різних предметів за k урнами; розподіл n однакових предметів за k урнами; розподіл різних предметів без урахування порядку предметів в урнах; розподіл різних предметів між однаковими урнами за умови, що урни не порожні; розподіл різних предметів з урахуванням їх порядку в урнах.

Підготовка і виконання практичного заняття проводиться за два етапи. Перший етап пов’язаний із вивченням на практичних прикладах таких основних понять і визначень: поняття «урна» в комбінаторному аналізі; однакові чи різні предмети під час розв’язання задач про розміщення; однакові чи різні урни під час розв’язання задач про розміщення; кількість способів розподілу n різних предметів за k урнами; кількість способів розподілу
n однакових предметів за k урнами; кількість способів розподілу різних предметів без урахування порядку предметів в урнах; кількість способів розподілу різних предметів між однаковими урнами за умови, що урни непорожні; числа Моргана; числа Стирлінга другого роду; числа Белла; кількість способів розподілу різних предметів з урахуванням їх порядку в урнах.

Під час виконання першого етапу студент повинен запропонувати і записати загальну формулу для кожного з розглянутих вище понять і визначень.

Другий етап виконання практичного заняття пов’язаний із розв’язуванням практичних завдань, що надаються у підрозділі 2.3, на основі запропонованих типових прикладів (див. підрозділ 2.4).

2.3 Контрольні запитання і завдання

2.3.1 Контрольні запитання

1. Як проводиться аналіз змісту комбінаторних задач про розміщення предметів?

2. За якою формулою обчислюється кількість розміщень за k урнами n різних предметів?

3. За якою формулою обчислюється кількість розміщень за k урнами n однакових предметів?

4. Чи можна знайти кількість розподілів різних предметів без урахування порядку предметів в урнах, використовуючи формулу ?

5. У якому випадку для розв’язання задач про розподіл предметів за урнами використовуються числа Моргана, число Стирлінга другого роду, числа Белла?

6. За якою формулою обчислюється кількість розподілів різних предметів з урахуванням їх порядку в урнах?

2.3.2 Контрольні завдання

Завдання 1. Скількома способами можна розкласти 12 п’ятаків у 5 пакетів?

Завдання 2. Скількома способами можна розмістити 20 однакових куль у чотирьох різних урнах?

Завдання 3. Скількома способами групу з 25 осіб можна поділити на сім коаліцій: дві – по 5 осіб, одна – 7 осіб, чотири – по 2 особи?

Завдання 4. Треба відправити 6 листів. Скількома способами це можна зробити, якщо відправлення листів можна доручити трьом кур’єрам, і кожний лист можна дати будь-якому з кур’єрів.

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

Завдання 6. Скількома способами можна розмістити 20 різних куль у трьох різних урнах так, щоб у першій, другій і третій урнах знаходилося відповідно 5, 3 та 12 куль?

Завдання 7. Скількома способами можна розкласти 12 п’ятаків у 5 пакетів, якщо ніякий пакет не буде порожнім?

Завдання 8. Скільки існує способів розподілити (по черзі) 15 пацієнтів до трьох лікарів однієї спеціальності, якщо лікар повинен прийняти не менш
ніж 3 пацієнти?

Завдання 9. На складі є 40 однакових комп’ютерів і 10 однакових принтерів. Скільки існує способів розподілення їх за 7 відділами, якщо в кожний відділ необхідно передати не менш ніж 2 комп’ютери і не менш ніж один принтер?

Завдання 10. Скільки існує способів закупити 1000 однакових пар взуття у чотирьох різних постачальників, якщо мінімальна партія постачання 100 штук?

Завдання 11. Скільки існує способів придбання 100 однакових мікросхем у трьох різних постачальників, якщо мінімальна партія поставки 25 штук?

2.4 Приклади аудиторних і домашніх завдань

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

Розв’язок. У задачі нас цікавить лише те, скільки дисків отримає кожний студент, а не те, які саме диски він отримає. Задача належить до задач розподілу однакових предметів за урнами (урни можуть бути порожніми).

( =20) однакових предметів між ( =4) особами можна розподілити способами, тому кількість способів розподілу дорівнює .

Завдання 2. У студентській групі, яка складається з 25 осіб, при виборі старости за висунуту кандидатуру проголосували 12 студентів; проти – 10; утрималися – 3. Скількома способами могло бути проведене таке голосування?

Розв’язок. Задача належить до задач розподілу різних предметів за урнами. Кількість розміщень різних предметів ( голосів) за урнами за умови, щоб у першу урну попало ( голосів «за» висунуту кандидатуру), у другу урну попало ( голосів «проти» висунутої кандидатури), у третю урну попало ( голосів «утрималися»), дорівнює

=1487285800, де .

Завдання 3. Скількома способами можна розділити 8 різних зошитів між 5 студентами?

Розв’язок. Задача належить до задач розподілу різних предметів без урахування порядку предметів в урнах. У випадку, коли ( =8) різних предметів розподіляються між ( =5) особами без обмежень (кожний студент, який бере участь у розподілі, може забрати собі усі зошити), кожний предмет можна вручити способами (кожний предмет вручається одному з учасників розподілу). Тому в задачі кількість роз’язків дорівнює .

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

Розв’язок. Задача належить до задач розподілу предметів (фотографій) між однаковими урнами (конвертами) за умови, що урни непорожні.

Кількість (число Моргана) розподілів різних предметів між різними урнами з використанням кожної урни у кожному розподілі («непорожні урни») дорівнює , де – число Стирлінга другого роду.

випливає з формули включень і виключень.

Кількість розподілів різних фотографій ( =8), при якому жоден із п’яти конвертів ( =5) не порожній, дорівнює

.

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

Розв’язок. Задача належить до задач розподілу різних предметів з урахуванням їх порядку в урнах

.

Завдання 6. Нехай у магазині є 8 однакових комп’ютерів і 15 комплектів різних прикладних програм. Скільки існує способів у п’яти покупців купити товар, якщо кожний покупець купує не менш ніж один комп’ютер і не менш ніж один комплект програм?

Розв’язок. Комп’ютери і програми купуються незалежно. Задачу про купівлю комп’ютерів можна вважати задачею про розподілення об’єктів (комп’ютерів) за урнами (покупцями) за умови, що немає порожніх урн. Кількість таких варіантів .

Задачу про купівлю комп’ютерних програм можна вважати задачею про розподілення об’єктів (комп’ютерних програм) за різними урнами (покупцями) за умови, що немає порожніх урн.

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

.

Отже, кількість способів купити товар за правилом добутку дорівнює

.

Что вызывает тренды на фондовых и товарных рынках Объяснение теории грузового поезда Первые 17 лет моих рыночных исследований сводились к попыткам вычис­лить, когда этот...

ЧТО ПРОИСХОДИТ ВО ВЗРОСЛОЙ ЖИЗНИ? Если вы все еще «неправильно» связаны с матерью, вы избегаете отделения и независимого взрослого существования...

Что способствует осуществлению желаний? Стопроцентная, непоколебимая уверенность в своем...

Конфликты в семейной жизни. Как это изменить? Редкий брак и взаимоотношения существуют без конфликтов и напряженности. Через это проходят все...

Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте: