###################################################################### ##RITSUF: Save this file as RITSUF # ## To use it, stay in the # ##same directory, get into Maple (by typing: maple ) # ##and then type: read RITSUF # ##Then follow the instructions given there # ## # ##Written by Doron Zeilberger, Rutgers University , # #zeilberg at math dot rutgers dot edu # ###################################################################### #Created: April 18, 2012 print(`Created: April 18 2012`): print(` This is RITSUF`): print(`It accompanies the article `): print(`Automatic Counting of Tilings of Skinny Plane Regions`): print(`by Shalosh B. Ekhad and Doron Zeilberger`): print(`and also available from Zeilberger's website`): print(``): print(`Please report bugs to zeilberg at math dot rutgers dot edu`): print(``): print(`The most current version of this package and paper`): print(` are available from`): print(`http://www.math.rutgers.edu/~zeilberg/ .`): print(`-------------------------------------------------------`): print(`For a list of the available lists of procedures type ezra(); ,`): print(`for help with`): print(`a specific procedure, type ezra(procedure_name); .`): print(``): print(`-------------------------------------------------------`): with(combinat): with(LinearAlgebra): ezraMD:=proc() if args=NULL then print(` The Monomer-Dimers procedures are: `): print(` GFframeDoubleMD `): print(` GFrectMD, NTframeMD,`): print(` SeqCrossCmd, SeqCrossMD `): print(` SeqFrameCmd, SeqFrameMD, `): print(` SeqRectCmd, SeqRectMD, `): print(` `): print(` `): else ezra(args): fi: end: ezraGuess:=proc() if args=NULL then print(` The Guessing procedures are: `): print(` GFfromRec, GuessRec, SeqFromRec `): else ezra(args): fi: end: ezraR:=proc() if args=NULL then print(` The procedures defining families of regions are: Cross, `): print(` Frame, JaggedRect, Rect, RectG, RectPlus `): else ezra(args): fi: end: ezraObsolete:=proc() if args=NULL then print(` The obsolete procedures are: `): print(` SeqFrameDoubleSlow, SeqFrameSlow, SeqFrameVerySlow `): else ezra(args): fi: end: ezraDmd:=proc() if args=NULL then print(` The procedures that use direct enumeration of`): print(` monomer-dimer tilings are: SeqFrameDirectMD, SeqRectDirectMD `): else ezra(args): fi: end: ezraDirect:=proc() if args=NULL then print(` The procedures that use direct enumeration of dimer tilings are: `): print(`SeqCrossDirect, SeqCrossDirectMD,`): print(` SeqCrossCdirect, SeqCrossCsqDirect, `): print(`SeqFrameCdirect,SeqFrameCsqDirect `): print(` SeqFrameDirect, SeqFrameDirectDouble, `): print(` SeqRectDirect `): else ezra(args): fi: end: ezra11:=proc() if args=NULL then print(` The (supporting)^2 procedures are: `): print(` CartProd, CoveredSet, NS, SN `): else ezra(args): fi: end: ezra1Dimer:=proc() if args=NULL then print(` The supporting procedures about Dimer tilings are: `): print(` Followers, GenTilingsNE, GenTilingsNW, `): print(` GenTilingsSE, GenTilingsSW `): print(` NT, NTrect, NuskhaF, OutsideSide, RectT, RTM, `): print(` SeqCross, SeqFrame `): print(`SeqFrameDouble, , SeqRect `): print(` SeqsInfo, SocPe, T, Tgen, TilS, TM `): else ezra(args): fi: end: ezra1MD:=proc() if args=NULL then print(` The supporting procedures for Monomer-Dimer tilings are: `): print(` FollowersMD, NTmd, RectTmd, RTMmd `): print(` TgenMD, Tmd `): print(` `): else ezra(args): fi: end: ezraSmd:=proc() if args=NULL then print(` The stories procedures are: `): print(` GFframeDoubleStoryMD, , SeferGFframeDoubleMD `): print(` SeqCrossCstoryMD, SeferCrossCmd `): print(` SeqFrameCstoryMD, SeferFrameCmd `): print(` SeqRectCstoryMD, SeferRectCmd `): else ezra(args): fi: end: ezraSd:=proc() if args=NULL then print(` The stories procedures are: `): print(` GFframeDoubleStory, SeferGFframeDouble `): print(` SeferCrossC, SeferCrossCsq, SeqCrossCstory, SeqCrossCsqStory, `): print(` SeferFrameC, SeferFrameCsq, SeqFrameCstory, SeqFrameCsqStory, `): print(` SeferRectC , SeqRectCstory `): else ezra(args): fi: end: ezraDimer:=proc() if args=NULL then print(`The procedures about dimer tilings are: `): print(` GFframeDouble `): print(`GFrect, NTframe, `): print(` SeqCrossC, SeqCrossCsq, `): print(` SeqFrameC, SeqFrameCsq `): print(`SeqRectC `): else ezra(args): fi: end: ezra:=proc() if args=NULL then print(`For the list of procedures for`): print(`Dimer tilings: type: ezraDimer(); `): print(`monomer-Dimer tilings: type: ezraMD(); `): print(`stories about Dimer tilings: type: ezraSd(); `): print(`stories about Monomer-Dimer tilings: type: ezraSmd(); `): print(`guessing: type: ezraGuess(); `): print(`supporting procedures about Dimer tilings: type: ezra1Dimer();`): print(`supporting procedures about Monomer-Dimer tilings: ezra1MD();`): print(` defining families of regions, type: ezraR(); `): print(` doing it directly, type: ezraDirect(); `): elif nops([args])=1 and op(1,[args])=CartProd then print(`CartProd(L1,L2,L3,L4): Given four multisets `): print(`{[a,m1]}, {[b,m2]}, {[c,m3]}, {[d,m4]}`): print(`finds the set {[[a,b,c,d],m1*m2*m3*m4]}`): print(`Try:`): print(`CartProd({[a,1]}, {[b,1]}, {[c,1]}, {[d,1]});`): elif nops([args])=1 and op(1,[args])=CoveredSet then print(`CoveredSet(T): given a tiling of lattice points, finds`): print(`the set of lattice points covered, try:`): print(`CoveredSet({{[0,1],[1,1]},{[2,1],[2,2]});`): elif nops([args])=1 and op(1,[args])=Cross then print(`Cross(v,h,m1,m2,m3,m4): The cross whose center is an h by v rectangle`): print(`with an m1 by v rectangle to its right, an h by m2 above,`): print(`an m3 by v to the left, and an h by m4 below`): print(`Try:`): print(`Cross(1,1,2,3,2,3);`): elif nops([args])=1 and op(1,[args])=Frame then print(`Frame(a1,a2,b1,b2,m,n): The region of`): print(`the picture frame of an (a1+m+a2)x(b1+n+b2)`): print(`rectangle with a middle mxn rectancle removed`): print(`Try: Frame(2,2,2,2,4,4);`): elif nops([args])=1 and op(1,[args])=Followers then print(`Followers(S,m): given a state S (a subset of {1, ...,m})`): print(`and a pos. integer m, outputs the set of states that`): print(`may follow S, Try:`): print(`Followers({1,2},2);`): elif nops([args])=1 and op(1,[args])=FollowersMD then print(`FollowersMD(S,m): given a state S (a subset of {1, ...,m})`): print(`and a pos. integer m, outputs the set of states that`): print(`may follow S, in a monomer-dimer tiling. Try:`): print(`FollowersMD({1,2},2);`): elif nops([args])=1 and op(1,[args])=GenTilingsNE then print(`GenTilingsNE(a2,b2): `): print(`Inputs positive integers a2 and b2`): print(`and outputs the set of pairs`): print(`[[LeftSideFree,DownSideFree],mult]`): print(`where we looked at generalized tilings of`): print(`Rect(a2,b2) where they all have to be covered,`): print(`but one has the option to use lattice points`): print(`with i=-1 or j=-1`): print(`Try:`): print(`GenTilingsNE(3,3);`): elif nops([args])=1 and op(1,[args])=GenTilingsNW then print(`GenTilingsNW(a2,b1): `): print(`Inputs positive integers a2 and b1`): print(`and outputs the set of pairs`): print(`[[RightSideFree,DownSideFree],mult]`): print(`where we looked at generalized tilings of`): print(`Rect(a2,b1) where they all have to be covered,`): print(`but one has the option to use lattice points`): print(`with i=b1 or j=-1`): print(`Try:`): print(`GenTilingsNW(3,3);`): elif nops([args])=1 and op(1,[args])=GenTilingsSE then print(`GenTilingsSE(a1,b2): `): print(`Inputs positive integers a1 and b2`): print(`and outputs the set of pairs`); print(`[[UpSideFree,LeftSideFree],mult]`): print(`where we looked at generalized tilings of`): print(`Rect(a1,b1) where they all have to be covered,`): print(`but one has the option to use lattice points`): print(`with i=-1 or j=a1`): print(`Try:`): print(`GenTilingsSE(3,3);`): elif nops([args])=1 and op(1,[args])=GenTilingsSW then print(`GenTilingsSW(a1,b1): `): print(`Inputs positive integers a1 and b1`): print(`and outputs the set of pairs`): print(`[[RightSideFree,UpSideFree],mult]`): print(`where we looked at generalized tilings of`): print(`Rect(a1,b1) where they all have to be covered,`): print(`but one has the option to use lattice points`): print(`with i=b1 or j=a1`): print(`Try:`): print(` GenTilingsSW(3,3); `): elif nops([args])=1 and op(1,[args])=GFframeDouble then print(`GFframeDouble(a1,a2,b1,b2,x,y,N): `): print(`inputs positive integers a1,a2,b1,b2 and symbols x,y`): print(`and a positive integer N (telling you how far to go in guessing)`): print(`and outputs the rational function in x,y `): print(`whose coeff. of x^m*y^n (when you take the Maclaurin expansion)`): print(`gives you the the number of tilings only using DIMERS`): print(`of the region Frame(a1,a2,b1,b2,m,n);`): print(`For example, try:`): print(`GFframeDouble(2,2,2,2,x,y,30);`): elif nops([args])=1 and op(1,[args])=GFframeDoubleMD then print(`GFframeDoubleMD(a1,a2,b1,b2,x,y,N): `): print(`inputs positive integers a1,a2,b1,b2 and symbols x,y`): print(`and a positive integer N (telling you how far to go in guessing)`): print(`and outputs the rational function in x,y `): print(`whose coeff. of x^m*y^n (when you take the Maclaurin expansion)`): print(`gives you the the number of tilings only using MONOMERS and DIMERS`): print(`of the region Frame(a1,a2,b1,b2,m,n);`): print(`For example, try:`): print(`GFframeDouble(2,2,2,2,x,y,30);`): elif nops([args])=1 and op(1,[args])=GFframeDoubleStory then print(`GFframeDoubleStory(a1,a2,b1,b2,x,y,N): `): print(`a verbose form of GFframeDouble(a1,a2,b1,b2,x,y,N): `): print(`For example, try:`): print(`GFframeDoubleStory(2,2,2,2,x,y,30);`): elif nops([args])=1 and op(1,[args])=GFframeDoubleStoryMD then print(`GFframeDoubleStoryMD(a1,a2,b1,b2,x,y,N): `): print(`a verbose form of GFframeDoubleMD(a1,a2,b1,b2,x,y,N): `): print(`For example, try:`): print(`GFframeDoubleStoryMD(2,2,2,2,x,y,30);`): elif nops([args])=1 and op(1,[args])=GFfromRec then print(`GFfromRec(C,t): the generating function of the C-finite`): print(`sequence C (starting with n=1)`): print(`Try: `): print(`GFfromRec([[-1,-1],[1,1]],t);`): elif nops([args])=1 and op(1,[args])=GFrect then print(`GFrect(a,t): the generating function for enumerating`): print(`domino tilings of an a by n rectangle directly from`): print(`inverting the matrix (1-TM(a)*t)`): print(`and taking the entry of 2^a by 2^a `): print(`Try: GFrect(4,t); `): elif nops([args])=1 and op(1,[args])=GFrectMD then print(`GFrectMD(a,t): the generating function for enumerating`): print(`monomer-dimer tilings of an a by n rectangle directly from`): print(`inverting the matrix (1-TMmd(a)*t)`): print(`and taking the entry of 2^a by 2^a `): print(`Try: GFrectMD(4,t); `): elif nops([args])=1 and op(1,[args])=GuessRec then print(`GuessRec(L): inputs a sequence of numbers, L, `): print(` and tries to guess a linear recurrence equation`): print(`of some order, r, satisfied by it`): print(`L(n)+c1*L(n-1)+...+cr*L(n-r)=0 for all n within the range`): print(`The output would be given as a list of r numbers`): print(`[[c1,c2,...,cr],InitialConditions]`): print(`For example, the Fibonacci sequence is`): print(`[[-1,-1], [1,1]] `): print(`Try:`): print(`GuessRec([1,1,2,3,5,8,13,21,34,55,89]);`): elif nops([args])=1 and op(1,[args])=JaggedRect then print(`JaggedRect(m,n,S1,S2): an m by n rectangle, `): print(`where the leftmost column only contains points with vertical`): print(`height in S1, and the rightmost column only contains points with`): print(`vertical height in S2`): print(`Try: JaggedRect(4,3,{1},{2,3});`): elif nops([args])=1 and op(1,[args])=NuskhaF then print(`NuskhaF(a1,a2,b1,b2,X,m,n): a formula in terms of the functions `): print(`X[SpecificNumber,i,j](Symbol), the number of tilings of `): print(` a SpecificNumber by Symbol rectangle`): print(` that starts at state i and ends at state j`): print(`for the number of domino tilings of`): print(`the (a1+m+a2)x(b1+n+b2)`): print(`rectangle with the middle mxn rectangle removed`): print(`Try: NuskhaF(2,2,2,2,X,m,n);`): elif nops([args])=1 and op(1,[args])=NS then print(`NS(S): given a positive integer n, and a set of integers S`): print(`finds its ID numbers (the numerical equivalent of its binary rep.`): print(`plus 1. For example, try:`): print(`NS({1,2});`): elif nops([args])=1 and op(1,[args])=NT then print(`NT(R): Given a set of lattice points finds the number of`): print(`perfect matchings (alias tilings with dimers). Try:`): print(`NT({[0,0],[1,0],[0,1],[1,1]});`): elif nops([args])=1 and op(1,[args])=NTmd then print(`NTmd(R): Given a set of lattice points finds the number of`): print(`not necessarily perfect matchings (tilings with dimers and monomers)`): print(`Try:`): print(`NTmd({[0,0],[1,0],[0,1],[1,1]}); `): elif nops([args])=1 and op(1,[args])=NTframe then print(`NTframe(a1,a2,b1,b2,m1,n1)`): print(`The number of domino tilings`): print(`of the region Frame(a1,a2,b1,b2,m1,n1)`): print(`Try:`): print(`NTframe(2,2,2,2,5,3);`): elif nops([args])=1 and op(1,[args])=NTframeMD then print(`NTframeMD(a1,a2,b1,b2,m1,n1)`): print(`The number of monomer-dimer tilings`): print(`of the region Frame(a1,a2,b1,b2,m1,n1)`): print(`Try:`): print(`NTframeMD(2,2,2,2,5,3);`): elif nops([args])=1 and op(1,[args])=NTrect then print(`NTrect(a,m):`): print(`The number of domino tilings`): print(`of the region Rect(a,m)`): print(`Try:`): print(`NTrect(2,20);`): elif nops([args])=1 and op(1,[args])=OutsideSide then print(`OutsideSide(a,b,S1): the set of lattice points outside`): print(`the generic a by b rectangle [0,a-1]x[0,b-1] on side S1`): print(`where `): print(` side 1=UP `): print(` side 2=LEFT `): print(` side 3=DOWN `): print(` side 4=RIGHT `): print(` Try : `): print(`OutsideSide(2,3,3);`): elif nops([args])=1 and op(1,[args])=Rect then print(`Rect(m,n): an m by n rectangle, try: Rect(3,4);`): elif nops([args])=1 and op(1,[args])=RectG then print(`RectG(m1,m2,n1,n2): The rectangle [m1,m2]x[n1,n2]`): print(`For example, try:`): print(`RectG(3,4,5,6);`): elif nops([args])=1 and op(1,[args])=RectPlus then print(`RectPlus(m,n,kv): inputs pos. integers m and n, and`): print(`a subset kv of {1,2,3,4}, and outputs the`): print(`rectangle Rect(m,n), followed by the`): print(`lattice points adjacent (outside) to the sides that`): print(`belong to S, where Right=1, Up=2, Left=3, Down=4, for`): print(`example, try:`): print(`RectPlus(3,4,{1,4});`): elif nops([args])=1 and op(1,[args])=RectT then print(`RectT(a,b): `): print(`Inputs positive integers a and b`): print(`indicating the vertical and horizontal side-lengths`): print(`respectively of an a by b specific rectangle`): print(`side 1=UP`): print(`side 2=LEFT`): print(`side 3=DOWN`): print(`side 4=RIGHT`): print(`and outputs the stick-out tensor,`): print(`a set of the form [i1,i2,i3,i4,co] refererring to`): print(`the states of the availability in the four sides of`): print(`domino tilings that definitely cover the a by b rectangle`): print(`but may stick out with states i1,i2,i3,i4 as above.`): print(`Try: `): print(` RectT(2,2); `): elif nops([args])=1 and op(1,[args])=RectTmd then print(`RectTmd(a,b) `): print(`Inputs positive integers a and b`): print(`indicating the vertical and horizontal side-lentghs`): print(`respectively of an a by b specific rectangle`): print(`side 1=UP`): print(`side 2=LEFT`): print(`side 3=DOWN`): print(`side 4=RIGHT`): print(`and outputs the stick-out tensor,`): print(`a set of the form [i1,i2,i3,i4,co] refererring to`): print(`the states of the availability in the four sides of`): print(`monomer-dimer tilings that definitely cover the a by b rectangle`): print(`but may stick out with states i1,i2,i3,i4 as above.`): print(`Try: `): print(` RectTmd(2,2); `): elif nops([args])=1 and op(1,[args])=RTM then print(`RTM(a,b,S1,S2): `): print(`Inputs positive integers a and b`): print(`indicating the vertical and horizontal side-lengths`): print(`respectively of an a by b specific rectangle`): print(`and distinct integers S1 and S2 from {1,2,3,4}`): print(`where the code is`): print(`side 1=UP`): print(`side 2=LEFT`): print(`side 3=DOWN`): print(`side 4=RIGHT`): print(`and outputs the transition matrix`): print(`between all the possible states`): print(`of side S1 and side S2.`): print(`FOR DIMER TILINGS`): print(`(with our convention for numbering the states:`): print(`1 plus the sum of the powers of 2 of the members of the set)`): print(`Try:`): print(`RTM(3,2,2,3);`): elif nops([args])=1 and op(1,[args])=RTMmd then print(`RTMmd(a,b,S1,S2): `): print(`Inputs positive integers a and b`): print(`indicating the vertical and horizontal side-lengths`): print(`respectively of an a by b specific rectangle`): print(`and distinct integers S1 and S2 from {1,2,3,4}`): print(`where the code is`): print(`side 1=UP`): print(`side 2=LEFT`): print(`side 3=DOWN`): print(`side 4=RIGHT`): print(`and outputs the transition matrix`): print(`between all the possible states`): print(`of side S1 and side S2.`): print(`FOR MONOMER-DIMER TILINGS`): print(`(with our convention for numbering the states:`): print(`1 plus the sum of the powers of 2 of the members of the set)`): print(`Try:`): print(`RTMmd(3,2,2,3);`): elif nops([args])=1 and op(1,[args])=SeferCrossC then print(`SeferCrossC(K,t,N): inputs a pos. integer K and outputs`): print(`a book with theorems about tilings with DIMERS, of crosses`): print(`whose central rectangle is an a by b rectangle`): print(`for 1<=a< b<=K; t is the variable for`): print(`the generating function.`): print(`It uses N data points.`): print(`Try: SeferCrossC(3,t,100);`): elif nops([args])=1 and op(1,[args])=SeferCrossCmd then print(`SeferCrossCmd(K,t,N): inputs a pos. integer K and outputs`): print(`a book with theorems about tilings with MONOMERS and`): print(`DIMERS, of crosses`): print(`whose central rectangle is an a by b rectangle`): print(`for 1<=a<=b<=K; t is the variable for`): print(`the generating function.`): print(`It uses N data points.`): print(`Try: SeferCrossCmd(3,t,100);`): elif nops([args])=1 and op(1,[args])=SeferCrossCsq then print(`SeferCrossCsq(K,t,N): inputs a pos. integer K and outputs`): print(`a book with theorems about tilings of picture crosses`): print(`with even parameters (a,a) from 1 to K; t is the variable for`): print(`the generating function.`): print(`It uses N data points.`): print(`Try: SeferCrossCsq(4,t,100);`): elif nops([args])=1 and op(1,[args])=SeferFrameC then print(`SeferFrameC(K,t,N): inputs a pos. integer K and outputs`): print(`a book with theorems about enumerating `): print(` domino tilings of picture frames`): print(`with parameters (a1,a2,b1,b2) from 1 to K; t is the variable for`): print(`the generating function.`): print(`It uses N data points.`): print(`Try: SeferFrameC(3,t,100);`): elif nops([args])=1 and op(1,[args])=SeferFrameCmd then print(`SeferFrameCmd(K,t,N): inputs a pos. integer K and outputs`): print(`a book with theorems about enumerating monomer-dimer `): print(`tilings of picture frames`): print(`with parameters (a1,a2,b1,b2) from 1 to K; t is the variable for`): print(`the generating function.`): print(`It uses N data points.`): print(`Try: SeferFrameCmd(3,t,100);`): elif nops([args])=1 and op(1,[args])=SeferFrameCsq then print(`SeferFrameCsq(K,t,N): inputs a pos. integer K and outputs`): print(`a book with theorems about tilings of picture frames`): print(`with thickness from 1 to K. t is the variable for`): print(`the generating function.`): print(`It uses N data points.`): print(`Try: SeferFrameCsq(3,t,100);`): elif nops([args])=1 and op(1,[args])=SeferGFframeDouble then print(`SeferGFframeDouble(K,x,y,N): inputs a pos. integer K `): print(`and a pos. integer N and two variable names x and y, and outputs`): print(`a web-book with theorems that discover rational functions in x and y`): print(`that are bivariate generating functions`): print(`enumerating dimer (i.e. domino) tilings of picture frames`): print(`with parameters (a1,a2,b1,b2) with rectangular centers`): print(`for 1<=a1,a2,b1,b2<=K .`): print(`It uses N data points.`): print(`Try: SeferGFframeDouble(2,x,y,40);`): elif nops([args])=1 and op(1,[args])=SeferGFframeDoubleMD then print(`SeferGFframeDoubleMD(K,x,y,N): inputs a pos. integer K `): print(`and a pos. integer N and two variable names x and y, and outputs`): print(`a web-book with theorems that discover rational functions in x and y`): print(`that are bivariate generating functions`): print(`enumerating MONOMER-DIMER tilings of picture frames`): print(`with parameters (a1,a2,b1,b2) with rectangular centers`): print(`for 1<=a1,a2,b1,b2<=K .`): print(`It uses N data points.`): print(`Try: SeferGFframeDoubleMD(2,x,y,40);`): elif nops([args])=1 and op(1,[args])=SeferRectC then print(`SeferRectC(K,t,N): inputs a pos. integer K and outputs`): print(`a book with theorems about tilings, with dimers, of rectangles`): print(`of width a for a from 1 to K; t is the variable for`): print(`the generating function.`): print(`It uses N data points. Try:`): print(`SeferRectC(4,t,100);`): elif nops([args])=1 and op(1,[args])=SeferRectCmd then print(`SeferRectCmd(K,t,N): inputs a pos. integer K and outputs`): print(`a book with theorems about tilings, with MONOMERS and DIMERS`): print(` of rectangles`): print(`of width a for a from 1 to K; t is the variable for`): print(`the generating function.`): print(`It uses N data points. Try:`): print(`SeferRectCmd(4,t,100);`): elif nops([args])=1 and op(1,[args])=SeqCross then print(`SeqCross(a,b,N): the first N terms of the`): print(`sequence: number of domino tilings of a cross`): print(`with an a by b rectangular center with`): print(`four arms of length n, for n=1..N`): print(`Try:`): print(`SeqCross(2,2,10);`): elif nops([args])=1 and op(1,[args])=SeqCrossC then print(`SeqCrossC(a,b,N,t): finds`): print(`a C-finite description, and the ordinary generating function`): print(`in the variable t, to the sequence enumerating`): print(`the number of dimer (also called domino) `): print(`tilings of Cross(a,b,n,n) for all n`): print(`using up to N data points, if it can't find anything`): print(`it returns FAIL, and N has to be made larger`): print(`The last output is 0 if the sequence is only non-zero`): print(`for even n, and then the output information is for the sequence`): print(`enumerating Cross(a,b,2*n,2*n).`): print(`Otherwise the last output is 1`): print(`Try:`): print(`SeqCrossC(2,2,20,t);`): elif nops([args])=1 and op(1,[args])=SeqCrossCmd then print(`SeqCrossCmd(a,b,N,t): finds`): print(`a C-finite description, and the ordinary generating function`): print(`in the variable t, to the sequence enumerating`): print(`the number of MONOMER- DIMER `): print(`tilings of Cross(a,b,n,n) for all n`): print(`using up to N data points, if it can't find anything`): print(`it returns FAIL, and N has to be made larger`): print(`Try:`): print(`SeqCrossCmd(2,2,20,t);`): elif nops([args])=1 and op(1,[args])=SeqCrossMD then print(`SeqCrossMD(a,b,N): the first N terms of the`): print(`sequence: number of monomer-dimer tilings of a cross`): print(`with an a by b rectangular center with`): print(`four arms of length n, for n=1..N`): print(`Try:`): print(`SeqCrossMD(2,2,10);`): elif nops([args])=1 and op(1,[args])=SeqCrossCsq then print(`SeqCrossCsq(a,b,N,t): finds`): print(`a C-finite description, and the ordinary generating function`): print(`in the variable t, to the square-root of the`): print(`sequence enumerating the number of `): print(`tilings of Cross(a,b,n,n) for all n`): print(`or of the square-root of half of them`): print(` (if it happens to be perfect squares or twice perfect squares `): print(` thanks for Mihai Ciucu's theorem about reflective symmetry)`): print(`If it is not it returns FAIL with a message`): print(`It uses up to N data points, if it can't find anything`): print(`it returns FAIL, and N has to be made larger`): print(`if it is twice the square root, the last output is 2`): print(`otherwise 1`): print(`Try:`): print(`SeqCrossCsq(2,2,20,t);`): elif nops([args])=1 and op(1,[args])=SeqCrossCsqStory then print(`SeqCrossCsqStory(a,b,N,t): The verbose form of`): print(`SeqCrossCsq(a,b,N,t). `): print(`Try:`): print(`SeqCrossCsqStory(2,2,20,t);`): elif nops([args])=1 and op(1,[args])=SeqCrossCdirect then print(`SeqCrossCdirect(v,h,N,t): `): print(`Like SeqCrossC(v,h,N,t) but directly (hence slower)`): print(`SeqCrossCdirect(2,2,20,t);`): elif nops([args])=1 and op(1,[args])=SeqCrossCstory then print(`SeqCrossCstory(a,b,N,t): The verbose form of`): print(`SeqFrameC(a,b,N,t). `): print(`Try:`): print(`SeqCrossCstory(2,2,20,t);`): elif nops([args])=1 and op(1,[args])=SeqCrossCstoryMD then print(`SeqCrossCstoryMD(a,b,N,t): The verbose form of`): print(`SeqFrameCmd(a,b,N,t). `): print(`Try:`): print(`SeqCrossCstoryMD(2,2,60,t);`): elif nops([args])=1 and op(1,[args])=SeqCrossCsqDirect then print(`SeqCrossCsqDirect(v,h,N,t): `): print(`Like SeqFrameCsq(v,h,N,t) but directly, and hence slower`): print(`Try:`): print(`SeqCrossCsqDirect(2,2,10,t);`): elif nops([args])=1 and op(1,[args])=SeqCrossDirect then print(`SeqCrossDirect(v,h,N): The `): print(`sequence enumerating the number of dimer tilings (perfect matchings)`): print(`for cross whose center is an h by v rectangle`): print(`with an n v rectangle to its right and left, an h by n above,`): print(`and below for n from 0 to N`): print(`Try:`): print(`SeqCrossDirect(1,1,10);`): elif nops([args])=1 and op(1,[args])=SeqCrossDirectMD then print(`SeqCrossDirectMD(v,h,N): The `): print(`sequence enumerating the number of monomer-dimer tilings`): print(`for cross whose center is an h by v rectangle`): print(`with an n v rectangle to its right and left, an h by n above,`): print(`and below for n from 0 to N`): print(`Try:`): print(`SeqCrossDirectMD(1,1,10);`): elif nops([args])=1 and op(1,[args])=SeqFrame then print(`SeqFrame(a1,a2,b1,b2,N): The first N terms of the sequence`): print(`enumerating domino tilings of`): print(`the (a1+n+a2)x(b1+n+b2)`): print(`rectangle with the middle nxn square removed`): print(`Try: SeqFrame(2,2,2,2,10);`): elif nops([args])=1 and op(1,[args])=SeqFrameDouble then print(`SeqFrameDouble(a1,a2,b1,b2,N1,N2): The terms of the `): print(`double sequence`): print(`enumerating domino tilings of`): print(`the (a1+i+a2)x(b1+j+b2)`): print(`For i=1..N1,j=1..N2`): print(`rectangle with the middle ixj square removed. Try: `): print(` SeqFrameDouble(2,2,2,2,10,3);`): elif nops([args])=1 and op(1,[args])=SeqFrameDoubleSlow then print(`Like SeqFrameD(a1,a2,b1,b2,N1,N2) but slower`): print(`Try: `): print(` SeqFrameDoubleSlow(2,2,2,2,10,3);`): elif nops([args])=1 and op(1,[args])=SeqFrameMD then print(`SeqFrameMD(a1,a2,b1,b2,N): The first N terms of the sequence`): print(`enumerating MONOMER-DIMER tilings of`): print(`the (a1+n+a2)x(b1+n+b2)`): print(`rectangle with the middle nxn square removed`): print(`Try: SeqFrameMD(2,2,2,2,10);`): elif nops([args])=1 and op(1,[args])=SeqFrameSlow then print(`SeqFrameSlow(a1,a2,b1,b2,N): like SeqFrame(a1,a2,b1,b2,N)`): print(`but slow. Do not use!`): print(`Try: SeqFrameSlow(2,2,2,2,10);`): elif nops([args])=1 and op(1,[args])=SeqFrameVerySlow then print(`SeqFrameVerySlow(a1,a2,b1,b2,N): like SeqFrame(a1,a2,b1,b2,N)`): print(`but very slow. Do not use!`): print(`Try: SeqFrameVerySlow(2,2,2,2,10);`): elif nops([args])=1 and op(1,[args])=SeqFrameC then print(`SeqFrameC(a1,a2,b1,b2,N,t): finds`): print(`a C-finite description to the sequence enumerating`): print(`the number of `): print(`DOMINO (dimer) tilings of Frame(a1,a2,b1,b2,n,n) for all n`): print(`using up to N data points, if it can't find anything`): print(`it returns FAIL, and N has to be made larger`): print(`It also returns the generating function, in t, of that`): print(`enumerating sequence (of course, it is a rational function`): print(`The last output is 0 if the sequence is only non-zero`): print(`for even n, and then the output information is for the sequence`): print(`enumerating Frame(a1,a2,b1,b2,2*n,2*n).`): print(`Otherwise the last output is 1`): print(`Try:`): print(`SeqFrameC(2,2,2,2,20,t);`): elif nops([args])=1 and op(1,[args])=SeqFrameCdirect then print(`SeqFrameCdirect(a1,a2,b1,b2,N,t): `): print(`Like SeqFrameC(a1,a2,b1,b2,N,t) but directly (hence slower)`): print(`SeqFrameCdirect(2,2,2,2,20,t);`): elif nops([args])=1 and op(1,[args])=SeqFrameCmd then print(`SeqFrameCmd(a1,a2,b1,b2,N,t): finds`): print(`a C-finite description to the sequence enumerating`): print(`the number of `): print(`MONOMER-DIMER tilings of Frame(a1,a2,b1,b2,n,n) for all n`): print(`using up to N data points, if it can't find anything`): print(`it returns FAIL, and N has to be made larger`): print(`It also returns the generating function, in t, of that`): print(`enumerating sequence (of course, it is a rational function`): print(`Try:`): print(`SeqFrameCmd(2,2,2,2,70,t);`): elif nops([args])=1 and op(1,[args])=SeqFrameCsq then print(`SeqFrameCsq(a1,a2,b1,b2,N,t): finds`): print(`a C-finite description, and the ordinary generating function`): print(`in the variable t, to the square-root of the`): print(`sequence enumerating the number of `): print(`tilings of Frame(a1,a2,b1,b2,n,n) for all n`): print(`or of the square-root of half of them`): print(` (if it happens to be perfect squares or twice perfect squares `): print(` thanks for Mihai Ciucu's theorem about reflective symmetry)`): print(`If it is not it returns FAIL with a message`): print(`It uses up to N data points, if it can't find anything`): print(`it returns FAIL, and N has to be made larger`): print(`if it is twice the square root, the last output is 2`): print(`otherwise 1`): print(`Try:`): print(`SeqFrameCsq(2,2,2,2,10,t);`): elif nops([args])=1 and op(1,[args])=SeqFrameCsqDirect then print(`SeqFrameCsqDirect(a1,a2,b1,b2,N,t): `): print(`Like SeqFrameCsq(a1,a2,b1,b2,N,t): `): print(`Try:`): print(`SeqFrameCsqDirect(2,2,2,2,20,t);`): elif nops([args])=1 and op(1,[args])=SeqFrameCstory then print(`SeqFrameCstory(a1,a2,b1,b2,N,t): The verbose form of`): print(`SeqFrameC(a1,a2,b1,b2,N,t). `): print(`Try:`): print(`SeqFrameCstory(2,2,2,2,20,t);`): elif nops([args])=1 and op(1,[args])=SeqFrameCstoryMD then print(`SeqFrameCstoryMD(a1,a2,b1,b2,N,t): The verbose form of`): print(`SeqFrameCmd(a1,a2,b1,b2,N,t). `): print(`Try:`): print(`SeqFrameCstoryMD(2,2,2,2,70,t);`): elif nops([args])=1 and op(1,[args])=SeqFrameCsqStory then print(`SeqFrameCsqStory(a1,a2,b1,b2,N,t): The verbose form of`): print(`SeqFrameCsq(a1,a2,b1,b2,N,t). `): print(`Try:`): print(`SeqFrameCsqStory(2,2,2,2,20,t);`): elif nops([args])=1 and op(1,[args])=SeqFrameDirect then print(`SeqFrameDirect(a1,a2,b1,b2,N): Like SeqFrame(a1,a2,b1,b2,N)`): print(`but done directly, for checking purposes only`): print(`Try: SeqFrameDirect(2,2,2,2,10);`): elif nops([args])=1 and op(1,[args])=SeqFrameDirectDouble then print(`SeqFrameDirectDouble(a1,a2,b1,b2,N1,N2): `): print(`Like SeqFrameDouble(a1,a2,b1,b2,N1,N2)`): print(`but done directly, for checking purposes only`): print(`Try: SeqFrameDirectDouble(2,2,2,2,3,10);`): elif nops([args])=1 and op(1,[args])=SeqFrameDirectMD then print(`SeqFrameDirectMD(a1,a2,b1,b2,N): Like SeqFrameMD(a1,a2,b1,b2,N)`): print(`but done directly, for checking purposes only`): print(`Try: SeqFrameDirectMD(2,2,2,2,10);`): elif nops([args])=1 and op(1,[args])=SeqFrameMD1human then print(`SeqFrameMD1human(n): an explicit formula, using a human approach`): print(`to the number of monomer-dimer tilings of`): print(`Frame(1,1,1,1,n); Try:`): print(`SeqFrameMD1human(n);`): elif nops([args])=1 and op(1,[args])=SeqFromRec then print(`SeqFromRec(C,N): the first N terms of the C-finite`): print(`sequence defined by C, try:`): print(`SeqFromRec([[-1,-1],[1,1]],10);`): elif nops([args])=1 and op(1,[args])=SeqRect then print(`SeqRect(m,N): inputs a pos. integer m, and`): print(`outputs the first N terms of the number of `): print(`tilings of Rect(m,n) if m is even and`): print(`of Rect(m,2*n) if m is odd.`): print(`Try:`): print(`SeqRect(4,10);`): elif nops([args])=1 and op(1,[args])=SeqRectC then print(`SeqRectC(a,N,t): finds`): print(`a C-finite description, and the ordinary generating function`): print(`in the variable t, to the sequence enumerating`): print(`the number of domino (also called dimer) `): print(`tilings of an a by n rectangle`): print(`using up to N data points, if it can't find anything`): print(`it returns FAIL, and N has to be made larger`): print(`if a is odd then it is the tilings of an a by 2n rectangle`): print(`Try:`): print(`SeqRectC(2,20,t);`): elif nops([args])=1 and op(1,[args])=SeqRectCmd then print(`SeqRectCmd(a,N,t): finds`): print(`a C-finite description, and the ordinary generating function`): print(`in the variable t, to the sequence enumerating`): print(`the number of monomer-dimer `): print(`tilings of an a by n rectangle`): print(`using up to N data points, if it can't find anything`): print(`it returns FAIL, and N has to be made larger`): print(`if a is odd then it is the tilings of an a by 2n rectangle`): print(`Try:`): print(`SeqRectC(2,20,t);`): elif nops([args])=1 and op(1,[args])=SeqRectDirect then print(`SeqRectDirect(m,N): inputs a pos. integer m, and`): print(`outputs the first N terms of the number of `): print(`tilings of Rect(m,n) if m is even and`): print(`of Rect(m,2*n) if m is odd.`): print(`Try:`): print(`SeqRectDirect(4,10);`): elif nops([args])=1 and op(1,[args])=SeqRectDirectMD then print(`SeqRectDirectMD(m,N): inputs a pos. integer m, and`): print(`outputs the first N terms of the number of `): print(`monomer-dimer tilings of Rect(m,n)`): print(`Try:`): print(`SeqRectDirectMD(4,10);`): elif nops([args])=1 and op(1,[args])=SeqRectCstory then print(`SeqRectCstory(a,N,t): The verbose form of`): print(`SeqRectC(a,N,t). `): print(`Try:`): print(`SeqRectCstory(2,20,t);`): elif nops([args])=1 and op(1,[args])=SeqRectCstoryMD then print(`SeqRectCstoryMD(a,N,t): The verbose form of`): print(`SeqRectCmd(a,N,t). `): print(`Try:`): print(`SeqRectCstoryMD(2,20,t);`): elif nops([args])=1 and op(1,[args])=SeqRectMD then print(`SeqRectMD(m,N): inputs a pos. integer m, and`): print(`outputs the first N terms of the number of `): print(`monomer-dimer tilings of Rect(m,n) `): print(`Try:`): print(`SeqRectMD(4,10);`): elif nops([args])=1 and op(1,[args])=SeqsInfo then print(`SeqsInfo(m,N): the 2^m by 2^m matrix (given a list of lists)`): print(`whose [i,j] entry is a list of length N whose n-th entry`): print(`is the number of ways of`): print(`getting from state i to state j in n steps, (n>=2). Try:`): print(`SeqsInfo(2,10);`): elif nops([args])=1 and op(1,[args])=SocPe then print(`SocPe(SetP): given a set partitions SetP outputs the`): print(`set of Social members (thsose that belong to a`): print(`a non-singleton block), try:`): print(`SocPe({{1,2},{3},{4,5},{6}});`): elif nops([args])=1 and op(1,[args])=SN then print(`SN(n): given a pos. integer n, finds the set of integers S`): print(`correponding to it`): print(` For example, try:`): print(`SN(3);`): elif nops([args])=1 and op(1,[args])=T then print(`T(R): Given a set of lattice points, R, finds the set of`): print(`matchings (tilings). Try:`): print(`T({[0,0],[1,0],[0,1],[1,1]});`): elif nops([args])=1 and op(1,[args])=Tmd then print(`Tmd(R): Given a set of lattice points, R, finds the set of`): print(`monomer-dimer tilings. Try:`): print(`Tmd({[0,0],[1,0],[0,1],[1,1]});`): elif nops([args])=1 and op(1,[args])=Tgen then print(`Tgen(R,S): Given a set of lattice points R,`): print(`and another set S, where R is a subset of S,finds the set of`): print(`matchings (tilings) such that every member of R is`): print(`covered, and some (possibly none and possibly all) of`): print(`the points in S minus R. Try`): print(`Tgen({[0,0],[1,0],[0,1],[1,1]},{[0,0],[1,0],[0,1],[1,1],[0,2],[1,2]});`): elif nops([args])=1 and op(1,[args])=TgenMD then print(`TgenMD(R,S): Given a set of lattice points R,`): print(`and another set S, where R is a subset of S,finds the set of`): print(`monomer-dimer tilings such that every member of R is`): print(`covered, and some (possibly none and possibly all) of`): print(`the points in S minus R. Try`): print(`TgenMD({[0,0],[1,0],[0,1],[1,1]},{[0,0],[1,0],[0,1],[1,1],[0,2],[1,2]});`): elif nops([args])=1 and op(1,[args])=TilS then print(`TilS(S): given a set, S`): print(`finds the number of ways of tiling it into`): print(`dimers and monomers`): print(`For example, try:`): print(`Tils({1,2,4,5});`): elif nops([args])=1 and op(1,[args])=TM then print(`TM(m): the transfer (0-1) matrix (as a list of lists)`): print(`for dimer tilings of a width-m rectangle. Try: `): print(`TM(2);`): elif nops([args])=1 and op(1,[args])=TMmd then print(`TMmd(m): the transfer (0-1) matrix (as a list of lists)`): print(`for monomer-dimer tilings of a width-m rectangle`): print(`Try:`): print(`TMmd(2);`): else print(`There is no ezra for`,args): fi: end: #TilS(S): given a set, S #finds the number of ways of tiling it into #dimers and monomers #For example, try: #Tils({1,2,4,5}); TilS:=proc(S) local k,gu,mu,mu1: option remember: if S={} then RETURN({{}}): fi: k:=max(op(S)): mu:=TilS(S minus {k}): gu:= {seq({{k},op(mu1)},mu1 in mu)}: if not member(k-1,S) then RETURN(gu): fi: mu:=TilS(S minus {k-1,k}): gu:=gu union {seq({{k,k-1},op(mu1)},mu1 in mu)}: end: #SocPe(SetP): given a set partitions SetP outputs the #set of Social members (thsose that belong to a #a non-singleton block), try: #SocPe({{1,2},{3},{4,5},{6}}); SocPe:=proc(SetP) local gu,s: gu:={}: for s in SetP do if nops(s)>1 then gu:=gu union s: fi: od: gu: end: #Followers(S,m): given a state S (a subset of {1, ...,m}) #and a pos. integer m, outputs the set of states that #may follow S, Try: #Followers({1,2},2); Followers:=proc(S,m) local mu,gu,mu1,ku,i: mu:=TilS(S): ku:={seq(i, i=1..m)} minus S: gu:={}: for mu1 in mu do gu:=gu union {ku union SocPe(mu1)}: od: gu: end: #TM(m): the transfer (0-1) matrix (as a list of lists) #for tilings of a width-m rectangle, #with the canonical numbering of sets. Try: #TM(2); TM:=proc(m) local gu,i,j,lu,ru: option remember: gu:=[]: for i from 1 to 2^m do lu:=[]: ru:=Followers(SN(i),m): for j from 1 to 2^m do if member(SN(j),ru) then lu:=[op(lu),1]: else lu:=[op(lu),0]: fi: od: gu:=[op(gu),lu]: od: gu: end: #SeqsInfo(m,N): the 2^m by 2^m matrix (given a list of lists) #whose [i,j] entry is a list of length N whose n-th entry #is the number of ways of #getting from state i to state j in n steps, try: #SeqsInfo(2,10); SeqsInfo:=proc(m,N) local gu,A,B,T,i,j,n: option remember: gu:=TM(m): A:=convert(gu,matrix): B:=A: for i from 1 to 2^m do for j from 1 to 2^m do T[i,j]:=[]: od: od: for n from 1 to N do for i from 1 to 2^m do for j from 1 to 2^m do T[i,j]:=[op(T[i,j]),B[i,j]]: od: od: B:=evalm(A&*B): od: [seq([seq(T[i,j],j=1..2^m)],i=1..2^m)]: end: #T(R): Given a set of lattice points, R, finds the set of #matchings (tilings). Try: #T({[0,0],[1,0],[0,1],[1,1]}); T:=proc(R) local gu,m,t,lu,t1,t2,gu1,R1,gu11: option remember: if R={} then RETURN({{}}): fi: if nops(R)=1 then RETURN({}): fi: m:=min(seq(t[1],t in R)): lu:={}: for t in R do if t[1]=m then lu:=lu union {t}: fi: od: m:=min(seq(t[2],t in lu)): for t in lu do if t[2]=m then t1:=t: break: fi: od: gu:={}: t2:=[t1[1]+1,t1[2]]: if member(t2,R) then R1:=R minus {t1,t2}: gu1:=T(R1): gu:=gu union {seq({op(gu11),{t1,t2}},gu11 in gu1)}: fi: t2:=[t1[1],t1[2]+1]: if member(t2,R) then R1:=R minus {t1,t2}: gu1:=T(R1): gu:=gu union {seq({op(gu11),{t1,t2}},gu11 in gu1)}: fi: gu: end: #NT(R): Given a set of lattice points finds the number of #matchings (tilings). Try: #NT({[0,0],[1,0],[0,1],[1,1]}): NT:=proc(R) local gu,m,t,lu,t1,t2,R1: option remember: if R={} then RETURN(1): fi: if nops(R)=1 then RETURN(0): fi: m:=min(seq(t[1],t in R)): lu:={}: for t in R do if t[1]=m then lu:=lu union {t}: fi: od: m:=min(seq(t[2],t in lu)): for t in lu do if t[2]=m then t1:=t: break: fi: od: gu:=0: t2:=[t1[1]+1,t1[2]]: if member(t2,R) then R1:=R minus {t1,t2}: gu:=gu+NT(R1): fi: t2:=[t1[1],t1[2]+1]: if member(t2,R) then R1:=R minus {t1,t2}: gu:=gu+NT(R1): fi: gu: end: #Tgen(R,S): Given a set of lattice points R, #and another set S, where R is a subset of S,finds the set of #matchings (tilings) such that every member of R is #covered, and some (possibly none and possibly) all of #the points in S minus R. Try #Tgen({[0,0],[1,0],[0,1],[1,1]},{[0,0],[1,0],[0,1],[1,1],[0,2],[1,2]}); Tgen:=proc(R,S) local gu,m,t,lu,t1,t2,gu1,R1,S1, gu11: option remember: if R={} then RETURN({{}}): fi: if nops(S)=1 then RETURN({}): fi: m:=min(seq(t[1],t in R)): lu:={}: for t in R do if t[1]=m then lu:=lu union {t}: fi: od: m:=min(seq(t[2],t in lu)): for t in lu do if t[2]=m then t1:=t: break: fi: od: gu:={}: t2:=[t1[1]+1,t1[2]]: if member(t2,S) then R1:=R minus {t1,t2}: S1:=S minus {t1,t2}: gu1:=Tgen(R1,S1): gu:=gu union {seq({op(gu11),{t1,t2}},gu11 in gu1)}: fi: t2:=[t1[1]-1,t1[2]]: if member(t2,S) then R1:=R minus {t1,t2}: S1:=S minus {t1,t2}: gu1:=Tgen(R1,S1): gu:=gu union {seq({op(gu11),{t1,t2}},gu11 in gu1)}: fi: t2:=[t1[1],t1[2]+1]: if member(t2,S) then R1:=R minus {t1,t2}: S1:=S minus {t1,t2}: gu1:=Tgen(R1,S1): gu:=gu union {seq({op(gu11),{t1,t2}},gu11 in gu1)}: fi: t2:=[t1[1],t1[2]-1]: if member(t2,S) then R1:=R minus {t1,t2}: S1:=S minus {t1,t2}: gu1:=Tgen(R1,S1): gu:=gu union {seq({op(gu11),{t1,t2}},gu11 in gu1)}: fi: gu: end: #JaggedRect(m,n,S1,S2): an m by n rectangle, #where the leftmost column only contains points with vertical #height in S1, and the rightmost column only contains points with #vertical height in S2 #Try: JaggedRect(4,5,{1},{2,3}); JaggedRect:=proc(m,n,S1,S2) local i,j,s: {seq(seq([i,j],j=0..m-1),i=1..n-2)} union {seq([0,s-1],s in S1), seq([n-1,s-1],s in S2)}: end: #Cross(v,h,m1,m2,m3,m4): The cross whose center is an h by v rectangle #with an m1 by v rectangle to its right, an h by m2 above, #an m3 by v to the left, and an h by m4 below #Try: #Cross(1,1,2,3,2,3); Cross:=proc(v,h,m1,m2,m3,m4) local R, i,j: R:={seq(seq([i,j],i=0..h-1),j=0..v-1)}: R:=R union {seq(seq([i,j],i=h..h+m1-1),j=0..v-1)}: R:=R union {seq(seq([i,j],i=0..h-1),j=v..v+m2-1)}: R:=R union {seq(seq([-i,j],i=1..m3),j=0..v-1)}: R:=R union {seq(seq([i,-j],i=0..h-1),j=1..m4)}: R: end: #Rect(m,n): an m by n rectangle, try: Rect(3,4); Rect:=proc(m,n) local i,j: {seq(seq([i,j],j=0..m-1),i=0..n-1)}: end: #Frame(a1,a2,b1,b2,m,n): The region of #the picture frame of an (a1+m+a2)x(b1+n+b2) #rectangle with a middle mxn rectancle removed #Try: Frame(2,2,2,2,4,4); Frame:=proc(a1,a2,b1,b2,m,n) local i,j: { seq(seq([i,j],i=0..a1+m+a2-1),j=0..b1-1), seq(seq([i,j],i=0..a1-1),j=b1..b1+n-1), seq(seq([i,j],i=a1+m..a1+m+a2-1),j=b1..b1+n-1), seq(seq([i,j],i=0..a1+m+a2-1),j=b1+n..b1+n+b2-1) }: end: #RectPlus(m,n,kv): inputs pos. integers m and n, and #a subset kv of {1,2,3,4}, and outputs the #rectangle Rect(m,n), followed by the #lattice points adjacent (outside) to the sides that #belong to S, where Right=1, Up=2, Left=3, Down=4, for #example, try: #RectPlus(3,4,{1,4}); RectPlus:=proc(m,n,kv) local i,j,R,S: R:={seq(seq([i,j],j=0..m-1),i=0..n-1)}: S:=R: if member(1,kv) then S:=S union {seq(seq([i,j],j=0..m-1),i=n..n)}: fi: if member(2,kv) then S:=S union {seq(seq([i,j],j=m..m),i=0..n-1)}: fi: if member(3,kv) then S:=S union {seq(seq([i,j],j=0..m-1),i=-1..-1)}: fi: if member(4,kv) then S:=S union {seq(seq([i,j],j=-1..-1),i=0..n-1)}: fi: R,S: end: #CoveredSet(T): given a tiling of lattice points, finds #the set of lattice points covered, try: #CoveredSet({{[0,1],[1,1]},{[2,1],[2,2]}); CoveredSet:=proc(T) local t: {seq(op(t),t in T)}: end: #GenTilingsSW(a1,b1): #Inputs positive integers a1 and b1 #and outputs the set of pairs #[[RightSideFree,UpSideFree],mult] #where we looked at generalized tilings of #Rect(a1,b1) where they all have to be covered, #but one has the option to use lattice points #with i=b1 or j=a1 #Try: #GenTilingsSW(3,3); GenTilingsSW:=proc(a1,b1) local R,S,i,j,mu,gu,mu1,B1,B2,lu,pt,ku,ku1,T,gu1: R:=Rect(a1,b1): S:=R union {seq([b1,j],j=0..a1-1)} union {seq([i,a1],i=0..b1-1)}: mu:=Tgen(R,S): gu:=[]: for mu1 in mu do lu:=CoveredSet(mu1) minus (R union {seq([i,a1],i=0..b1-1)}): B1:={seq(pt[2]+1,pt in lu)}: B1:={seq(j,j=1..a1)} minus B1: lu:=CoveredSet(mu1) minus (R union {seq([b1,j],j=0..a1-1)}): B2:={seq(pt[1]+1,pt in lu)}: B2:={seq(j,j=1..b1)} minus B2: gu:=[op(gu),[mu1,[B1,B2]]]: od: ku:={seq(gu[i][2],i=1..nops(gu))}: for ku1 in ku do T[ku1]:=0: od: for gu1 in gu do T[gu1[2]]:=T[gu1[2]]+1: od: {seq([ku1,T[ku1]],ku1 in ku)}: end: #GenTilingsSE(a1,b2): #Inputs positive integers a1 and b2 #and outputs the set of pairs #[[UpSideFree,LeftSideFree],mult] #where we looked at generalized tilings of #Rect(a1,b1) where they all have to be covered, #but one has the option to use lattice points #with i=-1 or j=a1 #Try: #GenTilingsSE(3,3); GenTilingsSE:=proc(a1,b2) local R,S,i,j,mu,gu,mu1,B1,B2,lu,pt,ku,ku1,T,gu1: R:=Rect(a1,b2): S:=R union {seq([-1,j],j=0..a1-1)} union {seq([i,a1],i=0..b2-1)}: mu:=Tgen(R,S): gu:=[]: for mu1 in mu do lu:=CoveredSet(mu1) minus (R union {seq([-1,j],i=0..a1-1)}): B1:={seq(pt[1]+1,pt in lu)}: B1:={seq(j,j=1..b2)} minus B1: lu:=CoveredSet(mu1) minus (R union {seq([i,a1],i=0..b2-1)} ): B2:={seq(pt[2]+1,pt in lu)}: B2:={seq(j,j=1..a1)} minus B2: gu:=[op(gu),[mu1,[B1,B2]]]: od: ku:={seq(gu[i][2],i=1..nops(gu))}: for ku1 in ku do T[ku1]:=0: od: for gu1 in gu do T[gu1[2]]:=T[gu1[2]]+1: od: {seq([ku1,T[ku1]],ku1 in ku)}: end: #GenTilingsNE(a2,b2): #Inputs positive integers a2 and b2 #and outputs the set of pairs #[[LeftSideFree,DownSideFree],mult] #where we looked at generalized tilings of #Rect(a2,b2) where they all have to be covered, #but one has the option to use lattice points #with i=-1 or j=-1 #Try: #GenTilingsNE(3,3); GenTilingsNE:=proc(a2,b2) local R,S,i,j,mu,gu,mu1,B1,B2,lu,pt,ku,ku1,T,gu1: R:=Rect(a2,b2): S:=R union {seq([-1,j],j=0..a2-1)} union {seq([i,-1],i=0..b2-1)}: mu:=Tgen(R,S): gu:=[]: for mu1 in mu do lu:=CoveredSet(mu1) minus (R union {seq([i,-1],i=0..b2-1)}): B1:={seq(pt[2]+1,pt in lu)}: B1:={seq(j,j=1..a2)} minus B1: lu:=CoveredSet(mu1) minus (R union {seq([-1,j],j=0..a2-1)}): B2:={seq(pt[1]+1,pt in lu)}: B2:={seq(j,j=1..b2)} minus B2: gu:=[op(gu),[mu1,[B1,B2]]]: od: ku:={seq(gu[i][2],i=1..nops(gu))}: for ku1 in ku do T[ku1]:=0: od: for gu1 in gu do T[gu1[2]]:=T[gu1[2]]+1: od: {seq([ku1,T[ku1]],ku1 in ku)}: end: #GenTilingsNW(a2,b1): #Inputs positive integers a2 and b1 #and outputs the set of pairs #[[RightSideFree,DownSideFree],mult] #where we looked at generalized tilings of #Rect(a2,b1) where they all have to be covered, #but one has the option to use lattice points #with i=b1 or j=-1 #Try: #GenTilingsNW(3,3); GenTilingsNW:=proc(a2,b1) local R,S,i,j,mu,gu,mu1,B1,B2,lu,pt,ku,ku1,T,gu1: R:=Rect(a2,b1): S:=R union {seq([i,-1],i=0..b1-1)} union {seq([b1,j],j=0..a2-1)}: mu:=Tgen(R,S): gu:=[]: for mu1 in mu do lu:=CoveredSet(mu1) minus (R union {seq([b1,j],j=0..a2-1)}): B1:={seq(pt[1]+1,pt in lu)}: B1:={seq(j,j=1..b1)} minus B1: lu:=CoveredSet(mu1) minus (R union {seq([i,-1],i=0..b1-1)}): B2:={seq(pt[2]+1,pt in lu)}: B2:={seq(j,j=1..a2)} minus B2: gu:=[op(gu),[mu1,[B1,B2]]]: od: ku:={seq(gu[i][2],i=1..nops(gu))}: for ku1 in ku do T[ku1]:=0: od: for gu1 in gu do T[gu1[2]]:=T[gu1[2]]+1: od: {seq([ku1,T[ku1]],ku1 in ku)}: end: #CartProd(L1,L2,L3,L4): Given four multisets #{[a,m1]}, {[b,m2]}, {[c,m3]}, {[d,m4]} #finds the set {[[a,b,c,d],m1*m2*m3*m4]} #Try: #CartProd({[a,1]}, {[b,1]}, {[c,1]}, {[d,1]}); CartProd:=proc(L1,L2,L3,L4) local gu1,gu2,gu3,gu4,mu: mu:={}: for gu1 in L1 do for gu2 in L2 do for gu3 in L3 do for gu4 in L4 do mu:=mu union {[[gu1[1],gu2[1],gu3[1],gu4[1]],gu1[2]*gu2[2]*gu3[2]*gu4[2]]}: od: od: od: od: mu: end: #NuskhaF(a1,a2,b1,b2,X,m,n): a formula in terms of the functions #X[SpecificNumber,i,j](Symbol), the number of tilings of #a SpecificNumber by Symbol rectangle # that starts at state i and ends at state j #for the number of domino tilings of #the (a1+m+a2)x(b1+n+b2) #rectangle with the middle mxn rectangle removed #Try: NuskhaF(2,2,2,2,X,m,n); NuskhaF:=proc(a1,a2,b1,b2,X,m,n) local gu1,gu2,gu3,gu4,lu,lu1,gu,m1: option remember: gu1:=GenTilingsSW(a1,b1): gu2:=GenTilingsSE(a1,b2): gu3:=GenTilingsNE(a2,b2): gu4:=GenTilingsNW(a2,b1): lu:=CartProd(gu1,gu2,gu3,gu4): gu:=0: for lu1 in lu do m1:=lu1[2]: lu1:=lu1[1]: gu:=gu+ m1*X[a1,NS(lu1[1][1]),NS(lu1[2][2])](n)* X[b2,NS(lu1[2][1]),NS(lu1[3][2])](m)* X[a2,NS(lu1[3][1]),NS(lu1[4][2])](n)* X[b1,NS(lu1[4][1]),NS(lu1[1][2])](m): od: gu: end: #NS(S): given a positive integer n, and a set of integers S #finds its ID numbers (the numerical equivalent of its binary rep. #plus 1. For example, try: #NS({1,2}); NS:=proc(S) local s: option remember: if not type(S,set) then RETURN(FAIL): fi: add(2^(s-1),s in S)+1: end: #SN(n): the set of in integers corresponding to the pos. integer n SN:=proc(n) local a: option remember: if not (type(n,integer) and n>0) then RETURN(FAIL): fi: if n=1 then RETURN({}): fi: a:=trunc(log[2](n-1))+1: {a} union SN(n-2^(a-1)): end: #SeqFrameVerySlow(a1,a2,b1,b2,N): The first N terms of the sequence #enumerating domino tilings of #the (a1+n+a2)x(b1+n+b2) #rectangle with the middle nxn square removed #Try: SeqFrameVerySlow(2,2,2,2,10); SeqFrameVerySlow:=proc(a1,a2,b1,b2,N) local X,n,mu,mu1,Li,n1,gu1,i,j,T,gu: gu:=NuskhaF(a1,a2,b1,b2,X,n,n): mu:={a1,a2,b1,b2}: for mu1 in mu do T[mu1]:=SeqsInfo(mu1,N): od: Li:=[NT(Frame(a1,a2,b1,b2,0,0))]: for n1 from 1 to N do gu1:=gu: for mu1 in mu do for i from 1 to 2^mu1 do for j from 1 to 2^mu1 do gu1:=subs(X[mu1,i,j](n)=T[mu1][i][j][n1],gu1): od: od: od: if not type(gu1,integer) then print(`Something is wrong`): RETURN(FAIL): else Li:=[op(Li),gu1]: fi: od: Li: end: #SeqRectDirect(m,N): inputs a pos. integer m, and #outputs the first N terms of the number of #tilings of Rect(m,n) if m is even and #of Rect(m,2*n) if m is odd. #Try: #SeqRectDirect(4,10); SeqRectDirect:=proc(m,N) local n: if m mod 2=0 then [seq(NT(Rect(m,n)), n=0..N)]: else [seq(NT(Rect(m,2*n)), n=0..N)]: fi: end: #SeqFrameDirect(a1,a2,b1,b2,N) #The first N terms of the number of #tilings of Frame(a1,a2,b1,b2,n,n). #Try: #SeqFrameDirect(2,2,2,2,5); SeqFrameDirect:=proc(a1,a2,b1,b2,N) local gu,n: gu:=[]: for n from 0 to N do gu:=[op(gu),NT(Frame(a1,a2,b1,b2,n,n))]: od: gu: end: #SeqCrossDirect(v,h,N): The #sequence enumerating the number of dimer tilings (perfect matchings) #for cross whose center is an h by v rectangle #with an n v rectangle to its right and left, an h by n above, #and below #for n from 0 to N #Try: #SeqCrossDirect(1,1,10); SeqCrossDirect:=proc(v,h,N) local n: [seq(NT(Cross(v,h,n,n,n,n)),n=0..N)]: end: #SeqFromRec(C,N): the first N terms of the C-finite #sequence defined by C, try: #SeqFromRec([[-1,-1],[1,1]],10); SeqFromRec:=proc(C,N) local gu,C1,C2,i,i1: C1:=C[1]: C2:=C[2]: gu:=C2: for i from 1 to N-nops(C2) do gu:=[op(gu),-add(C1[i1]*gu[nops(gu)+1-i1],i1=1..nops(C1))]: od: gu: end: #GFfromRec(C,t): the generating function of the C-finite #sequence C (starting with n=0) #Try: #GFfromRec([[-1,-1],[1,1]],t); GFfromRec:=proc(C,t) local mu,lu,N,lu1,i,i1: N:=5*nops(C[1])+5*nops(C[2]): mu:=SeqFromRec(C,N): lu:=add(mu[i]*t^(i-1),i=1..nops(mu))*(1+add(C[1][i1]*t^i1,i1=1..nops(C[1]))): lu:=expand(lu): lu:=add(coeff(lu,t,i)*t^i,i=0..N-nops(C[2])): if degree(lu,t)>=2*nops(C[1]) then print(lu): RETURN(FAIL): fi: lu:=lu/(1+add(C[1][i1]*t^i1,i1=1..nops(C[1]))): N:=2*(nops(C[1])+5*nops(C[2])): lu1:=taylor(lu,t=0,N+1): mu:=SeqFromRec(C,N): if [seq(coeff(lu1,t,i),i=0..N-1)]<>mu then RETURN(FAIL): fi: factor(lu): end: #GuessRec1(L,r): inputs a sequence of numbers, L, and a pos. #integer r, and tries to guess a linear recurrence equation #of order r satisfied by it #L(n)+c1*L(n-1)+...+cr*L(n-r)=0 for all n within the range #The output would be given as a list of r numbers #[[c1,c2,...,cr],InitialConditions] #For example, the Fibonacci sequence is #[[-1,-1], [1,1]] GuessRec1:=proc(L,r) local c,i,var,eq,n: if nops(L)<=2*r+4 then RETURN(FAIL): fi: var:={seq(c[i],i=1..r)}: eq:={seq( L[n]+add(c[i]*L[n-i],i=1..r)=0 , n=r+1..nops(L))}: var:=solve(eq,var): if var=NULL then RETURN(FAIL): fi: [[seq(subs(var, c[i]),i=1..r)], L[1..r] ] ; end: #GuessRec(L): inputs a sequence of numbers, L, # and tries to guess a linear recurrence equation #of some order, r, satisfied by it #L(n)+c1*L(n-1)+...+cr*L(n-r)=0 for all n within the range #The output would be given as a list of r numbers #[[c1,c2,...,cr],InitialConditions] #For example, the Fibonacci sequence is #[[-1,-1], [1,1]] GuessRec:=proc(L) local r,ans: for r from 1 to (nops(L)-4)/2 do ans:=GuessRec1(L,r): if ans<>FAIL then RETURN(ans): fi: od: FAIL: end: #SeqFrameC(a1,a2,b1,b2,N,t): finds #a C-finite description, and the ordinary generating function #in the variable t, to the sequence enumerating #the number of #DOMINO (dimer) tilings of Frame(a1,a2,b1,b2,n,n) for all n #using up to N data points, if it can't find anything #it returns FAIL, and N has to be made larger #The last output is 0 if the sequence is only non-zero #for even n, and then the output information is for the sequence #enumerating Frame(a1,a2,b1,b2,2*n,2*n). #Otherwise the last output is 1 #Try: #SeqFrameC(2,2,2,2,20,t); SeqFrameC:=proc(a1,a2,b1,b2,N,t) local gu,n,mu,T,i: option remember: gu:=SeqFrame(a1,a2,b1,b2,5): if gu=[0$nops(gu)] then RETURN(0): fi: if {seq(gu[2*i],i=1..nops(gu)/2)}={0} then gu:=[seq(gu[2*i-1],i=1..nops(gu)/2)]: T:=0: else T:=1: fi: for n from 5 by 10 to N do gu:=SeqFrame(a1,a2,b1,b2,n): if T=0 then gu:=[seq(gu[2*i-1],i=1..nops(gu)/2)]: fi: mu:=GuessRec(gu): if mu<>FAIL then RETURN(mu, GFfromRec(mu,t),T ): fi: od: FAIL: end: #SeqFrameCsq(a1,a2,b1,b2,N,t): finds #a C-finite description, and the ordinary generating function #in the variable t, to the square-root of the #sequence enumerating the number of #tilings of Frame(a1,a2,b1,b2,n,n) for all n #or of the square-root of half of them #(if it happens to be perfect squares or twice perfect squares #thanks for Mihai Ciucu's theorem about reflective symmetry) #If it is not it returns FAIL with a message #It uses up to N data points, if it can't find anything #it returns FAIL, and N has to be made larger #if it is twice the square root, the last output is 2 #otherwise 1 #Try: #SeqFrameCsq(2,2,2,2,10,t); SeqFrameCsq:=proc(a1,a2,b1,b2,N,t) local gu,n,mu,T,i,i1: gu:=SeqFrame(a1,a2,b1,b2,6): if gu=[0$nops(gu)] then print(` zero sequence`): RETURN(FAIL): fi: if {seq(type(sqrt(gu[i1]),integer),i1=1..6)}={true} then T:=1: elif {seq(type(sqrt(gu[i1]/2),integer),i1=1..6)}={true} then T:=2: else print(`The enumerating sequence is neither one of perfect squares`): print(`nor twice perfect squares`): RETURN(FAIL): fi: for n from 6 by 10 to N do gu:=SeqFrame(a1,a2,b1,b2,n): if {seq(type(sqrt(gu[i]/T),integer),i=1..nops(gu))}<>{true} then print(`The enumerating sequence is neither one of perfect squares`): print(`nor twice perfect squares`): RETURN(FAIL): fi: gu:=[seq(sqrt(gu[i]/T),i=1..nops(gu))]: mu:=GuessRec(gu): if mu<>FAIL then RETURN(mu, GFfromRec(mu,t),T ): fi: od: print(`Insufficient, data, make N bigger`): FAIL: end: #SeqFrameCstory(a1,a2,b1,b2,N,t): The verbose form of #SeqFrameC(a1,a2,b1,b2,N,t). #Try: #SeqFrameCstory(2,2,2,2,20,t); SeqFrameCstory:=proc(a1,a2,b1,b2,N,t) local gu,T,A,n,c,d,i1, mu,kavua1,kavua2: gu:=SeqFrameC(a1,a2,b1,b2,N,t): if gu=FAIL then RETURN(FAIL): fi: if gu=0 then print(`It is always zero`): RETURN(0): fi: T:=gu[3]: if T=1 then print(`Theorem: Let A(n) be the number of ways to tile, with dominoes, the`): print(`region in the plane obtained by removing from the `): print(c[1]+n+c[2], ` by `, d[1] +n + d[2] , `rectangle `): print(`the central `, n, ` by ` , n, `square. `): print(`where `, c[1]=a1, c[2]=a2, d[1]=b1, d[2]=b2 ): print(`Then `): print(Sum(A(n)*t^n,n=0..infinity)=factor(gu[2])): print(``): print(`and in Maple input format:`): lprint(factor(gu[2])): print(``): print(`Equivalently, A(n) satisfies the linear recurrence`): print(A(n)=add(-gu[1][1][i1]*A(n-i1),i1=1..nops(gu[1][1]))): print(``): print(`subject to the initial conditions`): print(seq(A(i1-1)=gu[1][2][i1],i1=1..nops(gu[1][2]))): mu:=SeqFromRec(gu[1],101): kavua1:=evalf(mu[101]/mu[100]): kavua2:=mu[101]/kavua1^100: print(`A(n) is asymptotic to`, kavua2*kavua1^n): print(`For the sake of Sloane here are the first 31 terms, starting at n=0`): print(SeqFromRec(gu[1],30)): else print(`Theorem: Let A(n) be the number of ways to tile, with dominoes, the`): print(`region in the plane obtained by removing from the `): print(c[1]+2*n+c[2], ` by `, d[1] +2*n + d[2] , `rectangle `): print(`the central `, 2*n, ` by ` , 2*n, `square. `): print(`where `, c[1]=a1, c[2]=a2, d[1]=b1, d[2]=b2 ): print(`Then `): print(Sum(A(n)*t^n,n=0..infinity)=factor(gu[2])): print(``): print(`and in Maple input format:`): lprint(factor(gu[2])): print(``): print(`Equivalently, A(n) satisfies the linear recurrence`): print(A(n)=add(-gu[1][1][i1]*A(n-i1),i1=1..nops(gu[1][1]))): print(``): print(`subject to the initial conditions`): print(seq(A(i1-1)=gu[1][2][i1],i1=1..nops(gu[1][2]))): mu:=SeqFromRec(gu[1],101): kavua1:=evalf(mu[101]/mu[100]): kavua2:=mu[101]/kavua1^100: print(`A(n) is asymptotic to`, kavua2*kavua1^n): print(`For the sake of Sloane here are the first 31 terms, starting at n=0`): print(SeqFromRec(gu[1],30)): fi: end: #OutsideSide(a,b,S1): the set of lattice points outside #the generic a by b rectangle [0,a-1]x[0,b-1] on side S1 #where #side 1=UP #side 2=LEFT #side 3=DOWN #side 4=RIGHT #Try #OutsideSide(2,3,3); OutsideSide:=proc(a,b,S1) local i: if S1=1 then {seq([i,a],i=0..b-1)}: elif S1=2 then {seq([-1,i],i=0..a-1)}: elif S1=3 then {seq([i,-1],i=0..b-1)}: elif S1=4 then {seq([b,i],i=0..a-1)}: else FAIL: fi: end: #RTM(a,b,S1,S2): #Inputs positive integers a and b #indicating the vertical and horizontal side-lengths #respectively of an a by b specific rectangle #and distinct integers S1 and S2 from {1,2,3,4} #where the code is #side 1=UP #side 2=LEFT #side 3=DOWN #side 4=RIGHT #and outputs the transition matrix #between all the possible states #of side S1 and side S2. #FOR DIMER TILINGS #(with our convention for numbering the states: #1 plus the sum of the powers of 2 of the members of the set) #Try: #RTM(3,2,2,3); RTM:=proc(a,b,S1,S2) local R,S,mu,M,N,mu1,T,S11,S21,i,j,mu1S1, mu1S2,kv1,kv2,ka: option remember: if not (type(a,integer) and type(b,integer) and a>0 and b>0 and type(S1,integer) and type(S2,integer) and S1<>S2 and member(S1,{1,2,3,4}) and member(S2,{1,2,3,4}) ) then print(`bad input!`): RETURN(FAIL): fi: R:=Rect(a,b): S11:=OutsideSide(a,b,S1): S21:=OutsideSide(a,b,S2): S:=R union S11 union S21 : mu:=Tgen(R,S): if S1=1 or S1=3 then M:=2^b: else M:=2^a: fi: if S2=1 or S2=3 then N:=2^b: else N:=2^a: fi: for i from 1 to M do for j from 1 to N do T[i,j]:=0: od: od: for mu1 in mu do mu1S1:=CoveredSet(mu1) intersect S11: mu1S2:=CoveredSet(mu1) intersect S21: if S1=1 or S1=3 then kv1:= {seq(i,i=1..b)} minus {seq(ka[1]+1,ka in mu1S1)}: else kv1:={seq(i,i=1..a)} minus {seq(ka[2]+1,ka in mu1S1)}: fi: if S2=1 or S2=3 then kv2:= {seq(i,i=1..b)} minus {seq(ka[1]+1,ka in mu1S2)}: else kv2:={seq(i,i=1..a)} minus {seq(ka[2]+1,ka in mu1S2)}: fi: T[NS(kv1),NS(kv2)]:=T[NS(kv1),NS(kv2)]+1: od: [seq([seq(T[i,j],j=1..N)],i=1..M)]: end: #NTframe(a1,a2,b1,b2,m1,n1) #The number of domino tilings #of the region Frame(a1,a2,b1,b2,m1,n1) #Try: #NTframe(2,2,2,2,5,3); NTframe:=proc(a1,a2,b1,b2,m1,n1) local A1,A2,A3,A4,B1,B2,B3,B4,M: option remember: A1:=convert(RTM(a1,b1,1,4),Matrix): A2:=convert(RTM(a1,b2,2,1),Matrix): A3:=convert(RTM(a2,b2,3,2),Matrix): A4:=convert(RTM(a2,b1,4,3),Matrix): B1:=convert(TM(a1),Matrix)^n1: B2:=convert(TM(b2),Matrix)^m1: B3:=convert(TM(a2),Matrix)^n1: B4:=convert(TM(b1),Matrix)^m1: M:=Multiply(A1,B1): M:=Multiply(M,A2): M:=Multiply(M,B2): M:=Multiply(M,A3): M:=Multiply(M,B3): M:=Multiply(M,A4): M:=Multiply(M,B4): Trace(M): end: #NTframeMD(a1,a2,b1,b2,m1,n1) #The number of monomer-dimer tilings #of the region Frame(a1,a2,b1,b2,m1,n1) #Try: #NTframeMD(2,2,2,2,5,3); NTframeMD:=proc(a1,a2,b1,b2,m1,n1) local A1,A2,A3,A4,B1,B2,B3,B4,M: option remember: A1:=convert(RTMmd(a1,b1,1,4),Matrix): A2:=convert(RTMmd(a1,b2,2,1),Matrix): A3:=convert(RTMmd(a2,b2,3,2),Matrix): A4:=convert(RTMmd(a2,b1,4,3),Matrix): B1:=convert(TMmd(a1),Matrix)^n1: B2:=convert(TMmd(b2),Matrix)^m1: B3:=convert(TMmd(a2),Matrix)^n1: B4:=convert(TMmd(b1),Matrix)^m1: M:=Multiply(A1,B1): M:=Multiply(M,A2): M:=Multiply(M,B2): M:=Multiply(M,A3): M:=Multiply(M,B3): M:=Multiply(M,A4): M:=Multiply(M,B4): Trace(M): end: #SeqFrameSlow(a1,a2,b1,b2,N): The first N terms of the sequence #enumerating domino tilings of #the (a1+n+a2)x(b1+n+b2) #rectangle with the middle nxn square removed #Try: SeqFrameSlow(2,2,2,2,10); SeqFrameSlow:=proc(a1,a2,b1,b2,N) local i: [seq(NTframe(a1,a2,b1,b2,i,i),i=0..N)]: end: #SeqFrameCsqStory(a1,a2,b1,b2,N,t): The verbose form of #SeqFrameCsq(a1,a2,b1,b2,N,t). #Try: #SeqFrameCsqStory(2,2,2,2,20,t); SeqFrameCsqStory:=proc(a1,a2,b1,b2,N,t) local gu,T,A,n,c,d,i1, mu,kavua1,kavua2,B: gu:=SeqFrameCsq(a1,a2,b1,b2,N,t): if gu=FAIL then RETURN(FAIL): fi: T:=gu[3]: print(`Theorem: Let A(n) be the number of ways to tile, with dominoes, the`): print(`region in the plane obtained by removing from the `): print(c[1]+n+c[2], ` by `, d[1] +n + d[2] , `rectangle `): print(`the central `, n, ` by ` , n, `square. `): print(`where `, c[1]=a1, c[2]=a2, d[1]=b1, d[2]=b2 ): print(`Then `): print(A(n)=T*B(n)^2): print(`where the sequence B(n) is given by the generating function`): print(Sum(B(n)*t^n,n=0..infinity)=gu[2]): print(``): print(`and in Maple input format:`): lprint(gu[2]): print(``): print(`Equivalently, B(n) satisfies the linear recurrence`): print(B(n)=add(-gu[1][1][i1]*B(n-i1),i1=1..nops(gu[1][1]))): print(``): print(`subject to the initial conditions`): print(seq(B(i1-1)=gu[1][2][i1],i1=1..nops(gu[1][2]))): mu:=SeqFromRec(gu[1],101): print(``): print(`Proof: Routine. Both sides are C-finite!`): print(`QED.`): print(``): kavua1:=evalf(mu[101]/mu[100]): kavua2:=mu[101]/kavua1^100: print(`B(n) is asymptotic to`, kavua2*kavua1^n): print(``): print(`Hence A(n), the number of domino tilings is asymptotic to`): print(T*kavua2^2*(kavua1^2)^n): print(`For the sake of Sloane here are the first 31 terms of B(n)`): print(`starting at n=0.`): print(``): mu:=SeqFromRec(gu[1],30): print(mu): mu:=[seq(T*mu[i1]^2,i1=1..nops(mu))]: print(`The first 31 terms of A(n), starting at n=0 are`): print(mu): end: #SeqFrame(a1,a2,b1,b2,N): The first N terms of the sequence #numerating domino tilings of #he (a1+n+a2)x(b1+n+b2) #rectangle with the middle nxn square removed #Try: SeqFrame(2,2,2,2,10); SeqFrame:=proc(a1,a2,b1,b2,N) local A1,A2,A3,A4,B1,B2,B3,B4,M,B1a,B2a, B3a,B4a,n,gu: A1:=convert(RTM(a1,b1,1,4),Matrix): A2:=convert(RTM(a1,b2,2,1),Matrix): A3:=convert(RTM(a2,b2,3,2),Matrix): A4:=convert(RTM(a2,b1,4,3),Matrix): B1:=convert(TM(a1),Matrix): B2:=convert(TM(b2),Matrix): B3:=convert(TM(a2),Matrix): B4:=convert(TM(b1),Matrix): B1a:=IdentityMatrix(2^a1): B2a:=IdentityMatrix(2^b2): B3a:=IdentityMatrix(2^a2): B4a:=IdentityMatrix(2^b1): gu:=[]: for n from 0 to N do M:=Multiply(A1,B1a): M:=Multiply(M,A2): M:=Multiply(M,B2a): M:=Multiply(M,A3): M:=Multiply(M,B3a): M:=Multiply(M,A4): M:=Multiply(M,B4a): gu:=[op(gu),Trace(M)]: B1a:=Multiply(B1a,B1): B2a:=Multiply(B2a,B2): B3a:=Multiply(B3a,B3): B4a:=Multiply(B4a,B4): od: gu: end: #SeqFrameDoubleSlow(a1,a2,b1,b2,N1,N2): #Like SeqFrameD(a1,a2,b1,b2,N1,N2) #but slower #Try: SeqFrameDoubleSlow(2,2,2,2,3,10); SeqFrameDoubleSlow:=proc(a1,a2,b1,b2,N1,N2) local i,j: [seq([seq(NTframe(a1,a2,b1,b2,i,j),j=1..N2)],i=1..N1)]: end: #SeqFrameDirectDouble(a1,a2,b1,b2,N1,N2) SeqFrameDirectDouble:=proc(a1,a2,b1,b2,N1,N2) local gu,i,j,gu1: gu:=[]: for i from 1 to N1 do gu1:=[]: for j from 1 to N2 do gu1:=[op(gu1),NT(Frame(a1,a2,b1,b2,i,j))]: od: gu:=[op(gu),gu1]: od: gu: end: #SeqFrameDouble(a1,a2,b1,b2,N1,N2): The first N1*N2 terms of the #double sequence #enumerating domino tilings of #the (a1+i+a2)x(b1+j+b2) #rectangle with the middle ixj rectangle removed #for i=1..N1, and j=1..N2 #Try: SeqFrameDouble(2,2,2,2,3,20); SeqFrameDouble:=proc(a1,a2,b1,b2,N1,N2) local A1,A2,A3,A4,B1,B2,B3,B4,M,B1a,B2a, B3a,B4a,i,j,gu1,gu: A1:=convert(RTM(a1,b1,1,4),Matrix): A2:=convert(RTM(a1,b2,2,1),Matrix): A3:=convert(RTM(a2,b2,3,2),Matrix): A4:=convert(RTM(a2,b1,4,3),Matrix): B1:=convert(TM(a1),Matrix): B2:=convert(TM(b2),Matrix): B3:=convert(TM(a2),Matrix): B4:=convert(TM(b1),Matrix): B2a:=IdentityMatrix(2^b2): B4a:=IdentityMatrix(2^b1): gu:=[]: for i from 1 to N1 do gu1:=[]: B1a:=IdentityMatrix(2^a1): B3a:=IdentityMatrix(2^a2): B2a:=Multiply(B2a,B2): B4a:=Multiply(B4a,B4): for j from 1 to N2 do B1a:=Multiply(B1a,B1): B3a:=Multiply(B3a,B3): M:=Multiply(A1,B1a): M:=Multiply(M,A2): M:=Multiply(M,B2a): M:=Multiply(M,A3): M:=Multiply(M,B3a): M:=Multiply(M,A4): M:=Multiply(M,B4a): gu1:=[op(gu1),Trace(M)]: od: gu:=[op(gu),gu1]: od: gu: end: #SeqFrameCsqStory1(a1,a2,b1,b2,N,t,co): #Like SeqFrameCsqStory1(a1,a2,b1,b2,N,t): #but with a numbered theorem #Try: #SeqFrameCsqStory1(2,2,2,2,20,t,10,1); SeqFrameCsqStory1:=proc(a1,a2,b1,b2,N,t,co) local gu,T,A,n,c,d,i1, mu,kavua1,kavua2,B: gu:=SeqFrameCsq(a1,a2,b1,b2,N,t): if gu=FAIL then RETURN(FAIL): fi: T:=gu[3]: print(`Theorem Number`, co, `: Let A(n) be the number of ways to tile, with dominoes, the`): print(`region in the plane obtained by removing from the `): print(c[1]+n+c[2], ` by `, d[1] +n + d[2] , `rectangle `): print(`the central `, n, ` by ` , n, `square. `): print(`where `, c[1]=a1, c[2]=a2, d[1]=b1, d[2]=b2 ): print(`Then `): print(A(n)=T*B(n)^2): print(`where the sequence B(n) is given by the generating function`): print(Sum(B(n)*t^n,n=0..infinity)=gu[2]): print(``): print(`and in Maple input format:`): lprint(gu[2]): print(``): print(`Equivalently, B(n) satisfies the linear recurrence`): print(B(n)=add(-gu[1][1][i1]*B(n-i1),i1=1..nops(gu[1][1]))): print(``): print(`subject to the initial conditions`): print(seq(B(i1-1)=gu[1][2][i1],i1=1..nops(gu[1][2]))): mu:=SeqFromRec(gu[1],101): print(``): print(`Proof: Routine. Both sides are C-finite!`): print(`QED.`): print(``): kavua1:=evalf(mu[101]/mu[100]): kavua2:=mu[101]/kavua1^100: print(`B(n) is asymptotic to`, kavua2*kavua1^n): print(``): print(`Hence A(n), the number of domino tilings is asymptotic to`): print(T*kavua2^2*(kavua1^2)^n): print(`For the sake of Sloane here are the first 31 terms of B(n)`): print(`starting at n=0.`): print(``): mu:=SeqFromRec(gu[1],30): print(mu): mu:=[seq(T*mu[i1]^2,i1=1..nops(mu))]: print(`The first 31 terms of A(n), starting at n=0 are`): print(mu): end: #SeferFrameCsq(K,t,N): inputs a pos. integer K and outputs #a book with theorems about tilings of picture frames #with thickness from 1 to K. t is the variable for #the generating function. #It uses N data points. #Try: SeferFrameCsq(3,t,100); SeferFrameCsq:=proc(K,t,N) local co,t0: t0:=time(): print(`The Number of Domino Tilings of Holey Squares with`): print(`thin Boundaries up to Thickness`, K): print(``): print(`By Shalosh B. Ekhad `): print(`[ShaloshBEkhad@gmail.com ]`): print(`-------------------------------------------------------------`): for co from 1 to K do SeqFrameCsqStory1(co,co,co,co,N,t,co): print(`-------------------------------------------------------------`): od: print(`I hope, dear reader, that you enjoined reading these`, K, `theorems `): print(`as much as I did discovering them.`): print(``): print(`This ends this fascinating book!`): print(`It took`, time()-t0, `seconds to generate it.`): end: #RectG(m1,m2,n1,n2): The rectangle [m1,m2]x[n1,n2] #For example, try: #RectG(3,4,5,6); RectG:=proc(m1,m2,n1,n2) local i,j: {seq(seq([i,j],j=m1..m2),i=n1..n2)}: end: #SeqFrameCdirect(a1,a2,b1,b2,N,t): #Like SeqFrameC(a1,a2,b1,b2,N,t) but directly (hence slower) #SeqFrameCdirect(2,2,2,2,20,t); SeqFrameCdirect:=proc(a1,a2,b1,b2,N,t) local gu,n,mu,T,i: gu:=SeqFrameDirect(a1,a2,b1,b2,5): if gu=[0$nops(gu)] then RETURN(0): fi: if {seq(gu[2*i],i=1..nops(gu)/2)}={0} then gu:=[seq(gu[2*i-1],i=1..nops(gu)/2)]: T:=0: else T:=1: fi: for n from 5 by 10 to N do gu:=SeqFrameDirect(a1,a2,b1,b2,n): if T=0 then gu:=[seq(gu[2*i-1],i=1..nops(gu)/2)]: fi: mu:=GuessRec(gu): if mu<>FAIL then RETURN(mu, GFfromRec(mu,t),T ): fi: od: FAIL: end: #SeqFrameCsqDirect(a1,a2,b1,b2,N,t): #Like SeqFrameCsq(a1,a2,b1,b2,N,t) but directly, and hence slower #Try: #SeqFrameCsqDirect(2,2,2,2,10,t); SeqFrameCsqDirect:=proc(a1,a2,b1,b2,N,t) local gu,n,mu,T,i,i1: gu:=SeqFrameDirect(a1,a2,b1,b2,6): if gu=[0$nops(gu)] then print(` zero sequence`): RETURN(FAIL): fi: if {seq(type(sqrt(gu[i1]),integer),i1=1..6)}={true} then T:=1: elif {seq(type(sqrt(gu[i1]/2),integer),i1=1..6)}={true} then T:=2: else print(`The enumerating sequence is neither one of perfect squares`): print(`nor twice perfect squares`): RETURN(FAIL): fi: for n from 6 by 10 to N do gu:=SeqFrameDirect(a1,a2,b1,b2,n): if {seq(type(sqrt(gu[i]/T),integer),i=1..nops(gu))}<>{true} then print(`The enumerating sequence is neither one of perfect squares`): print(`nor twice perfect squares`): RETURN(FAIL): fi: gu:=[seq(sqrt(gu[i]/T),i=1..nops(gu))]: mu:=GuessRec(gu): if mu<>FAIL then RETURN(mu, GFfromRec(mu,t),T ): fi: od: print(`Insufficient, data, make N bigger`): FAIL: end: #SeqCrossCdirect(v,h,N,t): #Like SeqCrossC(v,h,N,t) but directly (hence slower) #SeqCrossCdirect(2,2,20,t); SeqCrossCdirect:=proc(v,h,N,t) local gu,n,mu,T,i: gu:=SeqCrossDirect(v,h,5): if gu=[0$nops(gu)] then RETURN(0): fi: if {seq(gu[2*i],i=1..nops(gu)/2)}={0} then gu:=[seq(gu[2*i-1],i=1..nops(gu)/2)]: T:=0: else T:=1: fi: for n from 5 by 10 to N do gu:=SeqCrossDirect(v,h,n): if T=0 then gu:=[seq(gu[2*i-1],i=1..nops(gu)/2)]: fi: mu:=GuessRec(gu): if mu<>FAIL then RETURN(mu, GFfromRec(mu,t),T ): fi: od: FAIL: end: #SeqCrossCsqDirect(v,h,N,t): #Like SeqFrameCsq(v,h,N,t) but directly, and hence slower #Try: #SeqFrameCsqDirect(2,2,10,t); SeqCrossCsqDirect:=proc(v,h,N,t) local gu,n,mu,T,i,i1: gu:=SeqCrossDirect(v,h,6): if gu=[0$nops(gu)] then print(` zero sequence`): RETURN(FAIL): fi: if {seq(type(sqrt(gu[i1]),integer),i1=1..6)}={true} then T:=1: elif {seq(type(sqrt(gu[i1]/2),integer),i1=1..6)}={true} then T:=2: else print(`The enumerating sequence is neither one of perfect squares`): print(`nor twice perfect squares`): RETURN(FAIL): fi: for n from 6 by 10 to N do gu:=SeqCrossDirect(v,h,n): if {seq(type(sqrt(gu[i]/T),integer),i=1..nops(gu))}<>{true} then print(`The enumerating sequence is neither one of perfect squares`): print(`nor twice perfect squares`): RETURN(FAIL): fi: gu:=[seq(sqrt(gu[i]/T),i=1..nops(gu))]: mu:=GuessRec(gu): if mu<>FAIL then RETURN(mu, GFfromRec(mu,t),T ): fi: od: print(`Insufficient, data, make N bigger`): FAIL: end: #RectT(a,b): #Inputs positive integers a and b #indicating the vertical and horizontal side-lengths #respectively of an a by b specific rectangle #side 1=UP #side 2=LEFT #side 3=DOWN #side 4=RIGHT #and outputs the stick-out tensor, #a set of the form [i1,i2,i3,i4,co] refererring to #the states of the availability in the four sides #(in the above order, where co indicates how many #domnio tilings that definitely cover the a by b rectangle #but may stick out with states i1,i2,i3,i4 as above. #Try: #RectT(2,2); RectT:=proc(a,b) local R,S,mu,mu1,T,S1,S2,S3,S4,i1,i2,i3,i4, mu1S1,mu1S2,mu1S3,mu1S4,kv1,kv2,kv3,kv4,ka,i,gu,lu,lu1: option remember: if not (type(a,integer) and type(b,integer) and a>0 and b>0) then print(`bad input!`): RETURN(FAIL): fi: R:=Rect(a,b): S1:=OutsideSide(a,b,1): S2:=OutsideSide(a,b,2): S3:=OutsideSide(a,b,3): S4:=OutsideSide(a,b,4): S:=R union S1 union S2 union S3 union S4 : mu:=Tgen(R,S): for i1 from 1 to 2^b do for i2 from 1 to 2^a do for i3 from 1 to 2^b do for i4 from 1 to 2^a do T[i1,i2,i3,i4]:=0: od: od: od: od: for mu1 in mu do mu1S1:=CoveredSet(mu1) intersect S1: mu1S2:=CoveredSet(mu1) intersect S2: mu1S3:=CoveredSet(mu1) intersect S3: mu1S4:=CoveredSet(mu1) intersect S4: kv1:= {seq(i,i=1..b)} minus {seq(ka[1]+1,ka in mu1S1)}: kv2:= {seq(i,i=1..a)} minus {seq(ka[2]+1,ka in mu1S2)}: kv3:= {seq(i,i=1..b)} minus {seq(ka[1]+1,ka in mu1S3)}: kv4:= {seq(i,i=1..a)} minus {seq(ka[2]+1,ka in mu1S4)}: T[NS(kv1),NS(kv2),NS(kv3),NS(kv4)]:=T[NS(kv1),NS(kv2),NS(kv3),NS(kv4)]+1: od: lu:={seq( seq( seq( seq( [i1,i2,i3,i4,T[i1,i2,i3,i4]], i1=1..2^b), i2=1..2^a), i3=1..2^b), i4=1..2^a)}: gu:={}: for lu1 in lu do if lu1[5]<>0 then gu:=gu union {lu1}: fi: od: gu: end: #SeqCross(a,b,N): the first N terms of the #sequence: number of domino tilings of a cross #with an a by b rectangular center with #four arms of length n, for n=1..N #Try: #SeqCross(2,2,10); SeqCross:=proc(a,b,N) local B1,B2,B3,B4,B1a,B2a, B3a,B4a,n,mu,mu1,gu: mu:=RectT(a,b): B1:=convert(TM(b),Matrix): B2:=convert(TM(a),Matrix): B3:=convert(TM(b),Matrix): B4:=convert(TM(a),Matrix): B1a:=IdentityMatrix(2^b): B2a:=IdentityMatrix(2^a): B3a:=IdentityMatrix(2^b): B4a:=IdentityMatrix(2^a): gu:=[]: for n from 0 to N do gu:=[op(gu), add(mu1[5]* B1a[mu1[1],2^b]*B2a[mu1[2],2^a]*B3a[mu1[3],2^b]*B4a[mu1[4],2^a], mu1 in mu)]: B1a:=Multiply(B1a,B1): B2a:=Multiply(B2a,B2): B3a:=Multiply(B3a,B3): B4a:=Multiply(B4a,B4): od: gu: end: #SeqCrossC(a,b,N,t): finds #a C-finite description, and the ordinary generating function #in the variable t, to the sequence enumerating #the number of domino #tilings of Cross(a,b,n,n) for all n #using up to N data points, if it can't find anything #it returns FAIL, and N has to be made larger #The last output is 0 if the sequence is only non-zero #for even n, and then the output information is for the sequence #enumerating Cross(a,b,2*n,2*n). #Otherwise the last output is 1 #Try: #SeqCrossC(2,2,20,t); SeqCrossC:=proc(a,b,N,t) local gu,n,mu,T,i: option remember: gu:=SeqCross(a,b,5): if gu=[0$nops(gu)] then RETURN(0): fi: if {seq(gu[2*i],i=1..nops(gu)/2)}={0} then gu:=[seq(gu[2*i-1],i=1..nops(gu)/2)]: T:=0: else T:=1: fi: for n from 5 by 10 to N do gu:=SeqCross(a,b,n): if T=0 then gu:=[seq(gu[2*i-1],i=1..nops(gu)/2)]: fi: mu:=GuessRec(gu): if mu<>FAIL then RETURN(mu, GFfromRec(mu,t),T ): fi: od: FAIL: end: #SeqCrossCsq(a,b,N,t): finds #a C-finite description, and the ordinary generating function #in the variable t, to the square-root of the #sequence enumerating the number of #tilings of Cross(a,b,n,n,n,n) for all n #or of the square-root of half of them #(if it happens to be perfect squares or twice perfect squares #thanks for Mihai Ciucu's theorem about reflective symmetry) #If it is not it returns FAIL with a message #It uses up to N data points, if it can't find anything #it returns FAIL, and N has to be made larger #if it is twice the square root, the last output is 2 #otherwise 1 #Try: #SeqCrossCsq(2,2,20,t); SeqCrossCsq:=proc(a,b,N,t) local gu,n,mu,T,i,i1: gu:=SeqCross(a,b,6): if gu=[0$nops(gu)] then print(` zero sequence`): RETURN(FAIL): fi: if {seq(type(sqrt(gu[i1]),integer),i1=1..6)}={true} then T:=1: elif {seq(type(sqrt(gu[i1]/2),integer),i1=1..6)}={true} then T:=2: else print(`The enumerating sequence is neither one of perfect squares`): print(`nor twice perfect squares`): RETURN(FAIL): fi: for n from 6 by 10 to N do gu:=SeqCross(a,b,n): if {seq(type(sqrt(gu[i]/T),integer),i=1..nops(gu))}<>{true} then print(`The enumerating sequence is neither one of perfect squares`): print(`nor twice perfect squares`): RETURN(FAIL): fi: gu:=[seq(sqrt(gu[i]/T),i=1..nops(gu))]: mu:=GuessRec(gu): if mu<>FAIL then RETURN(mu, GFfromRec(mu,t),T ): fi: od: print(`Insufficient, data, make N bigger`): FAIL: end: #SeqCrossCstory(a,b,N,t): The verbose form of #SeqCrossC(a,b,N,t). #Try: #SeqCrossCstory(2,3,30,t); SeqCrossCstory:=proc(a,b,N,t) local gu,T,A,n,i1,mu: gu:=SeqCrossC(a,b,N,t): if gu=FAIL then RETURN(FAIL): fi: if gu=0 then print(`It is always zero`): RETURN(0): fi: T:=gu[3]: if T=1 then print(`Theorem: Let A(n) be the number of ways to tile, with dominoes, the`): print(`region in the plane consisting of a cross `): print(`whose center is an`, a, `by `, b , `rectangle `): print(`and that each of the four arms has length exacty n. `): print(`Then `): print(Sum(A(n)*t^n,n=0..infinity)=factor(gu[2])): print(``): print(`and in Maple input format:`): lprint(factor(gu[2])): print(``): print(`Equivalently, A(n) satisfies the linear recurrence`): print(A(n)=add(-gu[1][1][i1]*A(n-i1),i1=1..nops(gu[1][1]))): print(``): print(`subject to the initial conditions`): print(seq(A(i1-1)=gu[1][2][i1],i1=1..nops(gu[1][2]))): print(`For the sake of Sloane here are the first 31 terms, starting at n=0`): print(SeqFromRec(gu[1],30)): else print(`Theorem: Let A(n) be the number of ways to tile, with dominoes, the`): print(`region in the plane consisting of a cross `): print(`whose center is an`, a, `by `, b , `rectangle `): print(`and that has arms of length 2n in each direction `): print(`Then: `): print(Sum(A(n)*t^n,n=0..infinity)=factor(gu[2])): print(``): print(`and in Maple input format:`): lprint(factor(gu[2])): print(``): print(`Equivalently, A(n) satisfies the linear recurrence`): print(A(n)=add(-gu[1][1][i1]*A(n-i1),i1=1..nops(gu[1][1]))): print(``): print(`subject to the initial conditions`): print(seq(A(i1-1)=gu[1][2][i1],i1=1..nops(gu[1][2]))): mu:=SeqFromRec(gu[1],101): print(`For the sake of Sloane here are the first 31 terms, starting at n=0`): print(SeqFromRec(gu[1],30)): fi: end: #SeqCrossCstory1(a,b,N,t,co): The verbose form of #SeqCrossC(a,b,N,t) and with a numbered theorem #Try: #SeqCrossCstory1(2,3,30,t,co); SeqCrossCstory1:=proc(a,b,N,t,co) local gu,T,A,n,i1, mu,kavua1,kavua2: gu:=SeqCrossC(a,b,N,t): if gu=FAIL then RETURN(FAIL): fi: if gu=0 then print(`It is always zero`): RETURN(0): fi: T:=gu[3]: if T=1 then print(`Theorem number`, co,`: Let A(n) be the number of ways to tile, with dominoes, the`): print(`region in the plane consisting of a cross `): print(`whose center is an`, a, `by `, b , `rectangle `): print(`and that each of the four arms has length exacty n. `): print(`Then `): print(Sum(A(n)*t^n,n=0..infinity)=factor(gu[2])): print(``): print(`and in Maple input format:`): lprint(factor(gu[2])): print(``): print(`Equivalently, A(n) satisfies the linear recurrence`): print(A(n)=add(-gu[1][1][i1]*A(n-i1),i1=1..nops(gu[1][1]))): print(``): print(`subject to the initial conditions`): print(seq(A(i1-1)=gu[1][2][i1],i1=1..nops(gu[1][2]))): print(`For the sake of Sloane here are the first 31 terms, starting at n=0`): print(SeqFromRec(gu[1],30)): else print(`Theorem number`, co, `: Let A(n) be the number of ways to tile, with dominoes, the`): print(`region in the plane consisting of a cross `): print(`whose center is an`, a, `by `, b , `rectangle `): print(`and that has arms of length 2n in each direction `): print(`Then: `): print(Sum(A(n)*t^n,n=0..infinity)=factor(gu[2])): print(``): print(`and in Maple input format:`): lprint(factor(gu[2])): print(``): print(`Equivalently, A(n) satisfies the linear recurrence`): print(A(n)=add(-gu[1][1][i1]*A(n-i1),i1=1..nops(gu[1][1]))): print(``): print(`subject to the initial conditions`): print(seq(A(i1-1)=gu[1][2][i1],i1=1..nops(gu[1][2]))): mu:=SeqFromRec(gu[1],101): print(`For the sake of Sloane here are the first 31 terms, starting at n=0`): print(SeqFromRec(gu[1],30)): fi: end: #SeqCrossCsqStory(a,b,N,t): The verbose form of #SeqCrossCsq(a,b,N,t). #Try: #SeqCrossCsqStory(2,2,20,t); SeqCrossCsqStory:=proc(a,b,N,t) local gu,T,A,n,i1, mu,kavua1,kavua2,B: gu:=SeqCrossCsq(a,b,N,t): if gu=FAIL then RETURN(FAIL): fi: T:=gu[3]: print(`Theorem: Let A(n) be the number of ways to tile, with dominoes, the`): print(`region in the plane consisting of a cross `): print(`whose center is an`, a, `by `, b, `rectangle `): print(`and such that all the four arms of the cross each have length`): print(` exactly n`): print(`Then `): print(A(n)=T*B(n)^2): print(`where the sequence B(n) is given by the generating function`): print(Sum(B(n)*t^n,n=0..infinity)=factor(gu[2])): print(``): print(`and in Maple input format:`): lprint(factor(gu[2])): print(``): print(`Equivalently, B(n) satisfies the linear recurrence`): print(B(n)=add(-gu[1][1][i1]*B(n-i1),i1=1..nops(gu[1][1]))): print(``): print(`subject to the initial conditions`): print(seq(B(i1-1)=gu[1][2][i1],i1=1..nops(gu[1][2]))): mu:=SeqFromRec(gu[1],101): print(``): print(`Proof: Routine. Both sides are C-finite!`): print(`QED.`): print(``): kavua1:=evalf(mu[101]/mu[100]): kavua2:=mu[101]/kavua1^100: print(`B(n) is asymptotic to`, kavua2*kavua1^n): print(``): print(`Hence A(n), the number of domino tilings is asymptotic to`): print(T*kavua2^2*(kavua1^2)^n): print(`For the sake of Sloane here are the first 31 terms of B(n)`): print(`starting at n=0.`): print(``): mu:=SeqFromRec(gu[1],30): print(mu): mu:=[seq(T*mu[i1]^2,i1=1..nops(mu))]: print(`The first 31 terms of A(n), starting at n=0 are`): print(mu): end: #SeqCrossCsqStory1(a,b,N,t,co): The verbose form of #SeqCrossCsq(a,b,N,t). and with theorem numbered #Try: #SeqCrossCsqStory1(2,2,20,t,3); SeqCrossCsqStory1:=proc(a,b,N,t,co) local gu,T,A,n,i1, mu,kavua1,kavua2,B: gu:=SeqCrossCsq(a,b,N,t): if gu=FAIL then RETURN(FAIL): fi: T:=gu[3]: print(`Theorem Number`, co,`: Let A(n) be the number of ways to tile, with dominoes, the`): print(`region in the plane consisting of a cross `): print(`whose center is an`, a, `by `, b, `rectangle `): print(`and such that all the four arms of the cross each have length`): print(` exactly n`): print(`Then `): print(A(n)=T*B(n)^2): print(`where the sequence B(n) is given by the generating function`): print(Sum(B(n)*t^n,n=0..infinity)=factor(gu[2])): print(``): print(`and in Maple input format:`): lprint(factor(gu[2])): print(``): print(`Equivalently, B(n) satisfies the linear recurrence`): print(B(n)=add(-gu[1][1][i1]*B(n-i1),i1=1..nops(gu[1][1]))): print(``): print(`subject to the initial conditions`): print(seq(B(i1-1)=gu[1][2][i1],i1=1..nops(gu[1][2]))): mu:=SeqFromRec(gu[1],101): print(``): print(`Proof: Routine. Both sides are C-finite!`): print(`QED.`): print(``): kavua1:=evalf(mu[101]/mu[100]): kavua2:=mu[101]/kavua1^100: print(`B(n) is asymptotic to`, kavua2*kavua1^n): print(``): print(`Hence A(n), the number of domino tilings is asymptotic to`): print(T*kavua2^2*(kavua1^2)^n): print(`For the sake of Sloane here are the first 31 terms of B(n)`): print(`starting at n=0.`): print(``): mu:=SeqFromRec(gu[1],30): print(mu): mu:=[seq(T*mu[i1]^2,i1=1..nops(mu))]: print(`The first 31 terms of A(n), starting at n=0 are`): print(mu): end: #SeqFrameCsqStory1(a1,a2,b1,b2,N,t,co): #Like SeqFrameCsqStory1(a1,a2,b1,b2,N,t): #but with a numbered theorem #Try: #SeqFrameCsqStory1(2,2,2,2,20,t,10,1); SeqFrameCsqStory1:=proc(a1,a2,b1,b2,N,t,co) local gu,T,A,n,c,d,i1, mu,kavua1,kavua2,B: gu:=SeqFrameCsq(a1,a2,b1,b2,N,t): if gu=FAIL then RETURN(FAIL): fi: T:=gu[3]: print(`Theorem Number`, co, `: Let A(n) be the number of ways to tile, with dominoes, the`): print(`region in the plane obtained by removing from the `): print(c[1]+n+c[2], ` by `, d[1] +n + d[2] , `rectangle `): print(`the central `, n, ` by ` , n, `square. `): print(`where `, c[1]=a1, c[2]=a2, d[1]=b1, d[2]=b2 ): print(`Then `): print(A(n)=T*B(n)^2): print(`where the sequence B(n) is given by the generating function`): print(Sum(B(n)*t^n,n=0..infinity)=gu[2]): print(``): print(`and in Maple input format:`): lprint(gu[2]): print(``): print(`Equivalently, B(n) satisfies the linear recurrence`): print(B(n)=add(-gu[1][1][i1]*B(n-i1),i1=1..nops(gu[1][1]))): print(``): print(`subject to the initial conditions`): print(seq(B(i1-1)=gu[1][2][i1],i1=1..nops(gu[1][2]))): mu:=SeqFromRec(gu[1],101): print(``): print(`Proof: Routine. Both sides are C-finite!`): print(`QED.`): print(``): kavua1:=evalf(mu[101]/mu[100]): kavua2:=mu[101]/kavua1^100: print(`B(n) is asymptotic to`, kavua2*kavua1^n): print(``): print(`Hence A(n), the number of domino tilings is asymptotic to`): print(T*kavua2^2*(kavua1^2)^n): print(`For the sake of Sloane here are the first 31 terms of B(n)`): print(`starting at n=0.`): print(``): mu:=SeqFromRec(gu[1],30): print(mu): mu:=[seq(T*mu[i1]^2,i1=1..nops(mu))]: print(`The first 31 terms of A(n), starting at n=0 are`): print(mu): end: #SeqFrameCstory1(a1,a2,b1,b2,N,t,co): The verbose form of #SeqFrameC(a1,a2,b1,b2,N,t) with a numbered theorem #Try: #SeqFrameCstory1(2,2,2,2,20,t,4); SeqFrameCstory1:=proc(a1,a2,b1,b2,N,t,co) local gu,T,A,n,c,d,i1, mu,kavua1,kavua2: gu:=SeqFrameC(a1,a2,b1,b2,N,t): if gu=FAIL then RETURN(FAIL): fi: if gu=0 then print(`It is always zero`): RETURN(0): fi: T:=gu[3]: if T=1 then print(`Theorem Number`, co, `: Let A(n) be the number of ways to tile, with dominoes, the`): print(`region in the plane obtained by removing from the `): print(c[1]+n+c[2], ` by `, d[1] +n + d[2] , `rectangle `): print(`the central `, n, ` by ` , n, `square. `): print(`where `, c[1]=a1, c[2]=a2, d[1]=b1, d[2]=b2 ): print(`Then `): print(Sum(A(n)*t^n,n=0..infinity)=factor(gu[2])): print(``): print(`and in Maple input format:`): lprint(factor(gu[2])): print(``): print(`Equivalently, A(n) satisfies the linear recurrence`): print(A(n)=add(-gu[1][1][i1]*A(n-i1),i1=1..nops(gu[1][1]))): print(``): print(`subject to the initial conditions`): print(seq(A(i1-1)=gu[1][2][i1],i1=1..nops(gu[1][2]))): mu:=SeqFromRec(gu[1],101): kavua1:=evalf(mu[101]/mu[100]): kavua2:=mu[101]/kavua1^100: print(`A(n) is asymptotic to`, kavua2*kavua1^n): print(`For the sake of Sloane here are the first 31 terms, starting at n=0`): print(SeqFromRec(gu[1],30)): else print(`Theorem number`, co, `: Let A(n) be the number of ways to tile, with dominoes, the`): print(`region in the plane obtained by removing from the `): print(c[1]+2*n+c[2], ` by `, d[1] +2*n + d[2] , `rectangle `): print(`the central `, 2*n, ` by ` , 2*n, `square. `): print(`where `, c[1]=a1, c[2]=a2, d[1]=b1, d[2]=b2 ): print(`Then `): print(Sum(A(n)*t^n,n=0..infinity)=factor(gu[2])): print(``): print(`and in Maple input format:`): lprint(factor(gu[2])): print(``): print(`Equivalently, A(n) satisfies the linear recurrence`): print(A(n)=add(-gu[1][1][i1]*A(n-i1),i1=1..nops(gu[1][1]))): print(``): print(`subject to the initial conditions`): print(seq(A(i1-1)=gu[1][2][i1],i1=1..nops(gu[1][2]))): mu:=SeqFromRec(gu[1],101): kavua1:=evalf(mu[101]/mu[100]): kavua2:=mu[101]/kavua1^100: print(`A(n) is asymptotic to`, kavua2*kavua1^n): print(`For the sake of Sloane here are the first 31 terms, starting at n=0`): print(SeqFromRec(gu[1],30)): fi: end: #SeferFrameC(K,t,N): inputs a pos. integer K and outputs #a book with theorems about tilings of picture frames #with with parameters (a1,a2,b1,b2) from 1 to K; t is the variable for #the generating function. #It uses N data points. #Try: SeferFrameC(3,t,100); SeferFrameC:=proc(K,t,N) local co,t0,a1,a2,b1,b2,gu: co:=0: t0:=time(): print(`The Number of Domino Tilings of Holey Rectangles with`): print(`thin Boundaries up to width`, K): print(``): print(`By Shalosh B. Ekhad `): print(`[ShaloshBEkhad@gmail.com ]`): print(`-------------------------------------------------------------------`): for a1 from 1 to K do for a2 from 1 to K do for b1 from 1 to K do for b2 from 1 to K do gu:=SeqFrameC(a1,a2,b1,b2,N,t): if gu<>FAIL and gu<>0 then co:=co+1: SeqFrameCstory1(a1,a2,b1,b2,N,t,co): print(`-------------------------------------------------------------------`): print(``): fi: od: od: od: od: print(`I hope, dear reader, that you enjoined reading these`, co, `theorems `): print(`as much as I did discovering them.`): print(``): print(`This ends this fascinating book!`): print(`It took`, time()-t0, `seconds to generate it.`): end: #SeferCrossC(K,t,N): inputs a pos. integer K and outputs #a book with theorems about dimer-tilings of crosses #ith parameters (a,b) from 1 to K; t is the variable for #the generating function. #It uses N data points. #Try: SeferCrossC(3,t,100); SeferCrossC:=proc(K,t,N) local co,t0,a,b,gu: co:=0: t0:=time(): print(`The Number of Domino Tilings of Crosses with`): print(`equal arm-lengths whose central rectangle has side-lengths`): print(`up to`, K): print(``): print(`By Shalosh B. Ekhad `): print(`[ShaloshBEkhad@gmail.com ]`): print(`-------------------------------------------------------------------`): for a from 1 to K do for b from a+1 to K do gu:=SeqCrossC(a,b,N,t): if gu<>FAIL and gu<>0 then co:=co+1: SeqCrossCstory1(a,b,N,t,co): print(`-------------------------------------------------------------------`): print(``): fi: od: od: print(`I hope, dear reader, that you enjoined reading these`, co, `theorems `): print(`as much as I did discovering them.`): print(``): print(`This ends this fascinating book!`): print(`It took`, time()-t0, `seconds to generate it.`): end: #SeferCrossCsq(K,t,N): inputs a pos. integer K and outputs #a book with theorems about tilings of picture crosses #with even parameters (a,a) from 1 to K; t is the variable for #the generating function. #It uses N data points. #Try: SeferCrossCsq(4,t,100); SeferCrossCsq:=proc(K,t,N) local co,t0,a,gu: co:=0: t0:=time(): print(`The Number of Domino Tilings of Crosses with`): print(`equal arm-lengths whose central square has even side-lengths`): print(`up to`, K): print(``): print(`By Shalosh B. Ekhad `): print(`[ShaloshBEkhad@gmail.com ]`): print(`-------------------------------------------------------------------`): for a from 2 by 2 to K do gu:=SeqCrossCsq(a,a,N,t): if gu<>FAIL and gu<>0 then co:=co+1: SeqCrossCsqStory1(a,a,N,t,co): print(`-------------------------------------------------------------------`): print(``): fi: od: print(`I hope, dear reader, that you enjoined reading these`, co, `theorems `): print(`as much as I did discovering them.`): print(``): print(`This ends this fascinating book!`): print(`It took`, time()-t0, `seconds to generate it.`): end: #NTrect(a,m) #The number of domino tilings #of the region Rect(a,m) #Try: #NTrect(2,20); NTrect:=proc(a,m) local B1: B1:=convert(TM(a),Matrix)^m: B1[2^a,2^a]: end: #SeqRect(a,N): the sequence of the number of domino tilings #of an a by n rectangle for n=0..N #Try: #SeqRect(2,20); SeqRect:=proc(a,N) local B1,B1a,n,gu: if a mod 2=0 then B1:=convert(TM(a),Matrix): B1a:=IdentityMatrix(2^a): gu:=[]: for n from 0 to N do gu:=[op(gu),B1a[2^a,2^a]]: B1a:=Multiply(B1a,B1): od: RETURN(gu): else B1:=convert(TM(a),Matrix): B1:=Multiply(B1,B1): B1a:=IdentityMatrix(2^a): gu:=[]: for n from 0 to N do gu:=[op(gu),B1a[2^a,2^a]]: B1a:=Multiply(B1a,B1): od: RETURN(gu): fi: end: #SeqRectC(a,N,t): finds #a C-finite description, and the ordinary generating function #in the variable t, to the sequence enumerating #the number of domino (dimer) #tilings of an a by n rectangle #using up to N data points, if it can't find anything #it returns FAIL, and N has to be made larger #if a is odd then it is the tilings of an a by 2n rectangle #Try: #SeqRectC(2,20,t); SeqRectC:=proc(a,N,t) local gu,mu,n: option remember: for n from 10 by 10 to N do gu:=SeqRect(a,n): mu:=GuessRec(gu): if mu<>FAIL then RETURN(mu, factor(GFfromRec(mu,t))): fi: od: FAIL: end: #GFrect(a,t): the generating function for enumerating #domino tilings of an a by n rectangle directly from #inverting (1-A*t) GFrect:=proc(a,t) local A,B,B1,i,j: A:=convert(TM(a),matrix): if a mod 2=1 then A:=evalm(A^2): fi: B:=IdentityMatrix(2^a): B1:=Matrix(2^a,2^a): for i from 1 to 2^a do for j from 1 to 2^a do B1[i,j]:=B[i,j]-t*A[i,j]: od: od: factor(evalm(B1^(-1))[2^a,2^a]): end: #SeqRectCstory(a,N,t): The verbose form of #SeqRectC(a,N,t). #Try: #SeqRectCstory(2,20,t); SeqRectCstory:=proc(a,N,t) local gu,A,i1, mu,kavua1,kavua2,n: gu:=SeqRectC(a,N,t): if gu=FAIL then RETURN(FAIL): fi: if a mod 2=0 then print(`Theorem: Let A(n) be the number of ways to tile, with dominoes, the`): print(a, `by n rectangle. `): print(`Then `): print(Sum(A(n)*t^n,n=0..infinity)=factor(gu[2])): print(``): print(`and in Maple input format:`): lprint(factor(gu[2])): print(``): print(`Equivalently, A(n) satisfies the linear recurrence`): print(A(n)=add(-gu[1][1][i1]*A(n-i1),i1=1..nops(gu[1][1]))): print(``): print(`subject to the initial conditions`): print(seq(A(i1-1)=gu[1][2][i1],i1=1..nops(gu[1][2]))): mu:=SeqFromRec(gu[1],101): kavua1:=evalf(mu[101]/mu[100]): kavua2:=mu[101]/kavua1^100: print(`A(n) is asymptotic to`, kavua2*kavua1^n): print(`For the sake of Sloane here are the first 31 terms, starting at n=0`): print(SeqFromRec(gu[1],30)): else print(`Theorem: Let A(n) be the number of ways to tile, with dominoes, the`): print(a, `by 2n rectangle. `): print(`Then `): print(Sum(A(n)*t^n,n=0..infinity)=factor(gu[2])): print(``): print(`and in Maple input format:`): lprint(factor(gu[2])): print(``): print(`Equivalently, A(n) satisfies the linear recurrence`): print(A(n)=add(-gu[1][1][i1]*A(n-i1),i1=1..nops(gu[1][1]))): print(``): print(`subject to the initial conditions`): print(seq(A(i1-1)=gu[1][2][i1],i1=1..nops(gu[1][2]))): mu:=SeqFromRec(gu[1],101): kavua1:=evalf(mu[101]/mu[100]): kavua2:=mu[101]/kavua1^100: print(`A(n) is asymptotic to`, kavua2*kavua1^n): print(`For the sake of Sloane here are the first 31 terms, starting at n=0`): print(SeqFromRec(gu[1],30)): fi: end: #SeqRectCstory1(a,N,t,co): The verbose form of #SeqRectC(a,N,t). but with a numbered theorem #Try: #SeqRectCstory1(2,20,t,3); SeqRectCstory1:=proc(a,N,t,co) local gu,A,i1, mu,kavua1,kavua2,n: gu:=SeqRectC(a,N,t): if gu=FAIL then RETURN(FAIL): fi: if a mod 2=0 then print(`Theorem Number`, co, `: Let A(n) be the number of ways to tile, with dominoes, the`): print(a, `by n rectangle. `): print(`Then `): print(Sum(A(n)*t^n,n=0..infinity)=factor(gu[2])): print(``): print(`and in Maple input format:`): lprint(factor(gu[2])): print(``): print(`Equivalently, A(n) satisfies the linear recurrence`): print(A(n)=add(-gu[1][1][i1]*A(n-i1),i1=1..nops(gu[1][1]))): print(``): print(`subject to the initial conditions`): print(seq(A(i1-1)=gu[1][2][i1],i1=1..nops(gu[1][2]))): mu:=SeqFromRec(gu[1],101): kavua1:=evalf(mu[101]/mu[100]): kavua2:=mu[101]/kavua1^100: print(`A(n) is asymptotic to`, kavua2*kavua1^n): print(`For the sake of Sloane here are the first 31 terms, starting at n=0`): print(SeqFromRec(gu[1],30)): else print(`Theorem number`, co, `: Let A(n) be the number of ways to tile, with dominoes, the`): print(a, `by 2n rectangle. `): print(`Then `): print(Sum(A(n)*t^n,n=0..infinity)=factor(gu[2])): print(``): print(`and in Maple input format:`): lprint(factor(gu[2])): print(``): print(`Equivalently, A(n) satisfies the linear recurrence`): print(A(n)=add(-gu[1][1][i1]*A(n-i1),i1=1..nops(gu[1][1]))): print(``): print(`subject to the initial conditions`): print(seq(A(i1-1)=gu[1][2][i1],i1=1..nops(gu[1][2]))): mu:=SeqFromRec(gu[1],101): kavua1:=evalf(mu[101]/mu[100]): kavua2:=mu[101]/kavua1^100: print(`A(n) is asymptotic to`, kavua2*kavua1^n): print(`For the sake of Sloane here are the first 31 terms, starting at n=0`): print(SeqFromRec(gu[1],30)): fi: end: #SeferRectC(K,t,N): inputs a pos. integer K and outputs #a book with theorems about tilings of rectangles #with dimers #of width a for a from 1 to K; t is the variable for #the generating function. #It uses N data points. #Try: SeferRectC(4,t,100); SeferRectC:=proc(K,t,N) local co,t0,a,gu: co:=0: t0:=time(): print(`The Number of Domino Tilings of Rectangles of`): print(`width up to `, K): print(``): print(`By Shalosh B. Ekhad `): print(`[ShaloshBEkhad@gmail.com ]`): print(`-------------------------------------------------------------------`): for a from 1 to K do gu:=SeqRectC(a,N,t): if gu<>FAIL and gu<>0 then co:=co+1: SeqRectCstory1(a,N,t,co): print(`-------------------------------------------------------------------`): print(``): fi: od: print(`I hope, dear reader, that you enjoined reading these`, co, `theorems `): print(`as much as I did discovering them.`): print(``): print(`This ends this fascinating book!`): print(`It took`, time()-t0, `seconds to generate it.`): end: ######START Monomer-Dimer section #NTmd(R): Given a set of lattice points finds the number of #not necessarily perfect matchings (tilings with dimers and #monomers). Try: #NTmd({[0,0],[1,0],[0,1],[1,1]}): NTmd:=proc(R) local gu,m,t,lu,t1,t2,R1: option remember: if R={} then RETURN(1): fi: if nops(R)=1 then RETURN(1): fi: m:=min(seq(t[1],t in R)): lu:={}: for t in R do if t[1]=m then lu:=lu union {t}: fi: od: m:=min(seq(t[2],t in lu)): for t in lu do if t[2]=m then t1:=t: break: fi: od: R1:=R minus {t1}: gu:=NTmd(R1): t2:=[t1[1]+1,t1[2]]: if member(t2,R) then R1:=R minus {t1,t2}: gu:=gu+NTmd(R1): fi: t2:=[t1[1],t1[2]+1]: if member(t2,R) then R1:=R minus {t1,t2}: gu:=gu+NTmd(R1): fi: gu: end: #TgenMD(R,S): Given a set of lattice points R, #and another set S, where R is a subset of S,finds the set of #monomer-dimer tilings such that every member of R is #covered, and some (possibly none and possibly all) of #the points in S minus R. Try #TgenMD({[0,0],[1,0],[0,1],[1,1]},{[0,0],[1,0],[0,1],[1,1],[0,2],[1,2]}); #Tgen(R,S): Given a set of lattice points R, #and another set S, where R is a subset of S,finds the set of #matchings (tilings) such that every member of R is #covered, and some (possibly none and possibly) all of #the points in S minus R. Try #Tgen({[0,0],[1,0],[0,1],[1,1]},{[0,0],[1,0],[0,1],[1,1],[0,2],[1,2]}); TgenMD:=proc(R,S) local gu,m,t,lu,t1,t2,gu1,R1,S1, gu11: option remember: if R={} then RETURN({{}}): fi: if nops(S)=1 then RETURN({S}): fi: m:=min(seq(t[1],t in R)): lu:={}: for t in R do if t[1]=m then lu:=lu union {t}: fi: od: m:=min(seq(t[2],t in lu)): for t in lu do if t[2]=m then t1:=t: break: fi: od: gu:={}: R1:=R minus {t1}: S1:=S minus {t1}: gu1:=TgenMD(R1,S1): gu:=gu union {seq({op(gu11),{t1,t2}},gu11 in gu1)}: t2:=[t1[1]+1,t1[2]]: if member(t2,S) then R1:=R minus {t1,t2}: S1:=S minus {t1,t2}: gu1:=TgenMD(R1,S1): gu:=gu union {seq({op(gu11),{t1,t2}},gu11 in gu1)}: fi: t2:=[t1[1]-1,t1[2]]: if member(t2,S) then R1:=R minus {t1,t2}: S1:=S minus {t1,t2}: gu1:=TgenMD(R1,S1): gu:=gu union {seq({op(gu11),{t1,t2}},gu11 in gu1)}: fi: t2:=[t1[1],t1[2]+1]: if member(t2,S) then R1:=R minus {t1,t2}: S1:=S minus {t1,t2}: gu1:=TgenMD(R1,S1): gu:=gu union {seq({op(gu11),{t1,t2}},gu11 in gu1)}: fi: t2:=[t1[1],t1[2]-1]: if member(t2,S) then R1:=R minus {t1,t2}: S1:=S minus {t1,t2}: gu1:=TgenMD(R1,S1): gu:=gu union {seq({op(gu11),{t1,t2}},gu11 in gu1)}: fi: gu: end: #Tmd(R): Given a set of lattice points, R, finds the set of #monomer-dimer tilings. Try: #Tmd({[0,0],[1,0],[0,1],[1,1]}); Tmd:=proc(R) local gu,m,t,lu,t1,t2,gu1,R1,gu11: option remember: if R={} then RETURN({{}}): fi: if nops(R)=1 then RETURN({R}): fi: m:=min(seq(t[1],t in R)): lu:={}: for t in R do if t[1]=m then lu:=lu union {t}: fi: od: m:=min(seq(t[2],t in lu)): for t in lu do if t[2]=m then t1:=t: break: fi: od: R1:=R minus {t1}: gu1:=Tmd(R1): gu:={seq({op(gu11),{t1}},gu11 in gu1)}: t2:=[t1[1]+1,t1[2]]: if member(t2,R) then R1:=R minus {t1,t2}: gu1:=Tmd(R1): gu:=gu union {seq({op(gu11),{t1,t2}},gu11 in gu1)}: fi: t2:=[t1[1],t1[2]+1]: if member(t2,R) then R1:=R minus {t1,t2}: gu1:=Tmd(R1): gu:=gu union {seq({op(gu11),{t1,t2}},gu11 in gu1)}: fi: gu: end: #TMmd(m): the transfer (0-1) matrix (as a list of lists) #for monomer-dimer tilings of a width-m rectangle, #with the canonical numbering of sets. Try: #TMmd(2); TMmd:=proc(m) local gu,i,j,lu,ru: option remember: gu:=[]: for i from 1 to 2^m do lu:=[]: ru:=Followers(SN(i),m): for j from 1 to 2^m do if member(SN(j),ru) then lu:=[op(lu),1]: else lu:=[op(lu),0]: fi: od: gu:=[op(gu),lu]: od: gu: end: #FollowersMD(S,m): given a state S (a subset of {1, ...,m}) #and a pos. integer m, outputs the set of states that #may follow S in a monomer-dimer tiling, Try: #FollowersMD({1,2},2); FollowersMD:=proc(S,m) local mu,gu,mu1,ku,i,mu2,lu,Mu2,Mu2a: mu:=TilS(S): ku:={seq(i, i=1..m)} minus S: gu:=[]: for mu1 in mu do lu:=SocPe(mu1): mu2:=CoveredSet(mu1) minus lu: Mu2:=powerset(mu2): for Mu2a in Mu2 do gu:=[op(gu), ku union lu union Mu2a]: od: od: gu: end: #KamaMofia(L,a): given a list L, finds out how many times #a shows up KamaMofia:=proc(L,a) local i,co: co:=0: for i from 1 to nops(L) do if L[i]=a then co:=co+1: fi: od: co: end: #TMmd(m): the transfer (0-1) matrix (as a list of lists) #for monomer-dimer tilings of a width-m rectangle, #with the canonical numbering of sets. Try: #TMmd(2); TMmd:=proc(m) local gu,i,j,lu,ru: option remember: gu:=[]: for i from 1 to 2^m do lu:=[]: ru:=FollowersMD(SN(i),m): for j from 1 to 2^m do lu:=[op(lu),KamaMofia(ru,SN(j))]: od: gu:=[op(gu),lu]: od: gu: end: #GFrectMD(a,t): the generating function for enumerating #monomer-dimer tilings of an a by n rectangle directly from #inverting (1-TMmd(a)*t) GFrectMD:=proc(a,t) local A,B,B1,i,j: A:=convert(TMmd(a),matrix): B:=IdentityMatrix(2^a): B1:=Matrix(2^a,2^a): for i from 1 to 2^a do for j from 1 to 2^a do B1[i,j]:=B[i,j]-t*A[i,j]: od: od: factor(evalm(B1^(-1))[2^a,2^a]): end: #SeqRectMD(a,N): the sequence of the number of monomer-dimer tilings #of an a by n rectangle for n=0..N #Try: #SeqRectMD(2,20); SeqRectMD:=proc(a,N) local B1,B1a,n,gu: B1:=convert(TMmd(a),Matrix): B1a:=IdentityMatrix(2^a): gu:=[]: for n from 0 to N do gu:=[op(gu),B1a[2^a,2^a]]: B1a:=Multiply(B1a,B1): od: gu: end: #SeqRectDirectMD(m,N): inputs a pos. integer m, and #outputs the first N terms of the number of #monomer-dimer tilings of Rect(m,n) #Try: #SeqRectDirectMD(4,10); SeqRectDirectMD:=proc(m,N) local n: [seq(NTmd(Rect(m,n)), n=0..N)]: end: #SeqFrameDirectMD(a1,a2,b1,b2,N) #The first N terms of the number of #monomer-dimer tilings of Frame(a1,a2,b1,b2,n,n). #Try: #SeqFrameDirectMD(2,2,2,2,5); SeqFrameDirectMD:=proc(a1,a2,b1,b2,N) local gu,n: gu:=[]: for n from 0 to N do gu:=[op(gu),NTmd(Frame(a1,a2,b1,b2,n,n))]: od: gu: end: #SeqFrameMD1human(n): an explicit formula, using a human approach #to the number of monomer-dimer tilings of #Frame(1,1,1,1,n); Try: #SeqFrameMD1human(n); SeqFrameMD1human:=proc(n) local lu,x1,x2,y1,y2,co,gu,d1,d2, e1,e2,i,lu1: lu:=(1+y1+x1)*(1+y1+x2)*(1+y2+x2)*(1+y2+x1): lu:=expand(lu): gu:=0: for i from 1 to nops(lu) do lu1:=op(i,lu): d1:=degree(lu1,x1): d2:=degree(lu1,x2): e1:=degree(lu1,y1): e2:=degree(lu1,y2): co:=normal(lu1/x1^d1/x2^d2/y1^e1/y2^e2): if not type(co,integer) then RETURN(FAIL): fi: gu:=gu+co*fibonacci(n+1-d1)*fibonacci(n+1-d2) *fibonacci(n+1-e1)*fibonacci(n+1-e2): od: gu: end: #RTMmd(a,b,S1,S2): #Inputs positive integers a and b #indicating the vertical and horizontal side-lengths #respectively of an a by b specific rectangle #and distinct integers S1 and S2 from {1,2,3,4} #where the code is #side 1=UP #side 2=LEFT #side 3=DOWN #side 4=RIGHT #and outputs the transition matrix #between all the possible states #of side S1 and side S2. #FOR MONOMER-DIMER TILINGS #(with our convention for numbering the states: #1 plus the sum of the powers of 2 of the members of the set) #Try: #RTMmd(3,2,2,3); RTMmd:=proc(a,b,S1,S2) local R,S,mu,M,N,mu1,T,S11,S21,i,j,mu1S1, mu1S2,kv1,kv2,ka: option remember: if not (type(a,integer) and type(b,integer) and a>0 and b>0 and type(S1,integer) and type(S2,integer) and S1<>S2 and member(S1,{1,2,3,4}) and member(S2,{1,2,3,4}) ) then print(`bad input!`): RETURN(FAIL): fi: R:=Rect(a,b): S11:=OutsideSide(a,b,S1): S21:=OutsideSide(a,b,S2): S:=R union S11 union S21 : mu:=TgenMD(R,S): if S1=1 or S1=3 then M:=2^b: else M:=2^a: fi: if S2=1 or S2=3 then N:=2^b: else N:=2^a: fi: for i from 1 to M do for j from 1 to N do T[i,j]:=0: od: od: for mu1 in mu do mu1S1:=CoveredSet(mu1) intersect S11: mu1S2:=CoveredSet(mu1) intersect S21: if S1=1 or S1=3 then kv1:= {seq(i,i=1..b)} minus {seq(ka[1]+1,ka in mu1S1)}: else kv1:={seq(i,i=1..a)} minus {seq(ka[2]+1,ka in mu1S1)}: fi: if S2=1 or S2=3 then kv2:= {seq(i,i=1..b)} minus {seq(ka[1]+1,ka in mu1S2)}: else kv2:={seq(i,i=1..a)} minus {seq(ka[2]+1,ka in mu1S2)}: fi: T[NS(kv1),NS(kv2)]:=T[NS(kv1),NS(kv2)]+1: od: [seq([seq(T[i,j],j=1..N)],i=1..M)]: end: #SeqFrameMD(a1,a2,b1,b2,N): The first N terms of the sequence #numerating MONOMER-DIMER tilings of #he (a1+n+a2)x(b1+n+b2) #rectangle with the middle nxn square removed #Try: SeqFrameMD(2,2,2,2,10); SeqFrameMD:=proc(a1,a2,b1,b2,N) local A1,A2,A3,A4,B1,B2,B3,B4,M,B1a,B2a, B3a,B4a,n,gu: A1:=convert(RTMmd(a1,b1,1,4),Matrix): A2:=convert(RTMmd(a1,b2,2,1),Matrix): A3:=convert(RTMmd(a2,b2,3,2),Matrix): A4:=convert(RTMmd(a2,b1,4,3),Matrix): B1:=convert(TMmd(a1),Matrix): B2:=convert(TMmd(b2),Matrix): B3:=convert(TMmd(a2),Matrix): B4:=convert(TMmd(b1),Matrix): B1a:=IdentityMatrix(2^a1): B2a:=IdentityMatrix(2^b2): B3a:=IdentityMatrix(2^a2): B4a:=IdentityMatrix(2^b1): gu:=[]: for n from 0 to N do M:=Multiply(A1,B1a): M:=Multiply(M,A2): M:=Multiply(M,B2a): M:=Multiply(M,A3): M:=Multiply(M,B3a): M:=Multiply(M,A4): M:=Multiply(M,B4a): gu:=[op(gu),Trace(M)]: B1a:=Multiply(B1a,B1): B2a:=Multiply(B2a,B2): B3a:=Multiply(B3a,B3): B4a:=Multiply(B4a,B4): od: gu: end: #SeqFrameCmd(a1,a2,b1,b2,N,t): finds #a C-finite description, and the ordinary generating function #in the variable t, to the sequence enumerating #the number of #MONOMER-DIMER tilings of Frame(a1,a2,b1,b2,n,n) for all n #using up to N data points, if it can't find anything #it returns FAIL, and N has to be made larger #TryL #SeqFrameCmd(2,2,2,2,20,t); SeqFrameCmd:=proc(a1,a2,b1,b2,N,t) local gu,n,mu: option remember: gu:=SeqFrameMD(a1,a2,b1,b2,5): if gu=[0$nops(gu)] then RETURN(0): fi: for n from 10 by 20 to N do gu:=SeqFrameMD(a1,a2,b1,b2,n): mu:=GuessRec(gu): if mu<>FAIL then RETURN(mu, GFfromRec(mu,t)): fi: od: FAIL: end: #SeqFrameCstoryMD(a1,a2,b1,b2,N,t): The verbose form of #SeqFrameCmd(a1,a2,b1,b2,N,t). #Try: #SeqFrameCstoryMD(2,2,2,2,70,t); SeqFrameCstoryMD:=proc(a1,a2,b1,b2,N,t) local gu,A,n,c,d,i1, mu,kavua1,kavua2: gu:=SeqFrameCmd(a1,a2,b1,b2,N,t): if gu=FAIL then RETURN(FAIL): fi: print(`Theorem: Let A(n) be the number of ways `): print(` to tile, with MONOMERS (unit squares) and DIMERS (domino pieces)`): print(`the region in the plane obtained by removing from the `): print(c[1]+n+c[2], ` by `, d[1] +n + d[2] , `rectangle `): print(`the central `, n, ` by ` , n, `square. `): print(`where `, c[1]=a1, c[2]=a2, d[1]=b1, d[2]=b2 ): print(`Then `): print(Sum(A(n)*t^n,n=0..infinity)=factor(gu[2])): print(``): print(`and in Maple input format:`): lprint(factor(gu[2])): print(``): print(`Equivalently, A(n) satisfies the linear recurrence`): print(A(n)=add(-gu[1][1][i1]*A(n-i1),i1=1..nops(gu[1][1]))): print(``): print(`subject to the initial conditions`): print(seq(A(i1-1)=gu[1][2][i1],i1=1..nops(gu[1][2]))): mu:=SeqFromRec(gu[1],101): kavua1:=evalf(mu[101]/mu[100]): kavua2:=mu[101]/kavua1^100: print(`A(n) is asymptotic to`, kavua2*kavua1^n): print(`For the sake of Sloane here are the first 31 terms, starting at n=0`): print(SeqFromRec(gu[1],30)): end: #SeqFrameCstoryMD1(a1,a2,b1,b2,N,t,co): The verbose form of #SeqFrameCmd(a1,a2,b1,b2,N,t) with a theorem numbered co #Try: #SeqFrameCstoryMD1(2,2,2,2,70,t,co); SeqFrameCstoryMD1:=proc(a1,a2,b1,b2,N,t,co) local gu,A,n,c,d,i1, mu,kavua1,kavua2: gu:=SeqFrameCmd(a1,a2,b1,b2,N,t): if gu=FAIL then RETURN(FAIL): fi: print(`Theorem Number`, co,`: Let A(n) be the number of ways `): print(` to tile, with MONOMERS (unit squares) and DIMERS (domino pieces)`): print(`the region in the plane obtained by removing from the `): print(c[1]+n+c[2], ` by `, d[1] +n + d[2] , `rectangle `): print(`the central `, n, ` by ` , n, `square. `): print(`where `, c[1]=a1, c[2]=a2, d[1]=b1, d[2]=b2 ): print(`Then `): print(Sum(A(n)*t^n,n=0..infinity)=factor(gu[2])): print(``): print(`and in Maple input format:`): lprint(factor(gu[2])): print(``): print(`Equivalently, A(n) satisfies the linear recurrence`): print(A(n)=add(-gu[1][1][i1]*A(n-i1),i1=1..nops(gu[1][1]))): print(``): print(`subject to the initial conditions`): print(seq(A(i1-1)=gu[1][2][i1],i1=1..nops(gu[1][2]))): mu:=SeqFromRec(gu[1],101): kavua1:=evalf(mu[101]/mu[100]): kavua2:=mu[101]/kavua1^100: print(`A(n) is asymptotic to`, kavua2*kavua1^n): print(`For the sake of Sloane here are the first 31 terms, starting at n=0`): print(SeqFromRec(gu[1],30)): end: #SeferFrameCmd(K,t,N): inputs a pos. integer K and outputs #a book with theorems about monomer-dimer #tilings of picture frames #with with parameters (a1,a2,b1,b2) from 1 to K; t is the variable for #the generating function. #It uses N data points. #Try: SeferFrameCmd(2,t,100); SeferFrameCmd:=proc(K,t,N) local co,t0,a1,a2,b1,b2,gu: co:=0: t0:=time(): print(`The Number of Monomer-Dimer Tilings of Holey Rectangles with`): print(`thin Boundaries up to width`, K): print(``): print(`By Shalosh B. Ekhad `): print(`[ShaloshBEkhad@gmail.com ]`): print(`-------------------------------------------------------------------`): for a1 from 1 to K do for a2 from 1 to K do for b1 from 1 to K do for b2 from 1 to K do gu:=SeqFrameCmd(a1,a2,b1,b2,N,t): if gu<>FAIL and gu<>0 then co:=co+1: SeqFrameCstoryMD1(a1,a2,b1,b2,N,t,co): print(`-------------------------------------------------------------------`): print(``): fi: od: od: od: od: print(`I hope, dear reader, that you enjoined reading these`, co, `theorems `): print(`as much as I did discovering them.`): print(``): print(`This ends this fascinating book!`): print(`It took`, time()-t0, `seconds to generate it.`): end: #SeqRectCmd(a,N,t): finds #a C-finite description, and the ordinary generating function #in the variable t, to the sequence enumerating #the number of monomer-dimer #tilings of an a by n rectangle #using up to N data points, if it can't find anything #it returns FAIL, and N has to be made larger #if a is odd then it is the tilings of an a by 2n rectangle #Try: #SeqRectCmd(2,20,t); SeqRectCmd:=proc(a,N,t) local gu,mu,n: option remember: for n from 10 by 10 to N do gu:=SeqRectMD(a,n): mu:=GuessRec(gu): if mu<>FAIL then RETURN(mu, factor(GFfromRec(mu,t))): fi: od: FAIL: end: #SeqRectCstoryMD(a,N,t): The verbose form of #SeqRectCmd(a,N,t). #Try: #SeqRectCstoryMD(2,20,t); SeqRectCstoryMD:=proc(a,N,t) local gu,A,i1, mu,kavua1,kavua2,n: gu:=SeqRectCmd(a,N,t): if gu=FAIL then RETURN(FAIL): fi: print(`Theorem: Let A(n) be the number of ways to tile, with `): print(`MONOMERS and DIMERS, the`): print(a, `by n rectangle. `): print(`Then `): print(Sum(A(n)*t^n,n=0..infinity)=factor(gu[2])): print(``): print(`and in Maple input format:`): lprint(factor(gu[2])): print(``): print(`Equivalently, A(n) satisfies the linear recurrence`): print(A(n)=add(-gu[1][1][i1]*A(n-i1),i1=1..nops(gu[1][1]))): print(``): print(`subject to the initial conditions`): print(seq(A(i1-1)=gu[1][2][i1],i1=1..nops(gu[1][2]))): mu:=SeqFromRec(gu[1],101): kavua1:=evalf(mu[101]/mu[100]): kavua2:=mu[101]/kavua1^100: print(`A(n) is asymptotic to`, kavua2*kavua1^n): print(`For the sake of Sloane here are the first 31 terms, starting at n=0`): print(SeqFromRec(gu[1],30)): end: #SeqRectCstoryMD1(a,N,t,co): The verbose form of #SeqRectCmd(a,N,t) but with theorem number co #Try: #SeqRectCstoryMD1(2,20,t,3); SeqRectCstoryMD1:=proc(a,N,t,co) local gu,A,i1, mu,kavua1,kavua2,n: gu:=SeqRectCmd(a,N,t): if gu=FAIL then RETURN(FAIL): fi: print(`Theorem Number`,co,`: Let A(n) be the number of ways to tile, with `): print(`MONOMERS and DIMERS, the`): print(a, `by n rectangle. `): print(`Then `): print(Sum(A(n)*t^n,n=0..infinity)=factor(gu[2])): print(``): print(`and in Maple input format:`): lprint(factor(gu[2])): print(``): print(`Equivalently, A(n) satisfies the linear recurrence`): print(A(n)=add(-gu[1][1][i1]*A(n-i1),i1=1..nops(gu[1][1]))): print(``): print(`subject to the initial conditions`): print(seq(A(i1-1)=gu[1][2][i1],i1=1..nops(gu[1][2]))): mu:=SeqFromRec(gu[1],101): kavua1:=evalf(mu[101]/mu[100]): kavua2:=mu[101]/kavua1^100: print(`A(n) is asymptotic to`, kavua2*kavua1^n): print(`For the sake of Sloane here are the first 31 terms, starting at n=0`): print(SeqFromRec(gu[1],30)): end: #SeferRectCmd(K,t,N): inputs a pos. integer K and outputs #a book with theorems about tilings of rectangles #with monomers and dimers #of width a for a from 1 to K; t is the variable for #the generating function. #It uses N data points. #Try: SeferRectCmd(4,t,100); SeferRectCmd:=proc(K,t,N) local co,t0,a,gu: co:=0: t0:=time(): print(`The Number of MONOMER-DIMER Tilings of Rectangles of`): print(`width up to `, K): print(``): print(`By Shalosh B. Ekhad `): print(`[ShaloshBEkhad@gmail.com ]`): print(`-------------------------------------------------------------------`): for a from 1 to K do gu:=SeqRectCmd(a,N,t): if gu<>FAIL and gu<>0 then co:=co+1: SeqRectCstoryMD1(a,N,t,co): print(`-------------------------------------------------------------------`): print(``): fi: od: print(`I hope, dear reader, that you enjoined reading these`, co, `theorems `): print(`as much as I did discovering them.`): print(``): print(`This ends this fascinating book!`): print(`It took`, time()-t0, `seconds to generate it.`): end: #RectTmd(a,b): #Inputs positive integers a and b #indicating the vertical and horizontal side-lengths #respectively of an a by b specific rectangle #side 1=UP #side 2=LEFT #side 3=DOWN #side 4=RIGHT #and outputs the stick-out tensor, #a set of the form [i1,i2,i3,i4,co] refererring to #the states of the availability in the four sides #(in the above order, where co indicates how many #monomer-dimer #tilings that definitely cover the a by b rectangle #but may stick out with states i1,i2,i3,i4 as above. #Try: #RectTmd(2,2); RectTmd:=proc(a,b) local R,S,mu,mu1,T,S1,S2,S3,S4,i1,i2,i3,i4, mu1S1,mu1S2,mu1S3,mu1S4,kv1,kv2,kv3,kv4,ka,i,gu,lu,lu1: option remember: if not (type(a,integer) and type(b,integer) and a>0 and b>0) then print(`bad input!`): RETURN(FAIL): fi: R:=Rect(a,b): S1:=OutsideSide(a,b,1): S2:=OutsideSide(a,b,2): S3:=OutsideSide(a,b,3): S4:=OutsideSide(a,b,4): S:=R union S1 union S2 union S3 union S4 : mu:=TgenMD(R,S): for i1 from 1 to 2^b do for i2 from 1 to 2^a do for i3 from 1 to 2^b do for i4 from 1 to 2^a do T[i1,i2,i3,i4]:=0: od: od: od: od: for mu1 in mu do mu1S1:=CoveredSet(mu1) intersect S1: mu1S2:=CoveredSet(mu1) intersect S2: mu1S3:=CoveredSet(mu1) intersect S3: mu1S4:=CoveredSet(mu1) intersect S4: kv1:= {seq(i,i=1..b)} minus {seq(ka[1]+1,ka in mu1S1)}: kv2:= {seq(i,i=1..a)} minus {seq(ka[2]+1,ka in mu1S2)}: kv3:= {seq(i,i=1..b)} minus {seq(ka[1]+1,ka in mu1S3)}: kv4:= {seq(i,i=1..a)} minus {seq(ka[2]+1,ka in mu1S4)}: T[NS(kv1),NS(kv2),NS(kv3),NS(kv4)]:=T[NS(kv1),NS(kv2),NS(kv3),NS(kv4)]+1: od: lu:={seq( seq( seq( seq( [i1,i2,i3,i4,T[i1,i2,i3,i4]], i1=1..2^b), i2=1..2^a), i3=1..2^b), i4=1..2^a)}: gu:={}: for lu1 in lu do if lu1[5]<>0 then gu:=gu union {lu1}: fi: od: gu: end: #SeqCrossDirectMD(v,h,N): The #sequence enumerating the number of #monomer-dimer tilings (perfect matchings) #for cross whose center is an h by v rectangle #with an n v rectangle to its right and left, an h by n above, #and below #for n from 0 to N #Try: #SeqCrossDirectMD(1,1,10); SeqCrossDirectMD:=proc(v,h,N) local n: [seq(NTmd(Cross(v,h,n,n,n,n)),n=0..N)]: end: #SeqCrossMD(a,b,N): the first N terms of the #sequence: number of monomer-dimer tilings of a cross #with an a by b rectangular center with #four arms of length n, for n=1..N #Try: #SeqCrossMD(2,2,10); SeqCrossMD:=proc(a,b,N) local B1,B2,B3,B4,B1a,B2a, B3a,B4a,n,mu,mu1,gu: mu:=RectTmd(a,b): B1:=convert(TMmd(b),Matrix): B2:=convert(TMmd(a),Matrix): B3:=convert(TMmd(b),Matrix): B4:=convert(TMmd(a),Matrix): B1a:=IdentityMatrix(2^b): B2a:=IdentityMatrix(2^a): B3a:=IdentityMatrix(2^b): B4a:=IdentityMatrix(2^a): gu:=[]: for n from 0 to N do gu:=[op(gu), add(mu1[5]* B1a[mu1[1],2^b]*B2a[mu1[2],2^a]*B3a[mu1[3],2^b]*B4a[mu1[4],2^a], mu1 in mu)]: B1a:=Multiply(B1a,B1): B2a:=Multiply(B2a,B2): B3a:=Multiply(B3a,B3): B4a:=Multiply(B4a,B4): od: gu: end: #SeqCrossCmd(a,b,N,t): finds #a C-finite description, and the ordinary generating function #in the variable t, to the sequence enumerating #the number of monomer-dimer #tilings of Cross(a,b,n,n) for all n #using up to N data points, if it can't find anything #it returns FAIL, and N has to be made larger #Try: #SeqCrossCmd(2,2,20,t); SeqCrossCmd:=proc(a,b,N,t) local gu,n,mu,i: option remember: for n from 5 by 10 to N do gu:=SeqCrossMD(a,b,n): mu:=GuessRec(gu): if mu<>FAIL then RETURN(mu, GFfromRec(mu,t) ): fi: od: FAIL: end: #SeqCrossCstoryMD(a,b,N,t): The verbose form of #SeqCrossCmd(a,b,N,t). #Try: #SeqCrossCstoryMD(2,3,30,t); SeqCrossCstoryMD:=proc(a,b,N,t) local gu,A,n,i1: gu:=SeqCrossCmd(a,b,N,t): if gu=FAIL then RETURN(FAIL): fi: if gu=0 then print(`It is always zero`): RETURN(0): fi: print(`Theorem: Let A(n) be the number of ways to tile, using`): print(`MONOMERS and DIMERS, the`): print(`region in the plane consisting of a cross `): print(`whose center is an`, a, `by `, b , `rectangle `): print(`and that each of the four arms has length exacty n. `): print(`Then `): print(Sum(A(n)*t^n,n=0..infinity)=factor(gu[2])): print(``): print(`and in Maple input format:`): lprint(factor(gu[2])): print(``): print(`Equivalently, A(n) satisfies the linear recurrence`): print(A(n)=add(-gu[1][1][i1]*A(n-i1),i1=1..nops(gu[1][1]))): print(``): print(`subject to the initial conditions`): print(seq(A(i1-1)=gu[1][2][i1],i1=1..nops(gu[1][2]))): print(`For the sake of Sloane here are the first 31 terms, starting at n=0`): print(SeqFromRec(gu[1],30)): end: #SeqCrossCstoryMD1(a,b,N,t): The verbose form of #SeqCrossCmd(a,b,N,t) but with a theorem number #Try: #SeqCrossCstoryMD1(2,3,30,t); SeqCrossCstoryMD1:=proc(a,b,N,t,co) local gu,A,n,i1: gu:=SeqCrossCmd(a,b,N,t): if gu=FAIL then RETURN(FAIL): fi: if gu=0 then print(`It is always zero`): RETURN(0): fi: print(`Theorem Number:`,co,` Let A(n) be the number of ways to tile, using`): print(`MONOMERS and DIMERS, the`): print(`region in the plane consisting of a cross `): print(`whose center is an`, a, `by `, b , `rectangle `): print(`and that each of the four arms has length exacty n. `): print(`Then `): print(Sum(A(n)*t^n,n=0..infinity)=factor(gu[2])): print(``): print(`and in Maple input format:`): lprint(factor(gu[2])): print(``): print(`Equivalently, A(n) satisfies the linear recurrence`): print(A(n)=add(-gu[1][1][i1]*A(n-i1),i1=1..nops(gu[1][1]))): print(``): print(`subject to the initial conditions`): print(seq(A(i1-1)=gu[1][2][i1],i1=1..nops(gu[1][2]))): print(`For the sake of Sloane here are the first 31 terms, starting at n=0`): print(SeqFromRec(gu[1],30)): end: #SeferCrossCmd(K,t,N): inputs a pos. integer K and outputs #a book with theorems about tilings with monomers and dimers of crosses #ith parameters (a,b) from 1 to K; t is the variable for #the generating function. #It uses N data points. #Try: SeferCrossCmd(3,t,100); SeferCrossCmd:=proc(K,t,N) local co,t0,a,b,gu: co:=0: t0:=time(): print(`The Number of MONOMER-DIMER Tilings of Crosses with`): print(`equal arm-lengths whose central rectangle has side-lengths`): print(`up to`, K): print(``): print(`By Shalosh B. Ekhad `): print(`[ShaloshBEkhad@gmail.com ]`): print(`-------------------------------------------------------------------`): for a from 1 to K do for b from a to K do gu:=SeqCrossCmd(a,b,N,t): if gu<>FAIL and gu<>0 then co:=co+1: SeqCrossCstoryMD1(a,b,N,t,co): print(`-------------------------------------------------------------------`): print(``): fi: od: od: print(`I hope, dear reader, that you enjoined reading these`, co, `theorems `): print(`as much as I did discovering them.`): print(``): print(`This ends this fascinating book!`): print(`It took`, time()-t0, `seconds to generate it.`): end: ################Start GFframeDouble for Dimers############# #GFframeDouble(a1,a2,b1,b2,x,y,N): #inputs positive integers a1,a2,b1,b2 and symbols x,y #and a positive integer N (telling you how far to go in guessing) #and outputs the rational function in x,y #whose coeff. of x^m*y^n (when you take the Maclaurin expansion) #gives you the the number of dimer tilings #of the region Frame(a1,a2,b1,b2,m,n); #For example, try: #GFframeDouble(2,2,2,2,x,y,50); GFframeDouble:=proc(a1,a2,b1,b2,x,y,N) local mu,lu,fu,i,j,fu1, Fux, Fuy,MU,KU,KU1: option remember: fu:={}: for i from 1 to 6 do mu:=[seq(NTframe(a1,a2,b1,b2,i,j),j=0..N)]: if mu<>[0$nops(mu)] then lu:=GuessRec(mu): if lu=FAIL then RETURN(FAIL): fi: fu1:=denom(GFfromRec(lu,y)): fu:= fu union {fu1}: fi: od: Fuy:=lcm(op(fu)): fu:={}: for i from 1 to 6 do mu:=[seq(NTframe(a1,a2,b1,b2,j,i),j=0..N)]: if mu<>[0$nops(mu)] then lu:=GuessRec(mu): if lu=FAIL then RETURN(FAIL): fi: fu1:=denom(GFfromRec(lu,x)): fu:= fu union {fu1}: fi: od: Fux:=lcm(op(fu)): Fux,Fuy: MU:= expand( Fux*Fuy* add(add(NTframe(a1,a2,b1,b2,i,j)*x^i*y^j,i=0..2*degree(Fux,x)), j=0..2*degree(Fuy,y))): MU:= add( add(coeff(coeff(MU,x,i),y,j)*x^i*y^j,i=0..degree(Fux,x)),j=0..degree(Fuy,y)): MU:=factor(MU/Fux/Fuy): KU:=taylor(MU,x=0,3*degree(Fux,x)+1): for i from 0 to 3*degree(Fux,x) do KU1:=coeff(KU,x,i): KU1:=taylor(KU1,y=0,3*degree(Fuy,y)+1): if {seq(coeff(KU1,y,j)-NTframe(a1,a2,b1,b2,i,j),j=1..3*degree(Fuy,y))} <>{0} then RETURN(FAIL): fi: od: MU: end: #GFframeDoubleStory(a1,a2,b1,b2,x,y,N): #A verbose version of GFframeDouble(a1,a2,b1,b2,x,y,N): #try GFframeDoubleStory(2,2,2,2,x,y,20); GFframeDoubleStory:=proc(a1,a2,b1,b2,x,y,N) local gu,m,n,c,d: gu:=GFframeDouble(a1,a2,b1,b2,x,y,N): if gu=FAIL then RETURN(FAIL): fi: print(`Theorem: Let A(m,n) be the number of ways to tile, with dominoes, the`): print(`region in the plane obtained by removing from the `): print(c[1]+m+c[2], ` by `, d[1] +n + d[2] , `rectangle `): print(`the central `, m, ` by ` , n, `rectangle. `): print(`where `, c[1]=a1, c[2]=a2, d[1]=b1, d[2]=b2 ): print(`Then `): print(Sum(Sum(A(m,n)*x^m*y^n,m=0..infinity),n=0..infinity)=gu): print(``): print(`and in Maple input format:`): lprint(gu): end: #GFframeDoubleStory1(a1,a2,b1,b2,x,y,N,co): #A verbose version of GFframeDouble(a1,a2,b1,b2,x,y,N): #and a numbered theorem #try GFframeDoubleStory1(2,2,2,2,x,y,20,3); GFframeDoubleStory1:=proc(a1,a2,b1,b2,x,y,N,co) local gu,m,n,c,d: gu:=GFframeDouble(a1,a2,b1,b2,x,y,N): if gu=FAIL then RETURN(FAIL): fi: print(`Theorem Number`, co, `: Let A(m,n) be the number of ways to tile, with dominoes, the`): print(`region in the plane obtained by removing from the `): print(c[1]+m+c[2], ` by `, d[1] +n + d[2] , `rectangle `): print(`the central `, m, ` by ` , n, `rectangle. `): print(`where `, c[1]=a1, c[2]=a2, d[1]=b1, d[2]=b2 ): print(`Then `): print(Sum(Sum(A(m,n)*x^m*y^n,m=0..infinity),n=0..infinity)=gu): print(``): print(`and in Maple input format:`): lprint(gu): end: #SeferGFframeDouble(K,x,y,N): inputs a pos. integer K #and a pos. integer N and two variable names x and y, and outputs #a book with theorems with rational functions in x and y #that are bivariate generating functions #about dimer tilings of picture frames #with with parameters (a1,a2,b1,b2) with rectangular centers #It uses N data points. #Try: SeferGFframeDouble(2,x,y,40); SeferGFframeDouble:=proc(K,x,y,N) local co,t0,a1,a2,b1,b2,gu: co:=0: t0:=time(): print(`Bivariate Generating Functions for the Number of Domino Tilings`): print(` of Holey Rectangles with`): print(`thin Boundaries up to width`, K): print(``): print(`By Shalosh B. Ekhad `): print(`[ShaloshBEkhad@gmail.com ]`): print(`-------------------------------------------------------------------`): for a1 from 1 to K do for a2 from 1 to K do for b1 from 1 to K do for b2 from 1 to K do gu:=GFframeDouble(a1,a2,b1,b2,x,y,N): if gu<>FAIL then co:=co+1: GFframeDoubleStory1(a1,a2,b1,b2,x,y,N,co): print(`-------------------------------------------------------------------`): print(``): fi: od: od: od: od: print(`I hope, dear reader, that you enjoined reading these`, co, `theorems `): print(`as much as I did discovering them.`): print(``): print(`This ends this fascinating book!`): print(`It took`, time()-t0, `seconds to generate it.`): end: ################end GFframeDoule for Dimers############# ################Start GFframeDoubleMD for Monomer-Dimers############# #GFframeDoubleMD(a1,a2,b1,b2,x,y,N): #inputs positive integers a1,a2,b1,b2 and symbols x,y #and a positive integer N (telling you how far to go in guessing) #and outputs the rational function in x,y #whose coeff. of x^m*y^n (when you take the Maclaurin expansion) #gives you the the number of tilings with MONOMERS and DIMERS #of the region Frame(a1,a2,b1,b2,m,n); #For example, try: #GFframeDoubleMD(2,2,2,2,x,y,50); GFframeDoubleMD:=proc(a1,a2,b1,b2,x,y,N) local mu,lu,fu,i,j,fu1, Fux, Fuy,MU,KU,KU1: option remember: fu:={}: for i from 1 to 6 do mu:=[seq(NTframeMD(a1,a2,b1,b2,i,j),j=0..N)]: if mu<>[0$nops(mu)] then lu:=GuessRec(mu): if lu=FAIL then RETURN(FAIL): fi: fu1:=denom(GFfromRec(lu,y)): fu:= fu union {fu1}: fi: od: Fuy:=lcm(op(fu)): fu:={}: for i from 1 to 6 do mu:=[seq(NTframeMD(a1,a2,b1,b2,j,i),j=0..N)]: if mu<>[0$nops(mu)] then lu:=GuessRec(mu): if lu=FAIL then RETURN(FAIL): fi: fu1:=denom(GFfromRec(lu,x)): fu:= fu union {fu1}: fi: od: Fux:=lcm(op(fu)): Fux,Fuy: MU:= expand( Fux*Fuy* add(add(NTframeMD(a1,a2,b1,b2,i,j)*x^i*y^j,i=0..2*degree(Fux,x)), j=0..2*degree(Fuy,y))): MU:= add( add(coeff(coeff(MU,x,i),y,j)*x^i*y^j,i=0..degree(Fux,x)),j=0..degree(Fuy,y)): MU:=factor(MU/Fux/Fuy): KU:=taylor(MU,x=0,3*degree(Fux,x)+1): for i from 0 to 3*degree(Fux,x) do KU1:=coeff(KU,x,i): KU1:=taylor(KU1,y=0,3*degree(Fuy,y)+1): if {seq(coeff(KU1,y,j)-NTframeMD(a1,a2,b1,b2,i,j),j=1..3*degree(Fuy,y))} <>{0} then RETURN(FAIL): fi: od: MU: end: #GFframeDoubleStoryMD(a1,a2,b1,b2,x,y,N): #A verbose version of GFframeDouble(a1,a2,b1,b2,x,y,N): #try GFframeDoubleStoryMD(2,2,2,2,x,y,20); GFframeDoubleStoryMD:=proc(a1,a2,b1,b2,x,y,N) local gu,m,n,c,d: gu:=GFframeDoubleMD(a1,a2,b1,b2,x,y,N): if gu=FAIL then RETURN(FAIL): fi: print(`Theorem: Let A(m,n) be the number of ways to tile, `): print(` with MONOMERS and DIMERS, the`): print(`region in the plane obtained by removing from the `): print(c[1]+m+c[2], ` by `, d[1] +n + d[2] , `rectangle `): print(`the central `, m, ` by ` , n, `rectangle. `): print(`where `, c[1]=a1, c[2]=a2, d[1]=b1, d[2]=b2 ): print(`Then `): print(Sum(Sum(A(m,n)*x^m*y^n,m=0..infinity),n=0..infinity)=gu): print(``): print(`and in Maple input format:`): lprint(gu): end: #GFframeDoubleStory1MD(a1,a2,b1,b2,x,y,N,co): #A verbose version of GFframeDoubleMD(a1,a2,b1,b2,x,y,N): #and a numbered theorem #try GFframeDoubleStory1MD(2,2,2,2,x,y,20,3); GFframeDoubleStory1MD:=proc(a1,a2,b1,b2,x,y,N,co) local gu,m,n,c,d: gu:=GFframeDoubleMD(a1,a2,b1,b2,x,y,N): if gu=FAIL then RETURN(FAIL): fi: print(`Theorem Number`, co, `: Let A(m,n) be the number of ways to tile,`): print(` with MONOMERS and DIMERS, the`): print(`region in the plane obtained by removing from the `): print(c[1]+m+c[2], ` by `, d[1] +n + d[2] , `rectangle `): print(`the central `, m, ` by ` , n, `rectangle. `): print(`where `, c[1]=a1, c[2]=a2, d[1]=b1, d[2]=b2 ): print(`Then `): print(Sum(Sum(A(m,n)*x^m*y^n,m=0..infinity),n=0..infinity)=gu): print(``): print(`and in Maple input format:`): lprint(gu): end: #SeferGFframeDoubleMD(K,x,y,N): inputs a pos. integer K #and a pos. integer N and two variable names x and y, and outputs #a book with theorems with rational functions in x and y #that are bivariate generating functions #about tilings of picture frames with MONOMERS and DIMERS #with with parameters (a1,a2,b1,b2) with rectangular centers #It uses N data points. #Try: SeferGFframeDoubleMD(2,x,y,40); SeferGFframeDoubleMD:=proc(K,x,y,N) local co,t0,a1,a2,b1,b2,gu: co:=0: t0:=time(): print(`Bivariate Generating Functions for the Number of MONOMER-DIMER `): print(` Tilings of Holey Rectangles with`): print(`thin Boundaries up to width`, K): print(``): print(`By Shalosh B. Ekhad `): print(`[ShaloshBEkhad@gmail.com ]`): print(`-------------------------------------------------------------------`): for a1 from 1 to K do for a2 from 1 to K do for b1 from 1 to K do for b2 from 1 to K do gu:=GFframeDoubleMD(a1,a2,b1,b2,x,y,N): if gu<>FAIL then co:=co+1: GFframeDoubleStory1MD(a1,a2,b1,b2,x,y,N,co): print(`-------------------------------------------------------------------`): print(``): fi: od: od: od: od: print(`I hope, dear reader, that you enjoined reading these`, co, `theorems `): print(`as much as I did discovering them.`): print(``): print(`This ends this fascinating book!`): print(`It took`, time()-t0, `seconds to generate it.`): end: ################End GFframeDoubleMD for Monomer-Dimers#############