Encontrar todas las posibles combinaciones **patrón** - en lugar de todas las posibles combinaciones

Question

Empiezo intentando encontrar el número de posibles combinaciones para una cuadrícula de 5x5 (25 espacios), donde cada espacio podría ser un color del 1 al 4 (así que 1, 2, 3 o 4)

Hago 4^25 = 1,125,899,906,842,624 combinaciones diferentes

Sin embargo, ahora estoy tratando de cambiar el número de combinaciones para tener en cuenta cuadrículas con el mismo patrón de números, por ejemplo:

{ 1 1 1 1 1 }
{ 3 3 3 3 3 }
{ 4 4 2 2 3 }
{ 4 3 2 1 1 }
{ 2 2 1 2 3 }

1 ahora es 2, 2 ahora es 4, 3 ahora es 1, 4 ahora es 3

{ 2 2 2 2 2 }
{ 1 1 1 1 1 }
{ 3 3 4 4 1 }
{ 3 1 4 2 2 }
{ 4 4 2 4 1 }

Estoy teniendo dificultades para encontrar una ecuación que pueda usar para resolver esto para una cuadrícula de (x * y) donde cada espacio podría ser un color del 1 al (c).

Answer 1

Necesitas dividir el recuento según el número de diferentes números utilizados. Hay $4$ cuadrículas que usan un solo número cada una, pero todas producen el mismo patrón.

En el otro extremo hay

$$4^{25}-\binom43\cdot3^{25}+\binom42\cdot2^{25}-\binom41\cdot1^{25}=4^{25}-4\cdot3^{25}+6\cdot2^{25}-4$$

cuadrículas que utilizan los cuatro números. Los cuatro números se pueden permutar de $4!=24$ maneras diferentes, por lo que hay

$$\frac1{24}\left(4^{25}-4\cdot3^{25}+6\cdot2^{25}-4\right)$$

patrones.

Dados dos colores, digamos $a$ y $b$, podemos llenarlos en la cuadrícula de $2^{25}-2$ maneras (ya que necesitamos excluir las cuadrículas de un solo número). Sin embargo, esto cuenta cada patrón dos veces, ya que podemos intercambiar $a$ y $b$, por lo que este caso contribuye con $2^{24}-1$ patrones.

De manera similar, tres colores se pueden llenar en la cuadrícula en

$$3^{25}-\binom32\cdot2^{25}+\binom31\cdot1^{25}=3^{25}-3\cdot2^{25}+3$$

maneras, pero los colores se pueden permutar de $3!=6$ maneras, por lo que el número de patrones es solamente

$$\frac16\left(3^{25}-3\cdot2^{25}+3\right)=\frac12\left(3^{24}-2^{25}+1\right)\;.$$

Answer 2

$\sum _{n=1}^c \mathcal{S}_{x y}^{(n)}$ es lo que estás buscando, con $x, y, c$ las dos dimensiones y el número de colores. $\mathcal{S}_{x y}^{(n)}$ es el número de Stirling de segunda clase.

Esto se generaliza a dimensiones arbitrarias.

Answer 3

Observación. Nota que $${25\brace 1} + {25\brace 2} + {25\brace 3} + {25\brace 4} \\= 1 + 2^{24} -1 + \frac{1}{2}(3^{24}-2^{25}+1) + \frac{1}{24}(4^{25}-4\times3^{25}+6\times2^{25}-4).$$

Answer 4

Asigna cuatro colores (a, b, c, d) a los valores (1, 2, 3, 4) - ¿de cuántas formas se puede hacer esto? $4!=24$ Ese es el número por el que necesitas dividir, para cuadrículas que usan los cuatro colores, y (creo) para cuadrículas que solo usan tres colores. Para cuadrículas con solo uno o dos colores, el número de opciones se reduce, porque cambiar los colores no utilizados no hace ninguna diferencia. Así que, por ejemplo, con cuadrículas monocromáticas, en lugar de $4!=24$ opciones hay solo $\frac{4!}{6}=4$ opciones (por supuesto). Para cuadrículas con dos colores, hay $\frac{4!}{2}=12$ opciones para dividir.