Ayuda de la matriz: combinaciones

Question

¿Dada una matriz de 10 por 10 con 0s y 1s, son cuántos resultados posibles hay?

Suena bastante fácil como una combinación de $2^{100}$. El golpeador a la pregunta es que debe haber exactamente cinco 1 en cada fila y cada columna.

Esto es una cesión de crédito extra escuela que entiendo si nadie quiere ayudar pero me gustaría ganar una comprensión de los procesos matemáticos

Answer 1

Problemas como este son a menudo difíciles de resolver a mano, y también difícil de fuerza bruta en un equipo si la respuesta es demasiado grande, pero puede ser más inteligente que la fuerza bruta y obtener la respuesta rápidamente con un ordenador. Imaginar la construcción de su junta de fila por fila. Usted tiene sólo una opción para la última fila después de las 9 primeras filas se determinan. Deje $f(n,k_0,k_1,k_2,k_3,k_4,k_5)$ contar el número de $n \times 10$ consejos que usted puede hacer cuando usted tiene $k_i$ columnas con $i$, donde cada fila tiene 5. A continuación, desea calcular $f(10,0,0,0,0,0,10)$. Pero por el razonamiento por encima de este es igual a $f(9,0,0,0,0,5,5)$. Del mismo modo, usted puede venir para arriba con la generalizada contar argumentos para obtener $f(n,k_0,k_1,k_2,k_3,k_4,k_5)$ en términos de una combinación lineal de $f(n-1,k_0,k_1,k_2,k_3,k_4,k_5)$ para varias combinaciones diferentes de $k_i$. El uso de un ordenador puede calcular rápidamente todas las medidas necesarias, $f(n,k_0,k_1,k_2,k_3,k_4,k_5)$ valores en orden creciente de $n$. Nota: es probable que necesite sin signo enteros de 64 bits para almacenar la cuenta, dependiendo del tamaño. Usted puede incluso necesitar una precisión arbitraria entero paquete si la respuesta total es de más de $2^{64}$. Sin embargo, la respuesta total es limitada por ${10 \choose 5}^{10}$ y que ni siquiera toma en consideración el hecho de que tanto las filas Y las columnas están restringidas a tener 5 1 cada uno, así que probablemente la respuesta es menos de $2^{64}$, por lo que los enteros sin signo debe trabajar, así que usted puede utilizar cualquier lenguaje de programación estándar que desee, siempre y cuando usted está en una de 64 bits entorno de almacenamiento.

Como un ejemplo más de que el razonamiento, suponga que desea calcular $f(2,2,6,2,0,0,0)$. Usted sabe que el único válido caso base para $n=1$ $f(1,5,5,0,0,0,0)$ e tiene $f(2,2,6,2,0,0,0) = {6 \choose 2}{5 \choose 2} f(1,5,5,0,0,0,0)$ por la elección de los cuales 2 en las columnas 2 y que 2 columnas tienen 0. Y $f(1,5,5,0,0,0,0) = {10 \choose 5}$.

La complejidad de este algoritmo es limitada por el número de sub-casos en que puede obtener para cada una de las $n$. Ha $6$ no negativo índices de $k_i$ que deben sumar a $10$. También la suma de $\sum_i i k_i = 5n$, y también se $k_i = 0$$i > n$, pero vamos a ignorar las restricciones para un momento. Hay ${14 \choose 5} = 2002$ formas de obtener los 6 índices de $k_i$, de modo que $\sum_i k_i = 10$. Por lo tanto hay menos de $2002$ sub-casos para cada una de las $n$. Cuando se mueve de a$n$$n+1$, algunos sub-casos dependerá de múltiples anterior sub-casos. Pero incluso en el peor de los casos, si cada sub-caso depende de cada anteriores sub-caso, esto sólo se da en el orden de $2002^2 = 4$ millones de pares de sub-casos, se necesita calcular los coeficientes para cuando se mueve de a$n$$n+1$. Así que el total de la complejidad no es más que en el orden de $10 \times 4$ millones de = $40$ millones de cálculos de los coeficientes para los pares de sub-casos. Un ordenador puede resolver esto en cuestión de segundos o más rápido.

Nota usted probablemente no desea almacenar los $f(n,k_0,k_1,k_2,k_3,k_4,k_5)$ como una de las 7 dimensiones de la matriz, debido a que la matriz sería bastante grande y no sólo en la mayoría de las $20,020$ entradas necesita almacenar. Utilice una tabla hash (o una estructura del diccionario en python) y el uso de $(n,k_0,k_1,k_2,k_3,k_4,k_5)$ como el hash de la clave.