Комбинация

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

В математике комбинация — это выбор элементов из множества , имеющего различные элементы, так что порядок выбора не имеет значения (в отличие от перестановок ). Например, если даны три фрукта, скажем, яблоко, апельсин и груша, то из этого множества можно составить три комбинации из двух: яблоко и груша; яблоко и апельсин; или груша и апельсин. Более формально, 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 членов имеет перестановки так или . ^[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.

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

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}$$

для к  >  n .

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

Существует много способов перечислить k- комбинации. Один из способов — отслеживать k -индексы выбранных элементов, начиная с {0 .. k −1} (с нуля) или {1 .. k } (с единицы) как первой разрешенной k- комбинации. Затем многократно переходите к следующей разрешенной k -комбинации, увеличивая наименьший индексный номер, для которого это не создало бы два равных индексных номера, в то же время сбрасывая все меньшие индексные номера до их начальных значений.

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

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

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

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

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

Решение приведенного выше диофантова уравнения можно представить звездами , разделителем ( чертой ), затем еще звездами, еще одним разделителем и так далее. Общее количество звезд в этом представлении равно k , а количество черт равно n - 1 (так как для разделения на n частей требуется n-1 разделителей). Таким образом, строка из k + n - 1 (или n + k - 1) символов (звезд и черт) соответствует решению, если в строке есть k звезд. Любое решение можно представить, выбрав k из k + n − 1 позиций для размещения звезд и заполнив оставшиеся позиции чертами. Например, решение уравнения ( n = 4 и k = 10) можно представить как ^[14] ${\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).}$$Эта идентичность следует из перестановки звезд и полос в представлении выше. ^[15]

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

Например, если в меню есть четыре вида пончиков ( 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}. Это отображено в следующей таблице. ^[16] Во втором столбце перечислены пончики, которые вы фактически выбрали, в третьем столбце показаны неотрицательные целые решения уравнения , а в последнем столбце даны звездочки и полоски, представляющие решения. ^[17] ${\displaystyle [x_{1},x_{2},x_{3},x_{4}]}$ ${\displaystyle x_{1}+x_{2}+x_{3}+x_{4}=3}$

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

Число 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. Подсчет микроскопических состояний". Современный курс статистической физики . WILEY-VCH. стр. 30. ISBN 978-3-527-69048-0.
2. Мазур 2010, стр. 10
3. Райзер 1963, стр. 7 также упоминается как неупорядоченный выбор .
4. Когда термин «комбинация» используется для обозначения любой из ситуаций (как в (Brualdi 2010)), необходимо с осторожностью прояснить, обсуждаются ли множества или мультимножества.
5. Успенский 1937, стр. 18
6. Учебник для старшей школы для студентов очной формы обучения (обязательно) Математика Книга II B (на китайском языке) (2-е изд.). Китай: People's Education Press. Июнь 2006. С. 107–116. ISBN 978-7-107-19616-4.
7. 人教版高中数学选修2-3 (Учебник математики, том 2-3, для старших классов средней школы, People's Education Press). Народная образовательная пресса. п. 21.
8. Мазур 2010, стр. 21
9. Lucia Moura. «Generating Elementary Combinatory Objects» (PDF) . Site.uottawa.ca . Архивировано (PDF) из оригинала 9 октября 2022 г. . Получено 10 апреля 2017 г. .
10. "SAGE : Подмножества" (PDF) . Sagemath.org . Получено 10 апреля 2017 г. .
11. Бруальди 2010, стр. 52
12. Бенджамин и Куинн 2003, стр. 70
13. В статье Звезды и полосы (комбинаторика) роли n и k поменяны местами.
14. Бенджамин и Куинн 2003, стр. 71–72.
15. Бенджамин и Куинн 2003, стр. 72 (идентификация 145)
16. Бенджамин и Куинн 2003, стр. 71
17. Мазур 2010, стр. 10, где звездочки и полоски записаны как двоичные числа, причем звездочки = 0, а полоски = 1.

Ссылки

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

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

• Учебник Topcoder по комбинаторике
• Множество распространенных типов математических задач на перестановку и комбинацию с подробными решениями.
• Неизвестная формула для комбинаций, когда выбор может повторяться, а порядок не имеет значения.
• Задача о броске игральных костей с заданной суммой. Применение комбинаций с повторением к броску нескольких игральных костей.