Классификации сочетаний с повторениями

Рассмотрим m -сочетания с повторениями, составленные из элементов n+ 1 типов, скажем букв a, b, c, …,x. Число таких сочетаний равно

.

Разобьем все сочетания на классы, отнеся к k -му классу сочетания, в которые k раз входит буква a. Остальные m–k мест могут быть заняты оставшимися буквами b,c, …, x, число которых равно n. Поэтому в k- й класс входит столько сочетаний, сколько можно составить (m-k)-сочетаний с повторениями из элементов n типов, то есть

.