Обозначим через
количество сочетаний с повторениями (в терминологии
sergey zhukov —
шаров выбирается из урны с шарами
типов). При каждом таком сочетании либо последний
-й тип не используется, либо можно считать, что последний выбранный шар ровно
-го типа, то есть
. Отсюда формула выводится по индукции, ну и нужна база
,
при
.
А ещё можно через производящие функции. Так как
— это количество представлений
в виде суммы
натуральных чисел (0 считается натуральным), то
. Дальше раскрываем по биному Ньютона,
, ну и
. Только формулу с факториалами надо творчески понимать при
.