Тема 2. Сполуки з повтореннями Короткі теоретичні відомості

Нехай задано n-елементну множину М.

Розміщеннями з повтореннями з n елементів по k називаються k-елементні впорядковані набори виду , де , причому елементи в наборах можуть повторюватися. Кількість таких розміщень позначається . Справедлива формула: (для довільних натуральних n і k).

Інше комбінаторне тлумачення: – це число способів, якими можна розкласти k різних предметів у n комірках.

Нехай n-елементна множина містить елементи k різних типів, а саме: елементів першого типу, елементів другого типу, …, елементів k-го типу, причому .

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

Інше комбінаторне тлумачення: – це число способів, якими можна розкласти n різних предметів у k комірках, поклавши у ці комірки відповідно предметів.

Нехай множина М містить n елементів.

Комбінаціями з повтореннями з n елементів по k називаються k-елементні набори , складені з елементів множини М (не обов’язково різних). Позначається їх кількість . Справедлива формула: або .

Інше комбінаторне тлумачення: 1)  – це число способів, якими можна розкласти k однакових предметів у n комірках. 2) Якщо позначити через кількість предметів, що потрапили до і-ої комірки (і=1,2,…,п), тоді , і даватиме кількість розв’язків останнього рівняння в цілих невід’ємних числах.

Задачі для самостійного розв’язування

1. (А) У ліфт 12-поверхового будинку на першому поверсі зайшло 10 чоловік. Скількома способами вони можуть вийти з ліфта (починаючи з ІІ поверху)?

2. (А) Скільки 10-символьних „слів” можна утворити із символів „ · ”, „ – ”?

3. (А) Скількома способами можна колоду з 32 карт розділити навпіл так, щоб в кожній половині було порівну червоних і чорних карт?

4. (А) Скількома способами можна вибрати дві приголосні та одну голосну літеру із слова „логарифм”?

5. (А) Алфавіт племені складається з трьох літер – А, В, С. Словом вважається послідовність не більше, ніж 5 літер. Скільки слів у мові цього племені?

6. (А) Дитина переставляє кубики – букви слова а) „школа”, б) „сонце”, в) „зірка”, г) „молоко”, д) „інтернет”, е) „рівняння”. Скільки різних „слів” вона може скласти в кожному випадку?

7. (А) Скількома способами можна упакувати 9 різних книг у три бандеролі, поклавши дві – у першу, три – у другу, чотири – у третю бандероль?

8. (А) Скільки різних прямокутних паралелепіпедів можна побудувати, якщо довжина кожного його ребра може бути будь-яким цілим числом від 1 до 10?

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

10. (А) Скільки різних чисел вийде при перестановці цифр числа 2 233 344 455?

11. (Б) Мова племені «АББА» містить лише дві літери: «А» і «Б». Скільки слів з п’яти літер може утворити це плем’я? Скільки серед них містять три літери «А» і дві «Б»?

12. (Б) З 10 різних квіток треба скласти букет з не менше як двох квіток. Скількома способами це можна зробити?

13. (Б)Довести: а) ;б) .

14. (Б) Скількома способами можна 30 футбольних команд розділити на 6 підгруп по 5 команд у кожній? (Розв’язати задачу двома способами).

15. (Б) Скількома способами можна 28 костей доміно розділити по 7 між 4 гравцями? (Розв’язати задачу двома способами).

16. (Б) Автомобільні номери складаються з однієї, двох або трьох літер і 5 цифр. Знайти кількість всіх можливих номерів, якщо використовуються 24 літери і всі 10 цифр.

17. (Б) Скількома способами можна розділити 12 підручників між чотирма студентами? А якщо порівну?

18. (Б) Скількома способами можна розставити на книжковій полиці 5 книг з теорії ймовірностей, 3 книги з теорії ігор та 2 з математичної логіки, якщо книги з кожного предмета однакові?

19. (Б) Троє юнаків і дві дівчини вибирають собі місце роботи. Скількома способами це можна зробити, якщо в місті є 3 заводи (тільки для хлопців), 2 ткацькі фабрики (тільки для дівчат) і 2 фабрики (і для хлопців, і для дівчат)?

20. (Б) Скількома способами можна переставити букви слова «зоологія», щоб 3 букви «о» не стояли поруч?

21. (Б) Скільки існує 6-значних чисел, які діляться на 5?

22. (Б) Скількома способами можна переставити літери в слові «математика», щоб «ааа» не стояли поряд?

23. (Б) У деякій країні не було двох жителів з однаковим набором зубів. Якою може бути найбільша чисельність населення цієї країни? (Максимальна кількість зубів – 32).

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

25. (Б) Скількома способами можна розставити 18 різних книг у книжковій шафі з 5 полицями, якщо кожна полиця може вмістити всі 18 книг?

26. (Б) Азбука деякої мови налічує 10 голосних та 15 приголосних літер. Скільки в цій мові 5-буквених слів? Слів з двома різними голосними і трьома різними приголосними літерами? Слів, в яких голосні і приголосні літери чергуються? (Словом вважається будь-який набір літер).

27. (Б) Скільки існує трьохзначних натуральних чисел, у яких: а) перша цифра непарна; б) рівно одна непарна цифра; в) хоча б одна непарна цифра?

28. (Б) Скільки 5-символьних наборів, що складаються з нулів та одиниць, містять: а) хоча б один нуль; б) хоча б два нулі?

29. (Б) З 26 студентів групи треба виділити 5 для чергування. Скількома способами це можна зробити, якщо староста і два його заступники не можуть чергувати одночасно?

30. (Б) Скількома способами можна розділити 10 олівців між трьома учнями, якщо: а) олівці різні; б) олівці однакові; в) олівці однакові і кожен учень має одержати хоча б один олівець?

31. (В) П’ятеро дітлахів поділили п’ять однакових цукерок так, що одному з них нічого не дісталося. а) Скільки є способів такого поділу? б) А якщо відомо, що нічого не одержав саме Вася? в) Розв’язати задачу а), якщо всі цукерки різні?

32. (В) Троє хлопців зірвали 40 однакових яблук. Скількома способами їх можна розділити між трьома хлопцями: а) в загальному; б) так, щоб кожен одержав хоча б одне яблуко; в) щоб кожен одержав принаймні 8 яблук?

33. (В) Дано цифри 0, 1, 2, 3, 4, 5. Скількома способами можна утворити з них трицифрових чисел: а) всього; б) з різними цифрами; в) непарних; г) непарних з різними цифрами; д) з непарними цифрами; е) що містять хоча б одну парну цифру?

34. (В) Під час гри в більярд всі 11 куль були забиті в 6 луз. Скількома способами це можна зробити, якщо кулі: а) однакові; б) різні?

35. (В) Потяг складається з 15 вагонів. Кожний з 9 пасажирів вибирає собі вагон навмання. Скількома способами можна зробити вибір: а) в загальному; б) так, щоб всі пасажири потрапили в різні вагони; в) щоб хоча б в одному вагоні виявилось більше одного пасажира; г) щоб у першому вагоні було рівно 2 пасажири?

36. (В) 4 чоловіків і 4 жінок треба розсадити за круглий стіл з 8 місцями. а) Скільки є всього способів? б) Скільки способів, щоб жодні дві жінки не сиділи поряд? в) Щоб особи А і В сиділи поряд? г) Щоб особи А і В не сиділи поряд?