Тема 7. Вибірки елементів, r-перестановки і r-сполучення.
Питання теми
1. Вибірки і перестановки
2. Сполучення або комбінації. Основні властивості числа комбінацій.
3. Приклади розв’язання задач.
Основні терміни теми: вибірка, перестановка, комбінація.
1. Вибірки і перестановки
Вибірка елементів. Однією з задач комбінаторики є означення кількості різних підмножин, які можна утворювати вибіркою елементів з деякої множини по означеним правилам.
Вибірка r елементів з n називається r-перестановкою, якщо враховується порядок руху, та r-комбінацією, якщо беруться на увагу тільки елементи без урахування їх порядку.
Перестановки. Позначимо число r-перестановок з n різних елементів без повторень. Перший член перестановки можна вибрати з n елементів n різними способами. Так як елементи не повинні повторюватись, тоді вибір другого члена можна здійснювати n-1 способами і т.д. аж до r-го елемента, який можна вибирати n-r+1 способами. Застосовуючи послідовно правило добутку, отримуємо:
p( n,r ) = n( n-1 )...( n-r+1 ) n r
Звичайно n-перестановки з n різних об’єктів називаються просто - перестановками та визначаються за формулою
P = n( n - 1 )...2 1 = n!
n - перестановки з r різних об’єктів називають розміщенням та визначають
Розглянемо перестановки з повтореннями з n елементів, специфікація яких , де n = n1+n2…+nk. Через збіг деяких елементів число таких перестановок виявляється меншим ніж n!, тому що перестановка однакових елементів нічого не змінює. Елементи j-го класу припускають n способами, і в кожному такому класі також операції здійснюються незалежно. Тому відповідно до правила добутку можна здійснити n1!n2!…nk! перестановок, не змінюючи дану перестановку. Таким чином число різних перестановок з повтореннями, які виходять з n елементів визначаються формулою
Приклад. План забудови вулиці 10 будинками, серед яких тип А- 3 будинку, тип В- 5 будинків, тип С-2 будинку. Виявити кількість можливих варіантів забудови.
Рішення.
Якщо запас об’єктів n різних типів не обмежений, тоді кожне місце в r –перестановці можна заповнити n різними способами. Тому відповідно до правила добутку число r-перестановок з необмеженими повтореннями дорівнює U(n,r)=n . Це співвідношення визначає кількість різних r- розрядних чисел, записаних в позиційній системі з основою n.
2. Сполучення або комбінації
Комбінації. Визначимо r- сполучень з n різних елементів. З кожного такої комбінації можна утворити r! Перестановок, тому шукане число буде в r! Разів менше числа r-перестановок з n елементів тобто
Основні властивості числа комбінацій.
За означенням прийнято вважати:
.
3. Приклади розв’язання задач
1. Із міста А в В ведуть 6 доріг, із міста В в С - 4 дороги, із міста С в D - 8 доріг. Скільки можна вибрати маршрутів , які ведуть дорогами із міста А в D через міста В і С?
Розв’язання. За правилом добутку : (способами).
2. Скількома способами можна розсадити 7 гостей на 7 різних стільцях?
Розв’язання. Це кількість перестановок із семи елементів без повторення:
3. На площині точок. Кожні дві з них з’єднує відрізок. Скільки всього відрізків утворилось? Розгляньте різні випадки розміщення точок і співставте їх. Виділіть випадок, коли точки є вершинами випуклого десятикутника, і сформулюйте запитання.
Розв’язання. 1-й спосіб
2-й спосіб. З кожної із десяти точок в інші 9 іде відрізок, таким чином всього дістали б відрізків , при цьому кожен відрізок фактично полічили двічі, адже АВ=ВА, тому одержаний добуток треба поділити на 2. Отже, . Для 10-кутника це буде число всіх його сторін і діагоналей.
У групі 30 студентів. Кожен потиснув руку всім іншим. Скільки зроблено рукостискань?
Розв’язання. Кожен з 30 студентів потиснув руку іншим 29. Тому всього буде рукостискань
В скількох точках перетинаються діагоналі опуклого n-кутника, якщо жодні три з них не перетинаються в одній точці?
Розв’язання. Кожній точці перетину двох діагоналей відповідає чотири вершини n-кутника. Тому всіх точок перетину діагоналей буде
При n=5 матимемо:
Для преміювання трьох студентів купили 12 різних книжок. Скільки можливих способів розподілу премій по 4 книжки?
Розв’язання. Для першого студента маємо
Для другого -
Для третього -
Всього таких способів буде:
7. Є п’ять видів конвертів без марок і чотири види марок. Скількома способами можна вибрати конверт і марку для відправки листа?
Розв’язання. Позначимо А = {k , k , k , k , k } - множина конвертів, В = {m , m , m , m } - множина марок . Тоді (способів).
8. Із 12 слів чоловічого роду, 9 слів жіночого і 10 середнього роду треба вибрати по одному слову кожного роду. Скількома способами можна це зробити?
Розв’язання. Застосовуючи правило добутку, знаходимо:
(способами).
Приклади.
1. Скільки різних чисел можна дістати, переставляючи цифри в числах: а) 25 575; б) 11 182 288.
Розв’язання.
а) Запис числа 25575 складається з однієї двійки, трьох п’ятірок і однієї сімки. число різних шуканих чисел дорівнює числу перестановок з повтореннями, тобто
б) Число 11182288 має три одиниці, три вісімки, дві двійки. Число шуканих чисел дорівнює
2. Скількома способами можна оббити 6 різних стільців, якщо є 12 видів оббивки?
Розв’язання. Число таких способів дорівнює = 126.
5. Танцювальний гурток відвідують 12 юнаків і 15 дівчат. Скількома способами можна вибрати з них 4 пари для танцю?
Розв’язання. 4 юнаки з 12 можна вибрати С способами, а 4 дівчини з 15 - С способами. Отже, всього буде:
тут при обчисленні використали підстановку : = 1001.
4. Скільки трицифрових чисел можна записати дев’ятьма цифрами 1, 2, 3, 4, 5, 6, 7, 8, 9, якщо цифри в запису числа можуть повторюватись?
Розв’язання. Шукане число дорівнює числу розміщень з повтореннями з 9 елементів по 3: .
5. Скільки трицифрових чисел можна записати п’ятьма цифрами 0, 1, 2, 3, 4, якщо цифри в записі числа можуть повторюватись?
Розв’язання. Всього розміщень з повтореннями з 5 елементів по 3 буде 5 , серед них є 4 чисел, які починаються нулем. Отже, шукане число тризначних чисел дорівняє 5 - 4 = 109.