Тема 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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17  Наверх ↑