> #2 by 2 by n perfect matchings > #We set a,b,c,d equal to the polynomials of weights of n=1,2,3,4 respectively > a:= x^2 + y^2; 2 2 a := x + y > b:= (x^2+y^2+z^2)^2; 2 2 2 2 b := (x + y + z ) > c:= (x^2+y^2)*(x^2+y^2+2*z^2)^2; 2 2 2 2 2 2 c := (x + y ) (x + y + 2 z ) > d:= ((x^2+y^2)^2 + 3*z^2*(x^2+y^2) + z^4)^2; 2 2 2 2 2 2 4 2 d := ((x + y ) + 3 z (x + y ) + z ) > #Then we know that the recurrence when x=y=z=1 is a(n)=3a(n-1)+3a(n-2)-a(n-3) so we can test the most likely ways to get that recurrence (e.g. multiplying by 3 may be equivalent to multiplying by x^2 + 2y^2). Since x,y have been symmetric in the functions to this point, we will expect x,y to be symmetric in the multipliers. The coefficient of a(n-3) will most likely be x^2, y^2 or z^2 > m:= x^2 + y^2 + z^2; 2 2 2 m := x + y + z > n:= x^2 + 2*y^2; 2 2 n := x + 2 y > o:= x^2 + 2*z^2; 2 2 o := x + 2 z > p:= 2*x^2 + z^2; 2 2 p := 2 x + z > q:= 2*x^2 + y^2; 2 2 q := 2 x + y > evalb( d = m*c+m*b-(z^2)*a); false > evalb( d = m*c+m*b-(x^2)*a); false > evalb( d = m*c+m*b-(y^2)*a); false > r:= 2*y^2 + z^2; 2 2 r := 2 y + z > s:= y^2 + 2*z^2; 2 2 s := y + 2 z > evalb( d = m*c+n*b-(x^2)*a); false > evalb( d = m*c+n*b-(y^2)*a); false > evalb( d = m*c+n*b-(z^2)*a); false > evalb( d = m*c+o*b-(x^2)*a); false > evalb( d = m*c+o*b-(z^2)*a); false > evalb( d = m*c+o*b-(y^2)*a); false > evalb( d = m*c+p*b-(y^2)*a); false > evalb( d = m*c+p*b-(x^2)*a); false > evalb( d = m*c+p*b-(z^2)*a); false > evalb( d = m*c+q*b-(x^2)*a); false > evalb( d = m*c+q*b-(y^2)*a); false > evalb( d = m*c+q*b-(z^2)*a); false > t:= 3*z^2; 2 t := 3 z > evalb( d = m*c+t*b-(z^2)*a); false > evalb( d = m*c+t*b-(x^2)*a); false > evalb( d = m*c+t*b-(y^2)*a); false > evalb( d = t*c+t*b-(z^2)*a); false > evalb( d = t*c+t*b-(x^2)*a); false > evalb( d = t*c+t*b-(y^2)*a); false > evalb( d = t*c+m*b-(y^2)*a); false > evalb( d = t*c+m*b-(z^2)*a); false > evalb( d = t*c+m*b-(x^2)*a); false > #OK... so its not working so well. I guess it would be a good point to notice the z term in the n=4 case and compare it to the previous cases. The n=4 case has a z^8 term when expanded. The only other polynomial prior to that that has a z term alone is n=2 where z^4 appears. Since we do not want to multiply by anything with a negative exponent, the only way to get a z^8 term in n=4 from the n=1,2,3 cases then is to multiply the n=2 case by an expression containing z^4. > u:= x^4 + y^4 + z^4; 4 4 4 u := x + y + z > evalb( d = m*c+u*b-(z^6)*a); false > evalb( d = m*c+u*b-(z^8)*a); false > evalb( d = m*c+u*b-(z^10)*a); false > evalb( d = m*c+u*b-(z^4)*a); false > evalb( d = m*c+u*b-(z^2)*a); false > #I guess a few more cases couldnt hurt. I will try n=5 and report back. > #I found by brute force that n=5 can be written as the following > (x^2+y^2)*d+2*((x^2+y^2)*(c*z^2+b*z^4+a*z^6+z^8))+z^4*c; 2 2 2 2 2 2 2 2 4 2 2 2 (x + y ) ((x + y ) + 3 z (x + y ) + z ) + 2 (x + y ) ( 2 2 2 2 2 2 2 2 2 2 2 4 (x + y ) (x + y + 2 z ) z + (x + y + z ) z 2 2 6 8 4 2 2 2 2 2 2 + (x + y ) z + z ) + z (x + y ) (x + y + 2 z ) > simplify(%); 6 2 2 2 6 2 2 6 2 4 4 2 4 2 4 32 x z y + 48 x z y + 32 x y z + 48 x y z + 66 x y z 2 4 4 2 8 2 8 8 2 6 4 + 66 x y z + 9 x z + 9 y z + 5 x y + 10 x y 8 2 6 4 4 6 4 6 2 8 + 8 x z + 22 x z + 10 x y + 24 x z + 5 x y 8 2 6 4 4 6 10 10 + 8 y z + 22 y z + 24 y z + x + y > factor(%); 2 2 2 2 2 2 2 2 2 2 (x + y ) (x + y + z ) (y + x + 3 z ) > #We set x=y=z=1 to quickly check that indeed this is 2*15^2. Now we can set up a system of equations to get the recurrence (I hope that Maple solves systems for polynomial solutions) > e:= (x^2+y^2)*(x^2+y^2+z^2)^2*(y^2+x^2+3*z^2)^2; > 2 2 2 2 2 2 2 2 2 2 e := (x + y ) (x + y + z ) (y + x + 3 z ) > a; 2 2 x + y > b; 2 2 2 2 (x + y + z ) > c; 2 2 2 2 2 2 (x + y ) (x + y + 2 z ) > d; 2 2 2 2 2 2 4 2 ((x + y ) + 3 z (x + y ) + z ) > e; 2 2 2 2 2 2 2 2 2 2 (x + y ) (x + y + z ) (y + x + 3 z ) > solve( {g*b+h*a-i=c, g*c+h*b-i*a=d, g*d+h*c-i*b=e}, {g,h,i} ); 2 2 2 6 2 2 2 2 {g = x + y + z , i = z , h = (x + y + z ) z } > #Whew! That was easy. Notice that when x=y=z=1, g=h=3 and i=1, which is what we desired. Notice also that this system has a UNIQUE solution, AND we already know the case where x=y=z=1 follows a recurrence for all n (see my website), so it would be a pretty good guess that this recurrence works for all n. That is a[n](x,y,z) = (x^2+y^2+z^2)*a[n-1](x,y,z) + (x^2+y^2+z^2)*z^2*a[n-2](x,y,z) - z^6*a[n-3](x,y,z). So even though x and y are symmetric, like we thought, it would have taken a long time to guess g,h, and i. Lets use the new recurrence and see if it works well. > S:= proc(n) if n=0 then 1 elif n=1 then (x^2+y^2) elif n=2 then (x^2+y^2+z^2)^2 else factor((x^2+y^2+z^2)*S(n-1) + (x^2+y^2+z^2)*z^2*S(n-2) - z^6*S(n-3)); fi; end; S := proc(n) if n = 0 then 1 elif n = 1 then x^2 + y^2 elif n = 2 then (x^2 + y^2 + z^2)^2 else factor((x^2 + y^2 + z^2)*S(n - 1) + (x^2 + y^2 + z^2)*z^2*S(n - 2) - z^6*S(n - 3)) end if end proc > S(4); 4 2 2 4 2 2 2 2 4 2 (x + 2 x y + y + 3 z x + 3 z y + z ) > S(5); 2 2 2 2 2 2 2 2 2 2 (x + y ) (x + y + z ) (y + x + 3 z ) > S(6); 6 4 2 2 4 6 4 2 2 2 2 4 2 (x + 3 x y + 3 x y + y + 5 x z + 10 x z y + 5 y z 2 4 2 4 6 2 + 6 x z + 6 y z + z ) > S(7); 2 2 2 2 2 2 (x + y ) (x + y + 2 z ) 4 2 2 2 2 4 4 2 2 2 (y + 2 x y + 4 z y + x + 2 z + 4 z x ) > #Great! Alternating between a square and twice a square when x=y=z=1. Now to find a generating function F(x,y,z,w) where w^n counts the number of perfect matchings of the 2 x 2 x n grid. We know the recurrence, and we know that it satisfies that recurrence starting at the first term possible (namely n=3), so we expect the numerator to be less than the power of the denominator in the g.f. We have the first 6 terms, which should do. > f:= (1-(x^2+y^2+z^2)*w-(x^2+y^2+z^2)*z^2*w^2 + z^6*w^3); 2 2 2 2 2 2 2 2 6 3 f := 1 - (x + y + z ) w - (x + y + z ) z w + z w > expand(f*(S(1)+S(2)*w+S(3)*w^2+S(4)*w^3+S(5)*w^4+S(6)*w^5+S(7)*w^6+S(8)*w^7+S(9)*w^8)); 4 2 6 9 16 4 9 18 2 9 20 w z - w z - 137 w x z - 18 w x z - w y 9 6 4 10 9 6 6 8 9 12 6 2 - 22320 w x y z - 28880 w x y z - 4018 w x z y 9 6 2 12 9 6 8 6 9 6 10 4 - 8332 w x y z - 20090 w x y z - 7672 w x y z 9 6 12 2 9 4 4 12 9 8 10 2 - 1512 w x y z - 12498 w x y z - 2268 w x y z 9 4 6 10 9 4 8 8 9 8 8 4 - 22320 w x y z - 21660 w x y z - 9590 w x y z 9 10 2 8 9 10 4 6 9 12 2 6 - 2268 w x z y - 7672 w x z y - 1512 w x z y 9 14 2 4 9 12 4 4 9 8 10 2 - 648 w x z y - 3836 w x z y - 11160 w x z y 9 10 10 9 12 8 9 6 14 - 2232 w x z - 1444 w x z - 120 w x y 9 6 14 9 4 16 9 4 16 - 1106 w x z - 45 w x y - 295 w x z 9 2 18 9 8 12 9 12 8 - 10 w x y - 210 w x y - 210 w x y 9 14 6 9 16 4 9 18 2 - 120 w x y - 45 w x y - 10 w x y 9 10 10 9 18 2 9 16 4 - 252 w x y - 18 w y z - 137 w y z 9 14 6 9 8 12 9 12 8 - 574 w y z - 2083 w y z - 1444 w y z 9 10 10 9 6 14 9 4 16 20 9 - 2232 w y z - 1106 w y z - 295 w y z - z w 22 10 9 8 8 4 9 2 16 2 + z w - 21660 w z x y - 162 w x y z 9 2 14 4 9 2 12 6 9 10 8 2 - 1096 w x y z - 4018 w x y z - 8664 w x z y 9 2 6 12 9 2 10 8 9 2 8 10 - 8332 w x y z - 8664 w x y z - 11160 w x y z 9 2 4 14 9 2 2 16 9 6 14 - 3318 w x y z - 590 w x y z - 574 w z x 9 8 12 9 6 8 6 9 2 14 4 - 2083 w x z - 20090 w y x z - 1096 w y x z 9 2 16 2 18 11 2 4 8 11 6 10 - 162 w y x z + 1830 z w x y + 896 z w x y 16 11 2 6 14 11 2 8 + 3680 z w x y + 3855 z w x y 10 11 6 8 8 11 8 8 + 3710 z w x y + 1120 z w x y 10 11 8 6 8 11 14 2 8 11 10 6 + 3710 z w x y + 128 z w x y + 896 z w x y 8 11 12 4 10 11 12 2 + 448 z w x y + 742 z w x y 10 11 10 4 12 11 6 6 + 2226 z w x y + 7520 z w x y 16 11 6 2 12 11 2 10 + 3680 z w x y + 2256 z w x y 10 11 2 12 8 11 2 14 20 11 2 2 + 742 z w x y + 128 z w x y + 400 z w x y 16 11 4 4 14 11 4 6 + 5520 z w x y + 7710 z w x y 12 11 10 2 18 11 4 2 + 2256 z w x y + 1830 z w x y 12 11 4 8 10 11 4 10 + 5640 z w x y + 2226 z w x y 8 11 4 12 6 11 16 2 6 11 8 10 + 448 z w x y + 9 z w x y + 126 z w x y 14 11 6 4 14 11 8 2 6 11 4 14 + 7710 z w x y + 3855 z w x y + 36 z w x y 6 11 2 16 6 11 6 12 6 11 10 8 + 9 z w x y + 84 z w x y + 126 z w x y 6 11 12 6 6 11 14 4 18 11 6 + 84 z w x y + 36 z w x y + 610 z w x 16 11 8 14 11 10 12 11 12 + 920 z w x + 771 z w x + 376 z w x 20 11 4 22 11 2 8 11 16 + 200 z w x + 25 z w x + 16 z w y 10 11 14 12 11 12 6 11 18 + 106 z w y + 376 z w y + z w x 6 11 18 18 11 6 14 11 10 + z w y + 610 z w y + 771 z w y 16 11 8 20 11 4 22 11 2 + 920 z w y + 200 z w y + 25 z w y 2 10 20 4 10 18 2 10 20 18 10 4 - z w x - 17 z w y - z w y - 95 z w y 16 10 6 10 10 12 12 10 10 - 496 z w x - 1068 z w x - 1461 z w x 14 10 8 18 10 4 20 10 2 - 1163 z w x - 95 z w x - 5 z w x 20 10 2 10 10 12 16 10 6 - 5 z w y - 1068 z w y - 496 z w y 12 10 10 14 10 8 8 10 14 - 1461 z w y - 1163 z w y - 468 z w y 6 10 16 10 11 14 8 11 16 - 121 z w y + 106 z w x + 16 z w x 10 10 8 4 12 11 8 4 - 16020 z w x y + 5640 z w x y 6 10 2 14 6 10 4 12 - 968 z w x y - 3388 z w x y 6 10 12 4 6 10 10 6 - 3388 z w x y - 6776 z w x y 6 10 8 8 6 10 6 10 18 10 2 2 - 8470 z w x y - 6776 z w x y - 190 z w x y 2 10 6 14 2 10 4 16 4 10 2 16 - 120 z w x y - 45 z w x y - 153 z w x y 8 10 2 12 2 10 2 18 2 10 8 12 - 3276 z w x y - 10 z w x y - 210 z w x y 9 18 2 9 18 2 9 4 10 6 - 30 w z x - 30 w z y - 12054 w x y z 9 4 12 4 9 4 14 2 9 4 14 2 - 3836 w x y z - 648 w x y z - 3318 w x z y 6 10 16 4 10 18 9 20 - 121 z w x - 17 z w x - w x 8 10 10 4 8 10 6 8 - 9828 z w x y - 16380 z w y x 6 10 2 14 4 10 2 16 8 10 14 - 968 z w y x - 153 z w y x - 468 z w x 2 10 12 8 2 10 14 6 2 10 16 4 - 210 z w x y - 120 z w x y - 45 z w x y 2 10 18 2 2 10 10 10 - 10 z w x y - 252 z w x y 10 10 10 2 14 10 2 6 - 6408 z w x y - 4652 z w x y 10 10 2 10 12 10 2 8 - 6408 z w x y - 7305 z w x y 16 10 2 4 8 10 4 10 - 1488 z w x y - 9828 z w x y 4 10 4 14 16 10 4 2 - 612 z w x y - 1488 z w x y 12 10 6 4 10 10 6 6 - 14610 z w x y - 21360 z w x y 8 10 12 2 14 10 6 2 - 3276 z w x y - 4652 z w x y 8 10 6 8 4 10 6 12 - 16380 z w x y - 1428 z w x y 14 10 4 4 4 10 8 10 - 6978 z w x y - 2142 z w x y 12 10 4 6 10 10 4 8 - 14610 z w x y - 16020 z w x y 4 10 10 8 4 10 12 6 - 2142 z w x y - 1428 z w x y 4 10 14 4 12 10 8 2 - 612 z w x y - 7305 z w x y 9 10 6 4 2 2 2 2 2 2 - 12054 w x z y + x + y + w z x + w z y > #So wading through all of this and finding all terms with the order of w less than or equal to 2 we get the numerator of (x^2+y^2)+z^2*(x^2+y^2+z^2)*w-(z^6)*w^2, which is good since we can let x=y=z=1 to get a numerator of 2+3*w-w^2, which is what we had when we omitted the weighting scheme. One last check would be to expand the g.f through a taylor expansion. > factor(taylor( ((x^2+y^2)+z^2*(x^2+y^2+z^2)*w-(z^6)*w^2)/(f), w, 8)); 2 2 2 2 2 2 2 2 2 2 2 2 2 (x + y ) + (x + y + z ) w + (x + y ) (x + y + 2 z ) w + 4 2 2 4 2 2 2 2 4 2 3 (x + 2 x y + y + 3 z x + 3 z y + z ) w + 2 2 2 2 2 2 2 2 2 2 4 6 (x + y ) (x + y + z ) (y + x + 3 z ) w + (x 4 2 2 4 6 4 2 2 2 2 4 2 + 3 x y + 3 x y + y + 5 x z + 10 x z y + 5 y z 2 4 2 4 6 2 5 2 2 2 2 2 2 + 6 x z + 6 y z + z ) w + (x + y ) (x + y + 2 z ) 4 2 2 2 2 4 4 2 2 2 6 (y + 2 x y + 4 z y + x + 2 z + 4 z x ) w + 2 2 2 2 6 2 4 4 2 2 2 2 (x + y + z ) (y + 3 x y + 6 y z + 12 x z y 2 4 4 2 4 2 2 4 6 6 2 7 + 9 y z + 3 x y + 6 x z + 9 x z + x + z ) w + 8 O(w ) > #Looks good. Time to try for a bijection with our new information. >