[Help] patterns inside an NxN box, w/o rotations reflections

[DivusIulius]

Please, I need some help with the closed-form mathematical solution to Q, the number of unique patterns that require an N by N bounding box.

My progress so far...

Edge N, of the bounding box

Code: Select all

N = 0, 1, 2, 3, 4, 5...

M, the number of all patterns within an N by N bounding box:

Code: Select all

M = 2^(N^2) = 1, 2, 16, 512, 65536, 33554432, ...

P, the number of all unique patterns (that is, excluding rotations and reflections):

Code: Select all

If N is even, P = (1/8)*(2^(N^2)+2*2^(N^2/4)+3*2^(N^2/2)+2*2^((N^2+N)/2))
If N is odd, P = (1/8)*(2^(N^2)+2*2^((N^2+3)/4)+2^((N^2+1)/2)+4*2^((N^2+N)/2))

P = 1, 2, 6, 102, 8548, 4211744, ...

Q, the number of all unique patterns that require an N x N bounding box. [EDIT: excluding rotations and reflections.]

Some exact values are provided as an example:

Code: Select all

Q = f(N) = 1, 1, 3, 66, 6727, 3723810, ?, ...

Any help or hint will be very much appreciated... Thanks in advance...

[Kasuha]

Let's assume filling an MxN rectangle (I don't know what exactly are your rules for a square)
Let's assume an MxN rectangle is required if at least one cell in each edge is alive
In general case (large M and N) we have:
- four corner cells
- four "pure" edges, two of length M-2, two of length N-2
- inside (M-2) x (N-2)

anything can be in the inside so that's 2^((M-2)x(N-2)) times all valid variants in corners or edges

on the edge, either 2^x or (2^x)-1 variants is possible depending on whether the corner cell is set or not
(where M-2 or N-2 goes for x)

Corners have 16 variants. Let's just count each separately:

Order is:
corners: upper left, upper right, lower right, lower left, 0 means dead, 1 means alive
edges: upper (M), right (N), lower (M), left (N) - 1 means all variants possible, 0 means zeros not possible

Let's define
m = 2^(M-2)
n = 2^(N-2)

corners -> edges -> variants
0000 -> 0000 -> (m-1).(n-1).(m-1).(n-1)
0001 -> 0011 -> (m-1).(n-1).m.n
0010 -> 0110 -> (m-1).n.m.(n-1)
0011 -> 0111 -> (m-1).n.m.n
0100 -> 1100 -> (m-1).(n-1).m.n
0101 -> 1111 -> m.n.m.n
0110 -> 1110 -> m.n.m.(n-1)
0111 -> 1111 -> m.n.m.n
1000 -> 1001 -> m.(n-1).(m-1).n
1001 -> 1011 -> m.(n-1).m.n
1010 -> 1111 -> m.n.m.n
1011 -> 1111 -> m.n.m.n
1100 -> 1101 -> m.n.(m-1).n
1101 -> 1111 -> m.n.m.n
1110 -> 1111 -> m.n.m.n
1111 -> 1111 -> m.n.m.n

sum them up, multiply by the inside and you're done.

[DivusIulius]

sum them up, multiply by the inside and you're done.

Thanks for your comprehensive answer.

I forgot to emphasize one detail: How do I remove rotations and reflections from the sum?

[apg]

Use Burnside's lemma:

http://en.wikipedia.org/wiki/Burnside's_lemma

[DivusIulius]

Use Burnside's lemma:

http://en.wikipedia.org/wiki/Burnside's_lemma

Hey, thank you very much