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

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

Задача. Знайти число всіх кортежем довжини k, які можна скласти з елементів множини Х, якщо число цих елементів дорівнює m, n(X)=m.

Розв’язання

Потрібно знайти число елементів декартового добутку Х×Х×…×Х, яке складається із k однакових множників. Це число дорівнює (із попередньої теорії) n(X)…n(X) (k множників), тобто дорівнює n^k(X)=m^k.

 

Нехай, m=4, k=2, m^k= 4²=16.

1, 2, 3, 4

11 12 13 14

21 22 23 24

31 32 33 34

41 42 43 44

Нехай, m=4, k=3, m^k= 4³=64.

111 112 113 114

121 122 123 124

131 132 133 134

141 142 143 144

Стільки ж з «2» на першому місці.

Стільки ж з «3» на першому місці.

Стільки ж з «4» на першому місці.

 

Def: Кортежі довжини k, складені із елементів m-елементної множини X, називаються розміщеннями з повтореннями із m елементів по k ( ). Буква А від французького arrangement – розміщення. Рисочка над А говорить про те, що можливі повторення елементів.

=m^k (1)

 

Приклад 1. Скільки п’ятизначних номерів можна скласти із дев’яти цифр 1, 2, …, 9?

Розв’язання

Задача. Знайти число відображень множини Х в множину Y, якщо n(X)=k i n(Y)=m.

Розв’язання

X=(x₁, x₂,…, x_k). Кожному відображенню f множини X в Y відповідає кортеж довжини k, складений із образів цих елементів (взятих в тому ж порядку), тобто кортеж (f(x₁₎, f(x₂₎,…, f(x_k)). Навпаки, задання кортежа (y₁, y₂,…, y_k), складеного із елементів множини Y, однозначно визначає відображення f: елемент x_y переходить у елемент y_y.

Це означає, що число відображень множини X в множину Y дорівнює числу кортежей довжини k, складених із елементів множини Y. Так як n(Y)=m, то це число буде m^k.

 

I. m=2, k=3, m^k= 2³=8.

a, b, c 1, 2

1. a, b→1; c→2; 2. a, c→1; b→2; 3. b, c→1; a→2;

4. a, b→2; c→1; 5. a, c→2; b→1; 6. b, c→2; a→1;

7. a, b, c→1; 8. a, b, c→2.

II. m=3, k=2, m^k= 3²=9.

a, b 1, 2, 3

1. a→1; b→1; 2. a→1; b→2; 3. a→1; b→3;

4. a→2; b→1; 5. a→2; b→2; 6. a→2; b→3;

7. a→3; b→1; 8. a→3; b→2; 9. a→3; b→3.

Приклад 2. Скількома способами можна розділити 6 різних цукерок серед трьох дітей?

Розв’язання

Кожна цукерка може попасти на одне із трьох місць!

3⁶=729.

Взагалі, будь-яке відображення k-елементної множини X в m-елементну множину Y можна трактувати як розкладку k елементів по m ящиках. Число таких розкладок m^k.

Задача 3. Знайдемо число всіх підмножин множини X, якщо Х містить k елементів.

Розв’язання

Будемо розкладати елементи множини Х в два ящика. Кожній підмножині А множини Х відповідає спосіб розкладки, при якому елементи підмножини попадають в перший ящик, а решта елементів – в другий. Кожна така розкладка однозначно визначає підмножину елементів, які попали в перший ящик. Тому загальне число підмножини в Х дорівнює числу способів розкладки елементів множини по двом ящикам, тобто дорівнює

2^n(X)=2^k (1+ =2^k)

Це твердження можна довести і методом математичної індукції.

 

Приклад 3. Випишемо всі підмножини множини {a, b, c}.

Дана множина має вісім підмножин:

{Ø}, {a}, {b},{c},{a, b},{a, c},{b, c},{a, b, c}.

Так як 8=2³, це відповідає доведеному вище твердженню.

№422. Скільки існує п’ятизначних номерів, які не містять цифру 8? 0 і 8? Складених із цифр 2, 3, 5, 7?

Розв’язання

Всього п’ятизначних номерів n=10⁵.

n₁= 9⁵-9⁴=52488 (0 на 1^му, 2^му, 3^му, 4^му місці дає 9⁴ комбінацій);

n₂= 8⁵=2¹⁵=2¹⁰·2⁵=1024·32=32768;

n₃=4⁵ =2¹⁰=1024.

№423. Скількома способами можна розкласти 12 різних деталей по 3 ящиках?

Розв’язання

n=3¹².

№424. Маємо набір із 16 карток. На чотирьох із них написана буква «А», на чотирьох – «Б», на чотирьох – «В», на чотирьох – «Г». Скільки різних комбінацій букв можна одержати, вибираючи із набору 4 картки і розташовуючи їх в деякому порядку?

Розв’язання

n=4⁴.

№425. В деякому казковому королівстві не було двох людей з однаковим набором зубів. Яке могло бути найбільше число жителів цього королівства, якщо у людини 32 зуба?

Розв’язання

На 1^му місці може бути зуб, а може і не бути; на 2^му місці може бути зуб, а може і не бути; …; на 32^му місці може бути зуб, а може і не бути.

2·2·2·…·2=2³².

n=2³².

n= =2³².

- число сполучень по k зубів.