Sunday, October 07, 2007

Distribution with restrictions [S]

When I wrote this post I made a typo mistake. Here is what I intended.
*******************************************************************
Problem: Enumerate the number of solutions of the equation



such that for every

Lets suppose so that at least one solution is assured.
*************************
The flipside of this is simple. How many solutions with each

? Easy.. put balls in each of the boxes, a priori. Now distribute rest in :)
***********************************************************************
solution: Suppose

Let

(i) only one of the entries has size

and rest are less than that. Now we get the regular inclusion-exclusion expression

(ii) For two,

and so on.

Summing up individually we get



Hence the number of solutions with the given restriction is


1 comment:

talegari (ತಾಳೆಗರಿ) said...

The final simple form hints a easy solution without all this circus ... anybody can think of a easy proof ?