1.6: Вибір з повторенням

Більшість проблем з перестановкою та комбінацією ми бачили вибір підрахунку, зробленого без повторення, як коли ми запитали, скільки кидків трьох кубиків є, в яких кожна матриця має різне значення. Винятком стала найпростіша задача, запитуючи загальну кількість результатів при киданні двох або трьох кубиків, просте застосування принципу множення. Типові проблеми перестановки та комбінації можуть бути інтерпретовані з точки зору малювання куль з коробки, і неявно або явно правило полягає в тому, що куля, витягнута з коробки, залишається поза коробкою. Якщо замість цього кожен м'яч повертається до коробки після запису жеребкування, ми отримуємо проблему, по суті ідентичну загальній проблемі з кубиками. Наприклад, якщо є шість куль, пронумерованих 1—6, і ми малюємо три кулі з заміною, то кількість можливих результатів дорівнює\(6^3\). Інший варіант завдання не замінює м'яч після кожного розіграшу, але дозволяє кілька «однакових» кульок опинитися в коробці. Наприклад, якщо коробка містить 18 куль під номером 1—6, по три з кожним номером, то можливі результати, коли три кулі витягуються і не повертаються до коробки, знову\(6^3\). Якщо ж намальовані чотири кульки, проблема стає іншою.

Інший, можливо, більш математичний, спосіб словосполучення таких проблем - введення ідеї мультимножини. Мультимножина схожа на набір, за винятком того, що елементи можуть з'являтися більше одного разу. Якщо\(\{a,b\}\) і\(\{b,c\}\) є звичайними наборами, ми говоримо, що союз\(\{a,b\}\cup\{b,c\}\) є\(\{a,b,c\}\), ні\(\{a,b,b,c\}\). Якщо ми інтерпретуємо їх як мультимножини, однак, ми пишемо\(\{a,b,b,c\}\) і вважаємо це іншим, ніж\(\{a,b,c\}\). Щоб відрізнити мультимножини від множин, і скоротити вираз в більшості випадків, ми використовуємо номер повторення з кожним елементом. Наприклад, ми напишемо\(\{a,b,b,c\}\) як\(\{1\cdot a,2\cdot b,1\cdot c\}\). \(\{1\cdot a,1\cdot b,1\cdot c\}\)Написуючи, ми підкреслюємо, що це мультимножина, хоча жоден елемент не з'являється більше одного разу. Ми також дозволяємо включати елементи нескінченну кількість разів, позначені\(\infty\) для числа повторення, як\(\{\infty\cdot a, 5\cdot b, 3\cdot c\}\).

Взагалі кажучи, проблеми, в яких числа повторень нескінченні, легше, ніж ті, що стосуються скінченних чисел повторення. З огляду на мультимножину\(A=\{\infty\cdot a_1,\infty\cdot a_2,\ldots,\infty\cdot a_n\}\), скільки перестановок елементів довжини\(k\) існує? Тобто, скільки послідовностей\(x_1,x_2,\ldots,x_k\) можна сформувати? Це легко: відповідь є\(n^k\).

Тепер розглянемо комбінації мультимножини, тобто підмножини: З огляду на мультимножини, скільки підмножин заданого розміру вона має? Ми говоримо, що\(A\) мультимножина є підмножиною,\(B\) якщо число повторення кожного елемента\(A\) менше або дорівнює його номеру повторення в\(B\). Наприклад,\(\{20\cdot a, 5\cdot b, 1\cdot c\}\) це підмножина\(\{\infty\cdot a, 5\cdot b, 3\cdot c\}\). Мультимножина є кінцевою, якщо вона містить лише кінцеву кількість різних елементів, а числа повторення є кінцевими. Припустимо ще раз, що\(A=\{\infty\cdot a_1,\infty\cdot a_2,\ldots,\infty\cdot a_n\}\); скільки скінченних підмножин має розмір\(k\)? Це спочатку здається досить складним, але поставити в належному вигляді виходить знайома проблема. Уявіть, що у нас є\(k+n-1\) «порожні пробіли», ось так:

\[\underline{\qquad}\quad \underline{\qquad}\quad\underline{\qquad}\quad\underline{\qquad}\quad\underline{\qquad}\quad\underline{\qquad}\quad\underline{\qquad}\quad\underline{\qquad}\quad\cdots\quad\underline{\qquad}\quad\underline{\qquad}\quad\underline{\qquad}\quad\underline{\qquad}\nonumber\]

Тепер розміщуємо\(n-1\) маркери в деякі з цих плям:

\[\underline{\wedge}\quad \underline{\qquad}\quad\underline{\wedge}\quad\underline{\qquad}\quad\underline{\qquad}\quad\underline{\qquad}\quad\underline{\wedge}\quad\underline{\qquad}\quad\cdots\quad\underline{\qquad}\quad\underline{\qquad}\quad\underline{\wedge}\quad\underline{\qquad}\nonumber\]

Це однозначно визначає підмножину: заповнити всі пропуски до першого\(\land\) з\(a_1\), до другого з\(a_2\) і так далі:

\[\underline{\wedge}\quad \underline{a_2}\quad\underline{\wedge}\quad\underline{a_3}\quad\underline{a_3}\quad\underline{a_3}\quad\underline{\wedge}\quad\underline{a_4}\quad\cdots\quad\underline{a_{n-1}}\quad\underline{a_{n-1}}\quad\underline{\wedge}\quad\underline{a_n}\nonumber\]

Так що цей візерунок відповідає мультімножини\(\{1\cdot a_2,3\cdot a_3,\ldots, 1\cdot a_n\}\). Заповнення маркерів\(\land\) усіма можливими способами дає всі можливі підмножини розміру\(k\), тому існують\(k+n-1\choose n-1\) такі підмножини. Зверніть увагу, що це те саме, що\(k+n-1\choose k\); важка частина на практиці полягає в тому, щоб пам'ятати, що\(-1\) йде з\(n\), а не на\(k\).

\[\bullet\quad\bullet\quad\bullet\nonumber\]

Підсумовуючи високі моменти до цих пір: Кількість перестановок\(n\) речей,\(k\) зроблених за раз без заміни, є\( P(n,k)=n!/(n-k)!\); кількість перестановок\(n\) речей,\(k\) зроблених за раз із заміною, є\( n^k\). Кількість комбінацій\(n\) речей, взятих\(k\) за один раз без заміни, дорівнює\({n\choose k}\); кількість комбінацій\(n\) речей, взятих\(k\) за раз з заміною, дорівнює\({k+n-1 \choose k}\).

\[\bullet\quad\bullet\quad\bullet\nonumber\]

Якщо\(A=\{m_1\cdot a_1, m_2\cdot a_2,\ldots,m_n\cdot a_n\}\), подібні питання можуть бути досить важкими. Ось простіший особливий випадок: Скільки перестановок\(A\) мультимножини існує? Тобто, скільки послідовностей складаються з\(m_1\) копій\(a_1\),\(m_1\) копій\(a_2\) і так далі? Ця проблема піддається перерахунку: припустимо, для початку ми можемо розрізнити різні копії кожного\(a_i\); вони можуть бути пофарбовані по-різному\(a_1\), наприклад: червоний\(a_1\), синій тощо. Тоді у нас звичайний набір з\(M=\sum_{i=1}^n m_i\) елементами і\(M!\) перестановками. Тепер, якщо ми ігноруємо кольори, щоб усі копії\(a_i\) виглядали однаково, ми виявимо, що ми перерахували бажані перестановки. Перестановки з, скажімо,\(a_1\) пунктами в однакових позиціях виглядають однаково, як тільки ми ігноруємо кольори\(a_1\) s. Скільки вихідних перестановок мають цю властивість? \(m_1!\)Перестановки з'являться однаковими, як тільки ми ігноруємо кольори\(a_1\) елементів, оскільки в заданих\(m_1!\)\(m_1\) позиціях є\(a_1\) перестановки кольорових s. Отже, після викидання дублікатів кількість решти перестановок є\(M!/m_1!\) (припускаючи, що інші\(a_i\) все ще помітні). Тоді той самий аргумент застосовується до\(a_2\) s: є\(m_2!\) копії кожної перестановки, коли ми ігноруємо кольори\(a_2\) s, тому існують\( {M!\over m_1!\,m_2!}\) різні перестановки. Продовжуючи таким чином, ми бачимо, що кількість різних перестановок після ігнорування всіх кольорів є\[\frac{M!}{ m_1!\,m_2!\cdots m_n!}.\nonumber\]

Це часто пишуть\[{M\choose m_1\;\;m_2\;\ldots\; m_n},\nonumber\] під назвою багатономіальний коефіцієнт. Тут другий рядок містить\(n\) окремі записи, а не один запис продукту. Зверніть увагу, що якщо\(n=2\) це\[\label{eq:1}\eqalignno{ {M\choose m1\;\;m2}&= {M!\over m_1!\,m_2!}={M!\over m_1!\,(M-m_1)!}={M\choose m_1}.}\nonumber\]

Це легко побачити комбінаторно: з огляду на те, що\(\{m_1\cdot a_1, m_2\cdot a_2\}\) ми можемо сформувати перестановку, вибравши\(m_1\) місця, які будуть\(a_1\) займані, заповнивши інші\(m_2\) місця с\(a_2\). Кількість перестановок - це кількість способів вибору\(m_1\) локацій, яке є\(M\choose m_1\).

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

Скільки рішень\( x_1+x_2+x_3+x_4=20\) має в невід'ємних цілих числах? Тобто скільки 4-кортежів\((m_1,m_2,m_3,m_4)\) невід'ємних цілих чисел є розв'язками рівняння?

Рішення

Ми фактично вирішили цю проблему: Скільки підмножин розміром 20 є з мультимножини\(\{\infty\cdot a_1,\infty\cdot a_2,\infty\cdot a_3,\infty\cdot a_4\}\)? Підмножина розміром 20 має вигляд\(\{m_1\cdot a_1,m_2\cdot a_2,m_3\cdot a_3,m_4\cdot a_4\}\) де\(\sum m_i=20\), і вони знаходяться в 1-1 відповідності з безліччю 4-кортежів\((m_1,m_2,m_3,m_4)\) невід'ємних цілих чисел, таких що\(\sum m_i=20\). Таким чином, кількість рішень є\(20+4-1\choose 20\). Це міркування застосовується в цілому: кількість рішень\[\sum_{i=1}^n x_i = k\nonumber\] є\[{k+n-1\choose k}.\nonumber\]

Це відразу говорить про деякі узагальнення: замість загальної кількості розв'язків нам може знадобитися кількість розв'язків зі змінними\(x_i\) в певних діапазонах, тобто ми можемо вимагати це\(m_i\le x_i\le M_i\) для деяких нижніх і верхніх меж\(m_i\) і\(M_i\).

Кінцеві верхні межі може бути важко мати справу; якщо ми цього вимагаємо\(0\le x_i\le M_i\), це те саме, що підрахунок підмножин\(\{M_1\cdot a_1,M_2\cdot a_2,\ldots,M_n\cdot a_n\}\). Нижні межі легше боротися.

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

Знайти кількість рішень\( x_1+x_2+x_3+x_4=20\) з\(x_1\ge 0\),,\(x_2\ge 1\)\(x_3\ge 2\),\(x_4\ge -1\).

Рішення

Ми можемо перетворити це на початкову задачу, в якій всі нижні межі 0. Розв'язки, які ми прагнемо порахувати\(y_1=x_1\),\(y_2=x_2-1\) є розв'язками цього зміненого рівняння:\[ x_1+(x_2-1)+(x_3-2)+(x_4+1)=18.\nonumber\] Якщо ми встановимо\(y_4=x_4+1\),,, і, то\((x_1,x_2,x_3,x_4)\) є розв'язком цього рівняння тоді і тільки тоді, коли\((y_1,y_2,y_3,y_4)\) це рішення\[ y_1+y_2+y_3+y_4=18,\nonumber\] і, крім того, межі на\(x_i\) задовольняються\(y_3=x_3-2\) якщо і тільки якщо\(y_i\ge 0\). Оскільки кількість розв'язків останнього рівняння дорівнює\(18+4-1\choose 18\), це також кількість розв'язків вихідного рівняння.

Автори та атрибуція

• Template:ContribGuichard