1.3: Комбінації та перестановки

Last updated

Oct 27, 2022
Save as PDF
- 1.2: Біноміальні коефіцієнти
- 1.4: Комбінаторні докази

$\newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$

$\newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$

$\newcommand{\id}{\mathrm{id}}$

$\newcommand{\Span}{\mathrm{span}}$

$\newcommand{\kernel}{\mathrm{null}\,}$

$\newcommand{\range}{\mathrm{range}\,}$

$\newcommand{\RealPart}{\mathrm{Re}}$

$\newcommand{\ImaginaryPart}{\mathrm{Im}}$

$\newcommand{\Argument}{\mathrm{Arg}}$

$\newcommand{\norm}[1]{\| #1 \|}$

$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$

$\newcommand{\Span}{\mathrm{span}}$

$\newcommand{\id}{\mathrm{id}}$

$\newcommand{\Span}{\mathrm{span}}$

$\newcommand{\kernel}{\mathrm{null}\,}$

$\newcommand{\range}{\mathrm{range}\,}$

$\newcommand{\RealPart}{\mathrm{Re}}$

$\newcommand{\ImaginaryPart}{\mathrm{Im}}$

$\newcommand{\Argument}{\mathrm{Arg}}$

$\newcommand{\norm}[1]{\| #1 \|}$

$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$

$\newcommand{\Span}{\mathrm{span}}$

Template:MathJaxLevin

Досліджуйте!

У вас є купа фішок, які поставляються в п'яти різних кольорах: червоний, синій, зелений, фіолетовий і жовтий.

Скільки різних двокристальних стеків ви можете зробити, якщо нижній чіп повинен бути червоним або синім? Поясніть свою відповідь, використовуючи як адитивні, так і мультиплікативні принципи.
Скільки різних тричіпових стеків ви можете зробити, якщо нижній чіп повинен бути червоним або синім, а верхній чіп повинен бути зеленим, фіолетовим або жовтим? Як ця проблема пов'язана з попередньою?
Скільки існує різних тричіпових стеків, в яких не повторюється колір? А як щодо чотиричіпових стеків?
Припустимо, ви захотіли взяти три різнокольорових фішки і покласти їх в кишеню. Скільки різних варіантів у вас є? Що робити, якщо ви хочете чотири різнокольорові фішки? Як ці проблеми співвідносяться з попередньою?

Перестановка - це (можлива) перестановка об'єктів. Наприклад, існує 6 перестановок букв a, b, c:

\ begin {рівняння*} abc, ~~ acb, ~~ bac, ~~bca, ~~ кабіна, ~~ cba. \ end {рівняння*}

Ми знаємо, що у нас є всі перераховані вище - є 3 варіанти, для якої літери ми ставимо спочатку, потім 2 варіанти, для якої букви йде далі, що залишає лише 1 вибір для останньої літери. Мультиплікативний принцип говорить, що ми множимо $3\cdot 2 \cdot 1\text{.}$

Приклад $\PageIndex{1}$

Скільки перестановок літер a, b, c, d, e, f?

Відповідь: Ми НЕ хочемо намагатися перерахувати все це. Однак, якби ми це зробили, нам потрібно було б вибрати лист, щоб записати спочатку. Є 6 варіантів для цього листа. Для кожного вибору першої літери існує 5 варіантів для другої літери (ми не можемо повторити першу літеру; ми переставляємо літери і маємо лише одну з них), і для кожної з них є 4 варіанти для третьої, 3 варіанти для четвертої, 2 варіанти для п'ятої і, нарешті, лише 1 вибір для останньої лист. Так що є $6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 720$ permutations of the 6 letters.

Тут корисна частина позначення: $n!\text{,}$ читати « $n$ факторіал», є добутком всіх натуральних чисел менше або дорівнює $n$ (з міркувань зручності ми також визначаємо 0! бути 1). Отже, кількість перестановок 6 букв, як видно в попередньому прикладі $6! = 6\cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1\text{.}$ Це узагальнює:

Перестановки $n$ elements

Існують $n! = n\cdot (n-1)\cdot (n-2)\cdot \cdots \cdot 2\cdot 1$ перестановки $n$ (різних) елементів.

Підрахунок біктивних функцій

Скільки функцій $f:\{1,2,\ldots,8\} \to \{1,2,\ldots, 8\}$ є двооб'єктивними?

Рішення

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

\ begin {рівняння*} f =\ дволінійний {1\ ампер 2\ ампер 3\ ампер 4\ ампер 5\ ампер 6\ ампер 7\ ампер 8\ ампер 5\ ампер 7\ ампер 2\ ампер 4}\ кінець {рівняння*}

Те, що ми насправді робимо, це просто переставляти елементи кодомену, тому ми створюємо перестановку 8 елементів. Насправді «перестановка» - це ще один термін, який використовується для опису двооб'єктивних функцій від скінченної множини до себе.

Якщо ви вірите в це, то ви бачите відповідь повинна бути $8! = 8 \cdot 7 \cdot\cdots\cdot 1 = 40320\text{.}$ You can see this directly as well: for each element of the domain, we must pick a distinct element of the codomain to map to. There are 8 choices for where to send 1, then 7 choices for where to send 2, and so on. We multiply using the multiplicative principle.

Іноді ми не хочемо перемикати всі літери/номери/елементи, які нам даються.

Приклад $\PageIndex{3}$

Скільки 4 букви «слів» ви можете зробити з букв a - f, без повторюваних букв?

Рішення

Це так само, як проблема перестановки 4 букв, тільки тепер у нас є більше варіантів для кожної літери. Для першої літери існує 6 варіантів. Для кожного з них є 5 варіантів для другої літери. Тоді є 4 варіанти для третьої літери та 3 варіанти для останньої літери. Загальна кількість слів дорівнює$6\cdot 5\cdot 4 \cdot 3 = 360\text{.}$ This is not $6!$ because we never multiplied by 2 and 1. We could start with $6!$ and then cancel the 2 and 1, and thus write $\frac{6!}{2!}\text{.}$

Загалом, ми можемо запитати, скільки існує перестановок $k$ об'єктів, які вибирають ці об'єкти з більшої колекції $n$ об'єктів. (У прикладі вище, $k = 4\text{,}$ і $n = 6\text{.}$ ) Ми пишемо це число $P(n,k)$ і іноді називаємо його $k$ -перестановкою $n$ елементів. З наведеного вище прикладу ми бачимо, що для обчислення $P(n,k)$ ми повинні застосувати мультиплікативний принцип до $k$ чисел, починаючи з $n$ і рахуючи назад. Наприклад

\ почати {рівняння*} P (10, 4) = 10\ точка 9\ точка 8\ точка 7. \ end {рівняння*}

Зверніть увагу ще раз, що $P(10,4)$ починає виглядати, $10!\text{,}$ але ми зупиняємося після 7. Ми можемо формально врахувати цю «зупинку», розділивши частину факторіала, яку ми не хочемо:

\ почати {рівняння*} P (10,4) =\ frac {10\ точка 9\ точка 8\ точка 7\ точка 6\ точка 5\ точка 4\ точка 3\ точка 2\ точка 1} {6\ точка 5\ точка 4\ точка 3\ точка 2\ точка 1} =\ frac {10!} {6!}. \ end {рівняння*}

Обережно: Факторіал у знаменнику не є, $4!$ а скоріше $(10-4)!\text{.}$

$k$ -permutations of $n$ elements

$P(n,k)$ кількість $k$ -перестановок $n$ елементів, кількість способів розташування $k$ об'єктів, обраних з $n$ різних об'єктів.

\ begin {рівняння*} P (n, k) =\ frac {n!} {(n-k)!}. \ end {рівняння*}

Зауважте, що коли $n = k\text{,}$ ми маємо $P(n,n) = \frac{n!}{(n-n)!} = n!$ (оскільки ми визначили $0!$ , щоб бути 1). Це має сенс —ми вже знаємо, $n!$ дає кількість перестановок всіх $n$ об'єктів.

Підрахунок ін'єкційних функцій

Скільки функцій $f:\{1,2,3\} \to \{1,2,3,4,5,6,7,8\}$ є ін'єкційними?

Рішення

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

Нам потрібно вибрати елемент з codomain, щоб бути зображенням 1. Є 8 варіантів. Потім нам потрібно підібрати один з решти 7 елементів, щоб бути зображенням 2. Нарешті, один з решти 6 елементів повинен бути зображенням 3. Таким чином, загальна кількість функцій $8\cdot 7 \cdot 6 = P(8,3)\text{.}$

Що це демонструє в цілому, це те, що кількість ін'єкцій $f:A \to B\text{,}$ where $\card{A} = k$ and $\card{B} = n\text{,}$ is $P(n,k)\text{.}$

Ось ще один спосіб знайти кількість $k$ -перестановок $n$ елементів: спочатку виберіть, які $k$ елементи будуть в перестановці, потім порахуйте, скільки існує способів їх розташування. Після того, як ви вибрали $k$ об'єкти, ми знаємо, що існують $k!$ способи їх упорядкування (перестановки). Але як ви вибираєте $k$ об'єкти з $n$ об'єктів у $n\text{?}$ Вас є, і вам потрібно вибрати $k$ з них. Ви можете зробити це ${n \choose k}$ способами. Тоді для кожного вибору цих $k$ елементів ми можемо переглушити їх $k!$ способами. Використовуючи мультиплікативний принцип, отримаємо ще одну формулу для $P(n,k)\text{:}$

\ begin {рівняння*} P (n, k) = {n\ виберіть k}\ cdot k!. \ end {рівняння*}

Тепер, оскільки ми $P(n,k)$ вже маємо закриту формулу, ми можемо замінити це в:

\ begin {рівняння*}\ frac {n!} {(n-k)!} = {n\ виберіть k}\ cdot k!. \ end {рівняння*}

Якщо розділити обидві сторони на, то $k!$ отримаємо замкнуту формулу для ${n \choose k}\text{.}$

Закрита формула для ${n \choose k}$

\ begin {рівняння*} {n\ вибрати k} =\ frac {n!} {(н-к)! k!} \ end {рівняння*}

Ми говоримо, $P(n,k)$ підраховує перестановки та ${n \choose k}$ підраховує комбінації. Формули для кожного дуже схожі, є лише додаткове $k!$ в знаменнику Це додаткові $k!$ рахунки за те ${n \choose k}\text{.}$ , що ${n \choose k}$ не розрізняє різні порядки, в яких $k$ об'єкти можуть з'являтися. Ми просто вибираємо (або вибираємо) $k$ об'єкти, а не розставляємо їх. Можливо, «комбінація» - це оманлива етикетка. Ми не маємо на увазі це як кодовий замок (де замовлення, безумовно, має значення). Можливо, кращою метафорою є поєднання смаків — потрібно просто вирішити, які аромати поєднувати, а не порядок, в якому їх поєднувати.

Щоб додатково проілюструвати зв'язок між комбінаціями і перестановками, закриваємо прикладом.

Приклад $\PageIndex{5}$

Ви вирішили влаштувати звану вечерю. Незважаючи на те, що ви неймовірно популярні і маєте 14 різних друзів, у вас достатньо стільців, щоб запросити 6 з них.

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

Рішення

Ви повинні просто вибрати 6 друзів з групи з 14. Це можна зробити ${14 \choose 6}$ способами. Ми можемо знайти це число або за допомогою трикутника Паскаля, або замкнутої формули: $\frac{14!}{8!\cdot 6!} = 3003\text{.}$
Тут ви повинні порахувати всі способи, якими ви можете перемогти 6 друзів, обраних з групи з 14. Отже, відповідь полягає в тому $P(14, 6)\text{,}$ , що можна обчислити як $\frac{14!}{8!} = 2192190\text{.}$

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

Як пов'язані ці цифри? Зверніть увагу, $P(14,6)$ що набагато більше, ніж ${14 \choose 6}\text{.}$ Це має сенс. ${14 \choose 6}$ вибирає 6 друзів, але $P(14,6)$ організовує 6 друзів, а також вибирає їх. Насправді, ми можемо точно сказати, наскільки $P(14,6)$ більше. В обох задачах підрахунку ми вибираємо 6 з 14 друзів. Для першого зупиняємося на досягнутому, на 3003 шляхах. Але для другої проблеми підрахунку кожен з цих 3003 варіантів 6 друзів може бути організований точно так $6!$ . Отже, тепер у нас є $3003\cdot 6!$ вибір, і це саме $2192190\text{.}$

Як варіант, подивіться на першу проблему іншим способом. Ми хочемо вибрати 6 з 14 друзів, але нас не хвилює порядок, в якому вони відібрані. Щоб вибрати 6 з 14 друзів, ми можемо спробувати це:

\ begin {рівняння*} 14\ точка 13\ точка 12\ точка 1\ точка 10\ точка 9. \ end {рівняння*}

Це розумне припущення, так як у нас 14 варіантів для першого гостя, потім 13 для другого і так далі. Але здогадка невірна (насправді, що продукт точно $2192190 = P(14,6)$ ). Він розрізняє різні замовлення, в які ми могли б запросити гостей. Щоб виправити це, ми могли б розділити на кількість різних домовленостей 6 гостей (щоб все це вважалося лише одним результатом). Є точно $6!$ способи розташувати 6 гостей, тому правильна відповідь на перше питання

\ begin {рівняння*}\ frac {14\ cdot 13\ dot 12\ dot 1\ dot 10\ dot 9} {6!}. \ end {рівняння*}

Зверніть увагу, що ще один спосіб написати це

\ begin {рівняння*}\ гідророзриву {14!} {8! \ точка 6!}. \ end {рівняння*}

це те, що ми мали спочатку.