2

Number of ways $5$ people can take stones from a bag containing $5$ stones where the first persons may take up to $3$ stones ($0$ is allowed), second can take up to as many as the first person took, third may take up to as many as the second person took, and so on.

My solutions is brute force, just curious of better ways to approach the problem.

$ \sum_{a=0}^{3} \sum_{b=0}^{min(3,5-a,a)} \sum_{c=0}^{min(3,5-(a+b),b)} \sum_{d=0}^{min(3,5-(a+b+c),c} \sum_{e=0}^{min(3,5-(a+b+c+d),d))} \binom{5}{a,b,c,d,e} $

Roby5
  • 4,287
kporter
  • 123

1 Answers1

3

As the total number of stones taken does not have to be $5$, we need to find the number of ways of taking exactly $5$ stones in the manner described, the number of ways of taking exactly $4$ stones in the same manner, and so on (down to zero stones).

But in each of the above cases, we are merely counting the number of partitions of that integer, with the restriction that the greatest part be strictly smaller than $4$. An easy way to see this is to observe that that if the people choose stones according to the given condition and arrange them in rows, we get a Ferrers diagram of a (restricted) partition of the total number of stones chosen, and conversely, each Ferrers diagram also specifies a unique way for the people to pick the stones.

So now, we just need to count the total number of partitions of $k$, $0 \le k \le 5$, with the greatest part less than or equal to $3$, and add these up for $k = 0, \ldots, 5$. The generating function for the number of partitions with largest part of size less than or equal to $3$ is \begin{equation*} \dfrac{1}{(1-x)(1-x^2)(1-x^3)} \end{equation*}

Expand this, and add up the coefficients of $x^0$ (constant term), $x, x^2, \ldots, x^5$. This will be the answer.

M. Vinay
  • 9,004