Главная | Обратная связь

Розміщення з повтореннями

ЕЛЕМЕНТИ КОМБІНАТОРИКИ

Предмет комбінаторики. Правила суми і добутку

Приклад. Нехай з пункту А до пункту B є m доріг, з А до С — п доріг, з В до D — k доріг, з С до D — l доріг; В і С між собою дорогами не сполучені. Скількома дорогами можна потрапити з А до D?

 

Згідно з правилом добутку з А до D через В веде mk доріг, а через С — пl доріг; тому за правилом суми число всіх доріг з А до D mk+ nl.

Вправи

1. У їдальні є 3 перші страви, 5 других і 2 треті страви. Скількома способами можна скласти з них обід?

2. Скільки двоцифрових чисел можна скласти з цифр 1, 2, З, 4, 5, 6?

3. Скільки трицифрових чисел можна утворити з цифр 1, 2, 3, 4, 5, 6, якщо всі цифри утвореного числа повинні бути різними?

4. У школі навчається 1200 учнів. Довести,.що принаймні двоє з них мають однакові ініціали.

 

 

Упорядковані множини.

Розміщення (без повторень). Перестановки.

Приклад.Одного разу 10 друзів зайшли до ресторану. Хазяїн ресторану запропонував їм приходити до нього щодня і кожного разу сідати за той самий стіл по-іншому; після того, як усі способи розміщеннябудуть вичерпані, їх годуватимуть у ресторані безкоштовно. Коли настане цей день?

 

Число різних способів розміщення 10 чоловік за столом, очевид­но, дорівнює

Р₁₀ = 10! = 3 628 800.

Цей день настане через 9942 роки.

Вправи .

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

6. Скількома способами можна зробити триколірний прапорець з горизонтальними смугами однакової ширини, якщо є тканина 6 різних кольорів? Розв'яжіть цю задачу за умови, що один з кольорів має бути червоним.

7. Скількома способами можна з З0 учнів класу обрати старосту, фізорга і редактора стінгазети?

8. Скількома способами можна присудити золоту, срібну і брон­зову медалі на змаганнях, в яких беруть участь 15 чоловік?

9. У шаховому турнірі беруть участь 7 чоловік. Скількома спо­собами можуть розподілитись місця між ними?

10. Скількома способами можна скласти список з 8 учнів?

Комбінації (без повторень). Трикутник Паскаля.

Вправи

11. Скількома способами можна вибрати 3 фарби з 5 різних фарб?

12. З 52 делегатів конференції треба обрати президію з 5 чоловік і делегацію з 3 чоловік. Скількома способами можна здійснитивибір, якіцо: а) члени президії можуть входити до складу делегації; б) члени президії не повинні входити до складу делегації?

13. На шкільному вечорі присутні 12 дівчат і 15 юнаків. Скількома способами можна вибрати з них 4 пари для танців?

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

15. Скільки діагоналей має опуклий n-кутник (п > 3)?

16. Скількома способами можна групу з 15 учнів поділити на дві так, щоб в одній групі було 11 учнів, а в другій — 4 учні?

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

18. Скількома способами можна 15 шахістів поділити на три команди по 5 чоловік?

19. Доведіть рівності:

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

Розміщення з повтореннями

Приклади.1. Скільки існув функцій, що відображують n-множину D в п-множину M?

Нехай ; якщо функція відображає D в М, то . Таким чином, кожна така функція визначається впорядкованим набором елементів n-множини М, тобто k-вибіркою з n-множини. Тому число таких функцій до­рівнює .

2. Автомобільний номер складається з трьох букв та чотирьох цифр. Знайти кількість всіх можливих номерів, якщо використову­ються 32 букви російського алфавіту.

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

3. Скільки цілих чисел, менших за мільйон, можна записати за допомогою цифр 7, 8, 9, 0?

Кожне число, менше за мільйон, можна записати за допомогою шести цифр, дописавши в разі потреби необхідне число нулів зліва. Тому кількість таких чисел дорівнює .

4. Скільки цілих чисел, менших за мільйон, можна записати за допомогою цифр 7, 8, 9?

Оскільки число k-цифрових чисел, записаних за допомогою цифр 7, 8, 9, дорівнює , то всіх таких чисел, менших за мільйон, є .

Вправи

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

22. На залізничній станції є т світлофорів. Скільки різних сиг­налів можна подати за їхньою допомогою, якщо кожний світлофор має три сигнали — червоний, жовтий і зелений?

23. Поїзд, в якому їдуть п пасажирів, робить kr зупинок. Скіль­кома способами можуть вийти пасажири на цих зупинках?

24. Два листоноші повинні віднести 10 листів. Скількома спо­собами вони можуть розподілити між собою роботу?