Комбинация

В математике , А комбинация является выбором элементов из коллекции, таким образом, что порядок выбора не имеет значения ( в отличие от перестановок ). Например, для трех фруктов, скажем, яблока, апельсина и груши, из этого набора можно извлечь три комбинации из двух: яблоко и грушу; яблоко и апельсин; или груша и апельсин. Более формально, A K - комбинация из множества S является подмножеством K различных элементов S . Если в наборе n элементов, количество k -комбинаций равно биномиальному коэффициенту

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

которые могут быть написаны с использованием факториалов , как всякий раз , когда , и который равен нулю , когда . Множество всех k -комбинаций множества S часто обозначают .${\ displaystyle \ textstyle {\ frac {n!} {k! (nk)!}}}$${\ Displaystyle к \ Leq п}$${\ displaystyle k> n}$${\ displaystyle \ textstyle {\ binom {S} {k}}}$

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

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

Количество k- комбинаций [ править ]

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

Количество K -combinations из заданного набора S из п элементов часто обозначается в элементарной комбинаторике текстах , или путем вариацией , такие как , , , или даже (последняя форма была стандартной на французском, румынском, русском, китайском ^{[4 ]} и польские тексты ^{[ необходима ссылка ]} ). Однако такое же число встречается во многих других математических контекстах, где оно обозначается (часто читается как « n выбирают k »); в частности, он встречается как коэффициент в биномиальной формуле , отсюда и его название${\ Displaystyle С (п, к)}$${\ displaystyle C_ {k} ^ {n}}$${\ displaystyle {} _ {n} C_ {k}}$${\ displaystyle {} ^ {n} C_ {k}}$${\ displaystyle C_ {n, k}}$${\ displaystyle C_ {n} ^ {k}}$${\ displaystyle {\ tbinom {n} {k}}}$биномиальный коэффициент . Для всех натуральных чисел 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  >  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 -permutations от п , т последовательностей K различных элементов S , в то время как знаменатель дает число таких K -permutations , которые дают тот же K -combination , когда порядок игнорируются.

Когда 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}}}$

Пример подсчета комбинаций [ править ]

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

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

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

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

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

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

Эта связь может быть легко доказана с помощью представления, известного как звезды и столбцы . ^[11]

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

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

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

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

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

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

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

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

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

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

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

Количество k -комбинаций для всех k - это количество подмножеств набора из n элементов. Есть несколько способов узнать, что это число равно 2 ⁿ . В терминах комбинаций, которая представляет собой сумму n- й строки (считая от 0) биномиальных коэффициентов в треугольнике Паскаля . Эти комбинации (подмножества) пронумерованы цифрами 1 набора чисел с основанием 2, считая от 0 до 2 ⁿ  - 1, где каждая позиция цифры - это элемент из набора n .${\displaystyle \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 состоит в том, чтобы перебирать каждый элемент совокупности и на каждом шаге выбирать этот элемент с динамически изменяющейся вероятностью . (см. отбор проб из резервуара ).${\displaystyle {\frac {k-\#{\text{samples chosen}}}{n-\#{\text{samples visited}}}}}$

См. Также [ править ]

Примечания [ править ]

Ссылки [ править ]

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

Внешние ссылки [ править ]

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