Si se consideran todos los $10$ por $15$ matrices con entradas que son $0$ o $1$ Hay ${2^{15} \choose 10}$ sin filas repetidas (hasta la permutación de filas) y ${2^{10} \choose 15}$ sin columnas repetidas (hasta la permutación de columnas). ¿Cuántos hay sin filas ni columnas repetidas (hasta la permutación de filas o columnas)?
Respuestas
¿Demasiados anuncios?
En realidad, esto puede resolverse de forma mucho más sencilla de lo que parece, mediante un poco de razonamiento.
Supongamos que construimos un $10\times15$ matriz tal que no haya columnas repetidas. Ahora, tenemos que tener necesariamente que el número de filas repetidas esté en algún lugar entre 0 y 9 (suponiendo que una fila tiene que ser "única" antes de que haya una repetición). Y así, vamos a encontrar el número de posibilidades para cada cuenta de repetición empezando por la más alta.
Es bastante fácil ver que no puede haber 9 repeticiones, ya que eso requeriría que las 15 columnas fueran todas-zero o todas-uno, y por lo tanto a lo sumo dos serían "únicas". Del mismo modo, con 8 repeticiones, sólo habría dos filas "únicas" y, por tanto, sólo cuatro columnas posibles. Lo mismo puede decirse de 7 repeticiones, que proporcionarían sólo ocho columnas posibles. Así pues, empezamos con el caso de 6 repeticiones.
Si hay 6 repeticiones, entonces hay cuatro filas "únicas". Para satisfacer las condiciones, estas cuatro filas "únicas" deben contener 15 de las 16 combinaciones posibles de 4 bits. Las 6 filas restantes pueden elegirse entre las cuatro filas "únicas".
Si hay 5 repeticiones, entonces hay cinco filas "únicas", y podemos encontrar el número de éstas observando que es proporcional al número de $5\times15$ matrices sin columna repetida, para las que no hay filas repetidas (y por tanto se resta un número proporcional al que obtuvimos para 6 repeticiones).
Esto se puede repetir hasta llegar a $10\times15$ calculando el número de $n\times15$ se pueden hacer matrices sin repeticiones basadas en el valor de $n-1$ .
Con la $n\times15$ caso, hay ${2^n}\choose{15}$ posibles matrices (hasta la permutación de columnas). De éstas, debemos restar el número de matrices que tienen $k$ filas repetidas, con $k$ corriendo de $1$ a $n-4$ . Llamaremos al número de $n\times15$ matrices sin repeticiones $M_n$ .
Ahora, podemos ver que $$ M_n ={2^n\choose15} - \sum_{k=4}^{n-1} S(n,k)M_k $$ donde $S(n,k)$ es un número de Stirling del segundo tipo. Esto se debe a que estamos dividiendo nuestro conjunto de $n$ filas en subconjuntos no vacíos, de manera que haya $k$ subconjuntos únicos, y para los que el orden es irrelevante (es decir, tomamos el subconjunto que contiene la primera fila como subconjunto "1", luego el subconjunto que contiene la primera fila que no está en el primer subconjunto como subconjunto "2", y así sucesivamente).
Ahora, podemos hacer nuestros cálculos...
$$ M_4 = {16\choose15}\\ M_5 = {32\choose15} - S(5,4) M_4 = {32\choose15} - 10\times 16\\ M_6 = {64\choose15} - S(6,4) M_4 - S(6,5) M_5 = {64\choose15} - 65 M_4 - 15 M_5\\ \vdots $$ y así sucesivamente.
Una vez que tenga $M_{10}$ debe terminar el proceso dividiendo las posibles permutaciones de filas, es decir, dividiendo por $10!$ . Por supuesto, la cifra real va a estar muy cerca de ${2^{10}\choose15}/10!$ ya que es de esperar que las repeticiones sean mucho menos frecuentes que las no repeticiones.
(Mediante el uso de una hoja de cálculo, encuentro que el número es aproximadamente $2.709912\times10^{26}$ (aunque algún pequeño error de truncamiento puede haberse colado en esa expresión)
Gilles Bonnet
Puntos
993
Editar : Leí mal la pregunta y traté de responder a una pregunta diferente. Estoy tratando de obtener el número de matrices $10\times15$ sin filas ni columnas repetidas, pero no hago la identificación hasta la permutación de filas o columnas. Esta es probablemente una pregunta más difícil que la original.
Esto es sólo un intento. Esto no da una respuesta al problema, pero creo que las siguientes observaciones son interesantes y podrían ayudar a encontrar una respuesta. Al final explico el límite de este intento. Este límite es también la razón por la que creo que la respuesta de @clintonmonk no funciona.
Llame a $\hat{M}_{n, m}$ el subconjunto de $M_{n, m}(\mathbb{Z}_2)$ de matrices sin filas ni columnas repetidas.
Mi primera observación es que
Lema : Para cualquier $n\in\mathbb{N}, $ $\mathrm{Card}\hat{M}_{n, 2^n}=\mathrm{Card}\hat{M}_{n, 2^n-1}=2^n!$
Prueba : Tenemos $2^n$ posibles vectores con $n$ entradas binarias. Tenemos $2^n!$ maneras de ordenarlas sin repetirlas. Por eso $\mathrm{Card}\hat{M}_{n, 2^n}=2^n!$
Ahora, podemos definir una biyección entre $\hat{M}_{n, 2^n}$ y $\hat{M}_{n, 2^n-1}$ , dada por la eliminación de la última columna. La inversa es añadir al final de la matriz el vector (único) que falta.
Si aplicamos este lema con $n=4$ obtenemos:
Corolario: $\mathrm{Card}\hat{M}_{4, 16}=\mathrm{Card}\hat{M}_{4, 15}=16!$
Si completamos una matriz $M$ en $\hat{M}_{4, 15}$ por $6$ líneas diferentes a la $4$ líneas de $M$ y diferentes entre sí entonces obtenemos una matriz en $\hat{M}_{10, 15}$ . Así que para cada $M$ en $\hat{M}_{4, 15}$ tenemos $(2^{15}-4)!/(2^{15}-10)!$ posibilidades para completarla y obtener una matriz en $\hat{M}_{10, 15}$ . Por lo tanto:
$\mathrm{Card}\hat{M}_{10, 15}\geq 16! \frac{(2^{15}-4)!}{(2^{15}-10)!} \simeq 10^{40} $
El problema es que probablemente esto no sea una igualdad. En efecto, si $N\in\hat{M}_{10, 15}$ No necesariamente tenemos que la primera $4$ columnas de $N$ forman una matriz en $\hat{M}_{4, 15}$ . Puede ocurrir que $2$ filas de $M$ tienen el mismo primer $4$ y difieren en alguna parte del $6$ siguiente. Así que no vamos a enumerar todas las matrices por este procedimiento.
nelaar
Puntos
260
Considere la posibilidad de dividir el problema en dos: Encontrar un $10 \times 10$ matriz sin filas ni columnas repetidas y luego encontrar $10 \times 5$ valores adicionales.
Para encontrar un $10 \times 10$ sin filas ni columnas repetidas, busca todas las posibles matrices {0,1} que sean no singulares. El espacio de filas y el espacio de columnas tienen el mismo rango y una matriz no singular $n \times n$ matriz tendrá rango completo (por qué esto funciona). Por lo tanto, hay que calcular el número de matrices no singulares $n \times n$ {0,1}-matrices $N_{nonsingular}$ .
Podemos utilizar el algoritmo A046747 para hallar la probabilidad (asintótica) de que un $n \times n$ La matriz {0,1} es singular. ( A055165 es mejor, pero depende de A046747). Parece que $N_{nonsingular}$ puede tener que ser calculado por fuerza bruta, a menos que alguien encuentre un enfoque mejor. Por ahora, supongamos que $N_{nonsingular}$ para $n=10$ es conocido.
A continuación, como conocemos las filas y columnas del $10 \times 10$ son distintas, las 5 columnas restantes pueden ser cualquier cosa siempre que sean diferentes de las 10 primeras columnas.
$$ Possible\ combinations = N_{combos} = \frac{(2^{10} - 10)!}{(2^{10} - 15)!} \\ $$
Por lo tanto, nuestro número de matrices es: $$ N = N_{nonsingular} * N_{combos} $$
NOTA: Lo intenté originalmente con las fórmulas de los algoritmos enlazados, pero mis respuestas fueron más altas de lo esperado. Imagino que esto se debió a un error por mi parte y también a no saber muy bien qué ordenación deben tener las últimas 5 columnas "libres" con respecto a las otras 10 columnas. En cambio, espero que esta respuesta aporte alguna idea sobre una buena técnica a probar.
