Сочетанием называется неупорядоченная выборка элементов конечного множества с фиксированным числом и без повторений элементов. Различные сочетания должны отличаться хотя бы одним элементом, а порядок расположения элементов не имеет значения. Например, из множества всех гласных латинских букв {AEIOU} можно составить 10 различных сочетаний по 3 буквы, образуя следующие неупорядоченные тройки:

Интересно отметить, что из тех же пяти букв можно получить также 10 различных сочетаний, если комбинировать их по 2 буквы, составив следующие неупорядоченные пары:

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

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

C(n, m) ~ Cmn~

Независимо от формы обозначения, число сочетаний из n элементов по m элементов можно определить по следующим мультипликативной и факториальной формулам:

C(n, m) = Сmn= = n(n − 1) … (n − m + 1)m(m−1) … 1=n!m!(n − m)!

Несложно проверить, что результат вычислений по этим формулам совпадает с результатами рассмотренного выше примера с сочетаниями гласных латинских буквам. В частности, при n=5 и m=3 вычисления по этим формулам дадут следующий результат:

C(5, 3) = С35= = 5.4.33.2.1=5!3!(5 − 3)!=10

В общем случае все формулы для числа сочетаний имеют комбинаторный смысл и справедливы при любых целочисленных значениях n и m, таких, что n > m > 0. Если m > n и m < 0, то число сочетаний равно 0, так как в этом случае основное множество из n элементов вообще не имеет подмножеств мощности m:

Кроме того, полезно помнить следующие граничные числа сочетаний, которые легко проверить непосредственной подстановкой в мультипликативную и факториальную формулы:

Следует также отметить, что мультипликативная формула остается справедливой, даже когда n является отрицательным целым и действительным числом, но значение m по-прежнему должно быть целым. При этом для всех отрицательных целых значений n важнейшим считают случай, когда n равно (-1):

Некоторые нецелые значения n также могут оказаться полезны. Например, при отрицательном дробном значении n равном (-1/2) и любом натуральном значении m получается следующее соотношение:

Похожее соотношение можно получить для случая положительного вещественного значения n равного (+1/2). Причем соотношения для случаев, когда n равно (-1/2) и (+1/2), оказываются связаны следующим образом при любом натуральном значении m:

Все рассмотренные соотношения для дробных и отрицательных значений n получаются из мультипликативной формулы и формально справедливы, но не имеют никакой комбинаторной интерпретации. Однако обычно в комбинаторной практике рассматриваются задачи, которые связаны с определением чисел сочетаний при натуральных значениях n > m > 0.