¿Cuántas maneras existen de llenar una cuadrícula de $n×n$ $0$s y $1$s si se le permite a lo más dos $1$s en cada fila y dos $1$s en cada columna?
Necesito algunas ideas para solucionar este problema.
PD: Este problema es del libro de Matemáticas de Princeton compañero.
Respuesta
¿Demasiados anuncios?
JiminyCricket
Puntos
143
Debido a la demanda popular, aquí está una explicación de la recurrencia utilizado en el código que he publicado en OEIS.
Deje $a(k,l,m,n)$ el número de binario $m\times n$ matrices con un máximo de dos $1$s por fila, $k$ columna de sumas de $0$, $l$ columna de sumas de $1$ y el restante $n-k-l$ columna de sumas de $2$. En la siguiente, voy a llamar a una columna con la suma de $n$ $n$- la columna corta. Puesto que los números de los que estamos buscando no tienen restricciones en la $k$$l$, que está dado por
$$a(n)=\sum_{k=0}^n\sum_{l=0}^{n-k}a(k,l,n,n)\;.$$
No es exactamente una $0\times n$ de la matriz, y se ha $n$ columna de sumas de $0$, lo $a(n,0,0,n)=1$ $a(k,l,0,n)=0$ lo contrario. Para encontrar una relación de recurrencia para $a(k,l,m,n)$, podemos ir a través de todos los admisible maneras de agregar una nueva fila a una $(m-1)\times n$ matriz.
Podemos agregar una fila sin $1$s; que no cambia la columna de sumas y te da una contribución $a(k,l,m-1,n)$.
Podemos añadir una fila con un $1$, y el $1$ puede estar en un $0$-o de una columna $1$-columna. Si es en una $0$-columna, se reduce el $k$ y aumenta el $l$, y $k+1$ columnas a elegir, para una contribución de $a(k+1,l-1,m-1,n)(k+1)$. Si es en una $1$-columna, deja a $k$ sin cambios y reduce el $l$, y $l+1$ columnas a elegir, para una contribución de $a(k,l+1,m-1,n)(l+1)$.
O se puede añadir una fila con dos $1$s, y las columnas están en puede ser cualquiera de las dos $0$-columnas, una $0$-columna y un $1$-columna, o dos $1$-columnas. Si son dos $0$-columnas, $k$ es reducido por $2$ $l$ es mayor por $2$, y $(k+2)(k+1)/2$ pares de columnas de a elegir, para una contribución de $a(k+2,l-2,m-1,n)(k+2)(k+1)/2$. Si eres una $0$-columna y un $1$columna $k$ es reducido por $1$ $l$ es invariable, y hay $(k+1)l$ pares de columnas de a elegir, para una contribución de $a(k+1,l,m-1,n)(k+1)l$. Si son dos $1$-columnas, $l$ es reducido por $2$ $k$ es invariable, y hay $(l+2)(l+1)/2$ columnas a elegir, para una contribución de $a(k,l+2,m-1,n)(l+2)(l+1)/2$.
En resumen, tenemos
$$ \begin{eqnarray} a(k,l,m,n) =&& a(k,l,m-1,n) \\ &+&a(k+1,l-1,m-1,n)(k+1)+a(k,l+1,m-1,n)(l+1) \\ &+& a(k+2,l-2,m-1,n)(k+2)(k+1)/2 \\ &+& a(k+1,l,m-1,n)(k+1)l \\ &+& a(k,l+2,m-1,n)(l+2)(l+1)/2\;, \end{eqnarray} $$
donde los términos con los índices fuera de rango son la $0$.
