7
$\begingroup$

It has been explained here many times that $n$ indistinguishable sweets can be distributed to $r$ children in ${n+r-1\choose r-1}$ ways. Given two such allocations (multisets) $x=(x_i)_{1\leq i\leq r}$ and $y=(y_i)_{1\leq i\leq r}$ we can look at their discrepancy $$\sum_{i=1}^r|x_i-y_i|=:2d\geq0$$ (an even number). The question is: How many pairs $(x,y)$ of multisets of cardinality $n$ over the set $[r]$ are there, having given discrepancy $2d>0$?

This question (in a somewhat different disguise) has been asked here a few days ago, but unfortunately got closed before anybody had time to come up with a hint, let alone a full solution. I'm convinced this is a novel and challenging problem, off the standard stars and bars route. Therefore I dare to post it again, this time with the added context of sweets $\ldots$

$\endgroup$
0

1 Answer 1

5
$\begingroup$

Any pair of allocations can be represented in a diagram by charting the original allocation of $n$ sweets to $k$ children, colouring $d$ sweets blue (to represent the fact that they have been taken away), and then distributing another $d$ sweets to children without blue sweets. Here is an example for $n=31,\ k=12,\ d=4$. The white sweets represent the minimum number a child receives, over both allocations.

Distribution of 31 sweets to 12 children, with four coloured blue; and then another four brown sweets distributed to children without blue sweets

There are $\tbinom{n-d+k-1}{k-1}$ ways that the white sweets could be distributed.

Suppose that $i$ of the children receive at least one of the $d$ new sweets, where $0<i<k$. There are $\tbinom{d-1}{i-1}$ ways that could happen. Then the $d$ blue sweets must be among the other $k-i$ children, although some may have none. There are $\tbinom{d+k-i-1}{d}$ ways that could happen.

Therefore the number of pairs of allocations with discrepancy $2d$ is:

$$\binom{n-d+k-1}{k-1}{\large\sum}_{i=1}^{\min(k-1,\ d)}\binom{k}{i}\binom{d-1}{i-1}\binom{d+k-i-1}{d}$$

For example, if $n=5$ and $k=3$ the number of pairs with discrepancy $0,2,4,6,8,10$ is: $$21, 90, 120, 108, 72, 30$$ which sums to $\tbinom72^2$ as expected.

$\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.