0
$\begingroup$

I've encountered a problem, wchich sounds like this:

Mike has 25 roses and 5 friends. He wants to give the roses to his friends, in a way, that no friend is left without a rose, and no friend gets more than 7 roses. How many ways are there to distribute the roses among his friends? All roses are indistinguishable

I've managed to write this problem down as $$x_1 + x_2 + x_3 + x_4 + x_5 = 25 $$ where $$ 1 \leq x_1, x_2,x_3,x_4,x_5 \leq 7$$

I struggle to approach the problem

$\endgroup$
5
  • 1
    $\begingroup$ en.wikipedia.org/wiki/Partition_(number_theory) $\endgroup$ – jimjim Feb 4 '20 at 10:23
  • $\begingroup$ "Go and look again at the roses. You will understand now that yours is unique in all the world." ("The Little Prince", Chapter 21). If you're going to treat roses as indistinguishable, you should at least make this unrealistic assumption explicit :-) $\endgroup$ – joriki Feb 4 '20 at 10:26
  • $\begingroup$ @joriki yes, the roses are not unique $\endgroup$ – user747644 Feb 4 '20 at 10:27
  • $\begingroup$ @Arjang that isn't very helpful. If I were able to undestand this problem reading this wikipedia article, I wouldn't post this problem here $\endgroup$ – user747644 Feb 4 '20 at 10:43
  • $\begingroup$ It also happens to be the wrong article on the wrong concept. That would be the relevant concept if the friends were also indistinguishable. $\endgroup$ – joriki Feb 4 '20 at 10:47
1
$\begingroup$

There are various near-duplicates (Number of ways to distribute $n$ objects into $k$ distinguishable groups with constraints on the max size of each group?, calculate all combination of indistinguishable objects, Number of solutions of $x_1+x_2+\dots+x_k=n$ with $x_i\le r$, Formula to get total combination possibilities, coefficient on $s^{14}$ in generating function), but none of them really matches well enough to close this one with reference to it, so I’ll work this out specifically for your case.

If you have $k$ bins with capacities $a_j$, the number of ways to distribute $n$ balls over them can be found by inclusion–exclusion as explained in more detail at Balls in Bins with Limited Capacity:

We have $k$ constraints with indices in $[1,k]$. There are

$$ \binom{n+k-1-\sum_{j\in S}\left(a_j+1\right)}{k-1} $$

integer solutions that violate the constraints with indices in $S$. Thus by inclusion–exclusion there are

$$ \sum_{S\subseteq[1,k]}(-1)^{|S|}\binom{n+k-1-\sum_{j\in S}\left(a_j+1\right)}{k-1} $$

integer solutions that violate none of the constraints (where, contrary to the usual convention, the binomial coefficients are to be taken as zero if the upper index is negative).

Now in your case, all capacities are the same, and you have the additional constraint that each friend must get at least one rose. You can reduce this to the case allowing empty bins by giving each friend a rose, reducing each friend’s capacity by $1$ and reducing the total number of roses by the number of friends. Thus you now want to distribute $20$ roses to $5$ friends, with no friend getting more than $6$ roses. There are $\binom5m$ ways to select a subset $S$ of $m$ friends, so by the above the count is

\begin{eqnarray} \sum_{m=0}^5(-1)^m\binom5m\binom{20+5-1-m(6+1)}{5-1} &=& \binom50\binom{24}4-\binom51\binom{17}4+\binom52\binom{10}4 \\ &=& 1\cdot10626-5\cdot2380+10\cdot210 \\ &=& 826\;. \end{eqnarray}

$\endgroup$
1
  • 1
    $\begingroup$ Thanks! It seems clear now $\endgroup$ – user747644 Feb 4 '20 at 12:13
0
$\begingroup$

If you give each of five friends $p_i\in[1\,..\,7]$ roses you define a quintuple $(p_1,\ldots,p_5)$. On the other hand, if you multiply out the polynomial $$g(x):=(x+x^2+\ldots+x^7)^5$$ distributively you obtain $7^5$ terms, namely for each such quintuple a term $$x^{p_1}x^{p_2}\cdots x^{p_5}=x^{p_1+p_2+\ldots+p_5}\ .$$ If all these terms are collected in the usual way we obtain the form $g(x)=\sum_{n\geq0} a_nx^n$, where $a_n$ is equal to the number of terms with $p_1+\ldots+p_5=n$. It follows that we have to determine the number $a_{25}$. To this end we write $$\eqalign{g(x)&=x^5(1+x+\ldots+x^6)^5=x^5\left({1-x^7\over1-x}\right)^5\cr &=x^5(1-5x^7+10x^{14}+\ {\rm higher\ terms})\ \sum_{j=0}^\infty{5+j-1\choose j}x^j\ .\cr}$$ It is now easy to see that $$a_{25}={24\choose20}-5{17\choose13}+10{10\choose6}=826\ .$$

$\endgroup$

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.