######################################################################
## Decoupage.txt Save this file as Decoupage.txt  to use it,         #
# stay in the                                                        #
## same directory, get into Maple (by typing: maple <Enter> )        #
## and then type:  read  `Decoupage.txt` <Enter>                     #
## Then follow the instructions given there                          #
##                                                                   #
## Written by Doron Zeilberger, Rutgers University ,                 #
# and Robert Dougherty-Bliss, Darmouth College                       #
# and Natalya Ter-Saakov      , Rutgers University ,                 #
##  DoronZeil at gmail dot com                                       # 
######################################################################


print(`First Written: Sept. 10,  2025: tested for Maple 2020 `):
print(` This Version  : Sept. 10, 2025`):
print():
print(`This is Decoupage.txt, A Maple package`):
print(`accompanying Robert Dougherty-Bliss, Natalya Ter-Saakov  and Doron Zeilberger's  article: `):
print(`   In How Many Ways Can You Cut a 4 by n rectangle into two CONGRUENT Connected pieces?`):
print(` http://sites.math.rutgers.edu/~zeilberg/tokhniot/mamarim/mamarimhtml/decoupage.html `):
print():
print(`The most current version is available on WWW at:`):
print(` http://sites.math.rutgers.edu/~zeilberg/tokhniot/Decoupage.txt .`):
print(`Please report all bugs to: DoronZeil at gmail dot com .`):
print():
print(`For general help, and a list of the MAIN functions,`):
print(` type "ezra();". For specific help type "ezra(procedure_name);" `):
print(`For a list of the supporting functions type: ezra1();`):
print():
print(`-------------------`):




ezraS:=proc()
if args=NULL then

print(`The Story procedures are: PM, PMa ` ):
print(``):

else
ezra(args):

fi:


end:



ezra1:=proc()

if args=NULL then

print(`The SUPPORTING procedures are:  BV, CC, IsGM, Mat4na, Natasha, , Story1, Story2 `):

else
ezra(args):

fi:


end:

ezra:=proc()
if args=NULL then

print(` Decoupage.txt: A Maple package for  studying ways to cut a a 4 by n rectangle into two congruent connected pieces`):

print(`The MAIN procedures are: GF4, GFa, countM4n, countM4na, Good2ndRows, Mat4n, Mat4naA, Tuples `):


print(``):


elif nargs=1 and args[1]=BV then
print(`BV(n): all the 0-1 lists of length n. Try:`):
print(`BV(6);`):

elif nargs=1 and args[1]=CC then
print(`CC(G,v0): the connected component of vertex v0 in the graph G=[V,E]. Try`):
print(`CC([{1,2,3,4},{{1,2},{1,3},{3,4}}],1);`):

elif nargs=1 and args[1]=GF4 then
print(`GF4(x): The generating function for the number of cutting a 4 by n rectangle into two connected congruent pieces. Try:`):
print(`GF4(x);`):

elif nargs=1 and args[1]=GFa then
print(`GFa(x, a): The generating function for the number of 4xn rectangles cut into two connected, congruent pieces, where the first a entries of the first row are in the same part. Try:`):
print(`GFa(x, 10)`):

elif nargs=1 and args[1]=countM4n then
print(`countM4n(n): The number of ways to cut a 4 by n rectangle into two connected congruent pieces. Try:`):
print(`countM4n(20)`):

elif nargs=1 and args[1]=countM4na then
print(`countM4na(n, a): The number of 4xn rectangles cut into two connected, congruent pieces, where the first a entries of the first row are in the same part. Try:`):
print(`countM4n(20, 10)`):


elif nargs=1 and args[1]=Good2ndRows then
print(`Good2ndRows(n,a): the binary bectores of length n-1 such that if you append 1 you get a good matrix. Try:`):
print(`Good2ndRows(10,0);`):

elif nargs=1 and args[1]=IsGM then
print(`IsGM(M): Is the k by n 0-1 matrix a good one? i.e. are the 0's all connected and all the 1's all connected?. Try:`):
print(`IsGM([[1,0,0],[0,0,1]]);`):


elif nargs=1 and args[1]=Mat4n then
print(`Mat4n(n): all 4 by n 0-1 matrices such that the 0-regions and 1-regions are both connected and they are congruent to each other. Try:`):
print(`Mat4n(10);`):

elif nargs=1 and args[1]=Mat4na then
print(`Mat4na(n,a): all 4 by n 0-1 matrices with a 0s at the top (and hence n-a at the bottom)`):
print(`that can be cut into two congruent connected pieces. Try:`):
print(`Mat4na(10,0);`):


elif nargs=1 and args[1]=Mat4naA then
print(`Mat4naA(n,a): Like Mat4na(n,a) but the matrices are cut in half, since the second half is implied. Try:`):
print(`Mat4naA(10,0);`):


elif nargs=1 and args[1]=Natasha then
print(`Natasha(v): inputs a 0-1 vector and outputs its reflected complement. Try:`):
print(`Natasha([0,1,1,0]);`):

elif nargs=1 and args[1]=PM then
print(`PM(K): prints all the good matrices for n<=K. Try:`):
print(`PM(10);`):


elif nargs=1 and args[1]=PMa then
print(`PMa(K): prints all the ABBREVIATED good matrices for n<=K. Try:`):
print(`PMa(10);`):

elif nargs=1 and args[1]=Story1 then
print(`Story1(n,a): What possible letters can occur in the i-th location of a good matrix for i<=trunc(n/2). Try:`):
print(`Story1(10,0);`):

elif nargs=1 and args[1]=Story2 then
print(`Story1(n,a): What possible edges can occur between the i-th location and (i+1)-location of a good matrix for i<=trunc(n/2)-1. Try:`):
print(`Story2(10,0);`):

elif nargs=1 and args[1]=Tuples then
print(`Tuples(n,a,i,k): The set of {seq([op(i..i+k,x], x in Mat4naA(n,a))}: Try:`):
print(`Tuples(10,0,1,0);`):

else
 print(`There is no such thing as`, args):

fi:


end:

ez:=proc(): print(`  PM(K), Tuples(n,a,i,j), Story1(n,a), Story2(n,a)  `): end:




#start from Pegden

#CC(G,v0): the connected component of vertex v0 in the graph G=[V,E]
CC:=proc(G,v0) local V,E,N,v,e,v1,S,S1,S2:
V:=G[1]:
E:=G[2]:

if not member(v0,V) then
 RETURN(FAIL):
fi:

for v in V do
N[v]:={}:
od:
for e in E do
 N[e[1]]:=N[e[1]] union {e[2]}:
 N[e[2]]:=N[e[2]] union {e[1]}:
od:
S:={v0}:
S1:=S union N[v0]:
while S<>S1 do
 S2:=S1 union {seq(op(N[v1]),v1 in S1)}:
S:=S1:
S1:=S2:
od:
S1:
end:

#IsCon(G): is the graph G=[V,E] connected?. Try:
#IsCon([{1,2,3},{{1,2},{1,3}}]);
IsCon:=proc(G) local V:
V:=G[1]:

if V={} then
 RETURN(true):
fi:
evalb(CC(G,V[1])=V):
end:

#GG(k,n): the grid graph for a k by n square returns [Vertices, Edges]. Try:
#GG(2,4);
GG:=proc(k,n) local V,E,i,j:
V:={seq(seq([i,j],j=1..n),i=1..k)}:
E:={seq(seq({[i,j],[i+1,j]},i=1..k-1),j=1..n)} union {seq(seq({[i,j],[i,j+1]},i=1..k),j=1..n-1)}:
[V,E]:
end:


#IndG(G,V1): Given a graph G=[V,E] and a subset V1 of V outputs the innduced graph. Try
#IndG([{1,2,3,4},{{1,2},{1,3},{1,4},{2,3}}],{1,3});
IndG:=proc(G,V1) local V,E,e,E1:
V:=G[1]:
E:=G[2]:

if V1 minus V<>{} then
  RETURN(FAIL):
fi:

E1:={}:
for e in E do
 if e minus V1={} then
  E1:=E1 union {e}:
 fi:
od:
[V1,E1]:
end:

#IsGM(M): Is the k by n 0-1 matrix a good one? i.e. are the 0's all connected and all the 1's all connected?
IsGM:=proc(M) local n,k,G,V,V0,V1,v:
k:=nops(M):
n:=nops(M[1]):
G:=GG(k,n):
V:=G[1]:
V0:={}:
V1:={}:

for v in V do
 if M[v[1]][v[2]]=0 then
  V0:=V0 union {v}:
 elif M[v[1]][v[2]]=1 then
  V1:=V1 union {v}:
 fi:
od:

IsCon(IndG(G,V0)) and IsCon(IndG(G,V1)):

end:
#end from Pegden



BV:=proc(n) local S,s:
option remember:
if n=0 then
  RETURN({[]}):
  fi:
  S:=BV(n-1):

{seq([op(s),0],s in S), seq([op(s),1],s in S)}:
end:

#Natasha(v): inputs a 0-1 vector and outputs its reflected complement
Natasha:=proc(v) local n,i:
n:=nops(v):
[seq(1-v[n+1-i],i=1..n)]:
end:

#Mat4na(n,a): all 4 by n 0-1 matrices with a 0s at the top (and hence n-a at the bottom) and all possible 2nd rows
#and the implied third row. Try:
#Mat4na(10,0);
Mat4na:=proc(n,a) local S,gu, gu1,Ho,ho,i1:
option remember:
if a>n/2 then
 RETURN({}):
fi:

S[1]:=[0$a,1$(n-a)]:

S[4]:=[0$(n-a),1$a]:

gu:=BV(n-1):
gu:=[seq([op(gu1),1],gu1 in gu)]:

Ho:={}:

for i1 from 1 to nops(gu) do
 S[2]:=gu[i1]:
 S[3]:=Natasha(S[2]):
 ho:=[S[1],S[2],S[3],S[4]]:
 if IsGM(ho) then
  Ho:=Ho union {ho}:
 fi:
 od:
  
 Ho:

end:

#Mat4n(n): all 4 by n 0-1 matrices such that the 0-regions and 1-regions are both connected and they are congruent to each other. Try:
#Mat4n(10);
Mat4n:=proc(n) local a:
option remember:
{seq(op(Mat4na(n,a)),a=0..trunc(n/2))}:
end:



#PM(K): prints all the good matrices for n<=K. Try:
#PM(10);
PM:=proc(K) local x,n,a,gu,gu1,lu,lu1:

lu:=GF4(x):
lu1:=taylor(lu,x=0, K+3):

print(`All the 4 by n 0-1 matrices where the 0-part and 1-part are connected and congruent to each other (up to symmetry) `):

print(`By symmetry we can assume that the top-rightmost enrty, i.e. the (1,n) entry is a 1, we will only list these `):

for n from 2 to K do

print(`There are `, coeff(lu1,x,n), `such 4-rowed 0-1 matrices with`, n, `columns `):
print(``):
print(`The first row has consecutive zeroes followed by consecutive ones`):
print(`The number of zeroes at the top row is between 0 and`, trunc(n/2)):
print(``):
print(`We will now list them accordingly`):

for a from 0 to trunc(n/2) do

 gu:=Mat4na(n,a):

print(`The number of 4 by`, n, `such good 0-1 matrices  starting with `, a, `zeroes at the top row followed by`, n-a, `ones is `, nops(gu)):
  
print(`Here they are `):

for gu1 in gu do
print(``):
print(`--------------------`):
print(``):
print(matrix(gu1)):
od:
print(``):
print(`----------------------------`):
print(``):
od:

od:

end:


#PMa(K): prints all the ABBREVIATED good matrices for n<=K. Try:
#PMa(10);
PMa:=proc(K) local n,a,gu,gu1:

for n from 2 to K do
 for a from 0 to trunc(n/2) do
  print(`n=`, n, `a= `, a):
  
 gu:=Mat4naA(n,a):

for gu1 in gu do
print(``):
print(`--------------------`):
print(``):
print(matrix(gu1)):
od:

od:

od:

end:

#Tra(M): The transpose of the matrix M
Tra:=proc(M) local i,j:
[seq([seq(M[j][i],j=1..nops(M))],i=1..nops(M[1]))]:
end:

Mat4naA:=proc(n,a) local gu,gu1,lu,lu1:

gu:=Mat4na(n,a):

lu:={}:
for gu1 in gu do
lu1:=Tra(gu1):

lu1:=[op(1..trunc(n/2),lu1)]:

lu:=lu union {lu1}:
od:
lu:

end:


#Tuples(n,a,i,k): The set of {seq([op(i..i+k,x], x in Mat4naA(n,a))}: Try:
#Tuples(10,0,1,0);
Tuples:=proc(n,a,i,k) local gu,x:
gu:=Mat4naA(n,a):
{seq([op(i..i+k,x)], x in gu)}:
end:



#Story1(n,a): What possible letters can occur in the i-th location of a good matrix for i<=trunc(n/2). Try:
#Story1(10,0);
Story1:=proc(n,a) local i:

print(`For the creatuers with n=`,n, `a=`, a):

for i from 1 to trunc(n/2) do
 print(`The `, i, `-th letter may be `):
 lprint(Tuples(n,a,i,0)):
 od:

end:



#Story1(n,a): What possible edges can occur between the i-th location and the (i+1)-th of a good matrix for i<=trunc(n/2)-1. Try:
#Story2(10,0);

#Story2(n,a):
Story2:=proc(n,a) local i:

print(`For the creatuers with n=`,n, `a=`, a):

for i from 1 to trunc(n/2)-1 do
print(`----------------------`):
print(``):
print(`The `, [i,i+1], `-th letters may be `):
 lprint(Tuples(n,a,i,1)):
 od:

end:




#Good2ndRows(n,a): the binary bectores of length n-1 such that if you append 1 you get a good matrix. Try:
#Good2ndRows(10,0);
Good2ndRows:=proc(n,a) local S,gu, gu1,Ho,ho,i1:
option remember:
if a>n/2 then
 RETURN({}):
fi:

S[1]:=[0$a,1$(n-a)]:

S[4]:=[0$(n-a),1$a]:

gu:=BV(n-1):
gu:=[seq([op(gu1),1],gu1 in gu)]:

Ho:={}:

for i1 from 1 to nops(gu) do
 S[2]:=gu[i1]:
 S[3]:=Natasha(S[2]):
 ho:=[S[1],S[2],S[3],S[4]]:
 if IsGM(ho) then
  Ho:=Ho union {[op(1..n-1,gu[i1])]}:
 fi:
 od:
  
 Ho:

end:


#GF4(x): The generating function for the number of cutting a 4 by n rectangle into two connected congruent pieces. Try:
#GF4(x);
GF4:=proc(x):
TransferMatrixMethods[countGF](x):
end:

#GFa(x): The pre-computed list of length 6 whose i-th entry is the Sum(nops(Mat4na(n,i-1)*x^n,n=0..infinity); Try:
#GFa(x)
GFa:=proc(x, a):
    TransferMatrixMethods[countGFA](x, a):
end:

countM4n:=proc(n)
    TransferMatrixMethods[count](n):
end:

countM4na:=proc(n, a)
    TransferMatrixMethods[countA](n, a):
end:

L1 := [(x^6+x^5+x^3-3*x^2+1)/(x-1)/(x^4+3*x^2-1),-x^2*(x+1)^2/(x^4+3*x^2-1),x^4*(x^5-x^3-4*x^2+2*x+3)/(x-1)/(x^4+3*x^2-1),x^6*(3*x^5+x^4-3*x^3-9*x^2+5*x+7)/(x-1)/(x^4+3*x^2-1),
x^8*(8*x^5+3*x^4-7*x^3-22*x^2+12*x+17)/(x-1)/(x^4+3*x^2-1), x^10*(20*x^5+8*x^4-17*x^3-53*x^2+29*x+41)/(x-1)/(x^4+3*x^2-1)]:

### start of transfer matrix methods
# this is wrapped in a module because the transfer matrix states are annoying
# maple symbols. the exported methods can be used directly, or via the
# convenience functions defined above.
TransferMatrixMethods := module()
    uses LinearAlgebra, gfun;
    local e, d, t, m, a, b, g, wa, wb, start_alph, start_trans, adj1, adj, adj2, end_trans, end_alph,
          state_to_transfer, transfer_matrix, alph:
    export count, countA, countGF, countGFA:
    # matrix for initial part
    start_alph := [e,d,t,m]:
    start_trans := letter -> ListTools[Search](letter, start_alph):

    adj1 := Matrix(nops(start_alph)):

    adj1[start_trans(e), start_trans(e)] := 1:
    adj1[start_trans(e), start_trans(d)] := 1:
    adj1[start_trans(e), start_trans(t)] := 1:
    adj1[start_trans(e), start_trans(m)] := 1:

    adj1[start_trans(d), start_trans(d)] := 1:
    adj1[start_trans(d), start_trans(m)] := 1:

    adj1[start_trans(t), start_trans(t)] := 1:
    adj1[start_trans(t), start_trans(m)] := 1:

    adj1[start_trans(m), start_trans(d)] := 1:
    adj1[start_trans(m), start_trans(t)] := 1:
    adj1[start_trans(m), start_trans(m)] := 1:

    # matrix for "ending" (middle) part
    end_alph := [a, b, g, wa, wb]:
    end_trans := letter -> ListTools[Search](letter, end_alph):

    adj2 := Matrix(nops(end_alph)):

    adj2[end_trans(a), end_trans(a)] := 1:
    adj2[end_trans(a), end_trans(b)] := 1:
    adj2[end_trans(a), end_trans(g)] := 1:
    adj2[end_trans(a), end_trans(wb)] := 1:

    adj2[end_trans(b), end_trans(a)] := 1:
    adj2[end_trans(b), end_trans(b)] := 1:
    adj2[end_trans(b), end_trans(g)] := 1:
    adj2[end_trans(b), end_trans(wa)] := 1:

    adj2[end_trans(g), end_trans(a)] := 1:
    adj2[end_trans(g), end_trans(b)] := 1:
    adj2[end_trans(g), end_trans(g)] := 1:

    adj2[end_trans(wa), end_trans(wa)] := 1:
    adj2[end_trans(wa), end_trans(a)] := 1:

    adj2[end_trans(wb), end_trans(wb)] := 1:
    adj2[end_trans(wb), end_trans(b)] := 1:

    # matrix for getting from one to the other
    alph := [op(start_alph), op(end_alph)]:
    adj := Matrix(nops(start_alph), nops(end_alph)):

    adj[start_trans(e), end_trans(a)] := 1:
    adj[start_trans(e), end_trans(b)] := 1:
    adj[start_trans(e), end_trans(g)] := 1:
    adj[start_trans(e), end_trans(wb)] := 1:

    adj[start_trans(d), end_trans(b)] := 1:
    adj[start_trans(d), end_trans(g)] := 1:

    adj[start_trans(t), end_trans(wb)] := 1:
    adj[start_trans(t), end_trans(b)] := 1:

    adj[start_trans(m), end_trans(b)] := 1:
    adj[start_trans(m), end_trans(g)] := 1:

    # make a block matrix to connect the two parts.
    transfer_matrix := <<adj1 | ZeroMatrix(4, 5)>, <ZeroMatrix(5, 4) | adj2>>:
    # add the "links" from the upper to the lower block.
    transfer_matrix[start_trans(e), nops(start_alph) + end_trans(a)] := 1:
    transfer_matrix[start_trans(e), nops(start_alph) + end_trans(b)] := 1:
    transfer_matrix[start_trans(e), nops(start_alph) + end_trans(g)] := 1:
    transfer_matrix[start_trans(e), nops(start_alph) + end_trans(wb)] := 1:

    transfer_matrix[start_trans(d), nops(start_alph) + end_trans(b)] := 1:
    transfer_matrix[start_trans(d), nops(start_alph) + end_trans(g)] := 1:

    transfer_matrix[start_trans(t), nops(start_alph) + end_trans(b)] := 1:
    transfer_matrix[start_trans(t), nops(start_alph) + end_trans(wb)] := 1:

    transfer_matrix[start_trans(m), nops(start_alph) + end_trans(b)] := 1:
    transfer_matrix[start_trans(m), nops(start_alph) + end_trans(g)] := 1:

    state_to_transfer := proc(s)
        if s in [e, d, t, m] then
            return start_trans(s):
        elif s in [a, b, g, wa, wb] then
            return nops(start_alph) + end_trans(s):
        fi:

        lprint("bad state: ", s):
        error("should not be reached"):
    end:

    count := proc(n)
        option remember:
        local starts, accepts, M, start, final, total:
        starts := [e, a, g]:
        if n mod 2 = 0 then
            accepts := [e, d, t, a, b, g, wa, wb]:
        else
            accepts := [g, wa, wb]:
        fi:

        M := transfer_matrix^(ceil(n / 2) - 1):

        total := 0:
        for start in starts do
        for final in accepts do
            total += M[state_to_transfer(start), state_to_transfer(final)]:
        od:
        od:

        total:
    end:

    countA := proc(n, run_length)
        option remember:
        local total_steps, starts, M, accepts, total, A, B, start, final, accept:
        if run_length > n / 2 then
            return 0:
        fi:

        total_steps := ceil(n/2) - 1:

        if run_length = 0 then
            starts := [a, g]:
            M := adj2^total_steps:

            if n mod 2 = 0 then
                accepts := [a, b, g, wa, wb]:
            else
                accepts := [g, wa, wb]:
            fi:

            total := 0:
            for start in starts do
            for final in accepts do
                total += M[end_trans(start), end_trans(final)]:
            od:
            od:

            return total:
        fi:

        # we start with `e`, see a run of length run_length, then switch to a
        # non-run for the remaining steps.
        A := adj1^(run_length - 1):

        if run_length < n / 2 then
            # we *must* transition to a non-run state.
            # there were run_length - 1 steps above, and
            #
            #       1 + total_steps -run_length
            #
            # here, for a total of total_steps.
            B := adj . adj2^(total_steps - run_length):

            M := A . B:
            if n mod 2 = 0 then
                accepts := [a, b, g, wa, wb]:
            else
                accepts := [g, wa, wb]:
            fi:

            return add(M[start_trans(e), end_trans(accept)], accept in accepts):
        else
            # we *do not* transition to a non-run state.
            M := A:
            if n mod 2 = 0 then
                accepts := [e, d, t]:
            else
                accepts := []:
            fi:

            return add(M[start_trans(e), start_trans(accept)], accept in accepts):
        fi:
    end:

    # return the generating function for the number of "2-congruence" 4xn matrices
    # using rigorous linear algebra.
    countGF := proc(x)
        option remember:
        local starts, accepts, M, start, final, total, M_gf, even_gf, odd_gf, gf:
        starts := [e, a, g]:

        # get the gf for b(n) = a(2n + 2) and c(n) = a(2n + 1), respectively.
        # both are computed with M = transfer_matrix^n.
        M_gf := 1 / (1 - x * transfer_matrix):

        accepts := [e, d, t, a, b, g, wa, wb]:
        even_gf := 0:
        for start in starts do
        for final in accepts do
            even_gf += M_gf[state_to_transfer(start), state_to_transfer(final)]:
        od:
        od:

        accepts := [g, wa, wb]:
        odd_gf := 0:
        for start in starts do
        for final in accepts do
            odd_gf += M_gf[state_to_transfer(start), state_to_transfer(final)]:
        od:
        od:

        gf := x^2 * subs(x=x^2, even_gf) + x * subs(x=x^2, odd_gf):
        factor(gf):
    end:

    # return the generating function for the number of "2-congruence" 4xn matrices
    # whose first row begins with `a1` 0's using (rigorous) guessing.
    countGFA := proc(x, a1)
        option remember:
        local needed_terms, L, gfs, k, gf:
        # this is the degree of the lcm of the denominators of 1 / (1 - xM), where
        # M is the transfer matrix of our FSM. this means that every sequence
        # derived from this matrix satisfies a C-finite recurrence of order at most
        # 8, and therefore can be guessed with around 2 * 8 nonzero terms (or
        # something like that).
        needed_terms := 8 * 2:

        L := [seq(countA(k, a1), k=2*a1..2*a1+needed_terms)]:
        gfs := guessgf(L, x):
        if gfs = FAIL then
            return FAIL:
        fi:

        gf := factor(x^(2 * a1) * gfs[1]):
    end:
end: