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

Формула числа сочетаний

Определение числа сочетаний

Пусть имеется $n$ различных объектов и требуется найти число сочетаний из $n$ объектов по $k$. Будем выбирать комбинации из $k$ объектов всеми возможными способами, при этом будем обращать внимание на разный состав комбинаций, но не порядок (он тут не важен, в отличие от размещений).

Например, есть три ($n=3$) объекта {1,2,3}, составляем сочетания по $k=2$ объекта в каждом. Тогда выборки {1,2} и {2,1} — это одно и то же сочетание (так как комбинации отличаются лишь порядком). А всего различных сочетаний из 3 объектов по 2 будет три: {1,2}, {1,3}, {2,3}.

На картинке наглядно проиллюстрировано получение всех возможных сочетаний из 4 различных объектов по 2 (их будет 6, см. калькулятор сочетаний ниже, который даст формулу расчета).

Общая формула, которая позволяет найти число сочетаний из $n$ объектов по $k$ имеет вид:

$$C_n^k=frac{n!}{(n-k)!cdot k!}.$$

Чаще всего сочетания используются в комбинаторных задачах и задачах на расчет вероятности по формуле классической вероятности (см. теорию и примеры).

Смотрите также другие онлайн-калькуляторы

Чтобы вычислить число сочетаний $C_n^k$ онлайн, используйте калькулятор ниже.

Видеоролик о сочетаниях

Не все понятно? Посмотрите наш видеообзор для формулы сочетаний: как использовать Excel для нахождения числа сочетаний, как решать типовые задачи и использовать онлайн-калькулятор.

Расчетный файл из видео можно бесплатно скачать

Полезные ссылки

• Онлайн учебник по теории вероятностей
• Основные формулы комбинаторики
• Примеры решений задач по теории вероятностей
• Заказать свои задачи на вероятность

Решебник по ТВ

Решебник с задачами по комбинаторике и теории вероятностей:

Чтобы работать с теорией вероятностей и статистикой, нужно знать принципы комбинаторики — науки о подсчёте количества всевозможных комбинаций элементов.

• Факториал, правила суммы и произведения
• Перестановка
• Размещение
• Сочетание
• Как использовать перестановки, размещения и сочетания в анализе данных
• Совет эксперта

Самые популярные факториалы

Рекуррентная формула факториала

В этой формуле для получения следующего элемента необходимо знать предыдущий.

Правило суммы — если объект A можно выбрать способами, а объект B можно выбрать способами, то объект «A или B» можно выбрать n + m способами.

Правило произведения — если объект A можно выбрать n способами и после каждого такого выбора объект B можно выбрать m способами, то для пары «A и B» есть n ∙ m вариантов выбора.

Когда важно одно или другое — варианты выбора складываются, когда одно и другое — умножаются. Оба правила позволяют найти, сколько есть вариантов на выбор или, например, сколько есть способов различного расположения предметов.

Получить больше практики по расчёту количества комбинаций можно в модуле «Комбинаторика» тренажёра «Основы математики для цифровых профессий».

Пример. На странице интернет-магазина одежды размещены три футболки. Если поменять их расположение на странице, получится новая перестановка. Сколькими способами можно расположить футболки на странице?

Решение. Три футболки можно расположить на странице способами: P₃ = 3! = 1 ∙ 2 ∙ 3.

Пример. Чтобы выполнить ежедневный квест, игроку нужно принести магу корзину с четырьмя кристаллами разного цвета. Первой необходимо найти корзину, а кристаллы можно сложить в неё в произвольном порядке. Как найти число способов выполнить задание?

Решение. Для выполнения квеста нужно 5 предметов. Корзину всегда находят первой, поэтому её позиция зафиксирована. Порядок сбора 4 оставшихся предметов равен числу перестановок 4 элементов. Всего есть 4! = 24 способа выполнить задание.

В отличие от перестановки, у размещения два параметра: из скольких элементов выбирают (n) и сколько именно выбирают (k).

Порядок выбора элементов важен, когда:

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

Пример. Недалеко от пользователя есть 9 ресторанов. Из них надо выбрать 4, которые будут отображаться на главном экране. Сколько есть способов выбрать рестораны?

Решение. Порядок выбора важен, поэтому выбрать четыре ресторана поможет правило произведения: существует 9 ∙ 8 ∙ 7 ∙ 6 = 3024 способа. Это как раз и есть количество размещений из 9 по 4.

Пример. Сколькими способами можно заполнить спортивный пьедестал из трёх мест, если есть 10 претендентов?

Решение. Выбрать упорядоченную тройку можно 10 ∙ 9 ∙ 8 = 720 способами. По формуле для количества размещений это считается так:

Несколько частных значений для количества сочетаний:

Порядок выбора или расстановки не важен, когда:

● Выбирают несколько элементов одновременно. В учебниках по математике самый частый пример — мешок с шариками, откуда вытаскивают несколько шариков разом.
● Выбирают пару (тройку, группу) для взаимного или равноправного процесса. Например, двух человек для партии в шахматы, две команды для игры в хоккей, три бренда одежды для коллаборации, две точки для соединения отрезком, пять человек для хора.

Пример. Из 9 актёров выбирают четырёх для массовки. Порядок выбранных людей не важен. Сколько есть способов выбрать актёров?

Решение. Чтобы получить количество вариантов выбора 4 из 9 без учёта порядка, нужно

Это количество сочетаний из 9 по 4: сначала нашли количество способов выбрать 4 из 9, потом «склеили» все варианты с одним набором актёров, но разным порядком.

Пример. В сувенирном магазине продаются 6 видов кружек. Сколько есть способов выбрать 4 разные?

Решение. Общее количество перестановок для 6 элементов нужно разделить на (6 – 4)! и ещё на 4!, так как не нужно учитывать ни перестановки «невыбираемых» кружек, ни порядок среди выбираемых.

Поэтому для выбора 4 кружек из 6 есть

А если надо выбрать только 2 разные кружки?

Ответ получился такой же, потому что множители в знаменателе просто поменялись местами.

У этого есть и логическое обоснование: например, выбрать 4 кружки из 6 (и купить их) — это то же самое, что выбрать 2 кружки из 6 (и не купить их).

Аналогично получится, что

В общем виде это свойство выглядит так:

Его называют свойством симметрии для количества сочетаний.

Совет эксперта

Диана Миронидис
Выбирать приходится каждый день: сколько блюд получится сделать из продуктов в холодильнике, сколькими способами можно добраться до работы — ответы на все эти вопросы даёт комбинаторика. Это отличный фундамент для изучения анализа данных и тех областей математики, которые связаны с теорией вероятностей и статистикой. Например, чтобы работать с биномиальным распределением, нужно знать, что такое биномиальные коэффициенты и как их находить. А это как раз комбинаторные задачи.

Автор и методист курсов по математике

Определение числа сочетаний

Пусть имеется $n$ различных объектов. Чтобы найти число сочетаний из $n$ объектов по $k$, будем выбирать комбинации из $m$ объектов все возможными способами, при этом будем обращать внимание на разный состав комбинаций, но не порядок (он тут не важен, в отличие от размещений).

Например, есть три объекта <1,2,3>, составляем сочетания по 2 объекта в каждом. Тогда выборки <1,2>и <2,1>- это одно и то же сочетание (так как комбинации отличаются лишь порядком). А всего различных сочетаний из 3 объектов по 2 будет три: <1,2>, <1,3>, <2,3>.

На картинке наглядно проиллюстрировано получение всех возможных сочетаний из 4 различных объектов по 2 (их будет 6, см. калькулятор сочетаний ниже, который даст формулу расчета).

Общая формула, которая позволяет найти число сочетаний из $n$ объектов по $k$ имеет вид:

Найти сочетания из n по k

Чтобы вычислить число сочетаний $C_n^k$ онлайн, используйте калькулятор ниже.

Видеоролик о сочетаниях

Не все понятно? Посмотрите наш видеообзор для формулы сочетаний: как использовать Excel для нахождения числа сочетаний, как решать типовые задачи и использовать онлайн-калькулятор.

Расчетный файл из видео можно бесплатно скачать

Полезные ссылки

Решебник по ТВ

Решебник с задачами по комбинаторике и теории вероятностей:

Комбинаторика — это раздел математики, в котором изучаются вопросы о том, сколько различных комбинаций, подчиненных тем или иным условиям, можно составить из заданных объектов. Основы комбинаторики очень важны для оценки вероятностей случайных событий, т.к. именно они позволяют подсчитать принципиальновозможное количество различных вариантов развития событий.

Основная формула комбинаторики

Пусть имеется k групп элементов, причем i-я группа состоит из n_i элементов. Выберем по одному элементу из каждой группы. Тогда общее число N способов, которыми можно произвести такой выбор, определяется соотношением N=n₁*n₂*n₃*. *n_k.

Пример 1. Поясним это правило на простом примере. Пусть имеется две группы элементов, причем первая группа состоит из n₁ элементов, а вторая — из n₂ элементов. Сколько различных пар элементов можно составить из этих двух групп, таким образом, чтобы в паре было по одному элементу от каждой группы? Допустим, мы взяли первый элемент из первой группы и, не меняя его, перебрали все возможные пары, меняя только элементы из второй группы. Таких пар для этого элемента можно составить n₂. Затем мы берем второй элемент из первой группы и также составляем для него все возможные пары. Таких пар тоже будет n₂. Так как в первой группе всего n₁ элемент, всего возможных вариантов будет n₁*n₂.

Пример 2. Сколько трехзначных четных чисел можно составить из цифр 0, 1, 2, 3, 4, 5, 6, если цифры могут повторяться?
Решение: n₁=6 (т.к. в качестве первой цифры можно взять любую цифру из 1, 2, 3, 4, 5, 6), n₂=7 (т.к. в качестве второй цифры можно взять любую цифру из 0, 1, 2, 3, 4, 5, 6), n₃=4 (т.к. в качестве третьей цифры можно взять любую цифру из 0, 2, 4, 6).
Итак, N=n₁*n₂*n₃=6*7*4=168.

В том случае, когда все группы состоят из одинакового числа элементов, т.е. n₁=n₂=. n_k=n можно считать, что каждый выбор производится из одной и той же группы, причем элемент после выбора снова возвращается в группу. Тогда число всех способов выбора равно n k . Такой способ выбора в комбинаторики носит название выборки с возвращением.

Пример 3. Сколько всех четырехзначных чисел можно составить из цифр 1, 5, 6, 7, 8?
Решение. Для каждого разряда четырехзначного числа имеется пять возможностей, значит N=5*5*5*5=5 4 =625.

Рассмотрим множество, состоящие из n элементов. Это множество в комбинаторике называется генеральной совокупностью.

Число размещений из n элементов по m

Определение 1. Размещением из n элементов по m в комбинаторике называется любой упорядоченный набор из m различных элементов, выбранных из генеральной совокупности в n элементов.

Пример 4. Различными размещениями из трех элементов <1, 2, 3>по два будут наборы (1, 2), (2, 1), (1, 3), (3, 1), (2, 3),(3, 2). Размещения могут отличаться друг от друга как элементами, так и их порядком.

Число размещений в комбинаторике обозначается A_n m и вычисляется по формуле:

Замечание: n!=1*2*3*. *n (читается: «эн факториал»), кроме того полагают, что 0!=1.

Пример 5. Сколько существует двузначных чисел, в которых цифра десятков и цифра единиц различные и нечетные?
Решение: т.к. нечетных цифр пять, а именно 1, 3, 5, 7, 9, то эта задача сводится к выбору и размещению на две разные позиции двух из пяти различных цифр, т.е. указанных чисел будет:

Определение 2. Сочетанием из n элементов по m в комбинаторике называется любой неупорядоченный набор из m различных элементов, выбранных из генеральной совокупности в n элементов.

Пример 6. Для множества <1, 2, 3>сочетаниями являются <1, 2>, <1, 3>, <2, 3>.

Число сочетаний из n элементов по m

Число сочетаний обозначается C_n m и вычисляется по формуле:

Пример 7. Сколькими способами читатель может выбрать две книжки из шести имеющихся?

Решение: Число способов равно числу сочетаний из шести книжек по две, т.е. равно:

Перестановки из n элементов

Определение 3. Перестановкой из n элементов называется любой упорядоченный набор этих элементов.

Пример 7a. Всевозможными перестановками множества, состоящего из трех элементов <1, 2, 3>являются: (1, 2, 3), (1, 3, 2), (2, 3, 1), (2, 1, 3), (3, 2, 1), (3, 1, 2).

Число различных перестановок из n элементов обозначается P_n и вычисляется по формуле P_n=n!.

Пример 8. Сколькими способами семь книг разных авторов можно расставить на полке в один ряд?

Решение:эта задача о числе перестановок семи разных книг. Имеется P₇=7!=1*2*3*4*5*6*7=5040 способов осуществить расстановку книг.

Обсуждение. Мы видим, что число возможных комбинаций можно посчитать по разным правилам (перестановки, сочетания, размещения) причем результат получится различный, т.к. принцип подсчета и сами формулы отличаются. Внимательно посмотрев на определения, можно заметить, что результат зависит от нескольких факторов одновременно.

Во-первых, от того, из какого количества элементов мы можем комбинировать их наборы (насколько велика генеральная совокупность элементов).

Во-вторых, результат зависит от того, какой величины наборы элементов нам нужны.

И последнее, важно знать, является ли для нас существенным порядок элементов в наборе. Поясним последний фактор на следующем примере.

Пример 9. На родительском собрании присутствует 20 человек. Сколько существует различных вариантов состава родительского комитета, если в него должны войти 5 человек?
Решение: В этом примере нас не интересует порядок фамилий в списке комитета. Если в результате в его составе окажутся одни и те же люди, то по смыслу для нас это один и тот же вариант. Поэтому мы можем воспользоваться формулой для подсчета числа сочетаний из 20 элементов по 5.

Иначе будут обстоять дела, если каждый член комитета изначально отвечает за определенное направление работы. Тогда при одном и том же списочном составе комитета, внутри него возможно 5! вариантов перестановок, которые имеют значение. Количество разных (и по составу, и по сфере ответственности) вариантов определяется в этом случае числом размещений из 20 элементов по 5.

Задачи для самопроверки
1. Сколько трехзначных четных чисел можно составить из цифр 0, 1, 2, 3, 4, 5, 6, если цифры могут повторяться?

2. Сколько существует пятизначных чисел, которые одинаково читаются слева направо и справа налево?

3. В классе десять предметов и пять уроков в день. Сколькими способами можно составить расписание на один день?

4. Сколькими способами можно выбрать 4 делегата на конференцию, если в группе 20 человек?

5. Сколькими способами можно разложить восемь различных писем по восьми различным конвертам, если в каждый конверт кладется только одно письмо?

6. Из трех математиков и десяти экономистов надо составить комиссию, состоящую из двух математиков и шести экономистов. Сколькими способами это можно сделать?

Подсчет числа перестановок, размещений и сочетаний.

Ниже калькулятор, подсчитывающий число перестановок, размещений и сочетаний. Под ним, как водится, ликбез, если кто подзабыл.

Элементы комбинаторики. Перестановки, размещения, сочетания

Итак, есть множество из n элементов.

Вариант упорядочивания данного множества называется перестановкой (permutation).
Например, есть множество, состоящее из 3 элементов — А, В, и С. Пример перестановки — СВА. Число всех перестановок из n элементов:

Пример: Для случая А, В, С число всех перестановок 3! = 6. Перестановки: АВС, АСВ, ВАС, ВСА, САВ, СВА

Если из множества n элементов выбирают m в определенном порядке, это называется размещением (arrangement).
Пример размещения из 3 по 2: АВ или ВА — это два разных размещения. Число всех размещений из n по m

Пример: Для случая А, В, С число всех размещений из 3 по 2 равно 3!/1! = 6. Размещения: АВ, ВА, АС, СА, ВС, СВ

Также бывают размещения с повторениями, как ясно из названия, элементы на определенных позициях могут повторяться.
Число всех размещений из n по m с повторениями:

Пример: Для случая А, В, С число всех размещений из 3 по 2 с повторениями равно 3*3 = 9. Размещения: AA, АВ, АС, ВА, BB, ВС, СА, СВ, CC

Если из множества n элементов выбирают m, и порядок не имеет значения, это называется сочетанием (combination).
Пример сочетания из 3 по 2: АВ. Число всех сочетаний из n по m

Пример: Для случая А, В, С число всех сочетаний из 3 по 2 равно 3!/(2!*1!) = 3. Сочетания: АВ, АС, СВ

Приведем до кучи формулу соотношения между перестановками, размещениями и сочетаниями:

This article is about the mathematics of selecting part of a collection. For other uses, see Combination (disambiguation).

In mathematics, a combination is a selection of items from a set that has distinct members, such that the order of selection does not matter (unlike permutations). For example, given three fruits, say an apple, an orange and a pear, there are three combinations of two that can be drawn from this set: an apple and a pear; an apple and an orange; or a pear and an orange. More formally, a k—combination of a set S is a subset of k distinct elements of S. So, two combinations are identical if and only if each combination has the same members. (The arrangement of the members in each set does not matter.) If the set has n elements, the number of k-combinations, denoted by or , is equal to the binomial coefficient

which can be written using factorials as whenever , and which is zero when . This formula can be derived from the fact that each k-combination of a set S of n members has permutations so or .^[1] The set of all k-combinations of a set S is often denoted by .

A combination is a combination of n things taken k at a time without repetition. To refer to combinations in which repetition is allowed, the terms k-combination with repetition, k-multiset,^[2] or k-selection,^[3] are often used.^[4] If, in the above example, it were possible to have two of any one kind of fruit there would be 3 more 2-selections: one with two apples, one with two oranges, and one with two pears.

Although the set of three fruits was small enough to write a complete list of combinations, this becomes impractical as the size of the set increases. For example, a poker hand can be described as a 5-combination (k = 5) of cards from a 52 card deck (n = 52). The 5 cards of the hand are all distinct, and the order of cards in the hand does not matter. There are 2,598,960 such combinations, and the chance of drawing any one hand at random is 1 / 2,598,960.

Number of k-combinations[edit]

The number of k-combinations from a given set S of n elements is often denoted in elementary combinatorics texts by , or by a variation such as , , , or even (the last form is standard in French, Romanian, Russian, Chinese^[5][6] and Polish texts^{[citation needed]}). The same number however occurs in many other mathematical contexts, where it is denoted by (often read as «n choose k«); notably it occurs as a coefficient in the binomial formula, hence its name binomial coefficient. One can define for all natural numbers k at once by the relation

from which it is clear that

and further,

for k > n.

To see that these coefficients count k-combinations from S, one can first consider a collection of n distinct variables X_s labeled by the elements s of S, and expand the product over all elements of S:

it has 2ⁿ distinct terms corresponding to all the subsets of S, each subset giving the product of the corresponding variables X_s. Now setting all of the X_s equal to the unlabeled variable X, so that the product becomes (1 + X)ⁿ, the term for each k-combination from S becomes X^k, so that the coefficient of that power in the result equals the number of such k-combinations.

Binomial coefficients can be computed explicitly in various ways. To get all of them for the expansions up to (1 + X)ⁿ, one can use (in addition to the basic cases already given) the recursion relation

for 0 < k < n, which follows from (1 + X)ⁿ = (1 + X)^{n − 1}(1 + X); this leads to the construction of Pascal’s triangle.

For determining an individual binomial coefficient, it is more practical to use the formula

The numerator gives the number of k-permutations of n, i.e., of sequences of k distinct elements of S, while the denominator gives the number of such k-permutations that give the same k-combination when the order is ignored.

When k exceeds n/2, the above formula contains factors common to the numerator and the denominator, and canceling them out gives the relation

for 0 ≤ k ≤ n. This expresses a symmetry that is evident from the binomial formula, and can also be understood in terms of k-combinations by taking the complement of such a combination, which is an (n − k)-combination.

Finally there is a formula which exhibits this symmetry directly, and has the merit of being easy to remember:

where n! denotes the factorial of n. It is obtained from the previous formula by multiplying denominator and numerator by (n − k)!, so it is certainly computationally less efficient than that formula.

The last formula can be understood directly, by considering the n! permutations of all the elements of S. Each such permutation gives a k-combination by selecting its first k elements. There are many duplicate selections: any combined permutation of the first k elements among each other, and of the final (n − k) elements among each other produces the same combination; this explains the division in the formula.

From the above formulas follow relations between adjacent numbers in Pascal’s triangle in all three directions:

Together with the basic cases , these allow successive computation of respectively all numbers of combinations from the same set (a row in Pascal’s triangle), of k-combinations of sets of growing sizes, and of combinations with a complement of fixed size n − k.

Example of counting combinations[edit]

As a specific example, one can compute the number of five-card hands possible from a standard fifty-two card deck as:^[7]

Alternatively one may use the formula in terms of factorials and cancel the factors in the numerator against parts of the factors in the denominator, after which only multiplication of the remaining factors is required:

Another alternative computation, equivalent to the first, is based on writing

which gives

When evaluated in the following order, 52 ÷ 1 × 51 ÷ 2 × 50 ÷ 3 × 49 ÷ 4 × 48 ÷ 5, this can be computed using only integer arithmetic. The reason is that when each division occurs, the intermediate result that is produced is itself a binomial coefficient, so no remainders ever occur.

Using the symmetric formula in terms of factorials without performing simplifications gives a rather extensive calculation:

Enumerating k-combinations[edit]

One can enumerate all k-combinations of a given set S of n elements in some fixed order, which establishes a bijection from an interval of integers with the set of those k-combinations. Assuming S is itself ordered, for instance S = { 1, 2, …, n }, there are two natural possibilities for ordering its k-combinations: by comparing their smallest elements first (as in the illustrations above) or by comparing their largest elements first. The latter option has the advantage that adding a new largest element to S will not change the initial part of the enumeration, but just add the new k-combinations of the larger set after the previous ones. Repeating this process, the enumeration can be extended indefinitely with k-combinations of ever larger sets. If moreover the intervals of the integers are taken to start at 0, then the k-combination at a given place i in the enumeration can be computed easily from i, and the bijection so obtained is known as the combinatorial number system. It is also known as «rank»/»ranking» and «unranking» in computational mathematics.^[8][9]

There are many ways to enumerate k combinations. One way is to visit all the binary numbers less than 2ⁿ. Choose those numbers having k nonzero bits, although this is very inefficient even for small n (e.g. n = 20 would require visiting about one million numbers while the maximum number of allowed k combinations is about 186 thousand for k = 10). The positions of these 1 bits in such a number is a specific k-combination of the set { 1, …, n }.^[10] Another simple, faster way is to track k index numbers of the elements selected, starting with {0 .. k−1} (zero-based) or {1 .. k} (one-based) as the first allowed k-combination and then repeatedly moving to the next allowed k-combination by incrementing the last index number if it is lower than n-1 (zero-based) or n (one-based) or the last index number x that is less than the index number following it minus one if such an index exists and resetting the index numbers after x to {x+1, x+2, …}.

Number of combinations with repetition[edit]

A k—combination with repetitions, or k—multicombination, or multisubset of size k from a set S of size n is given by a set of k not necessarily distinct elements of S, where order is not taken into account: two sequences define the same multiset if one can be obtained from the other by permuting the terms. In other words, it is a sample of k elements from a set of n elements allowing for duplicates (i.e., with replacement) but disregarding different orderings (e.g. {2,1,2} = {1,2,2}). Associate an index to each element of S and think of the elements of S as types of objects, then we can let denote the number of elements of type i in a multisubset. The number of multisubsets of size k is then the number of nonnegative integer (so allowing zero) solutions of the Diophantine equation:^[11]

If S has n elements, the number of such k-multisubsets is denoted by

a notation that is analogous to the binomial coefficient which counts k-subsets. This expression, n multichoose k,^[12] can also be given in terms of binomial coefficients:

This relationship can be easily proved using a representation known as stars and bars.^[13]

As with binomial coefficients, there are several relationships between these multichoose expressions. For example, for ,

This identity follows from interchanging the stars and bars in the above representation.^[15]

Example of counting multisubsets[edit]

For example, if you have four types of donuts (n = 4) on a menu to choose from and you want three donuts (k = 3), the number of ways to choose the donuts with repetition can be calculated as

This result can be verified by listing all the 3-multisubsets of the set S = {1,2,3,4}. This is displayed in the following table.^[16] The second column lists the donuts you actually chose, the third column shows the nonnegative integer solutions of the equation and the last column gives the stars and bars representation of the solutions.^[17]

No.	3-multiset	Eq. solution	Stars and bars
1	{1,1,1}	[3,0,0,0]
2	{1,1,2}	[2,1,0,0]
3	{1,1,3}	[2,0,1,0]
4	{1,1,4}	[2,0,0,1]
5	{1,2,2}	[1,2,0,0]
6	{1,2,3}	[1,1,1,0]
7	{1,2,4}	[1,1,0,1]
8	{1,3,3}	[1,0,2,0]
9	{1,3,4}	[1,0,1,1]
10	{1,4,4}	[1,0,0,2]
11	{2,2,2}	[0,3,0,0]
12	{2,2,3}	[0,2,1,0]
13	{2,2,4}	[0,2,0,1]
14	{2,3,3}	[0,1,2,0]
15	{2,3,4}	[0,1,1,1]
16	{2,4,4}	[0,1,0,2]
17	{3,3,3}	[0,0,3,0]
18	{3,3,4}	[0,0,2,1]
19	{3,4,4}	[0,0,1,2]
20	{4,4,4}	[0,0,0,3]

Number of k-combinations for all k[edit]

The number of k-combinations for all k is the number of subsets of a set of n elements. There are several ways to see that this number is 2ⁿ. In terms of combinations, , which is the sum of the nth row (counting from 0) of the binomial coefficients in Pascal’s triangle. These combinations (subsets) are enumerated by the 1 digits of the set of base 2 numbers counting from 0 to 2ⁿ − 1, where each digit position is an item from the set of n.

Given 3 cards numbered 1 to 3, there are 8 distinct combinations (subsets), including the empty set:

Representing these subsets (in the same order) as base 2 numerals:

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

Probability: sampling a random combination[edit]

There are various algorithms to pick out a random combination from a given set or list. Rejection sampling is extremely slow for large sample sizes. One way to select a k-combination efficiently from a population of size n is to iterate across each element of the population, and at each step pick that element with a dynamically changing probability of (see Reservoir sampling). Another is to pick a random non-negative integer less than and convert it into a combination using the combinatorial number system.

Number of ways to put objects into bins[edit]

A combination can also be thought of as a selection of two sets of items: those that go into the chosen bin and those that go into the unchosen bin. This can be generalized to any number of bins with the constraint that every item must go to exactly one bin. The number of ways to put objects into bins is given by the multinomial coefficient

where n is the number of items, m is the number of bins, and is the number of items that go into bin i.

One way to see why this equation holds is to first number the objects arbitrarily from 1 to n and put the objects with numbers into the first bin in order, the objects with numbers into the second bin in order, and so on. There are distinct numberings, but many of them are equivalent, because only the set of items in a bin matters, not their order in it. Every combined permutation of each bins’ contents produces an equivalent way of putting items into bins. As a result, every equivalence class consists of distinct numberings, and the number of equivalence classes is .

The binomial coefficient is the special case where k items go into the chosen bin and the remaining items go into the unchosen bin:

See also[edit]

Notes[edit]

References[edit]

• Benjamin, Arthur T.; Quinn, Jennifer J. (2003), Proofs that Really Count: The Art of Combinatorial Proof, The Dolciani Mathematical Expositions 27, The Mathematical Association of America, ISBN 978-0-88385-333-7
• Brualdi, Richard A. (2010), Introductory Combinatorics (5th ed.), Pearson Prentice Hall, ISBN 978-0-13-602040-0
• Erwin Kreyszig, Advanced Engineering Mathematics, John Wiley & Sons, INC, 1999.
• Mazur, David R. (2010), Combinatorics: A Guided Tour, Mathematical Association of America, ISBN 978-0-88385-762-5
• Ryser, Herbert John (1963), Combinatorial Mathematics, The Carus Mathematical Monographs 14, Mathematical Association of America

External links[edit]

• Topcoder tutorial on combinatorics
• C code to generate all combinations of n elements chosen as k
• Many Common types of permutation and combination math problems, with detailed solutions
• The Unknown Formula For combinations when choices can be repeated and order does not matter
• Combinations with repetitions (by: Akshatha AG and Smitha B)^{[permanent dead link]}
• The dice roll with a given sum problem An application of the combinations with repetition to rolling multiple dice