2
$\begingroup$

I have $N$ indistinguishable objects and $K$ distinguishable boxes and I need to calculate ways how i can put this objects to boxes that no box has more than $X$ and not less than $Y$ objects.

I found topic How many ways to distribute $n$ objects into $r$ boxes so that each box have at least $1$ (but no more than $k$) objects? with recurrent formula but it's too slow and takes too much time with not little numbers.

Is there another way to calculate it?

$\endgroup$
0
$\begingroup$

Notice that what you want eventually reduces to distributing $N-((K-1)X) $ balls over $K $ boxes, with no box having more than $Y-X+1 $ balls, so it is reduced to the same problem you linked.

Distributing $N $ balls over $K $ boxes with a minimum of 1 ball and a maximum of $M $ is the same as distributing $N-M $ balls over $K $ boxes with each box having, at most, $M-1$ balls.

This means your problem is equivalent to distributing $N-(KX) $ balls over $K $ boxes with no box having more than $Y-X $ balls.

If you find a better solution to that problem then you find a better solution for yours.

I guess you could use the Principle of Inclusion-Exclusion to impose your restrictions but it is also not a closed formula. And although you can make it non-recursive, it is recursive in nature.

$\endgroup$
  • $\begingroup$ Thank you! Can you also tell or link how to count boxes with no box having more than $X$ objects? $\endgroup$ – Vladislav Nov 20 '16 at 18:41
  • $\begingroup$ P.S. We can calc it with this formula math.stackexchange.com/questions/89417/… But it takes too much time again ;( $\endgroup$ – Vladislav Nov 20 '16 at 18:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.