Каким количеством можно разложить 12 шариков по 4-м коробкам? коробки пронумерованы, шарики - нет. можно, чтобы шарики были не во всех коробках.

положить k шариков в 1 коробку существует P(k,1) = 1 для любого положить k шариков в 2 ящикa существует P(k,2) = k+1 (кладем 0,1,2,...,k шариков в 1-ю коробку, и, соответственно, k,k-1,k-2,...,0 шариков - во вторую коробку. Всего k+1 возможностей).

 

Также P(0,n) = 1 для любого n (мы можем единственным разложить 0 шариков по n коробкам).

 

Далее, из рекуррентной формулы P(k,n) = P(0,1)P(k,n-1) + P(1,1)*P(k-1,n-1) + P(2,1)*P(k-2,n-1) + ... P(k,1)*P(0,n-1) для P(12,4) и суммирования членов арифметических прогрессий следует наш результат P(12,4) = 455.

 

ответ