В отличие от классического сочетания, где все элементы различны, сочетание с повторениями образует неупорядоченная выборка элементов конечного множества, в которой любой элемент может появляться неопределенно часто и присутствовать необязательно в единственном экземпляре. При этом количество повторений элементов обычно ограничено только длиной сочетания, а различными считаются сочетания, которые отличаются хотя бы одним элементом. Например, выбирая по 4 необязательно различные цифры из набора {1, 2, 3} можно составить следующие 15 сочетаний с повторениями цифр:
Таблица 1    
1 1 1 11 1 1 21 1 1 31 1 2 21 1 2 3
1 1 3 31 2 2 21 2 2 31 2 3 31 3 3 3
2 2 2 22 2 2 32 2 3 32 3 3 33 3 3 3

В общем случае сочетания с повторениями могут быть образованы выборкой из n элементов произвольных типов. Однако им всегда можно сопоставить последовательные натуральные числа от 1 до n. Тогда любое сочетание из m необязательно различных чисел этого диапазона можно записать в форме вектора f, где они расположены их в неубывающем порядке своих величин слева направо:
f = (f1, f2, … fi, … fm); f1 ≤ f2 ≤ … ≤ fi ≤ … ≤ fm .
Естественно, что при такой форме записи любые соседние элементы могут оказаться равными вследствие возможности их неограниченных повторений. Однако каждому вектору сочетания с повторениями f из n элементов по m всегда можно поставить в соответствие вектор сочетания C из (n+m-1) различных элементов по m, который конструируется по элементам вектора f следующим образом:
C = (C1 = f1 + 0, C2 = f2 + 1, …, Ci = fi + i − 1, …, Cm = fm + m − 1).
Ясно, что при любых значениях элементов вектора f элементы вектора C будут гарантированно различны и оказываются строго упорядоченными по возрастанию своих значений в числовом диапазоне от 1 до (n + m - 1):
C1 < C2 < … < Ci < … < Cm .
Наличие взаимно однозначного соответствия между элементами векторов сочетаний f и C позволяет предложить следующий простой метод систематического перечисления сочетаний с повторениями из n элементов по m. Нужно только перечислять, например, в лексиграфическом порядке все C сочетания из (n+m - 1) различных элементов по m, последовательно преобразуя элементы каждого из них в соответствующие элементы сочетаний с повторениями f следующим образом:
f = (f1 = C1 − 0, f2 = C2 − 1, …, fi = Ci − i + 1, …, fm = Cm − m + 1).
В результате образуется последовательность векторов сочетаний с повторениями элементов, которые расположены в порядке, порождаемом перечислением соответствующих сочетаний без повторений элементов. В частности, для того, чтобы получить представленный выше набор сочетаний из трех цифр 1, 2 и 3 с повторениями по 4 цифры, требуется перечислить в лексиграфическом порядке все сочетания без повторений из шести цифр 1, 2, 3, 4, 5 и 6 по 4 цифры, последовательно преобразуя их рассмотренным способом. В частности, следующий пример демонстрируется указанное преобразование для сочетания (1, 3, 4, 6), которое имеет номер 8 в лексиграфическом порядке:
C = (1, 3, 4, 6) −> (1 − 0, 3 − 1, 4 − 2, 6 − 3) = (1, 2, 2, 3) = f.
Рассмотренное взаимно однозначное соответствие между сочетаниями с повторениями и без повторений элементов означает, что их множества равномощны. Поэтому в общем случае число сочетаний с повторениями из n элементов по m определяет число сочетаний без повторений из (n+m-1) элементов по m. Используя одинаковую символику для обозначения чисел сочетаний с повторениями элементов f и чисел сочетаний без повторений элементов C, это равенство можно записать следующим образом:
fmn = f(n, m) = Cmn+m-1 = C(n + m − 1, m) = (n + m − 1)!m!(n − 1)!
Используя это соотношение, несложно проверить, что для рассмотренного выше примера, где n=3 и m=4, число сочетаний с повторения элементов должно быть равно 15, что совпадает с результатом их непосредственного перечисления:
f43 = f(3, 4) = C46 = C(6, 4) = 6!4!2!= 15
Следует отметить, что в отличие от классического варианта, значения параметров сочетания с повторениями n и m непосредственно не связаны между собой, поэтому f(n,m)>0 при любой комбинации их положительных значений. Соответствующие граничные условия определяются из равенств между значениями (n+m-1) и (n-1) или (n+m-1) и m. Очевидно, такие равенства возможны только в случаях m=0 и n=1. Поэтому граничные значения сочетаний с повторением элементов имеют следующий вид:
f0n = fm1 = f(n, 0) = f(1, m) = 1
Также должно быть вполне очевидно, что если m равно 1, то никакие повторения элементов невозможны и, следовательно, при любом положительном значении n>0 будет справедливо следующее равенство:
f(n, 1) = f1n = C(n, 1) = C1n = n
Кроме того, для чисел сочетаний с повторениями при любых положительных значениях n и m справедливо следующее рекуррентное соотношение, которое похоже на тождество сложения для чисел сочетаний без повторений элементов:
fmn = fm-1n + fmn-1 или f(n, m) = f(n, m−1) + f(n−1, m).
Собственно, оно и превращается в указанное тождество сложения при формальной подстановке соответствующих чисел сочетаний без повторений в его левую и правую части:
Cmn+m-1 = Cm-1n+m-2 + Cmn +m-1
Рассмотренное рекуррентное соотношение можно использовать для эффективного определения чисел сочетаний с повторениями элементов, когда важно исключить трудоемкие операции вычисления факториальных произведений и заменить их более простыми операциями сложения. При этом для вычисления значения f(n,m) необходимо только применять данное рекуррентное соотношение до получения суммы слагаемых вида f(1,m) и f(i,1), где i принимает значениями в диапазоне от n до 1. По определению величины таких слагаемых равны 1 и i, соответственно. Следующий пример иллюстрирует использование данной техники преобразований для случая n=3 и m=4:
f43 = f33 + f42 = f23 + 2f32 + f43 = f13 + 3f22 + 2f31 + f41 = f13 + 3f21 + 3f12 + 2f31 + f41 = 15