Page 1 of 1
[Help] patterns inside an NxN box, w/o rotations reflections
Posted: April 29th, 2013, 2:21 pm
by 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
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, ...
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, ...
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...
Re: [Help] patterns inside an NxN bounding box
Posted: April 30th, 2013, 5:50 am
by 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.
Re: [Help] patterns inside an NxN bounding box
Posted: April 30th, 2013, 6:17 am
by DivusIulius
Kasuha wrote:
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?
Re: [Help] patterns inside an NxN box, w/o rotations reflections
Posted: April 30th, 2013, 6:55 pm
by apg
Re: [Help] patterns inside an NxN box, w/o rotations reflections
Posted: May 1st, 2013, 4:27 am
by DivusIulius
Hey, thank you very much
