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

Розглянемо число 714343733. У його записі цифра 1 зустрічається лише 1 раз, цифра 3 використана 4 рази, цифра 4 повторюється 2 рази, стільки ж разів використана цифра 7. У числі 66666 всі п’ять цифр однакові. Дані два чис­ла є прикладами розміщень з повтореннями. Нижче виписані всі розміщення з повтореннями по 4 символи у кожному, утворені з двох букв а і б; усіх їх 16:

аааа аааб ааба абаа

бааа аабб абаб абба

бааб баба ббаа аббб

бабб ббаб ббба бббб.

Нехай дано прізних елементіва, b, c, ..., l. Утворимо всі можливі упорядковані множини, кожна з яких міститьkелементів. У них деякі елементи можуть повторюватися два, три, ...,kразів. Такі упорядковані множини нази­ваютьрозміщеннями з повтореннями із n елементів,взятих по k.Інакше кажучи, маємо таке означення.

Означення.Розміщеннями з повтореннями з даних п елементів, взятих по k, називаються такі упорядковані множини, які містять по k елементів, кожний з яких є одним з елементів даної n-елементної множини.

Теорема 6.Кількість різних розміщень з повтореннями ізпелементів поkдорівнюєn^k.

■Для доведення скористаємось правилом множення. Перший елемент розміщення з повтореннями можна вибратиnспособами. Такою ж кількістю способів можна вибрати й другий елемент. Тому перші два елементи разом можна вибратиn²способами. Аналогічно, третій елемент теж можна вибратиnспособами, і т. д. Останнійk-й елемент так само можна вибратиnспособами, адже елементи можуть повторюватися. Отже, за правилом множення, шукана кількість розміщень дорівнюєn^k. ■

Доведення цієї теореми можна провести і за допомогою методу математичної індукції. Подумайте самостійно, як це зробити.

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

■ У першому разі шукане число дорівнює кількості розміщень з повтореннями із 6 елементів по 3, тобто 6³216. У другому разі від цього числа слід відкинути кількість записів, у яких на першому місці стоїть цифра 0, наприклад 012, 003, 000. Кількість таких записів дорівнює кількості розміщень з повтореннями із 6 елементів 0, 1, 2, 3, 4, 5 по 2, тобто 6²36. Отже, у другому разі шукане число дорівнює 216 – 36180. ■

§6. Приклади розв’язування комбінаторних задач

1.Скількома способами із 28 учнів класу можна вибрати групу для роботи в саду, якщо в групі може бути не більше 10 і не менше 4 чоловік?

■Групу із чотирьох учнів можна вибратиспособами. Інші групи — по 5, по 6, і т. д., по 10 чоловік — можна вибрати відповідноіспособами. За правилом додавання, маємо:

+++++. ■

2.У хорі 11 хлопчиків і 11 дівчаток. Скількома способами цих хористів можна розмістити в ряд таким чином, щоб поряд не стояли жодні два хлопчики і жодні дві дівчинки?

■Нехай хлопчики розміщуються на непарних місцях, а дівчатка — на парних. Існує 11! ∙ 11!(11!)²способів такого розміщення. Крім цього, є ще стільки само способів, при яких хлопчики стоятимуть на парних місцях, а дівчатка — на непарних. Тому шукана відповідь така: 2(11!)². ■

3.Для військового патруля потрібно призначити 6 солдатів, 3 сержанти і два офіцери. Скількома способами це можна зробити, якщо в роті є 30 сол­датів, 6 сержантів і 4 офіцери?

Відповідь.

4.Скільки дільників має число 10¹⁰?

■ Оригінальне розв’язування цієї задачі пов’язане з розглядом добутку (1 + 2 + 2²+…+ 2⁹+ 2¹⁰)  (1 + 5 + 5²+…+ 5⁹+ 5¹⁰). Якщо просто перемножити ці многочлени, то дістанемо многочлен з 11²одночленів. Кожний із одночленів буде дільником заданого числа і всі ці числа будуть різними. Тому всіх дільників є 121.

Набагато природнішим є, однак, розв’язання, що ґрунтується на комбінаторному правилі множення. Дільниками числа 10¹⁰2¹⁰5¹⁰є лише числа вигляду 2ⁿ5^m, депі m— цілі числа від 0 до 10. Показникnможна вибрати 11 способами. Те саме стосується й показникаm. Тому всіх дільників числа 10¹⁰є 1111121. ■

5.Для карнавального походу готують прапори. Скількома способами з п’яти сувоїв матерії різного кольору можна пошити різних прапорів, які мають по три горизонтальні смуги однакової ширини, якщо в одному прапорі жоден з кольорів не повинен повторюватися? Відповідь.

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

■ Різних приголосних букв у цьому слові 3, стільки ж різних голосних. Тому потрібні вибірки можна здійснитиспособами. ■

7.З колоди карт, у якій є 52 різних карти, потрібно витягнути 10 карт. Скількома способами це можна зробити?

■ Такий вибір можна зробитиспособами. ■

7а.У скількох випадках серед вибраних карт буде хоча б один туз? У скількох випадках — чотири тузи? У скількох — лише один туз?

■ Оскільки число показує, у скількох випадках в одержаних вибірках з десяти карт не буде жодного туза, то число–характеризує випадки,коли серед вибраних карт буде хоча б один туз. Чотири тузи буде в наборах (до чотирьох тузів додається 6 карт із 48). Один туз буде в наборах.■

8.Номер автомобільного причепа містить дві букви і чотири наступні за ними цифри. Скільки різних номерів можна скласти з 30 букв і 10 цифр?

■ Перші дві букви можна вибрати 30²способами, адже букви можуть повторюватися. Чотири цифри можна вибрати 10⁴способами. Тому всіх різних номерних знаків може бути 30² 10⁴ 910⁶9 000 000. ■

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

■ Це задача на використання поняття комбінації з повтореннями. Число, яке дорівнюєвизначило б кількість можливих розміщень для однакових книг. Але 25 різних книг на 25 місцях можна розмістити 25!способами. Тому всіх можливих розміщень цих книг буде ■

10.Ліфт, у якому знаходиться 9 пасажирів, може зупинятися на 10 по-верхах. Пасажири виходять групами по двоє, троє і четверо чоловік. Скількома способами це може відбутися?

■ Групу із двох чоловік можна утворитиспособами. Тоді групу із трьох чоловік з решта семи можна утворитиспособами. Третя група цілком визначиться вибором перших двох. Вибір трьох поверхів, на яких може вийти одна з груп, можливийспособами. Тому загальна кількість способів, про які запитується в задачі, дорівнює(або або ). ■

11.Шість ящиків з різними матеріалами розносять по вісьмох поверхах офісу. Скількома способами можна розподілити їх по поверхах? У скількох випадках на восьмий поверх буде доставлено не менше двох ящиків?

■ Скориставшись формулою для підрахунку кількості розміщень з повтореннями із 8 елементів по 6, дістанемо перше шукане число: 8⁶. На восьмий поверх можна доставити не менше двох ящиків 8⁶ – 7⁶ – 6  7⁵ способами. ■

12.У класній кімнаті 6 лампочок. Скільки існує способів освітлення кімнати цими лампочками?

■ Запропонуємо два способи розв’язування цієї задачі. Підрахувавши скількома способами можна увімкнути всі 6 лампочок, 5 лампочок, і т. д., нарешті яку-небудь одну лампочку, або навіть жодної з них, дістанемо шукане число:

Той самий результат матимемо, якщо скористаємося формулою для кількості розміщень з повтореннями із двох подій (світить, не світить) на шести місцях. Відповідне число дорівнює 2⁶. ■

13.Скільки існує шестизначних телефонних номерів, у яких хоча б один раз стоять поруч цифри 2 і 5 у такому порядку?

■ Можливі п’ять випадків, при яких цифри 2 і 5 стоять поруч (див. схему):

Зрозуміло, що І і II випадки після заповнення усіх вільних клітин не можуть дати жодного спільного номера. Випадки І і III могли б дати 10² спільних номерів вигляду  2   5   2   5   a   b , де а і b можуть бути будь-якими цифрами. Аналогічні ситуації можливі для випадків І і IV, І і V, II і ІV, II і V та III і V. Тому можливими є 6 ∙ 10² номерів, які входять одночасно до яких-небудь двож з відзначених варіантів. Може трапитися, що в І, ІІІ і V випадках з’явиться номер вигляду  2   5   2   5   2   5. Цей номер уже двічі враховувався, коли ми розглядали спільні номери для випадків І і III та III і V. Тому кількість номерів, у яких число 25 зустрічається хоча б один раз, буде 5 ∙10⁴ – 6 10² + 1  49401. ■