Quilt squares

In a discussion on comp.lang.perl.misc of what non-cgi things perl is used for, someone mentioned that he once generate all the quilt blocks of a certain type (sixteen-patch half-square triangles with 90-degree rotational symmetry) and printed out the result: http://www.plover.com/~mjd/misc/quilt/composites/bindexs.jpg

If mirror images considered identical, and negative images considered identical, there are 72 unique patterns.

How many unique patterns are there in the general NxN case, not just

First, note that N must be even.

Now a pattern is completely defined by its upper-left quadrant, since it has 4-way rotational symmetry. So we only need to consider the MxM grid which is the upper-left corner, where M=N/2.Each square can have one of 4 possible values. Call an assignment of values to this MxM grid a 'configuration'.

There are 4^(MxM) such configurations. We must find out how many are 'unique', subject to the equivalence rules of inversion and flipping.

Denote the inverse of a config X as i(X).

Any left-to-right or top-to-bottom flip of the whole pattern is equivalent to flipping the upper-left quadrant around its diagonal (i.e. doing a matrix transpose). Denote the flip of config X around its diagonal as f(X).

Observe that for all X, i(i(X)) = X and f(f(X)) = X and i(X)!=X. From this, the following lemmas are easy to prove: Lemma 1: for all X, f(X) = X implies f(i(X)) = f(i(X)) Lemma 2: for all X, i(f(X)) = f(i(X)) Lemma 3: for all X, f(X) != i(X) implies i(f(X)) != X

For the following bit, I'll define the 4 types of squares. Type 0 has its upper-left black. Type 1 has its lower-right black. Type 2 has its upper-right black and type 3 has its lower-left black.

How many configs are flip-invariant (i.e. f(X) = X) ? For X to be flip-invariant, all the squares along the diagonal must be type-0 or type-1. Also, all the pairs of (non-diagonal) 'opposite' squares must be (0,0), (1,1), (2,3) or (3,2). This gives a total of 2^(MxM) configs. Call this set A.

For how many configs is the inverse the same as the flip (i.e. f(X) = i(X)) ? For this to be true, all the squares along the diagonal must be type-2 or type-3. Also, all the pairs of (non-diagonal) 'opposite' squares must be (2,2), (3,3), (0,1) or (1,0). This gives a total of 2^(M*M) configs. Call this set B.

Note that A and B are non-intersecting, since i(X) != X for all X. Hence the number of remaining configs is 4^(M*M) - 2.2^(M*M). Call this set C.

Now consider set A. Using lemma 1, we can prove that its elements are divided into disjoint pairs (X, Y) such that (X,Y) are inverses, f(X) = X and f(Y)=Y. X and Y are equivalent configs since they are inverses. [We use the property that f(f(U)) = U and i(i(U)) = U to show that since all mappings go within the pair, none can map into the pair from any config outside the pair.]

Now consider set B. Similarly, we can prove that its elements are divided into disjoint pairs (X, Y) such that (X,Y) are inverses and flips of each-other. X and Y are again equivalent.

Now consider set C. Using lemmas 2 and 3, we can prove that its elements are divided into disjoint 4-tuples (V,W,X,Y) such that (V,W) are inverses, (X,Y) are inverses, (V,X) are flips and (W,Y) are flips. V,W,X and Y are equivalent.

Observe that no config in set A, B or C is equivalent to any config in a different set.

So the total number of unique configs under the equivalence rules is #elements(A) / 2 + #elements( / 2 + #elements(C) / 4.

This is (2^(M*M))/2 + (2^(M*M))/2 + (4^(M*M) - 2.2^(M*M))/4 = 4^(M*M-1) + 2^(M*M-1)

You can re-write it in terms of N if you like: = 4^(N*N/4-1) + 2^(N*N/4-1)

If N=4, this is 72 configs. What I want to know is why your diagram shows 73 ?

Regards,

Because the author made a mistake. In the 5th row, the 4th and 6th are equivilant. I'm not the author of the image... I saw the link on comp.lang.perl.misc, posted by a guy who had written a perl program to generate all the different possible quilt squares, eliminating equivilant squares. Obviously, there was a bug somewhere in his