¿Cuántos rectángulos $m \times n$ $(0,1)$ (donde $n>m$ ) están ahí con sumas de filas prescritas $r_i$ para $i=1$ a $m$ de forma que no haya dos columnas iguales.
Respuesta
¿Demasiados anuncios?
El recuento de $m\times n$ matrices binarias con sumas de filas especificadas $r_i, i=1,\ldots,m$ y columnas distintas puede expresarse como un producto:
$$ n! [1, 0, \ldots ,0] ( \Pi_{i=1}^m T_i ) [0, \ldots ,0, 1]^T $$
donde cada $T_i$ es una matriz triangular superior dispersa que sólo depende de $n$ y $r_i$ .
El factor $n!$ tiene en cuenta las permutaciones del $n$ columnas distintas. Suprimimos la consideración de ese factor exigiendo que las columnas se ordenen de forma descendente, considerando que el bit de una fila superior es más significativo que el de una fila inferior.
La matriz $T_i$ es la matriz de adyacencia de un multigrafo dirigido sobre estados que son particiones del número de columnas $n$ ordenadas por refinamiento, y cuyas aristas corresponden al refinamiento de una partición a otra mediante la asignación de $r_i$ a la siguiente fila de la matriz (pudiendo distinguir algunas columnas que eran idénticas hasta esa fila). Obsérvese que inicialmente (antes de asignar ninguna fila) todas las columnas son idénticas, lo que corresponde a la partición trivial $[n]$ . Una vez asignadas todas las filas, tendremos todas las columnas distintas, lo que corresponde a la partición ligeramente menos trivial $[1,1,\ldots ,1]$ .
Obsérvese que este grafo permite bucles propios, pero por lo demás no tiene ciclos. Tomando el producto de matrices se cuentan los caminos de un estado a otro, y nos interesa el recuento de caminos de $[n]$ a $[1,1,\ldots ,1]$ ya que corresponde (aparte de las permutaciones de columnas) al número de matrices binarias admisibles (sumas de filas especificadas y columnas distintas).
Aún omitiendo el $n!$ calculé a mano (y comprobé con fragmentos de código Prolog) pequeños ejemplos de la forma $2k \times 2k$ matrices binarias con todas las filas de igual suma $k$ . Para $k=1$ obtenemos 2 soluciones. Para $k=2$ hay 52 soluciones. Para $k=3$ hay 83.680 soluciones.
En la práctica, no es necesario considerar todas las particiones posibles de $n$ sólo las que son alcanzables. Teniendo en cuenta que la primera fila transita unívocamente de $[n]$ a $[r_1,n-r_1]$ reduce el producto de matrices en un índice y limita las particiones posibles. Para el caso $k=4$ en los ejemplos descritos anteriormente, sólo se necesitan ocho particiones, y la matriz de transición puede adoptar la forma:
$$ T = \begin{pmatrix} 2 & 2 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 4 & 0 & 4 & 0 & 6 & 0 & 0 \\ 0 & 0 & 6 & 0 & 0 & 12 & 0 & 1 \\ 0 & 0 & 0 & 6 & 2 & 8 & 6 & 0 \\ 0 & 0 & 0 & 0 & 10 & 0 & 20 & 0 \\ 0 & 0 & 0 & 0 & 0 & 14 & 16 & 6 \\ 0 & 0 & 0 & 0 & 0 & 0 & 30 & 20 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 70 \end{pmatrix} $$
Así, para $k=4$ obtendríamos (aparte del factor $8!$ ) un recuento de $(T^7)_{1,8}$ o 13.849.902.752 soluciones.
La utilidad de este enfoque estará limitada por el número de particiones/estados que necesiten los parámetros dados $m, n, r_i$ . Estaré encantado de publicar mis fragmentos de Prolog y/o intentar un problema mayor si alguien está interesado.
