¿Cuántas permutaciones de píxeles hay en un cuadrado?

Question

Dado un cuadrado de dimensiones x por y píxeles, ¿cuántas permutaciones de colores de píxeles hay en el cuadrado? Supongamos que cada cuadrado es de 1 píxel y que este cuadrado es de 5x5 píxeles. ¿De cuántas formas únicas puede permutarse este cuadrado de píxeles? Asume también que los colores específicos mostrados aquí no importan.

Answer 1

Supongamos que tenemos $k$ colores distintos y el número de cada color es $n_1,\ldots,n_k$ . Entonces la respuesta es $$\frac{(xy)!}{n_1!n_2!\cdots n_k!}$$ por la fórmula combinatoria elemental para enumerar permutaciones.

Answer 2

Si queremos hacer la pregunta más interesante permitiendo píxeles con el mismo color (es decir, píxeles indistinguibles), la solución general puede obtenerse como sigue:

Dejemos que $n_c$ sea el número de colores y $c_i, i=1..n_c$ sean las multiplicidades de los colores. Entonces el número total de permutaciones viene dado por $$P = \frac{(xy)!}{\prod_{i=1}^{n_c} c_i!}$$ Esto se debe a que hay $c_i!$ formas de reordenar el $i$ -píxeles de color sin cambiar la imagen. Para obtener el denominador de otra forma, podemos utilizar $$d(n):=|\{i | c_i \ge n\}|$$ que cuenta cuántos colores $i$ tienen al menos $n$ píxeles coloreados por $i$ . Entonces el denominador es $$\prod_{i=1}^{n_c} c_i! = 1\cdot2\cdot \ldots c_1 \cdot 1 \cdot \ldots c_2 \ldots c_{n_c} = 1\cdot 1\cdot \ldots 1 \cdot 2 \cdot \ldots = \prod_{j=1}^{xy} j^{d(j)}$$ El límite superior del producto RHS puede ser sustituido por $\max_{i} c_i \le xy$