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

Переходимо спочатку до підрахунку. Хоча це звучить просто, можливо, занадто просто для вивчення, це не так. Коли ми говоримо про підрахунок, то це скорочення для визначення розміру набору, або частіше, розмірів багатьох комплектів, все з чимось спільним, але різними розмірами в залежності від одного або декількох параметрів. Наприклад: скільки результатів можливі при прокатці штампу? Дві кістки? \(n \)кубики? Як було сказано, це неоднозначно: що ми маємо на увазі під «результатом»? Припустимо, кидаємо два кубика, скажімо червону вмирає і зелена вмирає. Чи є «червоний два, зелений три» інший результат, ніж «червоний три, зелений два»? Якщо так, то підраховуємо кількість можливих «фізичних» результатів, а саме 36. Якщо немає, то їх 21. Нас можуть навіть зацікавити просто можливі підсумки, і в цьому випадку є 11 результатів.

Навіть досить просте перше тлумачення спирається на певний ступінь знань про підрахунок; ми спочатку робимо два простих факти явними. Що стосується встановлених розмірів, припустимо, ми знаємо, що набір\(A \) має розмір,\(m \) а набір\(B \) має розмір\(n\). Який розмір\(A \) і\(B \) разом, тобто розмір\(A\cup B\)? Якщо ми знаємо, що\(A \) і не\(B \) мають спільних елементів, то розмір\(A\cup B \) є\(m+n\); якщо вони мають спільні елементи, нам потрібно більше інформації. Проста, але типова проблема такого типу: якщо ми кидаємо дві кістки, скільки способів отримати або 7, або 11? Так як є 6 способів отримати 7 і два способи отримати 11, відповідь є\(6+2=8\). Хоча цей принцип простий, легко забути вимогу про те, щоб два набори були нез'єднаними, а отже, використовувати його, коли обставини є інакше. Цей принцип часто називають принципом додавання.

Цей принцип можна узагальнити: якщо множини\(A_1 \)\(A_n \) наскрізні попарно нез'єднані і мають розміри\(m_1,\ldots m_n\), то розмір\(A_1\cup\cdots\cup A_n=\sum_{i=1}^n m_i\). Це можна довести простим індукційним аргументом.

Чому ми знаємо, не перераховуючи їх усіх, що є 36 результатів, коли кидаються дві кістки? Ми можемо розглядати результати як два окремі результати, тобто результат прокатної штампи номер один та результат прокатної штампи номер два. Для кожного з 6 результатів для першої матриці другий штамп може мати будь-який з 6 результатів, тому загальна сума є\(6+6+6+6+6+6=36\), або більш компактно,\(6\cdot6=36\). Зауважте, що ми дійсно використовуємо принцип додавання тут: set\(A_1 \) - це всі пари\((1,x)\), set\(A_2 \) - всі пари\((2,x)\) і так далі. Це дещо тонше, ніж спочатку очевидно. У цьому простому прикладі результати померти номер два не мають нічого спільного з результатами померти номер один. Ось трохи складніший приклад: скільки способів кинути дві кістки, щоб дві кістки не збігалися? Тобто виключаємо 1-1, 2-2 і так далі. Тут для кожного можливого значення на штампі номер один існує п'ять можливих значень для штампу номер два, але вони є різними п'ятьма значеннями для кожного значення на штампі номер один. Все-таки, тому що всі однакові, результат є\(5+5+5+5+5+5=30\), або\(6\cdot 5=30\). Загалом, тоді, якщо є\(m \) можливості для однієї події, а\(n \) для другої події кількість можливих результатів для обох подій разом дорівнює\(m\cdot n\). Це часто називають принципом множення.

Загалом, якщо\(n \) події мають\(m_i \) можливі результати, бо\(i=1,\ldots,n\), де кожен\(m_i \) не впливає на результати інших подій, то кількість можливих результатів в цілому дорівнює\(\prod_{i=1}^n m_i\). Це теж можна довести індукцією.

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

Скільки результатів можливо, коли три кістки кидаються, якщо жодна з них не може бути однаковою? Перші дві кістки разом мають\(6\cdot 5=30 \) можливі результати, зверху. Для кожного з цих 30 результатів, є чотири можливі результати для третього померти, так що загальна кількість результатів є\(30\cdot 4=6\cdot 5\cdot 4=120\). (Зверніть увагу, що ми вважаємо кістки помітними, тобто кидок 6, 4, 1 відрізняється від 4, 6, 1, тому що перший і другий кубики різні в двох кидках, хоча цифри в наборі однакові.)

Приклад\(\PageIndex{2}\)

Припустимо, блоки під номером 1 через\(n \) знаходяться в бочці; ми витягуємо\(k \) з них, поміщаючи їх в лінію, як ми робимо. Скільки можливих результатів? Тобто, скільки різних домовленостей\(k \) блоків ми можемо побачити?

Це, по суті, те саме, що і в попередньому прикладі: є\(k \) «плями», які потрібно заповнити блоками. Будь-який з\(n \) блоків може з'явитися першим у рядку; потім наступний\(n-1 \) може з'явитися будь-який з решти і так далі. Кількість результатів\(n(n-1)(n-2)\cdots(n-k+1)\), таким чином, за принципом множення. У попередньому прикладі першим «плямою» було вмирати номер один, друге місце було вмирати номер два, третє місце померти номер три, і\(6\cdot5\cdot4=6(6-1)(6-2)\); зверніть увагу, що\(6-2=6-3+1\).

Це досить загальна проблема:

Визначення\(\PageIndex{1}\): Permutations

Кількість перестановок\(n \) речей, зроблених за\(k \) один раз, становить

\[(P(n,k)=n(n-1)(n-2)\cdots(n-k+1)={n!\over (n-k)!}.\nonumber \]

Перестановка деяких об'єктів є певним лінійним упорядкуванням об'єктів; по\(P(n,k) \) суті підраховує дві речі одночасно: кількість способів вибору та порядку\(k \) з\(n \) об'єктів. Корисним особливим випадком є\(k=n\), в якому ми просто підраховуємо кількість способів впорядкування всіх\(n \) об'єктів. Це і є\(n(n-1)\cdots(n-n+1)=n!\). Зверніть увагу, що друга форма\(P(n,k) \) з визначення дає\[\frac{n!}{(n-n)!}=\frac{n!}{0!}.\nonumber\] Це правильно тільки в тому випадку\(0!=1\), якщо, тому ми приймаємо стандартну конвенцію, що це правда, тобто ми \(0! \)визначаємо бути\(1\).

Припустимо, ми хочемо порахувати тільки кількість способів вибору\(k \) елементів з\(n\), тобто нас не хвилює порядок. У прикладі\(\PageIndex{1}\) ми підрахували кількість кидків з трьох кубиків з різними цифрами, показаними. Кістки були помітні, або в певному порядку: перша вмирає, друга і третя. Тепер ми хочемо просто порахувати, скільки комбінацій чисел є, з 6, 4, 1 тепер вважається такою ж комбінацією, як 4, 6, 1.

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

Припустимо, ми повинні були перерахувати всі 120 можливостей у прикладі\(\PageIndex{1}\). Список містить багато результатів, які ми зараз хочемо вважати єдиним результатом; 6, 4, 1 і 4, 6, 1 були б у списку, але не повинні враховуватися окремо. Скільки разів буде з'являтися один результат у списку? Це проблема перестановки: є\(3! \) порядки, в яких можуть з'явитися 1, 4, 6, і всі 6 з них будуть в списку. Фактично кожен результат буде з'являтися в списку 6 разів, так як кожен результат може з'являтися в\(3! \) замовленнях. Отже, список занадто великий на 6 разів; правильний підрахунок для нової проблеми є\(120/6=20\).

Дотримуючись тих самих міркувань загалом, якщо у нас є\(n \) об'єкти, кількість способів їх вибору\(k \) є\(P(n,k)/k!\), оскільки кожна колекція\(k \) об'єктів буде підрахована\(k! \) раз\(P(n,k)\).

Визначення\(\PageIndex{2}\): Permutations

Кількість підмножин розміру набору\(k \) розміру\(n \) (також називається\(n\) -set) є\[C(n,k)=\frac{P(n,k)}{k!}=\frac{n!}{k!(n-k)!}={n\choose k}.\nonumber\] Позначення\(C(n,k) \) використовується рідко; замість цього ми використовуємо\(n\choose k\), вимовляється "\(n \)вибрати\(k\)».

Приклад \(\PageIndex{4}\)

Розглянемо\(n=0,1,2,3\). Легко перерахувати підмножини невеликого\(n\) -set; типовим\(n\) -set є\(\{a_1,a_2,\ldots,a_n\}\). \(0\)-set, а саме порожній набір, має одну підмножину, порожню множину;\(1\) -subset має дві підмножини, порожній набір і\(\{a_1\}\); a\(2\) -subset має чотири підмножини\(\emptyset\)\(\{a_1\}\),\(\{a_2\}\),,\(\{a_1,a_2\}\); і\(3\) -subset має вісім:\(\emptyset\),\(\{a_1\}\),\(\{a_2\}\), \(\{a_3\}\),\(\{a_1,a_2\}\)\(\{a_1,a_3\}\),\(\{a_2,a_3\}\),\(\{a_1,a_2,a_3\}\). З цих списків потім легко обчислити\(n\choose k\):

\[\displaylines{\cr \matrix{ &\rlap{\lower 3pt\hbox{$\Rule{65pt}{0pt}{0.5pt}$}}\cr &0\cr n&1\cr &2\cr &3\cr }\left\vert \matrix{ 0&\lower 3.5pt\hbox{}\rlap{\smash{\raise 1.5em \hbox{$k$}}}1&2&3\cr 1\cr 1&1\cr 1&2&1\cr 1&3&3&1\cr }\right.\cr}\nonumber\]

Ви, напевно, дізнаєтеся ці цифри: це початок трикутника Паскаля. Кожен запис у трикутнику Паскаля генерується шляхом додавання двох записів з попереднього рядка: тієї, що безпосередньо зверху, та тієї, що зверху та ліворуч. Це говорить про те\({n\choose k}={n-1\choose k-1}+{n-1\choose k}\), і дійсно це правда. Щоб зробити цю роботу акуратно, ми приймаємо конвенцію, що\({n\choose k}=0 \) коли\(k< 0 \) або\(k>n\).

Теорема \(\PageIndex{1}\)

\({n\choose k}={n-1\choose k-1}+{n-1\choose k}\).

Доказ

Типовий\(n\) -набір є\(A=\{a_1,\ldots,a_n\}\). Розглянуто два типи підмножин: ті, які містять\(a_n \) і ті, які не містять. Якщо\(k\) -subset\(A \) не містить\(a_n\), то це\(k\) -підмножина\(\{a_1,…,a_{n-1}\}\), і є\(n-1\choose k \) з них. Якщо він містить\(a_n\), то він складається з\(a_n \) і\(k-1 \) елементів\(\{a_1,…,a_{n-1}\}\); оскільки є з\(n-1\choose k-1 \) них, є\(n-1\choose k-1 \) підмножини цього типу. Таким чином, загальна кількість\(k\) -підмножин\(A \) є\({n-1\choose k-1}+{n-1\choose k}\).

Зверніть увагу\(k=0\), що коли\({n-1\choose k-1}={n-1\choose -1}=0\), і коли\(k=n\)\({n-1\choose k}={n-1\choose n}=0\), так що\({n\choose 0}={n-1\choose 0} \) і\({n\choose n}={n-1\choose n-1}\). Ці значення є граничними в трикутнику Паскаля.

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

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

Шість людей повинні сидіти за круглим столом; скільки там розсадження?

Рішення

Незрозуміло, що саме ми маємо на увазі розраховувати тут. Якщо є «спеціальне сидіння», наприклад, може мати значення, хто опиниться на цьому сидінні. Якщо це не має значення, ми дбаємо лише про відносне положення кожної людини. Тоді може мати значення, чи не має значення, чи знаходиться певна людина зліва чи праворуч від іншого. Так що це питання можна трактувати (принаймні) трьома способами. Давайте відповімо на них усім.

По-перше, якщо власне крісла, зайняті людьми, мають значення, то це точно так само, як підкладка шість осіб поспіль: 6 варіантів для сидіння номер один, 5 для сидіння два і так далі, в цілому\(6!\). Якщо стільці не мають значення, то\(6! \) розраховує одне і те ж розташування занадто багато разів, один раз для кожної людини, яка може бути на одному місці. Так що підсумок в даному випадку є\(6!/6=5!\). Інший підхід до цього: оскільки фактичні місця не мають значення, просто покладіть одного з шести людей у крісло. Потім потрібно розташувати решту 5 осіб поспіль, що можна зробити\(5! \) способами. Нарешті, припустимо, все, що нас хвилює, це хто поруч з ким, ігноруючи правого і лівого. Потім попередня відповідь підраховує кожну композицію двічі, один раз для порядку проти годинникової стрілки і один раз за годинниковою стрілкою. Отже, загальна сума є\(5!/2=P(5,3)\).

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

Приклад\(\PageIndex{6}\)

Скільки способів існує, щоб вибудувати шість людей, щоб конкретна пара людей не була сусідньою?

Рішення

Позначають народ\(A \) і\(B\). Загальна кількість замовлень є\(6!\), але це враховує ті замовлення з\(A \) і\(B \) поруч один з одним. Скільки їх там? Подумайте про цих двох людей як про одиницю; скільки способів є, щоб\(AB \) вирівняти блок з іншими 4 людьми? У нас є 5 пунктів, тому відповідь є\(5!\). Кожен з цих порядків відповідає двом різним порядкам, в яких\(A \) і\(B \) є суміжними, залежно від того,\(A \) чи\(B \) є першим. Отже,\(6! \) кількість занадто висока,\(2\cdot5! \) і кількість, яку ми шукаємо, є\(6!-2\cdot 5!=4\cdot5!\).

Дописувачі та атрибуція

• Template:ContribGuichard