Комбинация

Эта статья о математике выбора части коллекции. Чтобы узнать о других значениях, см. Комбинация (значения) .

«КОМБИН» перенаправляется сюда. Чтобы узнать о других значениях, см. Комбинация (значения) .

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

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

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

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

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

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

Основная статья: Биномиальный коэффициент

«КОМБИН» перенаправляется сюда. Чтобы узнать о других значениях, см. Комбинация (значения) .

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

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

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

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

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

и далее

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

для к > п .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

$${\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}}.$$

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

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

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

$${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.$$

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

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

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

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

который дает

$${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 , это можно вычислить, используя только целочисленную арифметику. Причина в том, что при каждом делении промежуточный результат сам по себе является биномиальным коэффициентом, поэтому остатков никогда не возникает.

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

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

Есть много способов перечислить 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 как о типах объектов, тогда мы можем позволить $x_{i}$обозначают количество элементов типа i в мультиподмножестве. Тогда количество мультиподмножеств размера k будет количеством неотрицательных целых (поэтому допускающих ноль) решений диофантового уравнения :

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

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

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

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

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

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

показывать

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

A solution of the above Diophantine equation can be represented by $x_{1}$ stars, a separator (a bar), then $x_{2}$ more stars, another separator, and so on. The total number of stars in this representation is k and the number of bars is n - 1 (since a separation into n parts needs n-1 separators). Thus, a string of k + n - 1 (or n + k - 1) symbols (stars and bars) corresponds to a solution if there are k stars in the string. Any solution can be represented by choosing k out of k + n − 1 positions to place stars and filling the remaining positions with bars. For example, the solution $x_{1}=3,x_{2}=2,x_{3}=0,x_{4}=5$ of the equation $x_{1}+x_{2}+x_{3}+x_{4}=10$ (n = 4 and k = 10) can be represented by

$$\bigstar \bigstar \bigstar |\bigstar \bigstar ||\bigstar \bigstar \bigstar \bigstar \bigstar .$$

The number of such strings is the number of ways to place 10 stars in 13 positions, ${\textstyle {\binom {13}{10}}={\binom {13}{3}}=286,}$ which is the number of 10-multisubsets of a set with 4 elements.

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

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

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

Это тождество следует из замены звезд и полос в приведенном выше представлении.

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

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

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

Нет.	3-мультисет	уравнение решение	Звезды и бары
1	{1,1,1}	[3,0,0,0]	$\bigstar \bigstar \bigstar |||$
2	{1,1,2}	[2,1,0,0]	$\bigstar \bigstar |\bigstar ||$
3	{1,1,3}	[2,0,1,0]	$\bigstar \bigstar ||\bigstar |$
4	{1,1,4}	[2,0,0,1]	$\bigstar \bigstar |||\bigstar$
5	{1,2,2}	[1,2,0,0]	$\bigstar |\bigstar \bigstar ||$
6	{1,2,3}	[1,1,1,0]	$\bigstar |\bigstar |\bigstar |$
7	{1,2,4}	[1,1,0,1]	$\bigstar |\bigstar ||\bigstar$
8	{1,3,3}	[1,0,2,0]	$\bigstar ||\bigstar \bigstar |$
9	{1,3,4}	[1,0,1,1]	$\bigstar ||\bigstar |\bigstar$
10	{1,4,4}	[1,0,0,2]	$\bigstar |||\bigstar \bigstar$
11	{2,2,2}	[0,3,0,0]	$|\bigstar \bigstar \bigstar ||$
12	{2,2,3}	[0,2,1,0]	$|\bigstar \bigstar |\bigstar |$
13	{2,2,4}	[0,2,0,1]	$|\bigstar \bigstar ||\bigstar$
14	{2,3,3}	[0,1,2,0]	$|\bigstar |\bigstar \bigstar |$
15	{2,3,4}	[0,1,1,1]	$|\bigstar |\bigstar |\bigstar$
16	{2,4,4}	[0,1,0,2]	$|\bigstar ||\bigstar \bigstar$
17	{3,3,3}	[0,0,3,0]	$||\bigstar \bigstar \bigstar |$
18	{3,3,4}	[0,0,2,1]	$||\bigstar \bigstar |\bigstar$
19	{3,4,4}	[0,0,1,2]	$||\bigstar |\bigstar \bigstar$
20	{4,4,4}	[0,0,0,3]	$|||\bigstar \bigstar \bigstar$

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

См. Также: Биномиальный коэффициент § Сумма строк коэффициентов.

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

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

$$|\{\{\};\{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}}}}}$(см. Отбор проб из резервуара ). Другой способ — выбрать случайное неотрицательное целое число меньше $\textstyle {\binom {n}{k}}$ и преобразуем ее в комбинацию, используя комбинаторную систему счисления .

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

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

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

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

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

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

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

См. также

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

Ссылки

• Бенджамин, Артур Т .; Куинн, Дженнифер Дж. (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 по комбинаторике
• Многие распространенные типы математических задач на перестановки и комбинации с подробными решениями.
• Неизвестная формула для комбинаций, когда выбор может повторяться и порядок не имеет значения .
• Задача о броске игральной кости с заданной суммой. Применение комбинаций с повторением для броска нескольких игральных костей.