Esta pregunta trata sobre una fórmula sorprendente que es la respuesta a un problema de conteo. Para mí sugiere que podría haber una interpretación combinatoria interesante del problema que aún no he encontrado. Incluso si no la hay, estoy seguro de que hay soluciones mucho más elegantes que la mía.
El problema
Supongamos que tenemos una cuadrícula de $n\times m$ cuadrados con $n$ filas y $m$ columnas. En cada cuadrado escribimos el número de rectángulos que se pueden hacer dentro de la cuadrícula y en los que está contenido. Consideremos, por ejemplo, el cuadrado verde en la imagen de abajo.
Vemos que está contenido en $8$ rectángulos que se pueden hacer dentro de esta cuadrícula de $2 \times 3$. Si contamos este número para cada cuadrado, obtenemos.
Ahora sea $f(n,m)$ la suma de estos números, entonces $f(2,3)=4 \cdot 6 + 2 \cdot 8=40$. La tarea es encontrar una fórmula general para $f(n,m)$.
Mi solución
Consideremos el cuadrado con coordenadas $(i,j)$, como en la imagen de abajo. Cualquier rectángulo en el que esté contenido debe tener su esquina superior izquierda en el área mostrada en rojo. Su esquina inferior derecha debe estar en el área mostrada en azul. Así que el cuadrado $(i,j)$ está contenido exactamente en $\color{red}{ i \cdot j} \cdot \color{blue}{ \left( n - i + 1 \right) \cdot \left( m - j + 1 \right)}$ rectángulos.
Ahora solo tenemos que sumar sobre todos los cuadrados para obtener $$ f(n,m)= \sum_{i=1}^n \sum_{j=1}^m \left [ i \cdot j \cdot \left( n - i + 1 \right) \cdot \left( m - j + 1 \right) \right ].$$ Para hacer este cálculo un poco más fácil, podemos introducir $S_n = \displaystyle \sum_{i=1}^n i$ y $T_n = \displaystyle \sum_{i=1}^n i^2$ de modo que \begin{align*} f(n,m) &= \sum_{i=1}^n \sum_{j=1}^m \left [ i \cdot j \cdot \left( n - i + 1 \right) \cdot \left( m - j + 1 \right) \right ] \\ &= \sum_{i=1}^n \sum_{j=1}^m \left [ i^2 j^2 - m\cdot i^2 j -i^2 j - n \cdot i j^2 -i j^2+ n m \cdot i j+ m \cdot i j + n \cdot i j +i j \right ] \\ &= T_n T_m - m\cdot T_n S_m - T_n S_m - n \cdot S_n T_m - S_n T_m + n m \cdot S_n S_m + m \cdot S_n S_m + n \cdot S_n S_m + S_n S_m \\ &= \left(S_n + n\cdot S_n - T_n\right)\cdot \left(S_m + m\cdot S_m - T_m\right) \end{align*}
Ahora podemos usar las fórmulas bien conocidas para $S_n$ y $T_n$ para encontrar que $$ S_n + n\cdot S_n - T_n = \frac{1}{6} n (n+1) (n+2) = \binom{n+2}{3}. $$ Juntando esto obtenemos que $$ f(n,m) = \binom{n+2}{3} \cdot \binom{m+2}{3}. $$
Me sorprendió bastante la naturaleza simple de esta respuesta. Especialmente por el hecho de que parece sugerir que en algún momento se eligen $3$ cosas de entre $n+2$ cosas y también de entre $m+2$ cosas. Me da una pequeña chispa de esperanza de que exista un argumento de conteo agradable que resuelva este problema. ¿Puede alguien dar una interpretación combinatoria de la fórmula para $f(n,m)$? También se aceptan soluciones más elegantes al problema.
