Практическое использование мультипликативной и факториальной формул для определения числа сочетаний при произвольных значениях n и m оказывается мало продуктивно из-за экспоненциального роста факториальных произведений их числителя и знаменателя. Даже при сравнительно небольших величинах n и m эти произведения часто превосходят возможности представления целых чисел в современных вычислительных и программных системах. При этом их величины оказываются значительно больше результирующего значения числа сочетаний, которое может быть сравнительно невелико. Например, число сочетаний из n=10 по m=8 элементов равно всего 45. Однако чтобы найти это значение по факториальной формуле нужно сначала вычислить значительно большие величины 10! в числителе и 8! в знаменателе как показано в следующем примере:
С(10,8)=С810==10!8!(10 − 8)!=362880040320.2=45
Чтобы исключить трудоемкие операции обработки больших величин, для определения числа сочетаний можно воспользоваться различными рекуррентными соотношениями, которые непосредственно следуют из мультипликативной или факториальной формул. В частности, из мультипликативной формулы числа сочетаний может быть получено следующее рекуррентное соотношение, которое позволяет выносить за знак числа сочетаний отношение его нижнего и верхнего индексов:
С810=nm=nmСmn-1
Наконец, сохранение неизменным нижнего индекса обеспечивает следующее рекуррентное соотношение, которое получается из факториальной формулы числа сочетаний умножением ее числителя и знаменателя на (n-m+1) и последующей группировки
Сmn=(n − (m − 1))m(n!(m − 1)!(n − (m − 1))!)=(n − m + 1)mСm-1n
После элементарных преобразований все три полученные рекуррентные соотношения можно представить в следующих видах:
(n-m)Сmn=nСmn-1; mСmn=nСm-1n-1; (n-m+1)Сm-1n=mСmn
Если теперь сложить левые и правые части двух первых формул и сократить результат на n, то получится рекуррентное соотношение, которое называется тождеством сложения для чисел сочетаний:
Сmn=Сmn-1+Сm-1n-1
Тождество сложения предоставляет основное рекуррентное правило для эффективного определения числа сочетаний при больших значениях n и m, так как оно позволяет заменить операции умножения в факториальных произведениях более простыми операциями сложения, причем для меньших чисел сочетаний. В частности, используя тождество сложения, теперь несложно определить число сочетаний из n=10 по m=8 элементов, которое рассматривалось выше, выполнив следующую последовательность рекуррентных преобразований
C810 = C89+C79 = C88+C78+C78+C68 =…= C88+2C77+3C66+4C55+5C44+6C33+7C22+8C11+9C01=45
Кроме того, из тождества сложения можно вывести несколько полезных соотношений для вычисления конечных сумм, в частности, формулу суммирования по нижнему индексу, которая имеет следующий вид:
Cm0+Cm1+Cm2+...+Cmk+...+Cmn=Cm+1n+1
Такое соотношение получается, если в тождестве сложения разворачивать рекуррентность по слагаемому с наибольшим верхним индексом, пока его нижний индекс больше 0. Следующий численный пример иллюстрирует указанный процесс рекуррентных преобразований:
C24 = C23+C13 = C22+C12+C13=C21+C11+C12+C13=(C20=0)+C10+C11+C12+C13=C10+C11+C12+C13
Формула суммирования по нижнему индексу часто применяется для вычисления суммы степеней натуральных чисел. В частности, полагая m=1, по этой формуле легко найти сумму n первых чисел натурального ряда:
0 + 1 + 2 + … + n =C10+C11+C12+C13+...+C1n=C2n+1=(n+1)n2
Еще один полезный вариант формулы суммирования можно получить, если разворачивать рекуррентность для тождества сложения по слагаемому с наименьшим верхним индексом. Следующий численный пример иллюстрирует этот вариант рекуррентных преобразований:
C35 = C34+C24 = C34+C23+C13=C34+C23+C12+C02=C34+C23+C12+C01+(C-11=0)
В общем случае в результате таких преобразований получается сумма чисел сочетаний, оба индекса которых отличаются на единицу от соседних слагаемых, а разность индексов сохраняет постоянную величину (в рассмотренном примере она также равна единице). Таким образом, получается следующая формула суммирования по обоим индексам чисел сочетаний:
C0r+C1r+1+C2r+2+...+Ckr+k...+Cnr+n=Cnr+n+1
Кроме рекуррентных соотношений и формул суммирования, которые были рассмотрены выше, в комбинаторном анализе получено много других полезных тождеств для чисел сочетаний. Наиболее важным среди них является тождество симметрии, которое получается взаимной заменой m на (n-m) в факториальной формуле числа сочетаний и имеет следующий вид:
Cmn=Cn-mn
Тождество симметрии имеет очевидный комбинаторный смысл, так как, определяя количество вариантов выбора m элементов из n, оно одновременно устанавливает число сочетаний для остальных (n-m) элементов, которые не были выбраны. В этом можно легко убедиться на следующем примере, сопоставив числа сочетаний из n=5 элементов по m=2 и по (n-m)=5-2
C25=C5-25=C35=10
В обширной литературе по комбинаторному анализу можно найти много других полезных тождеств для чисел сочетаний. Но сейчас будет достаточно упомянуть только одно тождество, которое обеспечивает следующее упрощение произведений чисел сочетаний:
CmnCkm=CknCm-kn-k
Числа и тождества сочетаний широко используются в различных областях современной вычислительной математики. Однако наиболее известное их применение связано с биномом Ньютона и треугольником Паскаля.