Элементы комбинаторики

Елементи комбінаторики

28предметів)?

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

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

44

Елементи комбінаторики

7. Комбінації з повтореннями

Стислі теоретичні відомості

Комбінаціязповтореннямиз m елементів по n елементів може містити будь-який елемент скільки завгодно разів від 1 до p включно або не містити його зовсім.

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

Приклад. Нехай є 5 різних видів марок і потрібно скласти з цих елементів комбінації по 3 елементи з повтореннями (тобто до ком­ плекту можуть входити три однакові марки).

Розв’язання. Маємо сполучення з 5 елементів по 3 з повторен-

з повтореннями іноді можна звести до задач на перестановки з по­ втореннями, що було докладно розглянуто раніше (див. приклади 4 і 5 із попереднього підрозділу).

Приклади розв’язування задач

Приклад 1. Знайти кількість комбінацій із повтореннями з чотирьох елементів a, b, c, d — по 3 елементи.

Відповідь: 20.

Приклад 2. У відділенні зв’язку продаються листівки 10 видів. Скількома способами можна купити в ньому 12 листівок?

Розв’язання. Оскільки листівки можуть бути однаковими, то

Відповідь: C2112 .

45

Елементи комбінаторики

Приклад 3. Скільки існує трикутників, довжини сторін яких набувають одного зі значень: 4, 5, 6, 7, 8?

Розв’язання. C53 = C73 = 7 6 5 = 35.

1 2 3

Відповідь: 35.

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

Розв’язання. C3 = C3 = 12 11 10 = 220 .

10 12 1 2 3

Відповідь: 220.

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

1.Знайдіть кількість комбінацій із повтореннями з шести елементів: а, б, в, г, д, е — по 4 елементи.

2.Укондитерськомумагазинієтістечкачотирьохвидів:заварні, пісочні, «наполеон» і «корзинка». Скількома способами можна купити в ньому 10 тістечок?

3.Скільки існує п’ятикутників, довжини сторін яких набувають значення з набору чисел 4, 5, 6, 7?

46

Елементи комбінаторики

8. Підсумкова таблиця (алгоритм розв’язування комбінаторних задач)

Вибір формули

Чи враховується порядок розміщення елементів?

Так

Усі елементи беруть участь?

47

Елементи комбінаторики

Самостійна робота

I варіант (з розв’язаннями)

У завданнях 1—2 виберіть одну правильну, на вашу думку, відповідь.

1. Вставтепропущенеслово:розміщеннязmелементівпоnелементів — це будь-яка ... підмножина m-елементної множини, що містить n елементів.

Розв’язання. У розміщенні важливий порядок.

Відповідь: А.

2. Кожна з перестановок, утворена з 5-елементної множини, містить елементів:

Відповідь: 35.

4.Скількома способами можна розмістити 6 ліхтарів у новорічній гірлянді?

Розв’язання. Розміщення ліхтарів у гірлянді — це перестанов-

ки 6 елементів. P6 = 6! = 720 .

Відповідь: 720.

5.Скільки різних трицифрових чисел можна скласти з цифр

1, 2, 3, 4, 5?

Розв’язання. Вибираємо різні впорядковані 3-елементні під-

множини із 5-елементної множини. A53 = 5 4 3 = 60 .

Відповідь: 60.

6.Скількома способами можна скласти команду із 2 дівчаток

і3 хлопчиків для участі в олімпіаді, якщо є 10 дівчаток і 12 хлоп­ чиків?

48

Елементи комбінаторики

Розв’язання. Двох дівчаток із 10 можна вибрати C102 способами. Трьох хлопчиків із 12 — C123 способами. За правилом добутку

Відповідь: 9900.

II варіант

У завданнях 1—2 виберіть одну правильну, на вашу думку, відповідь.

1. Вставте пропущене слово: кожна перестановка, утворена з елементів деякої множини,— це ... множина.

3. Чому дорівнює кількість перестановок із 4 елементів?

4. Скількома способами можна вибрати двох учасників естафети 100×200 із 6 спортсменів?

5. На площині 20 точок розмістили так, що жодні 3 не лежать на одній прямій. Скільки різних прямих можна провести через ці точки?

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

III варіант

У завданнях 1—2 виберіть одну правильну, на вашу думку, відповідь.

1. Вставте пропущене слово: комбінацією з m елементів по n елементів називають будь-яку ... підмножину, що містить n елементів.

49

Елементи комбінаторики

Контрольна робота 1

I варіант

У завданнях 1—5 виберіть одну правильну, на вашу думку, відповідь.

1. Кількість розміщень із n елементів по m елементів обчислюється за формулою:

50

Елементи комбінаторики

II варіант

У завданнях 1–5 виберіть одну правильну, на вашу думку, відповідь.

1. Число комбінацій із n елементів по m елементів обчислюється за формулою:

51

Елементи комбінаторики

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

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

7.Скільки різних «слів» можна скласти з букв слова «соче­ тание»?

8.Скількома способами можна розставити в шеренгу 5 дівчат

і7 юнаків, щоб усі дівчата стояли скраю?

9.Скільки різних чотирицифрових чисел можна скласти

зцифр 0, 1, 2, 3, 4 так, щоб жодна цифра не повторювалася?

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

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

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

52