Contar pares de multisectas con discrepancia prescrita

Question

Se ha explicado aquí muchas veces que $n$ indistinguible dulces puede ser distribuido a $r$ de los niños en ${n+r-1\choose r-1}$ maneras. Dadas dos de tales asignaciones (multisets) $x=(x_i)_{1\leq i\leq r}$ $y=(y_i)_{1\leq i\leq r}$ podemos ver su discrepancia $$\sum_{i=1}^r|x_i-y_i|=:2d\geq0$$ (un número). La pregunta es: ¿cuántos pares de $(x,y)$ de multisets de cardinalidad $n$ sobre el conjunto de $[r]$, después de haber dado discrepancia $2d>0$?

Esta pregunta (de una forma un tanto diferente disfraz) se ha pedido aquí hace un par de días, pero, lamentablemente, se cerró antes de que nadie tenía tiempo para llegar a una pista, y mucho menos una solución completa. Estoy convencido de que este es un nuevo y desafiante problema, fuera de la norma estrellas y bares de la ruta. Por lo tanto, me atrevo a publicar de nuevo, esta vez con el añadido de un contexto de dulces $\ldots$

Answer 1

Cualquier par de asignaciones pueden ser representados en un diagrama en la cartografía de la asignación original de $n$ dulces a $k$ de los niños, la coloración $d$ dulces azul (para representar el hecho de que se han quitado) y, a continuación, la distribución de otro $d$ dulces a los niños sin azul dulces. Aquí es un ejemplo para $n=31,\ k=12,\ d=4$. Los blancos dulces representan el número mínimo que recibe un niño, en las dos asignaciones.

Hay $\tbinom{n-d+k-1}{k-1}$ formas en que los blancos dulces podrían ser distribuidos.

Supongamos que $i$ de los niños reciben al menos una de las $d$ nueva dulces, donde $0<i<k$. Hay $\tbinom{d-1}{i-1}$ formas en que podría suceder. A continuación, el $d$ azul dulces debe ser entre los otros $k-i$ de los niños, aunque algunos pueden tener ninguno. Hay $\tbinom{d+k-i-1}{d}$ formas en que podría suceder.

Por lo tanto, el número de pares de las asignaciones con discrepancia $2d$ es:

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

Por ejemplo, si $n=5$ $k=3$ el número de pares con discrepancia $0,2,4,6,8,10$ es: $$21, 90, 120, 108, 72, 30$$ which sums to $\tbinom72^2$ como se esperaba.