Перестановка та комбінація: різниця, що пояснюється на прикладах формул

Перестановки та комбінації надзвичайно корисні в багатьох додатках - від комп'ютерного програмування до теорії ймовірностей до генетики.

Я збираюся познайомити вас з цими двома поняттями поруч, щоб ви могли побачити, наскільки вони корисні.

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

Наприклад, я народився в 1977 році . Це номер 1, за яким йде цифра 9 , за якою йде цифра 7 , за якою йде цифра 7 . У цьому конкретному порядку.

Якщо я заміню замовлення на 7917 , то це буде зовсім інший рік. Таким чином, порядок має значення .

У поєднанні, з іншого боку, основна увага приділяється групам елементів, де порядок не має значення.

Як і моя чашка кави - це поєднання кави , цукру та води . Немає значення, в якому порядку я додаю ці інгредієнти. Там також може бути вода , цукор та кава , це все та ж чашка кави. Таким чином, порядок не має значення.

А тепер давайте детальніше розглянемо ці поняття.

Частина 1: Перестановки

Перестановки, де допускається повторення

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

Крупним планом і особисто

Пароль повинен складатися з 4 цифр. Будь-які 4 цифри. І вони можуть повторюватися.

Для початку є 10 цифр. Це: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Отже, для першої цифри пароля у вас є 10 варіантів.

Оскільки ви можете знову використовувати ту саму цифру, кількість варіантів для другої цифри нашого пароля знову буде 10 ! Таким чином, вибравши дві цифри пароля, перестановки дорівнюють 10 разів у 10, або 10 х 10 = 100 або 102 .

Те саме мислення стосується третьої цифри вашого пароля. Ви знову можете вибрати один із тих самих 10 варіантів. Цього разу у вас буде 10 разів по 10 по 10 , або 10 х 10 х 10 = 1000 або 103 перестановок.

Нарешті, для четвертої цифри пароля і тих самих 10 цифр на вибір, ми отримуємо 10 разів по 10 разів по 10 разів 10 , або 10 x 10 x 10 x 10 = 10000 або 104 перестановок.

Як ви, напевно, помітили, вам потрібно було зробити 4 варіанти, і ви помножили 10 чотири рази (10 х 10 х 10 х 10), щоб отримати загальну кількість перестановок (10000). Якби вам довелося вибрати 3 цифри для свого пароля, ви б помножили 10 три рази. Якщо 7 , ви зробите це сім разів тощо.

Але життя - це не лише паролі з цифрами на вибір. Що робити, якщо у вас день народження і вам потрібно вибрати 5 кольорових кульок з 20 різних кольорів?

Оскільки у вас є 20 різних кольорів на вибір, і ви можете знову вибрати той самий колір, для кожної повітряної кулі у вас є 20 варіантів. Перший аеростат 20 , другий аеростат 20 разів 20 , або 20 х 20 = 400 і т. Д. Для п’ятого аеростата ви отримуєте 20 х 20 х 20 х 20 х 20 = 3 200 000 або 205 перестановок.

Давайте підведемо підсумок із загальним правилом: коли порядок має значення і повторення дозволено, якщо n - кількість речей на вибір (повітряні кулі, цифри тощо), а ви вибираєте r з них (5 куль для учасника, 4 цифри для пароля та ін.), кількість перестановок буде дорівнювати P = nr .

Перестановки там, де не допускається повторення

Далі розглянемо випадок, коли повторення заборонено . Як приклад, ми розглянемо планети нашої Сонячної системи.

Скільки різних способів можна розташувати ці 8 планет? Планетами є: Меркурій , Венера , Земля , Марс , Юпітер , Сатурн , Уран і Нептун . Вибравши, скажімо, Меркурій, ви не зможете вибрати його знову. Таким чином, вам доведеться зменшувати кількість доступних варіантів кожного разу, коли обирається планета.

Перший вибір матиме 8 можливостей. Другий вибір матиме 8 мінус 1 дорівнює 7 можливостям, потім 6 , за якими йдуть 5 , за якими йдуть 4, поки в списку не залишиться 1 планета.

Дотримуючись логіки попереднього сценарію, загальна кількість перестановок становить: P = 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 = 40,320 .

Іншими словами, це добуток цілого числа 8 та всіх додатних цілих чисел під ним. Цей продукт називається Factorial і позначається знаком оклику, наприклад: 8!

Кількість перестановок дорівнює P = 8! або більш загально P = n!

Що робити, якщо вам потрібно лише влаштувати, скажімо, 5 із цих 8 планет замість усіх? Тоді ви зробите лише перші 5 кроків у нашому методі. А саме P = 8 x 7 x 6 x 5 x 4 = 6720 - це скільки способів розташувати 5 планет з 8 .

Але навіщо тут зупинятися? Чому б не застосувати нашу логіку, щоб придумати більш загальну формулу? Щоб зробити наведені вище позначення легкими для запам’ятовування для будь-якої кількості об’єктів, ми скористаємося трюком. У частці множення чисельника та знаменника на одне і те ж число (крім нуля) не впливає на цю частку. Отже:

Кількість планет на вибір n = 8 , ви виберете r = 5 з них. Підставляючи числа до наведеної вище формули, ми отримуємо P = 8! / (8 - 5)! = 8! / 3! . Так само, як 8 x 7 x 6 x 5 x 4 = 6720 .

Звідси можна отримати результат із попереднього прикладу. Там ви розташували всі 8 із 8 доступних планет. Використовуючи нову формулу, P = 8! / (8 - 8)! = 8! / 0! . Оскільки факторіал нуля погоджується дорівнювати 1 , P = 8! / 1 = 8 !. Або загальніше:

P = n! / (n - n)! = n! / 0! = n! .  

Одне коротке та зручне позначення, яке часто використовується: P (n, r) = n! / (n - r)!

Важливо запам’ятовувати формули. Але найважливіше для вирішення реальних життєвих проблем - це знання, які формули використовувати в кожній ситуації. Практика допомагає.

Поп вікторини:

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

Виберіть 1 відповідь


30
360
720
15
Подати

Пояснення: у вас є на вибір 6 команд. Таким чином n = 6 . Золото та срібло разом дають вам 2 медалі для нагородження. Таким чином, r = 2 . Замінивши ці числа у свою формулу, ми отримаємо P (6, 2) = 6! / (6 - 2)! = 6! / 4! = 6 х 5 = 30 .

Частина 2. Комбінації

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

Щоб зробити порівняння більш яскравим, давайте переглянемо наш приклад вибору планети. Що робити, якщо ви хочете знати, які саме планети обрані, а не порядок їх появи?

Там у вас було 6720 різних способів розташування 5 з 8 планет. Але оскільки порядок появи зараз не має значення, багато з цих способів зайві . Вони однакові для нас.

Група Венери, Землі, Марс, Юпітер, Сатурн така ж група , як Марс, Юпітер, Венера, Сатурн і групи як Сатурн, Марс, Землі, Юпітера, Венери. Це просто різні послідовності тих самих 5 планет.

Скільки у вас однакових груп? Якщо ви виберете r планет для групи, ви отримаєте r! групи. Для r = 5 ви отримуєте r! = 5! = 120 груп.

Таким чином, щоб усунути непотрібні однакові групи, ви розділите кількість початкових 6720 перестановок на 5! . Результат - 6720/120 = 56 .

Щоб узагальнити, для того, щоб отримати кількість комбінацій , вам потрібно з'ясувати всі перестановки та розділити на всі надлишки .

Використовуючи короткі та зручні позначення: C (n, r) = P (n, r) / r! = n! / (r! (n - r)!)

І це передбачає, що порядок не має значення і немає повторень (тобто - на вибір є лише один Юпітер).

Давайте переглянемо приклад турніру:

Турнір триває, і змагаються шість команд. Перше місце отримує золото, а друге - срібні медалі. Скільки груп призерів медалей можливо? Порядок команд не має значення

Виберіть 1 відповідь


360
15
30
720
Подати

Як і раніше, у вас 6 команд. Отже, n = 6 . Нагороджено дві медалі, отже r = 2 . Однак цього разу не має значення, хто виграє золото, а хто срібло. Командне золото та командне срібло - це те саме, що командне срібло та командне золото. Замінивши ці числа у свою формулу, ми отримаємо C (6, 2) = 6! / (2! (6 - 2)!) = 6! / 2! 4! = 15 .

Поєднання з повторенням

Щоб завершити цю статтю, є один випадок, який вимагає особливої ​​уваги. Поки що в наших комбінаціях ми припускали, що повторення не було. Не було двох однакових предметів.

Що робити, якщо ми можемо мати повторення? Що робити, якщо, як і в нашому попередньому прикладі, ми можемо вибрати більше однієї кулі одного кольору? Якщо кількість повітряних куль , щоб вибрати з є п і виберемо г з них в той час дозволяючи для того ж кольору і без урахування порядку розташування, ми в кінцевому підсумку з (п + г - 1)! / (r! (n - 1)!) Комбінації .

Отже, підсумовуючи, ось таблиця, за якою можна посилатися на ці поняття та їх формули.

Сподіваюся, ця стаття допомогла вам краще зрозуміти ці два важливі математичні поняття. Дякуємо за читання.