Перестановка проти комбінації: Яка різниця між формулою перестановки та формулою комбінації?

Ось коротка версія.

Візьмемо для прикладу дзвони в церкві.

Перестановка - це упорядкування дзвонів. Ви знайдете найкращий порядок, щоб зателефонувати їм.

Комбінація - це вибір дзвонів. Ти вибираєш дзвони, щоб задзвонити. Якщо у вас забагато дзвонів, спочатку виберіть їх, а потім подумайте про те, щоб замовити їх.

Це породжує звичну ідентичність: (n P r) = (n C r) * r!

Спосіб замовлення rпредметів n- це спочатку вибрати rелементи з n, а потім замовити rтовари ( r!)

І, це означає (n P r) = n! / (n-r)!і(n C r) = n! / ( (n-r)! * r! )

Але ви хочете знати, як запам’ятати це назавжди?

Я великий шанувальник мислення перших принципів. Щоб зрозуміти проблему, перейдіть до її суті та обґрунтуйте звідти.

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

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

Цього разу ми будуємо інтуїцію для перестановок та комбінацій.

Наприклад, чи знаєте ви, чому формула комбінації (n C r)? Звідки це взялося? І чому тут використовуються факторіали?

Почнемо з джерела. Фактори, перестановки та комбінації народились із математиків, які грали разом, подібно до того, як Стів Джобс та Стів Возняк заснували Apple, граючи разом у своєму гаражі.

Подібно до того, як Apple перетворилася на повноцінну прибуткову компанію, простий факторіал !став атомом цілої галузі математики: комбінаторики.

Забудьте все, давайте почнемо думати знизу вгору.

Перший відомий цікавий випадок використання прийшов з Церков у 17 столітті.

Чи замислювались ви про те, як у церквах лунають дзвони? Є машина, яка «дзвонить» їм по порядку. Ми перейшли на машини, бо дзвони занадто великі. Також є тони дзвонів.

Як люди зрозуміли, в якій послідовності найкраще їх дзвонити? Що, якби вони хотіли змінити ситуацію? Як вони могли знайти найкращий звук? Кожна дзвіниця мала до 16 дзвонів!

Ви не могли змінити, наскільки швидко можна було бити в дзвоник - машини дзвонили лише по одному в секунду. Єдине, що ви могли зробити, це змінити порядок дзвонів. Отже, цей виклик полягав у визначенні найкращого порядку.

Чи могли б ми по дорозі також дізнатися всі можливі замовлення? Ми хочемо знати всі можливі замовлення, щоб з’ясувати, чи варто їх усі випробовувати.

Дзвонар, Фабіан Стедман прийняв цей виклик.

Почав із 2 дзвонів. Які різні замовлення він міг бити в ці дзвони? [1]

1 і 2.

або

2 і 1.

Це мало сенс. Іншого шляху не було.

Як щодо 3 дзвонів?

1, 2 та 3.

1, 3 і 2.

Потім, починаючи з другого дзвоника,

2, 1 і 3.

2, 3 та 1.

Потім, починаючи з третього дзвоника,

3, 1 і 2.

3, 2 та 1.

Всього, 6.

Потім він зрозумів, що це дуже схоже на два дзвони!

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

Скількома способами він міг виправити перший дзвоник? Будь-який із 3 дзвонів міг бути єдиним!

Гаразд, він продовжив. Потім він досяг 5 дзвонів.

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

Він повернувся до свого розуміння.

Якщо у нього було 5 дзвонів, і він зафіксував перший дзвінок, йому залишалося лише зрозуміти, як замовити 4 дзвони.

На 4 дзвони? Ну, якщо у нього було 4 дзвони, і він зафіксував перший дзвоник, все, що йому потрібно було зрозуміти, як замовити 3 дзвони.

І він знав, як це зробити!

Отже, замовлення 5 дзвонів = 5 * замовлення 4 дзвонів.

Замовлення 4 дзвонів = 4 * замовлення 3 дзвонів

Замовлення 3 дзвонів = 3 * замовлення 2 дзвонів.

.. Ви бачите візерунок, чи не так?

Цікавий факт: це ключ до техніки програмування, яка називається рекурсією.

Він теж зробив. Хоча, це зайняло набагато більше часу, оскільки ніхто поруч з ним цього ще не виявив. [2]

Таким чином, він з'ясував, що замовлення 5 дзвонів = 5 * 4 * 3 * 2 * 1.

Ця формула впорядкування в 1808 році стала відома як факторіал.

Ми вважаємо факторіальну нотацію базою, але ідея існувала задовго до того, як вона мала назву. Лише коли французький математик Крістіан Крамп помітив, що його використовують у кількох місцях, він назвав його факторіалом.

Таке впорядкування дзвонів називається перестановкою.

Перестановка - це впорядкування елементів.

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

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

У нас є 5 пробілів, так?

Скількома способами ми можемо вибрати перший дзвінок? 5, бо саме така кількість дзвонів у нас є.

Другий дзвоник? Що ж, ми використали один дзвоник, коли поставили його на перше місце, тож у нас залишилося 4 дзвони.

Третій дзвоник? Що ж, ми вибрали перші два, тож на вибір залишилось лише 3 дзвони.

Четвертий дзвін? Залишилося лише 2 дзвони, тому 2 варіанти.

П’ятий дзвін? Залишився лише 1, тому 1 варіант.

І ось у нас це загальна кількість замовлень 5 * 4 * 3 * 2 * 1

Таким чином, ми маємо свою першу загальну формулу.

Кількість способів замовлення Nтоварів становитьN!

Перестановка

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

Але наша дзвіниця все ще вміщує 5 дзвонів, тому нам потрібно з’ясувати найкраще замовлення з 8 дзвонів, які зробили кваліфіковані дзвонарі.

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

Для першого дзвоника ми можемо вибрати будь-який з 8 дзвонів.

Для другого дзвоника ми можемо вибрати будь-який із решти 7 дзвонів ... і так далі.

Врешті-решт, ми отримуємо 8 * 7 * 6 * 5 * 4можливі замовлення 8 дзвонів у 5 місцях.

Якщо ви знайомі з версією формули (n P r), яка є n! / (n-r)!, не хвилюйтеся, ми теж це отримаємо досить скоро!

Поганим способом його отримання є множення чисельника та знаменника на 3! у нашому прикладі вище -

отримуємо 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 / 3 * 2 * 1= 8! / 3!.

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

Комбінація

Тепер, коли ми знаємо, як замовляти речі, ми можемо з’ясувати, як їх вибирати!

Давайте розглянемо ту саму проблему. Там дзвіниця з 5 дзвонами, а у вас 8 дзвонів. Однак прямо зараз ви не хочете з’ясовувати порядок дзвонів (пам’ятайте, що таке перестановка).

Натомість ви хочете вибрати 5 найкращих дзвонів, і нехай хтось із кращим музичним смаком розбере порядок. По суті, ми розбиваємо проблему на частини: Спочатку ми з’ясовуємо, які дзвони вибрати. Далі розбираємося, як замовити обрані дзвіночки.

Як ви вибираєте дзвони? Це «комбінація» з перестановок та комбінацій.

Комбінація - це вибір. Ви ставитеся до вибірковості. Ви вибираєте 5 дзвонів з 8, зроблених вашими майстрами.

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

Давайте уявимо, що всі дзвони в одній лінії.

Перш ніж знайти всі способи вибору дзвонів, зупинимось на одному способі вибору дзвонів.

Один із способів - навмання вибрати будь-які 5. Це не дуже допомагає нам вирішити проблему, тому давайте спробуємо інший спосіб.

Ми ставимо дзвони в лінію, і вибираємо перші 5. Це один із способів вибрати дзвони.

Зверніть увагу, що навіть якщо ми змінимо положення перших 5 дзвонів, вибір не зміниться. Вони все одно і той самий спосіб вибрати 5 унікальних дзвонів.

Це справедливо і для останніх трьох дзвонів.

Тепер прекрасна математична хитрість - для цього одного способу вибору 5 дзвонів, яке все замовлення 8 дзвонів, де ми вибираємо саме ці 5 дзвонів? З малюнка вище, це всі упорядкування 5 дзвонів ( 5!) та всі замовлення решти трьох дзвонів ( 3!).

Таким чином, для кожного окремого способу вибору 5 дзвонів ми маємо ( 5! * 3!) замовлення 8 дзвонів.

Які загальні можливі замовлення 8 дзвонів? 8!.

Пам'ятайте, для кожного вибору перших 5 дзвонів ми маємо ( 5! * 3!) замовлення по 8 дзвонів, які дають однаковий вибір.

Тоді, якщо ми помножимо кількість способів вибрати перші 5 дзвонів з усіма можливими замовленнями одного вибору, ми повинні отримати загальну кількість замовлень.

Ways to choose 5 bells * orderings of one choice = Total orderings 

Тому,

Ways to choose 5 bells = the total possible orderings / total orderings of one choice. 

У математиці це стає:

(8 C 5) = 8! / ( 5! * 3!) 

Ось, ми знайшли інтуїтивне пояснення того, як вибрати 5 речей із 8.

Тепер ми можемо це узагальнити. Якщо у нас є N речей, і ми хочемо вибрати з них R, це означає, що ми проводимо лінію в R.

Що означає, що решта предметів буде N-R. Отже, для одного вибору Rпредметів ми маємо R! * (N-R)!замовлення, які дають однакові Rпредмети.

Для всіх способів вибору Rпредметів ми маємо N! / (R! * (N-R)!)можливості.

Кількість способів вибрати rпредмети з nє(n C r) = n! / (r! * (n-r)!)

У розмовній формі також вимовляється (n C r) n choose r, що допомагає закріпити уявлення про те, що комбінації призначені для вибору предметів.

Перестановка - переглянута

По завершенні та припорошенні комбінації повернемось до частини 2 нашої роботи. Наш дорогий друг вибрав найкращі 5 дзвонів, розібравши всі можливі комбінації з 5 дзвонів.

Наша робота зараз знайти ідеальну мелодію, з’ясувавши кількість замовлень.

Але це легко. Ми вже знаємо, як замовити 5 предметів. Це 5!, і ми закінчили.

Отже, для перестановки (замовлення) 5 предметів із 8 ми спочатку вибираємо 5 предметів, а потім замовляємо 5 предметів.

Іншими словами,

(8 P 5) = (8 C 5) * 5! 

І якщо ми розширимо формулу, (8 P 5) = (8! / ( 5! * 3!)) * 5!

(8 P 5) = 8! / 3!.

І ми дійшли повного кола до нашої початкової формули, правильно виведені.

Кількість способів замовлення rелементів з nIS(n P r) = n! / (n-r)!

Різниця між перестановкою та комбінацією

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

Перестановки - це впорядкування, тоді як комбінації - вибір.

Щоб замовити N елементів, ми знайшли два інтуїтивні способи з’ясувати відповідь. Обидва призводять до відповіді, N!.

Для того, щоб переставити 5 з 8 елементів, спочатку потрібно вибрати 5 елементів, а потім упорядкувати їх. Ви обираєте використовувати (8 C 5), а потім замовляєте 5 за допомогою 5!.

І інтуїція вибору R- Nце з’ясування всіх впорядкувань ( N!) та розподіл за впорядкуваннями, де перше Rта останнє N-Rзалишаються однаковими ( R!і (N-R)!).

І це все, що є для перестановок та комбінацій.

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

Якщо ви зацікавлені, ми можемо розглянути складні справи в іншому прикладі. Повідомте мене в Twitter.

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

Кінцеві примітки

  1. Ось так я уявляю, що він все зрозумів. Не сприймайте це як урок історії.
  2. У 12 столітті індіанці мали 400 років до нього.