Комбинация

Выбор предметов из набора

В математике комбинация — это выбор элементов из множества, состоящего из различных членов, причем порядок выбора не имеет значения (в отличие от перестановок ). Например, даны три фрукта, скажем, яблоко, апельсин и груша, из этого набора можно составить три комбинации из двух: яблоко и груша; яблоко и апельсин; или груша и апельсин. Более формально, k -комбинация множества S представляет собой подмножество из k различных элементов S . Итак, две комбинации идентичны тогда и только тогда, когда каждая комбинация состоит из одних и тех же членов. (Расположение членов в каждом наборе не имеет значения.) Если набор состоит из n элементов, количество k -комбинаций, обозначаемых или , равно биномиальному коэффициенту ${\displaystyle C(n,k)}$ ${\displaystyle C_{k}^{n}}$

$${\displaystyle {\binom {n}{k}}={\frac {n(n-1)\dotsb (n-k+1)}{k(k-1)\dotsb 1}},}$$

который можно записать с использованием факториалов , как всегда , и который равен нулю, когда . Эту формулу можно вывести из того факта, что каждая k -комбинация множества S из n членов имеет перестановки so или . ^[1] Множество всех k -комбинаций множества S часто обозначается . ${\displaystyle \textstyle {\frac {n!}{k!(n-k)!}}}$ ${\displaystyle k\leq n}$ ${\displaystyle k>n}$ ${\displaystyle k!}$ ${\displaystyle P_{k}^{n}=C_{k}^{n}\times k!}$ ${\displaystyle C_{k}^{n}=P_{k}^{n}/k!}$ ${\displaystyle \textstyle {\binom {S}{k}}}$

Комбинация — это комбинация n вещей, взятых k одновременно без повторения . Для обозначения комбинаций, в которых допускается повторение, часто используются термины k -комбинация с повторением, k - мультмножество , ^[2] или k -выбор, ^{[3] . [4]} Если бы в приведенном выше примере можно было иметь два фрукта любого одного вида, то было бы еще 3 2-выбора: один с двумя яблоками, один с двумя апельсинами и один с двумя грушами.

Хотя набор из трех фруктов был достаточно мал, чтобы написать полный список комбинаций, это становится непрактичным по мере увеличения размера набора. Например, покерную комбинацию можно описать как комбинацию из 5 карт ( k  = 5) из колоды из 52 карт ( n  = 52). Все 5 карт в руке различны, и порядок карт в руке не имеет значения. Таких комбинаций 2 598 960, а вероятность случайного выпадения любой руки равна 1/2 598 960.

Количество k -комбинаций

3-элементные подмножества набора из 5 элементов

Число k -комбинаций из данного множества S из n элементов часто обозначается в текстах по элементарной комбинаторике через или такой вариант, как , , или даже ^[5] (последняя форма является стандартной во французском, румынском, русском, Китайские ^{[6] [7]} и польские тексты ^{[ нужна ссылка ]} ). Однако то же число встречается во многих других математических контекстах, где оно обозначается (часто читается как « n выбирает k »); в частности, он встречается как коэффициент в биномиальной формуле , отсюда и его название «биномиальный коэффициент». Для всех натуральных чисел k можно определить сразу соотношением ${\displaystyle C(n,k)}$ ${\displaystyle C_{k}^{n}}$ ${\displaystyle {}_{n}C_{k}}$ ${\displaystyle {}^{n}C_{k}}$ ${\displaystyle C_{n,k}}$ ${\displaystyle C_{n}^{k}}$ ${\displaystyle {\tbinom {n}{k}}}$ ${\displaystyle {\tbinom {n}{k}}}$

$${\displaystyle (1+X)^{n}=\sum _{k\geq 0}{\binom {n}{k}}X^{k},}$$

откуда ясно, что

$${\displaystyle {\binom {n}{0}}={\binom {n}{n}}=1,}$$

и далее,

$${\displaystyle {\binom {n}{k}}=0}$$

для к  >  п .

Чтобы увидеть, что эти коэффициенты подсчитывают k -комбинации из S , можно сначала рассмотреть набор из n различных переменных X _s, помеченных элементами s из S , и разложить произведение по всем элементам  S :

$${\displaystyle \prod _{s\in S}(1+X_{s});}$$

он имеет 2 ⁿ различных членов, соответствующих всем подмножествам S , каждое подмножество дает произведение соответствующих переменных X _s . Теперь установив все X _s равными немаркированной переменной X , так что произведение становится (1 + X ) ⁿ , член для каждой k -комбинации из S становится X ^k , так что коэффициент этой степени в результате равен количество таких k -комбинаций.

Биномиальные коэффициенты можно явно вычислить различными способами. Чтобы получить их все для разложений до (1 + X ) ⁿ , можно использовать (помимо уже приведенных основных случаев) рекурсивное соотношение

$${\displaystyle {\binom {n}{k}}={\binom {n-1}{k-1}}+{\binom {n-1}{k}},}$$

для 0 < k < n , что следует из (1 + X ) ⁿ = (1 + X ) ^{n - 1} (1 + X ) ; это приводит к построению треугольника Паскаля .

Для определения индивидуального биномиального коэффициента практичнее использовать формулу

$${\displaystyle {\binom {n}{k}}={\frac {n(n-1)(n-2)\cdots (n-k+1)}{k!}}.}$$

В числителе указано количество k -перестановок n , т. е. последовательностей из k различных элементов S , а в знаменателе указано количество таких k -перестановок, которые дают одну и ту же k - комбинацию, когда порядок игнорируется.

Когда k превышает n /2, приведенная выше формула содержит множители, общие для числителя и знаменателя, и их сокращение дает соотношение

$${\displaystyle {\binom {n}{k}}={\binom {n}{n-k}},}$$

для 0 ≤ k ≤ n . Это выражает симметрию, которая очевидна из биномиальной формулы, и ее также можно понять в терминах k -комбинаций, взяв дополнение к такой комбинации, которое представляет собой ( n - k ) -комбинацию.

Наконец, есть формула, которая непосредственно демонстрирует эту симметрию и которую легко запомнить:

$${\displaystyle {\binom {n}{k}}={\frac {n!}{k!(n-k)!}},}$$

где н ! обозначает факториал числа n . Она получается из предыдущей формулы путем умножения знаменателя и числителя на ( n − k ) !, поэтому она, безусловно, менее эффективна в вычислительном отношении, чем эта формула.

Последнюю формулу можно понять непосредственно, рассмотрев n ! перестановки всех элементов S . Каждая такая перестановка дает k -комбинацию путем выбора ее первых k элементов. Существует много повторяющихся выборов: любая комбинированная перестановка первых k элементов между собой и последних ( n  −  k ) элементов между собой дает одну и ту же комбинацию; это объясняет деление в формуле.

Из приведенных выше формул следуют соотношения между соседними числами в треугольнике Паскаля во всех трех направлениях:

$${\displaystyle {\binom {n}{k}}={\begin{cases}{\binom {n}{k-1}}{\frac {n-k+1}{k}}&\quad {\text{if }}k>0\\{\binom {n-1}{k}}{\frac {n}{n-k}}&\quad {\text{if }}k<n\\{\binom {n-1}{k-1}}{\frac {n}{k}}&\quad {\text{if }}n,k>0\end{cases}}.}$$

Вместе с основными случаями они позволяют последовательно вычислить соответственно все числа комбинаций из одного и того же множества (строки в треугольнике Паскаля), k -комбинаций множеств растущего размера и комбинаций с дополнением фиксированного размера n - k. . ${\displaystyle {\tbinom {n}{0}}=1={\tbinom {n}{n}}}$

Пример счетных комбинаций

В качестве конкретного примера можно вычислить возможное количество комбинаций из пяти карт из стандартной колоды из пятидесяти двух карт следующим образом: ^[8]

$${\displaystyle {52 \choose 5}={\frac {52\times 51\times 50\times 49\times 48}{5\times 4\times 3\times 2\times 1}}={\frac {311{,}875{,}200}{120}}=2{,}598{,}960.}$$

В качестве альтернативы можно использовать формулу в терминах факториалов и сократить множители в числителе на части множителей в знаменателе, после чего требуется только умножение остальных множителей:

$${\displaystyle {\begin{alignedat}{2}{52 \choose 5}&={\frac {52!}{5!47!}}\\[5pt]&={\frac {52\times 51\times 50\times 49\times 48\times {\cancel {47!}}}{5\times 4\times 3\times 2\times {\cancel {1}}\times {\cancel {47!}}}}\\[5pt]&={\frac {52\times 51\times 50\times 49\times 48}{5\times 4\times 3\times 2}}\\[5pt]&={\frac {(26\times {\cancel {2}})\times (17\times {\cancel {3}})\times (10\times {\cancel {5}})\times 49\times (12\times {\cancel {4}})}{{\cancel {5}}\times {\cancel {4}}\times {\cancel {3}}\times {\cancel {2}}}}\\[5pt]&={26\times 17\times 10\times 49\times 12}\\[5pt]&=2{,}598{,}960.\end{alignedat}}}$$

Другое альтернативное вычисление, эквивалентное первому, основано на записи

$${\displaystyle {n \choose k}={\frac {(n-0)}{1}}\times {\frac {(n-1)}{2}}\times {\frac {(n-2)}{3}}\times \cdots \times {\frac {(n-(k-1))}{k}},}$$

который дает

$${\displaystyle {52 \choose 5}={\frac {52}{1}}\times {\frac {51}{2}}\times {\frac {50}{3}}\times {\frac {49}{4}}\times {\frac {48}{5}}=2{,}598{,}960.}$$

При оценке в следующем порядке: 52 ÷ 1 × 51 ÷ 2 × 50 ÷ 3 × 49 ÷ 4 × 48 ÷ 5 , это можно вычислить, используя только целочисленную арифметику. Причина в том, что при каждом делении промежуточный результат сам по себе является биномиальным коэффициентом, поэтому остатков никогда не возникает.

Использование симметричной формулы в терминах факториалов без выполнения упрощений дает довольно обширный расчет:

$${\displaystyle {\begin{aligned}{52 \choose 5}&={\frac {n!}{k!(n-k)!}}={\frac {52!}{5!(52-5)!}}={\frac {52!}{5!47!}}\\[6pt]&={\tfrac {80,658,175,170,943,878,571,660,636,856,403,766,975,289,505,440,883,277,824,000,000,000,000}{120\times 258,623,241,511,168,180,642,964,355,153,611,979,969,197,632,389,120,000,000,000}}\\[6pt]&=2{,}598{,}960.\end{aligned}}}$$

Перечисление k -комбинаций

Можно перечислить все k -комбинации данного множества S из n элементов в некотором фиксированном порядке, что устанавливает биекцию из интервала целых чисел с набором этих k -комбинаций. Предполагая , что S само упорядочено, например S = { 1, 2, ..., n }, существует две естественные возможности упорядочить его k -комбинации: сначала сравнивая их наименьшие элементы (как на иллюстрациях выше) или сравнивая в первую очередь их самые большие элементы. Последний вариант имеет то преимущество, что добавление нового наибольшего элемента к S не изменит начальную часть перечисления, а просто добавит новые k -комбинации большего набора после предыдущих. Повторяя этот процесс, перечисление можно расширить до бесконечности за счет k -комбинаций все более крупных множеств. Если, кроме того, интервалы целых чисел начинаются с 0, то k -комбинация в данном месте i в перечислении может быть легко вычислена из i , и полученная таким образом биекция известна как комбинаторная система счисления . В вычислительной математике он также известен как «ранг»/«ранжирование» и «отмена рейтинга». ^{[9] [10]} ${\displaystyle {\tbinom {n}{k}}}$

Есть много способов перечислить k комбинаций. Один из способов — просмотреть все двоичные числа меньше 2 ⁿ . Выбирайте те числа, которые имеют k ненулевых бит, хотя это очень неэффективно даже для малых n (например, n = 20 потребует посещения около миллиона чисел, тогда как максимальное количество разрешенных k комбинаций составляет около 186 тысяч для k = 10). Позиции этих 1 бит в таком числе представляют собой конкретную k -комбинацию набора {1,..., n }. ^[11] Другой простой и быстрый способ — отслеживать k порядковых номеров выбранных элементов, начиная с {0 .. k −1} (отсчет от нуля) или {1 .. k } (отсчет от единицы) в качестве первого разрешенного значения. k -комбинации, а затем неоднократно переходя к следующей разрешенной k -комбинации, увеличивая последний номер индекса, если он меньше n -1 (отсчет от нуля) или n (отсчет от единицы), или последний номер индекса x , который меньше номер индекса, следующий за ним, минус один, если такой индекс существует, и сброс номеров индексов после x на { x +1, x +2, ...}.

Количество комбинаций с повторением

k - комбинация с повторениями , или k - мультикомбинация , или мультиподмножество размера k из множества S размера n задается набором из k не обязательно различных элементов S , где порядок не учитывается: две последовательности определяют одно и то же мультимножество, если одно можно получить из другого перестановкой членов. Другими словами, это выборка из k элементов из набора из n элементов, допускающая дубликаты (т. е. с заменой), но не учитывающая разный порядок (например, {2,1,2} = {1,2,2}). Свяжите индекс с каждым элементом S и подумайте об элементах S как о типах объектов, тогда мы сможем обозначить количество элементов типа i в мультиподмножестве. Тогда количество мультиподмножеств размера k будет количеством неотрицательных целых (т. е. допускающих ноль) решений диофантового уравнения : ^[12] ${\displaystyle x_{i}}$

$${\displaystyle x_{1}+x_{2}+\ldots +x_{n}=k.}$$

Если S имеет n элементов, количество таких k -мультиподмножеств обозначается через

$${\displaystyle \left(\!\!{\binom {n}{k}}\!\!\right),}$$

обозначение, аналогичное биномиальному коэффициенту , который считает k -подмножества. Это выражение n multichoose k ^[13] также можно выразить через биномиальные коэффициенты :

$${\displaystyle \left(\!\!{\binom {n}{k}}\!\!\right)={\binom {n+k-1}{k}}.}$$

Эту связь можно легко доказать, используя представление, известное как звезды и полосы . ^[14]

Доказательство

Решение приведенного выше диофантова уравнения может быть представлено звездами , разделителем ( черта ), затем еще звездами, еще одним разделителем и так далее. Общее количество звезд в этом представлении равно k , а количество полосок равно n - 1 (поскольку для разделения на n частей требуется n-1 разделителей). Таким образом, строка из k + n - 1 (или n + k - 1) символов (звездочек и полосок) соответствует решению, если в строке есть k звездочек. Любое решение можно представить, выбрав k из k + n − 1 позиций для размещения звезд и заполнив оставшиеся позиции столбиками. Например, решение уравнения ( n = 4 и k = 10) можно представить в виде ^[15] ${\displaystyle x_{1}}$ ${\displaystyle x_{2}}$ ${\displaystyle x_{1}=3,x_{2}=2,x_{3}=0,x_{4}=5}$ ${\displaystyle x_{1}+x_{2}+x_{3}+x_{4}=10}$

$${\displaystyle \bigstar \bigstar \bigstar |\bigstar \bigstar ||\bigstar \bigstar \bigstar \bigstar \bigstar .}$$

Количество таких строк — это количество способов разместить 10 звезд в 13 позициях, что равно количеству 10-мультиподмножеств набора из 4 элементов. ${\textstyle {\binom {13}{10}}={\binom {13}{3}}=286,}$

Биекция между 3-подмножествами 7-множества (слева) и 3-мультимножествами с элементами из 5-множества (справа).
Это иллюстрирует это . ${\textstyle {\binom {7}{3}}=\left(\!\!{\binom {5}{3}}\!\!\right)}$

Как и в случае с биномиальными коэффициентами, между этими выражениями с множественным выбором существует несколько связей. Например, для , ${\displaystyle n\geq 1,k\geq 0}$

$${\displaystyle \left(\!\!{\binom {n}{k}}\!\!\right)=\left(\!\!{\binom {k+1}{n-1}}\!\!\right).}$$

^[16]

Пример подсчета мультиподмножеств

Например, если у вас есть четыре типа пончиков ( n  = 4) в меню на выбор и вы хотите три пончика ( k  = 3), количество способов выбрать пончики с повторением можно рассчитать как

$${\displaystyle \left(\!\!{\binom {4}{3}}\!\!\right)={\binom {4+3-1}{3}}={\binom {6}{3}}={\frac {6\times 5\times 4}{3\times 2\times 1}}=20.}$$

Этот результат можно проверить, перечислив все 3-мультиподмножества множества S = {1,2,3,4}. Это показано в следующей таблице. ^[17] Во втором столбце перечислены пончики, которые вы на самом деле выбрали, в третьем столбце показаны неотрицательные целочисленные решения уравнения , а в последнем столбце приведены звездочки и столбцы, представляющие решения. ^[18] ${\displaystyle [x_{1},x_{2},x_{3},x_{4}]}$ ${\displaystyle x_{1}+x_{2}+x_{3}+x_{4}=3}$

Количество k -комбинаций для всех k

Количество k -комбинаций для всех k — это количество подмножеств набора из n элементов. Есть несколько способов убедиться, что это число равно 2 ⁿ . С точки зрения комбинаций, , который представляет собой сумму n -й строки (считая от 0) биномиальных коэффициентов в треугольнике Паскаля . Эти комбинации (подмножества) нумеруются 1 цифрой набора чисел с основанием 2 , считая от 0 до 2 ⁿ  - 1, где каждая позиция цифры является элементом из набора n . ${\textstyle \sum _{0\leq {k}\leq {n}}{\binom {n}{k}}=2^{n}}$

Учитывая 3 карты с номерами от 1 до 3, существует 8 различных комбинаций ( подмножеств ), включая пустой набор :

$${\displaystyle |\{\{\};\{1\};\{2\};\{1,2\};\{3\};\{1,3\};\{2,3\};\{1,2,3\}\}|=2^{3}=8}$$

Представление этих подмножеств (в том же порядке) в виде цифр с основанием 2:

• 0 – 000
• 1 – 001
• 2 – 010
• 3 – 011
• 4 – 100
• 5 – 101
• 6 – 110
• 7 – 111

Вероятность: выборка случайной комбинации

Существуют различные алгоритмы выбора случайной комбинации из заданного набора или списка. Отбраковка выборки происходит чрезвычайно медленно при больших размерах выборки. Один из способов эффективного выбора k -комбинации из совокупности размера n — это перебирать каждый элемент совокупности и на каждом шаге выбирать этот элемент с динамически изменяющейся вероятностью (см. Отбор проб из резервуара ). Другой способ — выбрать случайное неотрицательное целое число меньше и преобразовать его в комбинацию, используя комбинаторную систему счисления . ${\textstyle {\frac {k-\#{\text{samples chosen}}}{n-\#{\text{samples visited}}}}}$ ${\displaystyle \textstyle {\binom {n}{k}}}$

Количество способов положить предметы в корзины

Комбинацию также можно рассматривать как выбор двух наборов предметов: тех, которые попадают в выбранную корзину, и тех, которые попадают в невыбранную корзину. Это можно обобщить на любое количество ячеек с ограничением, согласно которому каждый элемент должен помещаться ровно в одну корзину. Количество способов положить предметы в контейнеры определяется мультиномиальным коэффициентом.

$${\displaystyle {n \choose k_{1},k_{2},\ldots ,k_{m}}={\frac {n!}{k_{1}!\,k_{2}!\cdots k_{m}!}},}$$

где n — количество предметов, m — количество корзин, а — количество предметов, которые попадают в ячейку i . ${\displaystyle k_{i}}$

Один из способов понять, почему это уравнение справедливо, — это сначала пронумеровать объекты произвольно от 1 до n и поместить объекты с номерами в первую ячейку по порядку, объекты с номерами — во вторую ячейку по порядку и так далее. Существуют различные нумерации, но многие из них эквивалентны, поскольку имеет значение только набор предметов в корзине, а не их порядок в ней. Каждая комбинированная перестановка содержимого каждой корзины дает эквивалентный способ помещения предметов в корзины. В результате каждый класс эквивалентности состоит из различных нумераций, а число классов эквивалентности равно . ${\displaystyle 1,2,\ldots ,k_{1}}$ ${\displaystyle k_{1}+1,k_{1}+2,\ldots ,k_{2}}$ ${\displaystyle n!}$ ${\displaystyle k_{1}!\,k_{2}!\cdots k_{m}!}$ ${\displaystyle \textstyle {\frac {n!}{k_{1}!\,k_{2}!\cdots k_{m}!}}}$

Биномиальный коэффициент — это особый случай, когда k элементов помещаются в выбранную корзину, а остальные элементы попадают в невыбранную корзину: ${\displaystyle n-k}$

$${\displaystyle {\binom {n}{k}}={n \choose k,n-k}={\frac {n!}{k!(n-k)!}}.}$$

Смотрите также

• Математический портал

• Биномиальный коэффициент
• Комбинаторика
• Блочный дизайн
• График Кнезера
• Список тем перестановок
• Мультисет
• Треугольник Паскаля
• перестановка
• Вероятность
• Подмножество

Примечания

1. Райхл, Линда Э. (2016). «2.2. Подсчет микроскопических состояний». Современный курс статистической физики . ВИЛИ-ВЧ. п. 30. ISBN 978-3-527-69048-0.
2. Мазур 2010, с. 10
3. Райзер 1963, с. 7 также называется неупорядоченным выбором .
4. Когда термин « комбинация» используется для обозначения любой ситуации (как в (Brualdi 2010)) необходимо позаботиться о том, чтобы уточнить, обсуждаются ли наборы или мультимножества.
5. Успенский 1937, с. 18
6. Учебник средней школы для учащихся дневного отделения (обязательно). Книга по математике II B (на китайском языке) (2-е изд.). Китай: Народная образовательная пресса. Июнь 2006 г., стр. 107–116. ISBN 978-7-107-19616-4.
7. 人教版高中数学选修2-3 (Учебник математики, том 2-3, для старших классов средней школы, People's Education Press). Народная образовательная пресса. п. 21.
8. Мазур 2010, с. 21
9. Люсия Моура. «Генерация элементарных комбинаторных объектов» (PDF) . Сайт.uottawa.ca . Архивировано (PDF) из оригинала 9 октября 2022 года . Проверено 10 апреля 2017 г. .
10. «SAGE: Подмножества» (PDF) . Sagemath.org . Проверено 10 апреля 2017 г. .
11. «Комбинации - Кодекс Розетты» . 23 октября 2022 г.^{[ источник, созданный пользователем? ]}
12. Бруальди 2010, с. 52
13. Бенджамин и Куинн 2003, стр. 70
14. В статье «Звезды и полосы (комбинаторика)» роли n и k поменяны местами.
15. Бенджамин и Куинн 2003, стр. 71–72.
16. Бенджамин и Куинн 2003, стр. 72 (идентификатор 145)
17. Бенджамин и Куинн 2003, стр. 71
18. Мазур 2010, с. 10, где звезды и столбцы записаны в виде двоичных чисел, где звезды = 0, а столбцы = 1.

Рекомендации

• Бенджамин, Артур Т .; Куинн, Дженнифер Дж. (2003), Доказательства, которые действительно имеют значение: искусство комбинаторного доказательства , Математические экспозиции Дольчиани 27, Математическая ассоциация Америки, ISBN 978-0-88385-333-7
• Бруальди, Ричард А. (2010), Вводная комбинаторика (5-е изд.), Пирсон Прентис Холл, ISBN 978-0-13-602040-0
• Эрвин Крейциг , Высшая инженерная математика , John Wiley & Sons, INC, 1999.
• Мазур, Дэвид Р. (2010), Комбинаторика: экскурсия , Математическая ассоциация Америки, ISBN 978-0-88385-762-5
• Райзер, Герберт Джон (1963), Комбинаторная математика , Математические монографии Каруса 14, Математическая ассоциация Америки
• Успенский, Джеймс (1937), Введение в математическую вероятность, McGraw-Hill

Внешние ссылки

• Урок Topcoder по комбинаторике
• Код C для генерации всех комбинаций из n элементов, выбранных как k.
• Многие распространенные типы математических задач на перестановки и комбинации с подробными решениями.
• Неизвестная формула для комбинаций, когда выбор может повторяться и порядок не имеет значения.
• Комбинации с повторениями (авторы: Акшата А.Г. и Смита Б) ^{[ постоянная мертвая ссылка ]}
• Задача о броске игральной кости с заданной суммой. Применение комбинаций с повторением для броска нескольких игральных костей.