Комбинация

редактировать

Выбор элементов из коллекции

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

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

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

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

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

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

Содержание

1 Количество k-комбинаций
- 1.1 Пример подсчета комбинаций
- 1.2 Перечисление k-комбинаций
2 Количество комбинаций с повторением
- 2.1 Пример подсчета мультиподмножеств
3 Количество k-комбинаций для всех k
4 Вероятность: выборка случайной комбинации
5 См. Также
6 Примечания
7 Ссылки
8 Внешние ссылки

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

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

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

(1 + X) n = ∑ к ≥ 0 (NK) Икс К, {\ Displaystyle (1 + X) ^ {п} = \ сумма _ {к \ geq 0} {\ binom {n} {k}} X ^ {k},}

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

, из которого видно, что

(n 0) = (nn) = 1, {\ displaystyle {\ binom {n} {0}} = {\ binom {n} {n}} = 1,}

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

и далее,

(nk) = 0 {\ displaystyle {\ binom {n} {k}} = 0}

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

для k>n.

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

∏ s ∈ S (1 + X s); {\ displaystyle \ prod _ {s \ in S} (1 + X_ {s});}

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

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

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

(nk) = (n - 1 k - 1) + (n - 1 к), {\ displaystyle {\ binom {n} {k}} = {\ binom {n-1} {k-1}} + {\ binom {n-1} {k}},}

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

для 0 < k < n, which follows from (1 + X) = (1 + X)(1 + X); this leads to the construction of треугольник Паскаля.

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

(nk) = n (n - 1) (n - 2) ⋯ (n - k + 1) к! {\ displaystyle {\ binom {n} {k}} = {\ frac {n (n-1) (n-2) \ cdots (n-k + 1)} {k!}}}

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

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

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

(nk) = (nn - k), {\ displaystyle { \ binom {n} {k}} = {\ binom {n} {nk}},}

{\ displaystyle {\ binom {n} {k}} = {\ binom {n} {nk}},}

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

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

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

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

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

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

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

(nk) = {(nk - 1) n - k + 1 k, если k>0 (n - 1 k) nn - k, если k < n ( n − 1 k − 1) n k if n, k>0 {\ 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} {nk}} и \ quad {\ text {if}} k 0 \ end {ases}}

{\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} {nk}} \ quad {\ text {if}} k <n\\{\binom {n-1}{k-1}}{\frac {n}{k}}\quad {\text{if }}n,k>0 \ end {cases}}

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

Пример счетного гребня inations

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

(52 5) = 52 × 51 × 50 × 49 × 48 5 × 4 × 3 × 2 × 1 = 311 875 200 120 = 2 598 960. {\ 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.}

{52 \ выберите 5} = {\ frac {52 \ times 51 \ раз 50 \ раз 49 \ раз 48} {5 \ раз 4 \ раз 3 \ раз 2 \ раз 1}} = {\ frac {311 {,} 875 {,} 200} {120}} = 2 {,} 598 {,} 960.

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

(52 5) = 52! 5! 47! = 52 × 51 × 50 × 49 × 48 × 47! 5 × 4 × 3 × 2 × 1 × 47! = 52 × 51 × 50 × 49 × 48 5 × 4 × 3 × 2 = (26 × 2) × (17 × 3) × (10 × 5) × 49 × (12 × 4) 5 × 4 × 3 × 2 = 26 × 17 × 10 × 49 × 12 = 2 598 960. {\ displaystyle {\ begin {alignat} {2} {52 \ choose 5} = {\ frac {52!} {5! 47!}} \\ [5pt] = {\ frac {52 \ times 51 \ раз 50 \ раз 49 \ раз 48 \ раз {\ 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 {alignat}}}

{\ displaystyle {\ begin {alignat} {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 {alignat}} }

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

(nk) = (n - 0) 1 × (n - 1) 2 × (n - 2) 3 × ⋯ × (n - (k - 1)) k, {\ displaystyle {п \ выбрать k} = {\ frac {(n-0)} {1}} \ times {\ frac {(n-1)} {2}} \ times {\ frac {(n-2)} {3}} \ times \ cdots \ times {\ frac {(n- (k-1))} {k}},}

{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 5) = 52 1 × 51 2 × 50 3 × 49 4 × 48 5 = 2,598,960 {\ 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 \ 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, это можно вычислить, используя только целочисленную арифметику. Причина в том, что когда происходит каждое деление, получаемый промежуточный результат сам по себе является биномиальным коэффициентом, поэтому остатки никогда не возникают.

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

(52 5) = n! к! (п - к)! = 52! 5! (52-5)! = 52! 5! 47! = 80, 658, 175, 170, 943, 878, 571, 660, 636, 856, 403, 766, 975, 289, 505, 440, 883, 277, 824, 000, 000, 000, 000 120 × 258, 623, 241, 511, 168, 180, 642, 964, 355, 153, 611, 979, 969, 197, 632, 389, 120, 000, 000, 000 = 2 598 960. {\ displaystyle {\ begin {align} {52 \ choose 5} = {\ frac {n!} {k! (nk)!}} = {\ 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,120,611,355,000} {120 \ times 258,623,241,511,168,180,642,120,611,355,000} {120 \ times 258,623,241,511,168,180,642,611,355,000} \,} 960. \ end {align}}}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

★ ★ ★ | ★ ★ | | Оо, оо, оо, оо, оо {\ displaystyle \ bigstar \ bigstar \ bigstar | \ bigstar \ bigstar || \ bigstar \ bigstar \ bigstar \ bigstar \ bigstar}

\ bigstar \ bigstar \ bigstar | \ bigstar \ bigstar || \ bigstar \ bigstar \ bigstar \ bigstar \ bigstar

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

Взаимное соответствие между 3-мя подмножествами 7-набора (слева) и 3-мультимножествами с элементами из 5-набора (справа).. Это иллюстрирует, что

(7 3) = (( 5 3)) {\ displaystyle \ textstyle {7 \ choose 3} = \ left (\! \! {5 \ choose 3} \! \! \ Right)}

\ textstyle {7 \ select 3 } = \ left (\! \! {5 \ выберите 3} \! \! \ right)

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

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

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

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

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

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

((4 3)) = (4 + 3 - 1 3) = (6 3) = 6 × 5 × 4 3 × 2 × 1 = 20. {\ 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. }

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

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

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

Количество k-комбинаций для всех k - это количество подмножеств набора из n элементов. Есть несколько способов узнать, что это число равно 2. С точки зрения комбинаций, $∑ 0 ≤ k ≤ n (nk) = 2 n {\ displaystyle \ sum _ {0 \ leq {k} \ leq {n} } {\ binom {n} {k}} = 2 ^ {n}}$ $\ 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 {\ Displaystyle | \ {\ {\}; \ {1 \}; \ {2 \}; \ {1,2 \}; \ {3 \}; \ {1,3 \}; \ {2,3 \}; \ {1,2,3 \} \} | = 2 ^ {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 - это перебирать каждый элемент совокупности и на каждом шаге выбирать этот элемент с динамически изменяющейся вероятностью $k - # выборок выбрано n - # выборок посетил {\ displaystyle {\ frac {k - \ # {\ text {samples selected}}} {n - \ # {\ text {samples selected}}}}}$ ${\ displaystyle {\ frac {k - \ # {\ text {samples selected}}} {n - \ # {\ text {посещенные образцы }}}}}$ . (см. отбор проб из пласта ).

См. Также

Портал математики

Примечания

Ссылки

Бенджамин, Артур Т. ; Куинн, Дженнифер Дж. (2003), Доказательства, которые действительно важны: Искусство комбинаторного доказательства, The Dolciani Mathematical Expositions 27, The Mathematical Association of America, ISBN 978-0-88385-333-7
Brualdi, Ричард А. (2010), Введение в комбинаторику (5-е изд.), Pearson Prentice Hall, ISBN 978-0-13-602040-0
Эрвин Крейсциг, Advanced Engineering Mathematics, John Wiley Sons, INC, 1999.
Mazur, David R. (2010), Combinatorics: A Guided Tour, Mathematical Ассоциация Америки, ISBN 978-0-88385-762-5
Райзер, Герберт Джон (1963), Комбинаторная математика, Математические монографии Каруса 14, Математическая ассоциация Америки

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

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