Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Metodichka2012.doc
Скачиваний:
3
Добавлен:
01.07.2025
Размер:
5 Мб
Скачать
☆

2.2. Розміщення та сполучення.

У комбінаториці важливими є поняття розміщення, сполучення та перестановки. Наведемо визначення цих понять.

Нехай  фіксована множина. Упорядковані підмножини з елементів множини називаються -перестановками, або -розміщеннями, або розміщеннями з елементів по . Якщо у перестановці беруть участь всі елементи множини ( -перестановка), то використовують термін перестановка.

Два розміщення з по вважають різними, якщо або вони складаються з різних елементів, або з однакових елементів, але розміщених у різному порядку. Символом позначають кількість розміщень із елементів по . Символом позначають кількість перестановок -множини.

В тих випадках, коли не цікавий порядок елементів у вибірці, а важливий лише її склад, говорять про сполучення (іноді використовують термін „комбінація”). Сполученням з елементів по називається будь-яке -розміщення з цих елементів, в якому враховується лише склад елементів і не враховується їх порядок. Кількість -сполучень з елементів позначається (або, зазвичай у англомовній літературі ).

Знайдемо кількісні характеристики вищенаведених позначень.

Твердження 2.1. Справедливі рівності

1) (2.1.1);

2) (2.1.2);

3) (2.1.3).

Доведення. Доведемо першу рівність. Перший елемент перестановки можна обрати способами (будь-який елемент множини); другий елемент  способами (будь-який, окрім того, що обрали на перше місце); третій  способами (будь-який, окрім тих, що обрали на перше та друге місце) і так далі. Останній -й елемент можна обрати 1 способом. За правилом добутку .

Доведемо другу рівність. Перший елемент будь-якої -розміщення можна обрати способами (будь-який елемент множини); другий елемент  способами (будь-який, окрім того, що обрали на перше місце); третій  способами (будь-який, окрім тих, що обрали на перше та друге місце) і так далі. Останній -й елемент можна обрати способами. За правилом добутку

Доведемо третю рівність. Нехай  будь-яке -сполучення множини . Тоді з цього сполучення шляхом перестановки елементів можна одержати різних розміщень. Кожне інше -сполучення дасть розміщень, що не співпадають із попередніми. Тому кількість сполучень з елементів по в разів менша, ніж розміщень з елементів по , тобто . ■

Для чисел та справедливо наступне корисне твердження.

Твердження 2.2. Справедливі рівності

1) (2.2.1);

2) (2.2.2);

3) (2.2.3).

Доведення. Всі ці рівності можна довести шляхом підстановки відповідних значень у формули, що доведені у твердженні 2.1. Ми доведемо ці рівності комбінаторним шляхом з урахуванням змісту поняття розміщення та сполучення.

Доведемо першу рівність. Зафіксуємо деякий елемент з множини . Всі розміщення з елементів множини можна поділити на два класи, що не перетинаються: першому класу належать ті і тільки ті розміщення, в яких є елемент ; другому  ті, в яких відсутній. Знайдемо кількість елементів у кожному класі. В першому класі елемент можна виставити на будь-яке місце (всього варіантів), а на місце, що залишилось, виставляються інші елементи множини , утворюючи -розміщення. Тобто, кількість елементів у першому класі дорівнює . Елементами другого класу є -розміщення із елементів множини . Кількість таких розміщень дорівнює . За правилом суми кількість всіх розміщень з елементів по дорівнює сумі кількості елементів з вищенаведених класів, тобто .

Доведемо другу рівність. Аналогічно до попереднього випадку зафіксуємо деякий елемент з множини і всі сполучення з елементів множини розділимо на два класи, що не перетинаються: першому класу належать ті сполучення, в яких є елемент ; другому  ті, в яких відсутній. Знайдемо кількість елементів у кожному класі. У першому класі треба на вільне місце розставити елементів (це можна зробити способами). У другому класі всі місць вільні, а кількість елементів, які можна розміщувати дорівнює (всі, крім елементу ). Тому у другому класі елементів. За правилом суми .

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

Зауважимо, що рівність (2.2.2) ми використаємо при доведенні теореми в наступному підрозділі. Рівність (2.2.3) часто називають правилом симетрії. Використовуючи відповідні формули з твердження 2.2 можна скласти таблицю значень – так званий трикутник Паскаля, що зображено на рис. 2.1.

0

1

2

3

4

5

6

7

8

0

1

1

1

1

2

1

2

1

3

1

3

3

1

4

1

4

6

4

1

5

1

5

10

10

5

1

6

1

6

15

20

15

6

1

7

1

7

21

35

35

21

7

1

8

1

8

28

56

70

56

28

8

1

Рис. 2.1. Трикутник Паскаля.

В цій таблиці на перетині -го рядка і -го стовпчика міститься число . Кожний рядок таблиці починається з одиниці та закінчується (на головній діагоналі) одиницею. Всі інші значення можна швидко заповнити за допомогою рівності (2.2.2), а саме елемент, що знаходиться на перетині -го рядка і -го стовпчика дорівнює сумі двох елементів з попереднього -го рядка: елемента з -го та -го стовпчиків. Цю таблицю ще записують у вигляді рівнобедреного трикутника (тому і назва «трикутник Паскаля»).

Вищенаведені перестановки, розміщення та сполучення зображують вибірки попарно різних елементів початкової множини . Часто доводиться робити вибірки з повторенням деяких елементів. Наведемо необхідні означення.

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

Аналогічно, невпорядковані -послідовності з цих предметів називають -комбінаціями з необмеженими повтореннями із елементів. Кількість таких -комбінацій позначають через .

Знайдемо кількісні характеристики вищенаведених позначень.

Твердження 2.3. Справедливі рівності

1) (2.3.1);

2) (2.3.2).

Доведення. Доведемо першу рівність. Кожний елемент -перестановки з необмеженими повтореннями можна обрати способами (будь-який елемент множини). За правилом добутку .

Доведемо другу рівність. Кожній -комбінації з необмеженими повтореннями із елементів поставимо у взаємнооднозначну відповідність послідовність з одиниць і нулів за таким правилом: кількість одиниць, що розташовані зліва від першого нуля дорівнюють кількості предметів першого виду; кількість одиниць, що розташовані між першим та другим нулем  кількості предметів другого виду і так далі. Кількість одиниць, що розташовані справа від останнього, -го нуля дорівнюють кількості предметів -го виду предметів. Неважко пересвідчитися, що ця відповідність є взаємнооднозначною (кожній комбінації однозначно відповідає деяка послідовність, і навпаки, кожній послідовності однозначно відповідає деяка комбінація). Тому кількість таких -комбінацій дорівнює кількості послідовності з одиниць і нулів. Підрахуємо кількість послідовностей. Для однозначного визначення послідовності треба або визначити всі місця, на яких знаходяться нулі (тобто з місць треба вибрати , і це можна зробити способами), або визначити всі місця, на яких знаходяться одиниці (тобто з місць треба вибрати , це можна зробити способами). ■

Розглянемо ще один випадок сполучення із повтореннями. Розглянемо впорядковані -послідовності, що складаються з елементів першого виду, елементів другого виду,..., елементів -го виду. Такі послідовності називають -перестановками із заданою специфікацією . Кількість всіх таких перестановок позначають через . Знайдемо цю величину. Твердження 2.4. Справедлива рівність (2.4).

Доведення. елементів першого виду можна розташувати на будь-які місця перестановки способами. Залишилось вільних місць, на будь-які з них можна розмістити елементів другого виду ( способів). елементів третього виду можна розмістити на вільних місць способами і так далі. елементів -го виду можна розташувати на місць способами. За правилом добутку:

.

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

Зауважимо, що перестановки із заданою специфікацією будуть використані у поліноміальній формулі.