¿De cuántas formas diferentes puede utilizarse una cuadrícula de cómic de 9 paneles?

Question

Mientras escribía mi respuesta a ¿Por qué "Watchmen" utiliza la cuadrícula de 9 paneles? Utilicé esta imagen para indicar las muchas formas en que se puede dividir en grupos (que pueden utilizarse para los paneles de un cómic, como ocurrió en "Watchmen"):

_{<a href="https://davidpetersen.blogspot.com.tr/2009/11/square-format-when-mouse-guard-first.html" rel="noreferrer">Fuente de la imagen</a>}

Posteriormente, se ha me señaló en un comentario que hay algunas combinaciones que no están presentes en esta imagen:

El $81$ variaciones en el $9$ La rejilla del panel en ese diagrama no agota las posibilidades -- hay ciertamente muchos otros. Por ejemplo, esta es una de las muchas que no se muestran allí.

Otro comentario dice que la rejilla de 9 paneles puede utilizarse en $4096$ diferentes maneras:

Los son $12$ bordes interiores, cada uno de los cuales puede incluirse o excluirse en un determinado diseño. Es decir $2^{12} = 4096$ posibilidades.

Una página doble trata de dos $3 \times 3$ rejillas como una sola $6 \times 3$ rejilla con $21$ fronteras interiores, para $2,097,152$ posibilidades.

¿Cómo puedo calcularlo? He intentado lo siguiente:

• Hay un $3$ formas de agrupar la tercera fila.
• Eso nos deja con $4$ paneles en la 2ª y 3ª fila. Cuento $4$ formas de agruparlas.
• El $12$ combinaciones hasta ahora deben ser multiplicadas por $4$ (porque puedo girarlas) y por $2$ (porque puedo reflejarlos).

Esto me da $96$ variaciones. La imagen de arriba tiene $81$ el comentario dice que hay $4096$ .

¿Existe una solución geométrica fácil de entender? No estoy realmente interesado en un valor preciso ( un montón es suficiente para mí), me interesa más la técnica o una regla. ¿Existe una regla general para una cuadrícula de n por n?

Para aclarar : los paneles deben ser rectangulares, es decir, deben estar formados por la fusión de algunos de los $9$ paneles en horizontal o en vertical:

Answer 1

Supongamos que creamos un diseño eliminando los bordes entre los paneles de un $3\times 3$ de la red, como se ha sugerido en varias ocasiones. Pero pongamos algunas restricciones a los bordes que podemos eliminar, de modo que no sean posibles los paneles no rectangulares, pero sí todos los diseños con paneles rectangulares.

Considere los cuatro segmentos del borde que se encuentran en un solo vértice en el $3\times 3$ de la rejilla. Rotula estos segmentos $N, E, S, W$ en el sentido de las agujas del reloj, empezando por la parte superior. Si elimina tres de estos segmentos y deja uno intacto, acabará teniendo un panel con una "grieta", no un rectángulo. Hay $4$ prohibidos los acuerdos de este tipo. Si se eliminan dos segmentos "adyacentes" como $N, E,$ se termina con un panel que tiene una esquina "cóncava", de nuevo no un rectángulo. Eso nos da otra $4$ arreglos prohibidos.

Pero cualquiera de los otros $16 - 4 - 4 = 8$ Las combinaciones de segmentos de borde en torno a un vértice común pueden darse en un diseño formado exclusivamente por rectángulos. Llamémoslas permitido combinaciones.

Parece "obvio" (aunque quizá no sea tan obvio cómo demostrarlo) que mientras los cuatro vértices del interior de la cuadrícula tengan combinaciones de aristas permitidas, el trazado estará formado sólo por rectángulos.

En realidad, contar las combinaciones que pueden darse juntas es más complicado. No es $8^4,$ porque hay muchas formas en que la elección de la combinación de aristas en un vértice puede ser restringida por las combinaciones en los vértices adyacentes.

Para enumerar las posibilidades, considere los bordes que podrían existir o no alrededor del cuadrado central del $3\times 3$ de la rejilla.

Caso 1. Las cuatro aristas existen. Por lo tanto, el $NE$ vértice de este cuadrado tiene al menos $W$ y $S$ bordes; hay $3$ combinaciones permitidas de las otras dos aristas. Del mismo modo, existe el área $3$ combinaciones permitidas en cada uno de los otros tres vértices del cuadrado central. Esto nos da $3^4=81$ posibles disposiciones.

Caso 2. Existen tres bordes. Para empezar, tenemos $4$ para elegir la arista que se va a eliminar. Entonces, en cada uno de los dos vértices adyacentes a la arista eliminada, hay exactamente $2$ combinaciones permitidas de aristas. (Por ejemplo, si eliminamos el $E$ borde del cuadrado central pero no sus otros tres bordes, el $NE$ el vértice tiene una arista $W$ pero no el borde $S$ Por lo tanto, debe tener un borde $E$ pero el borde $N$ es opcional). En cada uno de los otros dos vértices, todavía hay $3$ combinaciones permitidas. En total, hay $4 \times 2^2 \times 3^2 = 144$ de este tipo.

Caso 3. Existen dos aristas opuestas, las otras dos se eliminan. Hay $2$ formas de elegir qué par de aristas eliminar alrededor del cuadrado central; en cada uno de los cuatro vértices hay entonces $2$ combinaciones de bordes permitidas. En total hay $2\times 2^4 = 32$ de este tipo.

Caso 4. Existen dos aristas adyacentes, las otras dos se eliminan. Hay $4$ formas de elegir qué par de aristas eliminar alrededor del cuadrado central. En el vértice con dos aristas hay entonces $3$ combinaciones de aristas permitidas; en cada uno de los dos vértices adyacentes, hay $2$ combinaciones de aristas permitidas; y en el cuarto vértice (el que ya tiene dos aristas adyacentes eliminadas) se deben eliminar las cuatro aristas. En total hay $4\times 3 \times 2^2 = 48$ de este tipo.

Caso 5. Existe un borde. Tenemos $4$ opciones de qué borde será. Entonces, en cada uno de los dos vértices adyacentes a la arista restante, hay exactamente $2$ combinaciones permitidas de aristas. Los otros dos vértices ya tienen dos aristas adyacentes eliminadas, por lo que cada uno de ellos debe tener las cuatro aristas eliminadas. En total, hay $4 \times 2^2 = 16$ de este tipo.

Caso 6. No existen bordes alrededor del cuadrado central. Sólo hay una disposición con esta propiedad, la que consta de un solo panel.

Sumando, tenemos $$ 81 + 144 + 32 + 48 + 16 + 1 = 322,$$ por lo que hay $322$ posibles disposiciones.

Answer 2

Aunque no se trata tanto de una solución matemática como de una solución de software, voy a añadirla de todos modos, aunque sólo sea por la bonita imagen del final.

El proceso utilizado para encontrar todas las cuadrículas es el siguiente.

En primer lugar, a cada una de las casillas de la cuadrícula de 3x3 se le asigna un índice de 1 a 9 en función de la coordenada ( $n=3(y-1)+x$ ), donde $(1,1)$ es la parte superior izquierda y $(3,3)$ es de abajo a la derecha. Este número representa el índice más alto de un panel que puede cubrirlo.

Esencialmente, esto significa que los paneles deben crecer desde cualquier cuadrado hacia la derecha y hacia abajo. Esta limitación evita las entradas duplicadas: cada panel que crece hacia la derecha y hacia abajo es idéntico a uno que crece hacia la izquierda y hacia arriba.

La tarea consiste entonces en construir simplemente una lista de posibles rejillas añadiendo paneles. Los paneles utilizan un enfoque recursivo que abandona todas las cuadrículas que sólo podrían ser cubiertas tienen más de un panel con el mismo índice, evitando así las cuadrículas duplicadas.

Para quien esté interesado en ver el código MATLAB que enumera todas las cuadrículas, lo he incluido al final de la respuesta.

Es impresionante lo rápido que crece el número de cuadrículas posibles.

Para una cuadrícula de 3x3 tenemos las 322 posibilidades identificadas por las otras respuestas. Si pasamos a 4x4 tenemos 70878 cuadrículas posibles. Si pasamos a una cuadrícula de dos páginas de 3x6, el número aumenta a la friolera de 314662 cuadrículas posibles.

---

Una vez construidas todas las cuadrículas posibles, sólo tiene sentido exportarlas en algo bonito. A continuación se muestran todas las cuadrículas en mosaico y convertidas en una imagen combinada de todos los 322 posibles rejillas. En la imagen, el color de un panel representa el índice del cuadrado superior izquierdo de ese panel.

Las cuadrículas están ordenadas en el orden en que se encontraron, que es esencialmente el de empezar con un cuadrado sólido y luego trabajar hacia atrás desde la esquina inferior derecha.

---

Las siguientes funciones de MATLAB se utilizan para producir las mallas.

function [found] = makeGrids(found,grid,depth,x,y)
    if (depth > (x*y))
        %If at max depth then grid is valid.
        found = [found grid]; %So add to list
        disp(grid)
        %found=found+1; %So one more found
    else
        %Show current depth and found count during search.
        if (depth<=(x*(y-1)))
            disp([repmat('..> ',1,depth) num2str(depth) ' (found:' num2str(numel(found)) ')']);
        end
        %Another layer to do
        for k=1:depth
            %For each number in this layer
            grid(depth)=k; %Update grid with new number. Depth is linear index
            %Now we check to see if the current state of the grid is
            %acceptable (if it isn't then no lower down ones possibly can)
            if (checkPanels(grid,depth,x,y)) %If it is acceptable (i.e. there are no remaining values with no frame)
                found=makeGrids(found,grid,depth+1,x,y); %Work through the next layer
            end
        end
    end
end

function success = checkPanels(grid,depth,x,y)
    success = false;
    for ys=1:y
        for xs=1:x
            %Start at (1,1) and work through to (n,n)
            expected = xs+(ys-1)*x; %Linear index of this cell
            if(expected > depth)
                %If the expected val is more than current depth
                return; %Then we are done searching
            end
            panelFound=false;
            for xe=x:-1:xs
                for ye=y:-1:ys
                    %For each end value starting from largest to smallest
                    panel=grid(xs:xe,ys:ye); %Extract the current panel
                    panel(panel==expected)=0; %Cover all instances of expected value in panel
                    panelFound = all(all(~panel));%Check if every number in this panel is covered
                    if (panelFound) %If we have found a complete panel
                        grid(xs:xe,ys:ye) = -1; %then mark panel a covered in the grid.
                        break; %We can only have one panel for any given number, so break.
                    end
                end
                if (panelFound)
                    break; %We can only have one panel for any given number, so continue break.
                end
            end
            %Check if entire grid is covered
            if (all(all(grid==-1)))
                success = true; %Grid is all covered and valid
                return;
            end
        end
    end
end

A continuación se utiliza el siguiente script para llamar a la función y crear la imagen en mosaico (aunque yo he añadido los bordes con detección de bordes en Photoshop)

%Grid Size
x=3; %3x3
y=3;
%Enumerate all grids
grids=makeGrids({},zeros(x,y),1,x,y);
gridCount = numel(grids);
disp(['Grids Found: ' num2str(gridCount)]);
%Colour mapping for image - hot(x*y), hsv(x*y) and jet(x*y) all look good
map=[jet(x*y);0,0,0]; %;0,0,0 is for black borderd
%Create images for all grids
nameFormat = ['%0' num2str(ceil(log10(gridCount))) 'd'];
for i=1:gridCount
    img=grids{i};
    img(x+1,:)=(x*y)+1;
    img(:,y+1)=(x*y)+1;
    [img, newmap]=imresize(img,map,32,'nearest');
    imwrite(ind2rgb(img,newmap),['Grid' num2str(i,nameFormat) '.png']);
end

%Create tiled montage of images
dirOutput = dir('Grid*.png');
fileNames = {dirOutput.name}';
vertical = max(factor(gridCount));
horizontal = gridCount/vertical;
montage(fileNames, 'Size', [vertical horizontal]);
%And save montage as PNG.
allGrids=getframe(gca);
imwrite(allGrids.cdata,'AllGrids.png');

Answer 3

Por desgracia, este tipo de cuestiones geométricas rara vez tienen una respuesta satisfactoria y clara, como una fórmula para una cuadrícula de cualquier tamaño. Esto se debe a que la estrategia de "divide y vencerás" no funciona: en cuanto se corta la cuadrícula en dos cuadrículas más pequeñas para analizarlas por separado, se pierden todos los patrones que tienen paneles que cruzan la línea de corte, y esos no son fáciles de clasificar o contar.

He intentado contar todos los patrones a mano, así que es probable que haya cometido errores. La tabla siguiente enumera los patrones que he encontrado. La columna de la izquierda enumera los paneles grandes (los de 1x1 no aparecen en la lista). La columna de la derecha enumera el número de disposiciones posibles de esos paneles. La multiplicación entre paréntesis es para todas las rotaciones/reflexiones de esos patrones (así que uno asimétrico se multiplica por 8).

[Después de comparar con la respuesta de David K, he corregido 4 errores y mi recuento final ahora coincide con el suyo].

3x3                     -> 1 (\*1)

2x3 + 1x3               -> 1 (\*4)
2x3 + 1x2               -> 1 (\*8)
2x3                     -> 1 (\*4)

2x2 + 1x3               -> 1 (\*8)
2x2 + 1x3 + 2x1         -> 1 (\*8)
2x2 + 1x2 + 2x1         -> 1 (\*4) + 1 (\*8)
2x2 + 1x2               -> 2 (\*8)
2x2                     -> 1 (\*4)

1x3 + 1x3 + 1x3         -> 1 (\*2)
1x3 + 1x3 + 1x2         -> 1 (\*8) + 1 (\*4)
1x3 + 1x3               -> 1 (\*4) + 1 (\*2)

1x3 + 2x1 + 2x1 + 2x1   -> 1 (\*4)
1x3 + 1x2 + 1x2 + 2x1   -> 1 (\*8)
1x3 + 1x2 + 1x2         -> 2 (\*8) + 2 (\*4)
1x3 + 1x2 + 2x1         -> 2 (\*8)
1x3 + 2x1 + 2x1         -> 1 (\*8) + 1 (\*4)
1x3 + 1x2               -> 3 (\*8)
1x3 + 2x1               -> 1 (\*8) + 1 (\*4)
1x3                     -> 1 (\*4) + 1 (\*2)

1x2 + 1x2 + 1x2 + 2x1   -> 2 (\*8)
1x2 + 1x2 + 2x1 + 2x1   -> 1 (\*2)
1x2 + 1x2 + 1x2         -> 2 (\*4) + 1 (\*8)
1x2 + 1x2 + 2x1         -> 5 (\*8)
1x2 + 1x2               -> 2 (\*4) + 2 (\*8)
1x2 + 2x1               -> 1 (\*4) + 2 (\*8)
1x2                     -> 1 (\*8) + 1 (\*4)
1x1                     -> 1 (\*1)

Si mi lista es correcta, y la he contado correctamente, eso da 322 patrones diferentes. Si se consideran idénticos los patrones girados o reflejados (es decir, se omiten todas las multiplicaciones entre paréntesis), entonces hay 54.

Algunos ejemplos de los patrones que faltan en la imagen de la pregunta son:

• un único panel de 1x3 o 3x1 en el centro
• Dos paneles no adyacentes de 1x3 o 3x1

---

Anexo

Después de pensar un poco más en el método de David K, descubrí una forma de calcular el número de patrones de paneles en una cuadrícula de 3xn.

Consideremos dos vértices verticalmente adyacentes. Hay dos segmentos horizontales de borde a la izquierda, dos segmentos horizontales de borde a la derecha y tres segmentos verticales de borde en el centro. Para los dos segmentos de la izquierda hay cuatro posibilidades de que estén presentes o se borren, y de forma similar en la derecha. Para cada una de esas 4*4=16 combinaciones podemos contar cuántas posibilidades hay para los segmentos verticales.

Esto se muestra en la siguiente imagen, donde cada segmento vertical gris oscuro tiene dos posibilidades:

Esto da una matriz de transición, que nos dice cuántas formas hay de conectar las entradas de la izquierda con las salidas de la derecha.

$$\begin{pmatrix} 8 & 2 & 2 & 1 \\ 2 & 4 & 1 & 1 \\ 2 & 1 & 4 & 1 \\ 1 & 1 & 1 & 2 \end{pmatrix}$$

Sumando todas las entradas de la matriz se obtiene 34, que es el número de formas en que una cuadrícula de 3x2 puede dividirse en rectángulos.

Para una cuadrícula de 3x3 aplicamos dos transiciones, elevando la matriz al cuadrado.

$$\begin{pmatrix} 8 & 2 & 2 & 1 \\ 2 & 4 & 1 & 1 \\ 2 & 1 & 4 & 1 \\ 1 & 1 & 1 & 2 \end{pmatrix}^2 = \begin{pmatrix} 73 & 27 & 27 & 14 \\ 27 & 22 & 13 & 9 \\ 27 & 13 & 22 & 9 \\ 14 & 9 & 9 & 7 \end{pmatrix}$$

Sumando todas las entradas, obtenemos la respuesta para una cuadrícula de 3x3:

$$\begin{pmatrix} 1 & 1 & 1 & 1 \end{pmatrix} \begin{pmatrix} 73 & 27 & 27 & 14 \\ 27 & 22 & 13 & 9 \\ 27 & 13 & 22 & 9 \\ 14 & 9 & 9 & 7 \end{pmatrix} \begin{pmatrix} 1 \\ 1 \\ 1 \\ 1 \end{pmatrix} = 322$$

Evaluando lo mismo para la potencia n-ésima de la matriz se obtiene el número de formas de subdividir una malla de 3x(n+1):

$$\begin{pmatrix} 1 & 1 & 1 & 1 \end{pmatrix} \begin{pmatrix} 8 & 2 & 2 & 1 \\ 2 & 4 & 1 & 1 \\ 2 & 1 & 4 & 1 \\ 1 & 1 & 1 & 2 \end{pmatrix}^n \begin{pmatrix} 1 \\ 1 \\ 1 \\ 1 \end{pmatrix} = 4, 34, 322, 3164, 31484, 314662, 3149674, 31544384, ...$$

Esta secuencia se encuentra en la OEIS como A208215.

Si se aplicara este método a cuadrículas de 4xn, se necesitaría una matriz de 16x16. Cada fila adicional duplica el tamaño de la matriz, por lo que pronto se vuelve difícil de manejar.

Answer 4

Para las cuadrículas cuadradas, el "Número de formas de dividir un $n\times n$ cuadrado en rectángulos de lados enteros" es la secuencia OEIS A182275 . No hay fórmulas, pero para $n\le12$ las siguientes cifras han sido calculadas por Joshua Smith y Helena Verrill:

1 1
2 8
3 322
4 70878
5 84231996
6 535236230270
7 18100579400986674
8 3250879178100782348462
9 3097923464622249063718465240
10 15657867573050419014814618149422562
11 419678195343896524683571751908598967042082
12 59647666241586874002530830848160043213559146735474

Ver también A034999 para $2\times n$ rejillas y A116694 para $m\times n$ rejillas.

Answer 5

Aunque esta es una discusión fascinante, la realidad es que muchas de estas cuadrículas serían ilegibles porque no es inmediatamente evidente qué panel viene a continuación es una secuencia. Un panel vertical a la derecha, con pilas a la izquierda es problemático porque el lector no sabe si debe leer hacia la derecha o hacia abajo. De los mostrados anteriormente, sólo $175$ de ellos son funcionales.