Question

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

Answer 1

Способов положить k шариков в 1 коробку существует P(k,1) = 1 для любого k.

 

Способов положить 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.

 

Ответ: 455 способами.