4.5: Комбінаторика і кратність

Визначення

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

Імовірність: Імовірність результату є мірою ймовірності того, що результат відбудеться в порівнянні з усіма можливими результатами.

Перестановка: один «спосіб», в якому всі або частина набору об'єктів можуть бути впорядковані або розташовані.

Комбінація: один «спосіб» виділення всього або частини набору об'єктів без урахування порядку вибору об'єктів.

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

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

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

Основні принципи підрахунку

Принцип множення

Протягом ресторанного тижня ви виходите поїсти на вечерю. Меню тижня ресторану дає вам можливість вибрати між трьома закусками, чотирма записами та двома десертами. Ви відчуваєте себе трохи переповненим кількістю можливостей; скільки різних варіантів їжі існує?

• Кожна з цих відбіркових подій має різну кількість можливих результатів або варіантів:
  • Вибір закуски = 3 варіанти
  • Вибір входу = 4 варіанти
  • Десертна подія = 2 варіанти
• Оскільки ви виберете одну закуску І один entrée І один десерт, загальна кількість різних способів приготування їжі:\[W=3 \times 4 \times 2=24\]
• Один з Основоположних принципів підрахунку, Принцип множення стверджує, що якщо для кожного типу події n можливих результатів, i, в послідовності, то загальна кількість можливих результатів дорівнює значенням n, помноженим разом:\[W=n_{1} n_{2} \cdots n_{t}=\prod_{i=1}^{t} n_{i}\] де\(\prod\) символ - оператор добутку ( аналогічно\(\sum\) символу для оператора sum).
• У цьому контексті кожен\(n_i\) представляє кількість можливих результатів для кожної події. Тому кратність кожного типу подій, дорівнює\(W_i\), а сумарна кратність\(W_{t o t a l}\), може бути визначена за допомогою:\(n_i\)\[W_{t o t a l}=W_{1} W_{2} \cdots W_{3}=\prod_{i=1}^{t} W_{i}\]

Принцип додавання

Ви хочете придбати новий сполучний матеріал для зберігання нотаток класу. Ви розриваєтеся між сполучною речовиною 1 «та 1,5» сполучною речовиною. 1» сполучна речовина поставляється в 5 кольорах, а 1, 5-дюймова сполучна - у 3. Скільки загальних варіантів підшивки ви розглядаєте?

• Два в'яжучих речовини мають різну кількість можливих результатів:
  • 1» в'яжучий = 5 результатів
  • 1.5» в'яжучий = 3 результати
• Оскільки ви виберете 1 «сполучного або 1,5» сполучного, загальна кількість різних результатів, які ви розглядаєте, є:\[W=5+3=8\]
• Один з основоположних принципів підрахунку, Принцип додавання говорить, що якщо є n можливих результатів для кожної події, i, і ми не можемо зробити обидва одночасно, то загальна кількість можливі результати дорівнюють значенням n, складеним разом:\[W=n_{1}+n_{2}+n_{3} \cdots=\sum_{i=1}^{t} n_{i}\]

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

Перестановки помітних результатів без повторення: ВСІ вибрані результати

Ви вирішили взяти на себе завдання спробувати кожен з 40 смаків молочних коктейлів CookOut! Якщо у вас є інший молочний коктейль кожен день, поки ви не спробували їх усіх (без повторів!) , скільки різних послідовностей молочних коктейлів (тобто замовлень або домовленостей) можливі?

• Оскільки ви не повторюєте жодних молочних коктейлів протягом цього часу, ви виберете з 40 молочних коктейлів у перший день І 39 у другий день І 38 на третій день тощо Відповідно до принципу множення вище, загальна кількість послідовностей становить:\[W=40 \times 39 \times 38 \times 37 \times \cdots \times 2 \times 1=40 !=8.16 \times 10^{47}\]
• Порядок молочних коктейлів має значення в цьому питанні, але ніякі молочні коктейлі не повторюються; це називається перестановкою без повторення:\[W=N !\] де\(N\) загальна кількість можливих результатів і все можливі результати вибірки (тобто ви будете продовжувати вибирати молочні коктейлі, поки ви не спробували всі молочні коктейлі). Оскільки ви можете визначити, який молочний коктейль ви намагаєтеся щодня, результати або варіанти вважаються помітними.

Перестановки помітних результатів без повторення: лише ДЕЯКІ результати

З другої думки, мати інший молочний коктейль щодня протягом 40 днів може бути трохи багато... Натомість ви вирішили мати інший молочний коктейль кожен день протягом тижня. (Тоді ви зробите перерву і повернетеся, щоб вирішити решту меню в майбутньому!) Скільки різних домовленостей або послідовностей можливо протягом першого тижня?

• Математика аналогічна попередньому питанню, за винятком того, що нам потрібно лише помножити перші сім чисел у факторіала протягом перших семи днів:\[W=40 \times 39 \times 38 \times 37 \times 36 \times 35 \times 34=93963542400\]
• Більш загальний вираз для цієї перестановки без повторення включає загальну кількість можливих результатів, N та загальну кількість подій вибору, r, яка виражається як «\(N\), взяти\(r\)» (або ви можете подумати це як «\(N\), організувати\(r\)»):\[W=\ _{N}P_{r}=\frac{N !}{(N-r) !}\] де\( _{N}P_{r}\) загальне позначення для перестановки без повторення.
• Для нашого прикладу це було б:\[W={ }_{40} P_{7}=\frac{40 !}{(40-7) !}=\frac{40 !}{33 !}=\frac{40 \times 39 \times 38 \times 37 \times 36 \times 35 \times 34 \times 33 !}{33 !}=93963542400\]
• Попередній приклад (з усіма 40 молочними коктейлями) також можна зобразити таким чином, однак, оскільки всі предмети\(N\) відібрані, і\(r\) рівні:\[W={ }_{40} P_{40}=\frac{40 !}{(40-40) !}=\frac{40 !}{0 !}=40!\]

Перестановки помітних результатів з повторенням

Щоб допомогти вам пройти фінал, ви вирішите мати молочний коктейль щодня під час фінального тижня, але ви не збираєтеся турбуватися про спробу різних; Ви можете просто вирішити мати один і той же кожен день! Якою буде загальна кількість послідовностей молочних коктейлів у цьому випадку?

• Якщо кожен день у вас є можливість 40 різних молочних коктейлів, кількість можливих послідовностей становить:\[W=40 \times 40 \times 40 \times 40 \times 40 \times 40 \times 40=40^{7}=163840000000\]
• Це перестановка з повторенням, і рівняння дає кількість можливих послідовностей для r подій, кожна з яких має N можливих результатів:\[W=N^{r}\]
• Термін повторення вказує на те, що результат або об'єкт не видаляється з наявного пулу після вибору. Іншим способом позначення цієї концепції є перестановка з заміною; після вибору конкретного результату цей результат повертається до пулу вибору, щоб доступні параметри вибору завжди були однаковими.

Перестановки нерозрізнених результатів

Протягом зимових канікул ви купуєте 11 унцій мішок святкового молочного шоколаду Hershey поцілунків. У сумці 72 поцілунків у вас 25 червоних, 23 срібних та 24 зелених поцілунків. Якщо витягнути поцілунки з сумки по одному, скільки різних послідовностей святкових кольорів можливо?

• Може здатися, що цей опис також стосується обчислення кількості перестановок для елементів, які повторюються (оскільки існує кілька поцілунків кожного кольору обгортки), і насправді деякі ресурси посилаються на рівняння таким чином. Однак цей сценарій не повторюється так само, як попередній приклад.
  • Термін повторення використовується для серії подій або набору об'єктів, де результати можуть повторюватися після вибору (тобто пул вибору не змінюється, оскільки вибраний результат замінюється іншим результатом того ж типу).
  • У поточному сценарії вибрані окремі поцілунки не «повторюються», оскільки вони не повертаються в сумку; коли кожен поцілунок видаляється, доступний пул вибору зменшується. Натомість перед початком вибору у пулі вибору є просто кілька нерозрізнених елементів. Це робить різницю з точки зору того, скільки предметів кожного типу (тобто поцілунків кожного кольору) доступні для вибору.
• Якби наші поцілунки були позначені так, щоб кожен поцілунок був помітний від інших, то наша загальна кількість перестановок буде розрахована, як описано раніше:\[W=72 !\] Однак цей розрахунок буде рахуватися\(red_A\) за іншою послідовністю від\(red_B\) подальшої\(red_B\)\(red_A\) . Ці два результати неможливо розрізнити без міток A та B, тому кількість унікальних послідовностей повинна визначатися факторингом кількості однакових або надлишкових домовленостей.
• Кількість можливих домовленостей для кожного окремого типу поцілунку:\[n_{r e d} =25 !\]\[n_{s i l v e r} =23 ! \]\[n_{g r e e n} =24 !\] Отже, наша кількість унікальних послідовностей або домовленостей становить:\[W=\frac{N !}{n_{red} ! n_{silver} ! n_{green} !}=\frac{72 !}{25 ! 23 ! 24 !}\]
• Іншим способом посилання на цей тип перестановки є багатомножинна перестановка, оскільки загальний набір складається з менших підмножин нерозрізнених результатів. Загальний вираз для багатомножинної\[W=\frac{N !}{n_{1} ! n_{2} ! \cdots n_{t} !}\] перестановки: де кожна\(n_i\) - це кількість можливих результатів для кожного типу вибору\(i\), а загальна кількість результатів або об'єктів:\(N\)\[N=\sum_{i=1}^{t} n_{i}\]

Комбінації

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

У весняному семестрі ви вирішуєте, що у вас було достатньо молочних коктейлів CookOut на деякий час. Натомість ви купуєте морозиво Blue Bell у продуктовому магазині! У вас є 5 смаків: печиво та вершки (CC), м'ятний шоколадний чіп (M), полуниця (S), голландський шоколад (DC) та банановий пудинг (B). Якщо ви завжди отримуєте три ложки різних смаків, скільки різних комбінацій можливо?

• Перерахуємо наші п'ять доступних смаків морозива:

Припустимо, ми вибираємо B для першого совку. Якщо ми не можемо мати кожен аромат більше одного разу (тобто без повторення), то B більше не є варіантом для решти совків. Тому другий совок має лише чотири варіанти:

Вибираємо S для другого совку, і видаляємо його з наявних ароматів:

Нарешті, вибираємо DC для третього совка:

• Поки що цей процес виглядає як перестановка без повторів, і рівняння перестановки дасть:\[{ }_{5} P_{3}=\frac{5 !}{(5-3) !}=\frac{5 !}{2 !}=5 \times 4 \times 3=60\]

Однак комбінація {B, S, DC} не відрізняється від інших комбінацій B, S і DC черпаються в іншому порядку. Потрапивши в чашу, порядок не має значення. Рівняння перестановки підраховуватиме кожну послідовність B, S та DC окремо, тому нам потрібно виправити кількість повторюваних або нерозрізнених комбінацій.

Ми можемо проілюструвати цей момент далі, розглянувши приклад B, S та DC більш детально:

Існує шість помітних послідовностей, які виробляють невиразні комбінації. Ми також могли б обчислити це значення, використовуючи перестановку без повторення для кількості совків:\[\ _{3} P_{3}=\frac{3 !}{(3-3) !}=\frac{3 !}{0 !}=3 !=6\]

• Щоб визначити кількість унікальних або помітних комбінацій (де порядок не має значення), нам потрібно розділити наше число помітних послідовностей на кількість послідовностей, які виробляють нерозрізнені комбінації:\[W=\frac{60}{6}=10\]\[W=\frac{ _{5} P_{3}}{3 !}=\frac{\frac{5 !}{(5-3) !}}{3 !}=\frac{5 !}{(5-3) ! 3 !}=\frac{5 !}{2 ! 3 !}=10\]
• Загальне рівняння для цієї комбінації без повторення, яке іменується «\(N\), вибираємо\(r\)» (або в нашому випадку «5 смаків морозива, вибираємо 3») таке:

\ [W=\ _ {N} C_ {r} =\ left (\ begin {масив} {l}
N\
r
\ кінець {масив}\ правий) =\ frac {_ {N} P_ {r}} {r!} =\ гідророзриву {N!} {(н-р)! r!} \]

де\(\ _{N} C_{r}\) і\ (\ left (\ begin {array} {l}
N\\
r
\ end {array}\ right)\) є загальними позначеннями для комбінації без повторення.

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

Замість того, щоб завжди робити три різні совки, скільки різних комбінацій можливо, якщо ви включаєте повторення (тобто комбінації з більш ніж однією мірною ложкою певного аромату)?

• Це поняття називається поєднанням з повторенням або комбінацією з заміною. В цьому випадку простіше думати про заміну.

Давайте знову перерахуємо наші п'ять смаків морозива:

Припустимо, ми вибираємо B для першого совку. Однак, на відміну від раніше, після того, як B було взято з доступних ароматів, ми замінимо його іншим B, залишивши варіанти вибору тими ж:

Вибираємо другий черпак B поруч, замінюючи його знову іншим B:

Нарешті, вибираємо DC для останнього совка:

• Що ви бачите, це те, що якщо у вас є повторення або заміни, ви не отримуєте «5, виберіть 3». Замість цього, через заміни після перших двох совок, у вас було 7 загальних доступних варіантів під час процесу відбору, зробивши «7, виберіть 3». \[W=\ _{7} C_{3}=\frac{7 !}{4 ! 3 !}=35\]
• Розглядаючи це більш загально, сподіваємось, ви можете визнати, що, незалежно від кількості\(N_initial\) варіантів, з якими ви почали, якщо ви дозволите заміни, ви в кінцевому підсумку додасте\((r-1)\) додаткові параметри (на один менше, ніж кількість виборів) за вашим остаточним вибором. Таким чином, ваша кінцева кількість доступних варіантів стає:\[N_{\text {final}}=N_{\text {initial}}+(r-1)\] Ми можемо взяти цей вираз за кінцеву кількість доступних варіантів і підставити його в формулу комбінації з попереднього прикладу:\[\ _{N} C_{r}=\frac{N !}{(N-r) ! r !}=\frac{N_{\text {final}} !}{\left(N_{\text {final}}-r\right) ! r !}=\frac{\left(N_{\text {initial}}+(r-1)\right) !}{\left(N_{\text {initial}}+(r-1)-r\right) ! r !}=\frac{\left(N_{\text {initial}}+(r-1)\right) !}{\left(N_{\text {initial}}-1\right) ! r !}\] Ми можемо переставити це рівняння так:\ [\ left (\ left (\ begin {array} {l}
  N \\
  r
  \ end {масив}\ праворуч)\ праворуч) =\ frac {\ ліворуч (\ ліворуч (N_ {\ text {початковий}} -1\ праворуч) +r\ праворуч)!} {\ ліворуч (N_ {\ text {початковий}} -1\ праворуч)! r!} \] де позначення\ (\ left (\ left (\ left (\ begin {array} {l}
  N
  \
  r\ end {array}\ right)\ right)\) використовується для позначення комбінації з заміною і називається «\(N\), multichoose»\(r\).
• Цей новий вираз нагадує перестановку для двох елементів з нерозрізненими наслідками: є\((N_{\text {initial}}-1)\) невиразні результати одного\(r\) елемента та іншого. Це звідки приходить представлення рядка/точка.

Ми будемо розвивати систему, яка має\((N_{\text {initial}}-1 )\) лінії і\(r\) точки. Тому для наших 5 смаків морозива та 3 мірних ложки ми будемо використовувати 4 лінії та 3 точки:\[W=\frac{(4+3) !}{4 ! 3 !}=35\]

• Хоча це рівняння дає правильну відповідь, все одно може здатися дивним переробити проблему таким чином. Давайте подивимося на це ще раз: зробіть вигляд, що у вас є машина для зачерпування морозива, і ви дали цій машині інструкції в коді рядків і точок. Кожна точка являє собою одну кульку морозива, і кожен рядок відокремлює (або розділяє) один аромат від іншого. Для того, щоб передати комбінацію {B, B, DC} машині, ви надсилаєте наступний код (пам'ятаючи, що порядок не має значення):

Якби ви хотіли {CC, M, DC}, це було б:

І якщо ви хотіли всі CC:

Щоб продемонструвати, що метод line/dot працює загалом, визнайте, що для\(N_{\text {initial}}\) варіантів завжди будуть потрібні\((N_{\text {initial}}-1 )\) рядки, щоб відокремити їх один від одного. Для\(r\) вибору вам завжди знадобиться загальна кількість\(r\) крапок, по одній на кожен вибір. Він працює, щоб використовувати три точки, розміщені серед чотирьох рядків, які розділяють п'ять смаків!

Отже, комбінація «\(N\), multichoose\(r\)» з рівнянням заміни дорівнює рівнянню перестановки для\((N_{\text {initial}}-1 )\) ліній і\(r\) точок, де лінії і точки нерозрізнені:\ [\ left (\ left (\ begin {array} {l}
N\\
r
\ end {масив}\ право)\ право) = {} _ {N-1} P_ {r} =\ frac {((N-1) +r)!} {(N-1)! r!} \]