El problema combinatorio es el siguiente:
Dejemos que $H_3(r)$ denotan el número de $3\times 3$ matrices con entradas enteras no negativas tales que cada fila y cada columna sumen $r$ . Demostrar que $$H_3(r) = \binom{r+5}{5} - \binom{r+2}{5}$$
Teorema. (Birkhoff-von Neumann). Cada $n \times n$ cuadrado mágico con suma de filas y columnas $r$ es una suma de $r$ matrices de permutación (de tamaño $n \times n)$ .
Utilizando este teorema y el hecho de que el número de $3\times 3$ matrices de permutación es $3! = 6$ . Me parece que si no hay casos "repetidos", el número es $\binom{r+5}{5}$ . Pero hay, por ejemplo, $r = 3$ : $$\begin{aligned} &\left[\begin{array}{lll} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{array}\right]+\left[\begin{array}{lll} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{array}\right]+\left[\begin{array}{lll} 0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{array}\right]=\\ &\left[\begin{array}{lll} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{array}\right]+\left[\begin{array}{lll} 0 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \end{array}\right]+\left[\begin{array}{lll} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{array}\right]=\left[\begin{array}{lll} 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{array}\right] \end{aligned}$$
Pregunta : Cómo demostrar que el número de matrices superfluas es exactamente $\binom{r+2}{5}$ para un general $r$ para que podamos restarlo con seguridad de $\binom{r+5}{5}$ ?
Intenté pensar en ello pero no lo conseguí. Se agradece cualquier ayuda.
