Counting pairs of multisets with prescribed discrepancy

Question

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$

Answer 1

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.

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.