How would you divide $x$ number of things among $y$ people but each person can only have $z$ max things?

151 Views Asked by At

I've heard of using a strategy to solve problems like find the ways to divide $x$ things among $y$ people where you solve by saying you have $x$ stars and put $y-1$ bars in between to divide between them and so you'd do $\binom{x + y -1}{y-1}$. If there's a minimum amount, you need to to simply subtract the minimum of each person. So if each person has to have $1$ minimum, you'd subtract $x$ from $x+y-1$.

What if there was a maximum? Say each person could only have $5$ maximum? Is there a generalized way to solve this with variable $z$?

1

There are 1 best solutions below

0
On BEST ANSWER

Normally, you may have to apply inclusion-exclusion, but at times, there is a neat short cut. I shall illustrate with an example.

Suppose you have to distribute $18$ apples to $4$ people, with no one getting more than $6\;$ then applying inclusion-exclusion

The answer will work out to $\binom{21}3 -\binom4 1\binom{14}3 + \binom4 2\binom7 3 = 84$

[All ways - at least one person getting $7$ + at least two persons getting $7$]

The intuitive shortcut is to imagine $6$ apples each already given, ie $24$ apples in toto, and take out $24-18$ = $6$ apples in any which way, thus $\binom{6+4-1}{4-1} = 84$

Of course, you can only do this if there are enough apples to be thus taken out !