##################################################################### ##KamaTzviot: Save this file as KamaTzviot # ## To use it, stay in the # ##same directory, get into Maple (by typing: maple ) # ##and then type: read KamaTzviot # ##Then follow the instructions given there # ## # ##Written by Doron Zeilberger, Rutgers University , # #zeilberg at math dot rutgers dot edu # ###################################################################### #First Posted: March 30, 2011 #This version: April 26 (correcting procedures GFGE and GFkE) print(`Created: March 30, 2011`): print(`This version: April 26, 2011`): print(` This is KamaTzviot `): print(`It is accompanies the article `): print(`Automatic Generation of `): print(`Generating Functions for Chromatic Polynomials`): print(`of Grid Graphs (and much more general creatures) of fixed `): print(`(but arbitrary!) width `): print(`by Shalosh B. Ekhad, Jocelyn Quaintance, and Doron Zeilberger`): print(`dedicated in loving memory of`): print(` Guru Phillippe FLAJOLET (Dec. 1, 1948- March 22, 2011) .`): print(`The article is exclusively published in the Personal Journal of`): print(`Shalosh B. Ekhad and Doron Zeilberger `): print(` http://www.math.rutgers.edu/~zeilberg/pj.html `): print(`and arxiv.org `): print(`the direcet url being:`): print(`http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/tzeva.html`): print(``): print(`Please report bugs to zeilberg at math dot rutgers dot edu`): print(``): print(`The most current version of this package `): print(` is available from`): print(`http://www.math.rutgers.edu/~zeilberg/tokhniot/KamaTzviot .`): print(`-----------------------------------------------`): print(`For a list of the Checking procedures type ezraC();, for help with`): print(`a specific procedure, type ezra(procedure_name); .`): print(``): print(`-----------------------------------------------`): print(`For a list of the supporting procedures type ezra1();, for help with`): print(`a specific procedure, type ezra(procedure_name); .`): print(``): print(`-----------------------------------------------`): print(`For a list of the Story procedures type ezraS();, for help with`): print(`a specific procedure, type ezra(procedure_name); .`): print(``): print(`-----------------------------------------------`): print(`For a list of the MAIN procedures type ezra();, for help with`): print(`a specific procedure, type ezra(procedure_name); .`): print(``): print(`-----------------------------------------------`): with(combinat): ezraS:=proc() if args=NULL then print(` The story procedures are: `): print(` SipurGFRect, SipurGFCyl, SipurSeqCyl, SipurSeqRect `): print(` SquareSeqStory `): else ezra(args): fi: end: ezraC:=proc() if args=NULL then print(` The checking procedures are: `): print(` CartProdGraphs `): print(` CheckGFkF ,CheckGFkS, CheckGFGG `): print(` ContractE, CP, DeleteE, `): print(` LadderG, SeqknSlow, SeqGnSlow`): print(` `): else ezra(args): fi: end: ezra1:=proc() if args=NULL then print(` The supporting procedures are: `): print(` CC, CheckGFkS, ExtendColoring `): print(` LegalRows , LegalColorings, LegalVectors, LoopGraph, `): print(` Options,OptionsG,PathGraph, SP , Spg, SPtoSt, `): print(` States , TMk, TMG,TS1S2, ,TS1S2G `): else ezra(args): fi: end: ezra:=proc() if args=NULL then print(`The main procedures are: `): print(` GFk, GFkE, GFG, GFGE, GFGG, SeqGn, Seqkn , SquareSeq `): elif nops([args])=1 and op(1,[args])=CartProdGraphs then print(`CartProdGraphs(G1,G2): the Cartesian product of two graphs`): print(`G1=[V1,E1] and G2=[V2,E2]. For example, try:`): print(`CartProdGraphs(PathGraph(2), PathGraph(2));`): elif nops([args])=1 and op(1,[args])=CC then print(` CC(G): all the canonical colorings of a graph G=[V,E] `): print(` with exactly c colors. For example, try: `): print(` CC(PathGraph(2)); `): elif nops([args])=1 and op(1,[args])=CheckGFGG then print(`CheckGFGG(G,m,N): checks GFGG(G,m,c,t) for n=1..N`): print(`For example, try: CheckGFGG({{1,2}},2,{[1,1],[2,2]},4); `): elif nops([args])=1 and op(1,[args])=CheckGFkS then print(`CheckGFkS(k,N,C): checks GFk(k,c,t) for c=2..C and n=1..N`): print(`completey naively, by actually constructing the set of c-colorings`): print(`for numeric c`): print(`For example, try: CheckGFkS(3,8,3);`): elif nops([args])=1 and op(1,[args])=CheckGFkF then print(`CheckGFkF(k,N): checks GFk(k,c,t) `): print(` by cmputing the Chromatic polynomials`): print(`of a k by n grid graph for n=1..N, using procedure CP`): print(`For example, try: CheckGFkF(3,8);`): elif nops([args])=1 and op(1,[args])=ContractE then print(`ContractE(G,e): Given a graph G=[V,E] and an edge e `): print(` contracts it. For example, try: `): print(` ContractE([{1,2},{{1,2}}],{1,2}); `): elif nops([args])=1 and op(1,[args])=CP then print(` CP(G,c): The chromatic polynomial of the graph `): print(` G=[V,E]. For example, try: CP([{1,2,3},{{1,2},{1,3},{2,3}}],c); `): elif nops([args])=1 and op(1,[args])=DeleteE then print(`DeleteE(G,e): Given a graph G=[V,E] and an edge e `): print(` deletes it. For example, try: `): print(` DeleteE([{1,2},{{1,2}}],{1,2}); `): elif nops([args])=1 and op(1,[args])=ExtendColoring then print(` ExtendColoring(v,N): Given `): print(` a canonical coloring v of V and a set of indices N, finds the set `): print(` of extensions of v if a new vertex is added `): print(` that is adjacent to the set of vertices indexed by N .`); print(` For example, try: `): print(` ExtendColoring([1,2],{1}); `): elif nops([args])=1 and op(1,[args])=GFG then print(` GFG(G,c,t): Inputs a graph G, a symbol t,`): print(`and a symbol (or positive) integer c, outputs`): print(` the rational function in t (and c if it symbolic) such that `): print(` the coeff. of t^n in its Maclaurin expansion is the `): print(` number of ways of coloring the graph Gx[1,n] `): print(`with c colors, but not necesserily using all of them`): print(` For example, try: `): print(` GFG(PathGraph(3),c,t); `): elif nops([args])=1 and op(1,[args])=GFGG then print(`GFGG(G,m,C,c,t): Inputs a graph G, on the set of vertices `): print(`{1,...m}, given as a set of edges, and a connection graph`): print(`C, a subset of [1,m]x[1,m], and symbols c and t`): print(`and outputs`): print(`the rational function in t and c such that `): print(`the coeff. of t^n in its Maclaurin expansion is the`): print(`number of ways of c-coloring the Ladder Graph of`): print(`G repeated n times with connections C`): print(`For example, try:`): print(`GFGG({{1,2},{2,3}},3,{[1,1],[2,2],[3,3]},c,t);`): elif nops([args])=1 and op(1,[args])=GFGE then print(` GFGE(G,c,t): Inputs a graph G, a symbol t,`): print(`and a positive integer c, outputs`): print(` the rational function in t such that `): print(` the coeff. of t^n in its Maclaurin expansion is the `): print(` number of ways of coloring the graph Gx[1,n] `): print(`with c colors, using each color at least once.`): print(` For example, try: `): print(` GFGE(PathGraph(3),3,t); `): elif nops([args])=1 and op(1,[args])=GFk then print(` GFk(k,c,t): Inputs a positive integer, a symbol t,`): print(`and a symbol (or positive) integer c, outputs`): print(` the rational function in t (and c if it symbolic) such that `): print(` the coeff. of t^n in its Maclaurin expansion is the `): print(` number of ways of coloring the grid graph [1,k]x[1,n] `): print(`with c colors, but not necesserily using all of them`): print(` For example, try: `): print(` GFk(2,c,t); `): elif nops([args])=1 and op(1,[args])=GFkE then print(` GFkE(k,c,t): Inputs a positive integer k, a symbol t,`): print(`and a positive integer c, outputs`): print(` the rational function, in t, such that `): print(` the coeff. of t^n in its Maclaurin expansion is the `): print(` number of ways of coloring the grid graph [1,k]x[1,n] `): print(`with c colors, where every color is used at least once`): print(` For example, try: `): print(` GFkE(2,3,t); `): elif nops([args])=1 and op(1,[args])=LadderG then print(`LadderG(G,C,k): Given a graph G, on the set of vertices`): print(`{1,...m}, expressed as a set of edges`): print(`and a subset of GxG (the connections)`): print(`constructs the ladder-graph with k copies of G.`): print(`For example try:`): print(`LadderG({{1,2},{1,3},{2,3}},{[1,1],[2,2],[3,3]},3,5);`): elif nops([args])=1 and op(1,[args])=LegalColorings then print(`LegalColorings(k,n,c): all the legal colorings of a k by n grid graph`): print(`for example, try: `): print(`LegalColorings(2,2,3);`): elif nops([args])=1 and op(1,[args])=LegalRows then print(` (k,c): the set of vectors of size k with entries `): print(` in [1,c] where no two adjacent entries can be the same `): print(` For example, try: `): print(` LegalRows(3,2);` ): elif nops([args])=1 and op(1,[args])=LegalVectors then print(`LegalVectors(L): given a list of sets of non-negative integers`): print(`returns all the ways of choosing one element from each set`): print(`where all non-zero components are different. For example, try:`): print(`LegalVectors([{0,1,3},{0,1,2}]);`): elif nops([args])=1 and op(1,[args])=LoopGraph then print(`LoopGraph(k): the loop of length k in the format of a graph [V,E].`): print(`For example, try:`): print(` LoopGraph(3); `): elif nops([args])=1 and op(1,[args])=SipurGFRect then print(`SipurGFRect(K,c,t): inputs a positive integer K,`): print(`a symbol (or pos. integer) c, and a variable t, and `): print(`outputs all the generating functions (in nice and ugly format)`): print(`(that happen to be rational functions of t)`): print(`whose coeff. of t^n (in its MacLaurin expansion) yields`): print(`the chromatic polynomial of teh grid graph [1,k]x[1,n] for`): print(`numeric k between 1 and K. For example, try:`): print(`SipurGFRect(3,c,t);`): elif nops([args])=1 and op(1,[args])=SipurGFCyl then print(`SipurGFCyl(K,c,t): inputs a positive integer K, `): print(`a symbol (or pos. integer) c, and a variable t, and `): print(`outputs all the generating functions (in nice and ugly format)`): print(`(that happen to be rational functions of t)`): print(`whose coeff. of t^n (in its MacLaurin expansion) yields`): print(`the chromatic polynomial of [1,k]x[1,n] discrete cylinder for`): print(`numeric k between 1 and K. For example, try:`): print(`SipurGFCyl(3,c,t);`): elif nops([args])=1 and op(1,[args])=SipurSeqCyl then print(`SipurSeqCyl(K,c,N,C): inputs positive integers K, N, and C and`): print(`and a symbol c; `): print(`outputs all the sequences of length N, in computerize,`): print(`whose n-th term is the`): print(`the chromatic polynomial of [1,k]x[1,n] discrete cylinder for`): print(`numeric k between 1 and K. `): print(`It also spells out the numeric sequences for c between 2 and C`): print(`For example, try:`): print(`SipurSeqCyl(3,c,20,5);`): elif nops([args])=1 and op(1,[args])=SipurSeqRect then print(`SipurSeqRect(K,c,N,C): inputs positive integer K, N, C and`): print(`a symbol c, `): print(`outputs all the sequences of length N, in computerize,`): print(`whose n-th term is `): print(`the chromatic polynomial of the grid graph [1,k]x[1,n] for`): print(`numeric k between 1 and K. `): print(`It also spells out the numeric sequences for c between 2 and C`): print(`For example, try:`): print(`SipurSeqRect(3,c,20,5);`): elif nops([args])=1 and op(1,[args])=SquareSeq then print(`SquareSeq(K,c): Inputs a pos. integer K and variable c`): print(`and outputs the sequence whose n-th term is the`): print(`chromatic polynomial of an a by n square in the variable c`): print(`For example, try:`): print(`SquareSeq(4,c);`): elif nops([args])=1 and op(1,[args])=SquareSeqStory then print(`SquareSeqStory(K,c,C): Inputs a pos. integer K and variable c`): print(`and tells you the chromatic polynomials of the n by n grid-graph`): print(`for n from 1 to K, and spells out the number of colorings`): print(`for the number of colors (c) ranging from 2 to C`); print(`SquareSeqStory(5,c,5);`): elif nops([args])=1 and op(1,[args])=TMk then print(` TMk(k,c): Inputs a positive integer, `): print(`and a symbol (or positive integer) c, outputs`): print(` the transfer matrix written as a list of lists `): print(`and the initial vectors. The nubmber of ways of`): print(`coloring a k by n grid graph with c colors equals`): print(`[1, 1 , ... 1]M^n V0 `); print(` For example, try: `): print(` TMk(2,c); `): elif nops([args])=1 and op(1,[args])=TMG then print(` TMG(k,c): Inputs a graph G, `): print(`and a symbol (or positive integer) c, outputs`): print(` the transfer matrix written as a list of lists `): print(`and the initial vectors. The nubmber of ways of`): print(`coloring the graph Gx[1,n] with c colors equals`): print(`[1, 1 , ... 1]M^n V0 `); print(` For example, try: `): print(` TMG(PathGraph(3),c); `): elif nops([args])=1 and op(1,[args])=Options then print(`Options(S1,S2): the non-Options for state S2 coming right`): print(` after state S1`): print(` For example, try:`): print(`Options([1,2],[1,2]);`): elif nops([args])=1 and op(1,[args])=OptionsG then print(`OptionsG(S1,S2,C): the non-Options `): print(`for state S2 coming right after state S1 with connection set C`): print(`For example, try:`): print(`OptionsG([1,2],[1,2],{[1,1],[2,2]});`): elif nops([args])=1 and op(1,[args])=PathGraph then print(`PathGraph(k): the path of length k in the format of a graph [V,E].`): print(`For example, try:`): print(` PathGraph(3); `): elif nops([args])=1 and op(1,[args])=SeqGn then print(`SeqGn(G,c,N): Inputs a graph G and a symbol (or integer) c`): print(`and outputs the list of length N whose i-th component is`): print(`the number of ways of c-coloring the graph Gx[1,n]. For example,`): print(`try SeqGn(PathGraph(3),c,10);`): elif nops([args])=1 and op(1,[args])=SeqGnSlow then print(`SeqGnSlow(G,c,N): like SeqGn(G,c,N) but slower. Only for`): print(`checking purporses`): print(`try SeqGnSlow(PathGraph(3),c,10);`): elif nops([args])=1 and op(1,[args])=Seqkn then print(`Seqkn(k,c,N): Inputs a pos. integer k and a symbol (or integer c)`): print(`and outputs the list of length N whose i-th component is`): print(`the number of ways of c-coloring the k by n grid graph. For example,`): print(`try Seqkn(3,c,10);`): elif nops([args])=1 and op(1,[args])=SeqknSlow then print(`SeqknSlow(k,c,N): like Seqkn(k,c,N) but slower. Only for`): print(`checking purporses`): print(`try SeqknSlow(3,c,10);`): elif nops([args])=1 and op(1,[args])=SP then print(`SP(n): all the set partitions of {1, ,n} written as a list`): print(`ordered according to the smallest element. For example, try:`): print(`SP(5);`): elif nops([args])=1 and op(1,[args])=SPg then print(`SPg(n,g): all the set partitions of {1, ,n} written as a list`): print(`where two members of the same block must have`): print(` difference at least g,`): print(`ordered according to the smallest element. For example, try:`): print(`SPg(5,1);`): elif nops([args])=1 and op(1,[args])=SPtoSt then print(`SPtoSt(L,k): converts a good set partition of `): print(` {1, ..., k} to a legal state `): print(` For example, try: `): print(` SPtoSt([[1],[2]],2); `): elif nops([args])=1 and op(1,[args])=States then print(`States(k): all the states for the coloring of a k by n strip`): print(`with numeric k. For example, try:`): print(`States(3);`): elif nops([args])=1 and op(1,[args])=TS1S2 then print(`TS1S2(S1,S2,c): the number of ways state S2 can follow state S1`): print(`when there are c colors. For example, try:`); print(`TS1S2([1,2],[1,2],c);`): elif nops([args])=1 and op(1,[args])=TS1S2G then print(`TS1S2G(S1,S2,C,c): the number of ways state S2 can follow state S1`): print(`when there are c colors. For example, try:`): print(`TS1S2G([1,2],[1,2],{[1,1],[2,2]},c);`): else print(`There is no ezra for`,args): fi: end: #LegalRows(k,c): the set of vectors of size k with entries #in [1,c] where no two adjacent entries can be the same #For example, try: #LegalRows(3,2); LegalRows:=proc(k,c) local i,mu,gu,mu1: option remember: if k=0 then RETURN({[]}): fi: if k=1 then RETURN({seq([i],i=1..c)}): fi: mu:=LegalRows(k-1,c): gu:={}: for mu1 in mu do for i from 1 to c do if mu1[k-1]<>i then gu:=gu union {[op(mu1),i]}: fi: od: od: gu: end: #LegalColorings(k,n,c): all the legal colorings of a k by n rectangle #for example, try: #LegalColorings(2,2,3); LegalColorings:=proc(k,n,c) local gu,mu,lu,lu1,mu1,i1: option remember: if n=0 then RETURN({[]}): fi: mu:=LegalRows(k,c): if n=1 then RETURN({seq([mu1],mu1 in mu)}): fi: lu:=LegalColorings(k,n-1,c): gu:={}: for lu1 in lu do for mu1 in mu do if {seq(evalb(lu1[n-1][i1]<>mu1[i1]),i1=1..k)}={true} then gu:=gu union {[op(lu1),mu1]}: fi: od: od: gu: end: #SP(n): all the set partitions of {1, ,n} written as a list #ordered according to the smallest element. For example, try: #SP(5); SP:=proc(n) local gu,mu,mu1,i: option remember: if n=0 then RETURN({}): fi: if n=1 then RETURN({[[1]]}): fi: mu:=SP(n-1): gu:={}: for mu1 in mu do for i from 1 to nops(mu1) do gu:=gu union {[op(1..i-1,mu1),[op(mu1[i]),n],op(i+1..nops(mu1),mu1)]}: od: gu:=gu union {[op(mu1),[n]]}: od: gu: end: #SPg(n,g): all the set partitions of {1, ,n} where each block #can't have members <=g apart #written as a list #ordered according to the smallest element. For example, try: #SPg(5,1); SPg:=proc(n,g) local gu,mu,mu1,i: option remember: if n=0 then RETURN({}): fi: if n=1 then RETURN({[[1]]}): fi: mu:=SPg(n-1,g): gu:={}: for mu1 in mu do for i from 1 to nops(mu1) do if n-mu1[i][nops(mu1[i])]>g then gu:=gu union {[op(1..i-1,mu1),[op(mu1[i]),n],op(i+1..nops(mu1),mu1)]}: fi: od: gu:=gu union {[op(mu1),[n]]}: od: gu: end: #SPtoSt(L,k): converts a good set partition of {1, ..., k} to a legal state #For example, try #SPtoSt([[1],[2]],2); SPtoSt:=proc(L,k) local T,i,j: for i from 1 to nops(L) do for j in L[i] do T[j]:=i: od: od: [seq(T[j],j=1..k)]: end: #States(k): all the states for the coloring of a k by n strip #with numeric k. For example, try: #States(3); States:=proc(k) local gu,gu1: gu:=SPg(k,1): {seq(SPtoSt(gu1,k), gu1 in gu)}: end: #Options(S1,S2): the non-Options for state S2 coming right after state S1 #For example, try: #Options([1,2],[1,2]); Options:=proc(S1,S2) local k,lu,T,lu1,i,mu: k:=nops(S1): if nops(S2)<>k then RETURN(FAIL): fi: lu:=convert(S2,set): for lu1 in lu do T[lu1]:={}: od: for i from 1 to nops(S2) do T[S2[i]]:=T[S2[i]] union {S1[i]}: od: mu:=convert(S1,set): [seq(mu minus T[i] union {0},i=1..nops(lu))]: end: #LegalVectors(L): given a list of sets of non-negative integers #returns all the ways of choosing one element from each set #where all non-zero components are different. For example, try: #LegalVectors([{0,1,3},{0,1,2}]); LegalVectors:=proc(L) local gu,i,L1,mu,mu1,lu,lu1: if L=[] then RETURN({[]}): fi: if nops(L)=1 then RETURN({seq([L[1][i]],i=1..nops(L[1]))}): fi: L1:=[op(1..nops(L)-1,L)]: mu:=LegalVectors(L1): lu:=L[nops(L)]: gu:={}: for mu1 in mu do for lu1 in lu do if lu1=0 or (lu1<>0 and not member(lu1,mu1)) then gu:=gu union {[op(mu1),lu1]}: fi: od: od: gu: end: #NuZ(L): the number of 0's in the list K NuZ:=proc(L) local i,co: co:=0: for i from 1 to nops(L) do if L[i]=0 then co:=co+1: fi: od: co: end: fp:=proc(x,k) local i: expand(mul(x-i,i=0..k-1)):end: #TS1S2(S1,S2,c): the number of ways state S2 can follow state S1 #when there are c colors. For example, try: #TS1S2([1,2],[1,2],c); TS1S2:=proc(S1,S2,c) local k,mu,mu1: k:=nops(convert(S1,set)): mu:=LegalVectors(Options(S1,S2)): expand(add(fp(c-k,NuZ(mu1)),mu1 in mu)): end: #GFk(k,c,t): Inputs a positive integer, and symbols c and t #and outputs #the rational function in t and c such that #the coeff. of t^n in its Maclaurin expansion is the #number of ways of c-coloring the rectangle graph [1,k]x[1,n] #For example, try: #GFk(2,c,t); GFk:=proc(k,c,t) local eq,var,x,gu,gu1,eq1,gu2,lu,lu1,lu2: gu:=States(k): eq:={}: var:={}: for gu1 in gu do var:=var union {x[gu1]}: eq1:=x[gu1]-t*fp(c,nops(convert(gu1,set))): for gu2 in gu do eq1:=eq1 -t*TS1S2(gu2,gu1,c)*x[gu2]: od: eq:=eq union {eq1}: od: var:=solve(eq,var): lu:=normal(add(subs(var,x[gu1]),gu1 in gu)): lu1:=numer(lu): lu2:=denom(lu): lu1:=add(factor(coeff(lu1,t,i))*t^i,i=0..degree(lu1,t)): lu2:=add(factor(coeff(lu2,t,i))*t^i,i=0..degree(lu2,t)): lu1/lu2: end: #CheckGFkS(k,N,C): checks GFk(k,c,t) for c=2..C and n=1..N #completey naively, by actually constructing the set of c-colorings #for numeric c #For example, try: CheckGFkS(3,8,3); CheckGFkS:=proc(k,N,C) local lu,n,c,c1,t: lu:=GFk(k,c,t): lu:=taylor(lu,t=0,N+1): for c1 from 2 to C do for n from 1 to N do if nops(LegalColorings(k,n,c1))<>subs(c=c1,coeff(lu,t,n)) then print(`When there are`, c1, `colors and the rectangle is`, k, ` by `, n): print(`the formula disagrees`): RETURN(FAIL): fi: od: od: true: end: #GFkE(k,c,t): Inputs positive integers k and c #the rational function in t and c such that #the coeff. of t^n in its Maclaurin expansion is the #number of ways of c-coloring the rectangle graph [1,k]x[1,n] #For example, try: #GFkE(2,3,t); GFkE:=proc(k,c,t) local i,lu,c1: if not type(c, integer) then RETURN(`The second argument, c, must be a pos. integer`): fi: lu:=GFk(k,c1,t): normal(add((-1)^i*binomial(c,i)*subs(c1=c-i,lu),i=0..c-1)): end: #ContractE(G,e): Given a graph G=[V,E] and an edge e #contracts it. For example, try: #ContractE([{1,2},{{1,2}}],{1,2}); ContractE:=proc(G,e) local V,E,i,j: V:=G[1]: E:=G[2]: if not member(e,E) then RETURN(FAIL): fi: i:=e[1]: j:=e[2]: E:=E minus {e}: E:=subs(j=i,E): V:=V minus {j}: [V,E]: end: #DeleteE(G,e): Given a graph G=[V,E] and an edge e #delets it. For example, try: #DeleteE([{1,2},{{1,2}}],{1,2}); DeleteE:=proc(G,e) local V,E: V:=G[1]: E:=G[2]: if not member(e,E) then RETURN(FAIL): fi: E:=E minus {e}: [V,E]: end: #CP(G,c): The chromatic polynomial of the graph #G=[V,E]. For example, try: CP([{1,2,3},{{1,2},{1,3},{2,3}}],c); CP:=proc(G,c) local e: option remember: if G[2]={} then c^nops(G[1]): else e:=G[2][1]: expand(CP(DeleteE(G,e,c),c)-CP(ContractE(G,e,c),c)): fi: end: #PathGraph(k): the path of length k in the format of a graph [V,E] #For example, try: #PathGraph(3); PathGraph:=proc(k) local i: [{seq(i,i=1..k)},{seq({i,i+1},i=1..k-1)}]: end: #LoopGraph(k): the loop of length k in the format of a graph [V,E] #For example, try: #LoopGraph(3); LoopGraph:=proc(k) local i: [{seq(i,i=1..k)},{seq({i,i+1},i=1..k-1),{1,k}}]: end: #CartProdGraphs(G1,G2): the Cartesian product of two graphs #G1=[V1,E1] and G2=[V2,E2]. For example, try: #CartProdGraphs(PathGraph(2), PathGraph(2)); CartProdGraphs:=proc(G1,G2) local V1,V2,E1,E2,V,E,v1,v2,e1,e2: V1:=G1[1]: E1:=G1[2]: V2:=G2[1]: E2:=G2[2]: V:={seq(seq([v1,v2],v2 in V2),v1 in V1)}: E:= {seq(seq({[v1,e2[1]],[v1,e2[2]]},e2 in E2),v1 in V1)} union {seq(seq({[e1[1],v2],[e1[2],v2]},e1 in E1),v2 in V2)}: [V,E]: end: #CheckGFkF(k,N): checks GFk(k,c,t) for n=1..N #For example, try: CheckGFkF(3,8); CheckGFkF:=proc(k,N) local c,n,t,lu: lu:=GFk(k,c,t): lu:=taylor(lu,t=0,N+1): evalb({true}= {seq( evalb( expand(coeff(lu,t,n))=CP(CartProdGraphs(PathGraph(k),PathGraph(n)),c) ), n=1..N)}): end: #TMk(k,c): Inputs a positive integer k and a symbol c #and outputs the transfer matrix and the initial vector #For example, try: #TMk(2,c); TMk:=proc(k,c) local V,M,i,j,M1,gu: option remember: gu:=States(k): V:=[seq(fp(c,nops(convert(gu[i],set))),i=1..nops(gu))]: M:=[]: for i from 1 to nops(gu) do M1:=[]: for j from 1 to nops(gu) do M1:=[op(M1),TS1S2(gu[j],gu[i],c)]: od: M:=[op(M),M1]: od: M,V: end: #Seqkn(k,c,N): Inputs a pos. integer k and a symbol (or integer c) #and outputs the list of length N whose i-th component is #the number of ways of c-coloring the k by n rectangle. For example, #try Seqkn(3,c,10); Seqkn:=proc(k,c,N) local gu,n,lu,V,M,i1,j1: lu:=TMk(k,c): V:=lu[2]: M:=lu[1]: gu:=[]: for n from 1 to N do gu:=[op(gu),convert(V,`+`)]: V:=[seq(expand(add(M[i1][j1]*V[j1],j1=1..nops(V))),i1=1..nops(M))]: od: gu: end: #ExtendColoring(v,N): Given a #a canonical coloring v of and a set of indices #(subset of {1, ..., nops(v)} #Finds the set #of extensions of v if a new vertex is added #that is adjacent to the set of vertices whose index is N #For example, try: #ExtendColoring([1,2],{1}); ExtendColoring:=proc(v,N) local c,i,n1,mu,mu1: c:=nops(convert(v,set)): if {seq(i,i=1..c)}<>convert(v,set) then RETURN(FAIL): fi: mu:={seq(i,i=1..c)} minus {seq(v[n1],n1 in N)}: {seq([op(v),mu1],mu1 in mu)} union {[op(v),c+1]}: end: #CC(G): all the canonical colorings of a graph G=[V,E] #For example, try: #CC(PathGraph(2)); CC:=proc(G) local V,E,N,V1,E1,n,ku,gu,i,v: V:=G[1]: E:=G[2]: if nops(V)=1 then RETURN({[1]}): fi: n:=nops(V): E1:=E: N:={}: for i from 1 to n-1 do if member({V[i],V[n]},E) then E1:=E1 minus {V[i],V[n]}: N:=N union {i}: fi: od: V1:=[op(1..n-1,V)]: ku:=CC([V1,E1]): gu:={}: for v in ku do gu:=gu union ExtendColoring(v,N): od: gu: end: #GFG(G,c,t): Inputs a graph G and symbols c and t #and outputs #the rational function in t and c such that #the coeff. of t^n in its Maclaurin expansion is the #number of ways of c-coloring the graph Gx[1,n] #For example, try: #GFG(PathGraph(3),c,t); GFG:=proc(G,c,t) local eq,var,x,gu,gu1,eq1,gu2,lu,lu1,lu2: gu:=CC(G): eq:={}: var:={}: for gu1 in gu do var:=var union {x[gu1]}: eq1:=x[gu1]-t*fp(c,nops(convert(gu1,set))): for gu2 in gu do eq1:=eq1 -t*TS1S2(gu2,gu1,c)*x[gu2]: od: eq:=eq union {eq1}: od: var:=solve(eq,var): lu:=normal(add(subs(var,x[gu1]),gu1 in gu)): lu1:=numer(lu): lu2:=denom(lu): lu1:=add(factor(coeff(lu1,t,i))*t^i,i=0..degree(lu1,t)): lu2:=add(factor(coeff(lu2,t,i))*t^i,i=0..degree(lu2,t)): lu1/lu2: end: #TMG(G,c): Inputs a graph G and a symbol c #and outputs the transfer matrix and the initial vector #For example, try: #TMG(PathGraph(3),c); TMG:=proc(G,c) local V,M,i,j,M1,gu: option remember: gu:=CC(G): V:=[seq(fp(c,nops(convert(gu[i],set))),i=1..nops(gu))]: M:=[]: for i from 1 to nops(gu) do M1:=[]: for j from 1 to nops(gu) do M1:=[op(M1),TS1S2(gu[j],gu[i],c)]: od: M:=[op(M),M1]: od: M,V: end: #SeqGn(G,c,N): Inputs a graph G and a symbol (or integer c) #and outputs the list of length N whose i-th component is #the number of ways of c-coloring the k by n rectangle. For example, #try SeqGn(G,c,10); SeqGn:=proc(G,c,N) local gu,n,lu,V,M,i1,j1: lu:=TMG(G,c): V:=lu[2]: M:=lu[1]: gu:=[]: for n from 1 to N do gu:=[op(gu),convert(V,`+`)]: V:=[seq(expand(add(M[i1][j1]*V[j1],j1=1..nops(V))),i1=1..nops(M))]: od: gu: end: #GFGE(G,c,t): Inputs a graph G and a symbol c #and outputs #the rational function in t and c such that #the coeff. of t^n in its Maclaurin expansion is the #number of ways of c-coloring the graph Gx[1,n] #For example, try: #GFGE(PathGraph(3),3,t); GFGE:=proc(G,c,t) local i,lu,c1: if not type(c, integer) then RETURN(`The second argument, c, must be a pos. integer`): fi: lu:=GFG(G,c1,t): normal(add((-1)^i*binomial(c,i)*subs(c1=c-i,lu),i=0..c-1)): end: #SeqknSlow(k,c,N): A slow version of #SeqknSlow(k,c,N) for checking purporses #Inputs a pos. integer k and a symbol (or integer c) #and outputs the list of length N whose i-th component is #the number of ways of c-coloring the k by n rectangle. For example, #try SeqknSlow(3,c,10); SeqknSlow:=proc(k,c,N) local lu,t,i: lu:=GFk(k,c,t): lu:=taylor(lu,t=0,N+1): expand([seq(coeff(lu,t,i),i=1..N)]): end: #SeqGnSlow(k,c,N): A slow version of #SeqGnSlow(k,c,N) for checking purporses #Inputs a pos. integer k and a symbol (or integer c) #and outputs the list of length N whose i-th component is #the number of ways of c-coloring the k by n rectangle. For example, #try SeqGnSlow(3,c,10); SeqGnSlow:=proc(G,c,N) local lu,t,i: lu:=GFG(G,c,t): lu:=taylor(lu,t=0,N+1): expand([seq(coeff(lu,t,i),i=1..N)]): end: #SipurGFRect(K,c,t): inputs a positive integer K and #outputs all the generating functions (in nice and ugly format) #(that happen to be rational functions of t) #whose coeff. of t^n (in its MacLaurin expansion) yields #the chromatic polynomials of [1,k]x[1,n] rectangles for #numeric k between 1 and K. For example, try: #SipurGFRect(3,c,t); SipurGFRect:=proc(K,c,t) local k,lu,n,t0: t0:=time(): print(`The Generating Function for the Chromatic Polynomials`): print(`of Grid Graphs with fixed Width`): print(`By Shalosh B. Ekhad`): print(`This is the story for the generating functions, in n, `): print(`using the variable`, t): print(`for the chromatic polynomials of a k by n rectangle`): print(`for k between 1 and `, K): for k from 1 to K do print(`-------------------------------------------------`): lu:=GFk(k,c,t): print(`The rational function whose coefficient of`, t^n, ` in `): print(`its Maclaurin expansion tells you the number of ways of`): print(`coloring an n by`, k, `rectangle with`, c, `colors is :`): print(lu): print(`And in Maple input format:`): lprint(lu): od: print(`The whole thing took`, time()-t0, `seconds. `): end: #SipurGFCyl(K,c,t): inputs a positive integer K and #outputs all the generating functions (in nice and ugly format) #(that happen to be rational functions of t) #whose coeff. of t^n (in its MacLaurin expansion) yields #the chromatic polynomials of [1,k]x[1,n] cylinder for #numeric k between 1 and K. For example, try: #SipurGFCyl(3,c,t); SipurGFCyl:=proc(K,c,t) local k,lu,n,t0: t0:=time(): print(`The Generating Function for the Chromatic Polynomials`): print(`of Cylinders with fixed Width`): print(`By Shalosh B. Ekhad`): print(`This is the story for the generating functions, in n, `): print(`using the variable`, t): print(`for the chromatic polynomials of a k by n disrete cylinder`): print(`for k between 1 and `, K): for k from 1 to K do print(`-------------------------------------------------`): lu:=GFG(LoopGraph(k),c,t): print(`The rational function whose coefficient of`, t^n, ` in `): print(`its Maclaurin expansion tells you the number of ways of`): print(`coloring an n by`, k, ` discrete cylinder with`, c, `colors is :`): print(lu): print(`And in Maple input format:`): lprint(lu): od: print(`The whole thing took`, time()-t0, `seconds.`): end: #SipurSeqRect(K,c,N,C): inputs a positive integer K and #outputs all the sequences of length N (in nice and ugly format) #whose n-th term is the #the chromatic polynomials of [1,k]x[1,n] rectangles for #numeric k between 1 and K. #It also spells out the numeric sequences for c between 2 and C #For example, try: #SipurSeqRect(3,c,30,5); SipurSeqRect:=proc(K,c,N,C) local k,lu,t0,c1: t0:=time(): print(`The Number of Ways to Color a Grid Graph`): print(`By Shalosh B. Ekhad`): print(`This is the story `): print(`for the chromatic polynomials of a k by n grid graph`): print(`for n between 1 and `, N): print(`and for k between 1 and `, K): for k from 1 to K do lu:=Seqkn(k,c,N): print(`-------------------------------------------------`): print(`The first`, N , `terms of the sequence `): print(`enumerating the number of ways of`): print(`coloring an n by`, k, `rectangle with`, c, `colors is :`): lprint(lu): print(`This implies the following.`): for c1 from 2 to C do print(`The number of ways of coloring a`, k, `by n rectangle`): print(`with `, c1 , `colors, for n between 1 and`, N , `are given by:`): print(subs(c=c1,lu)): od: od: print(`The whole thing took`, time()-t0, `seconds. `): end: #SipurSeqCyl(K,c,N,C): inputs a positive integer K and #outputs all the sequences of length N (in nice and ugly format) #whose n-th term is the #the chromatic polynomials of [1,k]x[1,n] discrete cylinder for #numeric k between 1 and K. #It also spells out the numeric sequences for c between 2 and C #For example, try: #SipurSeqCyl(3,c,30,5); SipurSeqCyl:=proc(K,c,N,C) local k,lu,t0,c1: t0:=time(): print(`The Number of Ways to Color a (discrete) Cylinder`): print(`By Shalosh B. Ekhad`): print(``): print(`This is the story `): print(`for the chromatic polynomials of a k by n discrete cylinder`): print(`for n between 1 and `, N): print(`and for k between 1 and `, K): for k from 1 to K do lu:=SeqGn(LoopGraph(k),c,N): print(`-------------------------------------------------`): print(`The first`, N, `terms of the sequence that tells you`): print(`the number of ways of`): print(`coloring an n by`, k, `discrete cylinder with`, c, `colors is :`): lprint(lu): print(`This implies the following.`): for c1 from 2 to C do print(`The number of ways of coloring a`, k, `by n cylinder`): print(`with `, c1 , `colors, for n between 1 and`, N , `are given by:`): print(subs(c=c1,lu)): od: od: print(`The whole thing took`, time()-t0, `seconds. `): end: #SquareSeq(K,c): Inputs a pos. integer K and variable c #and outputs the sequence whose n-th term is the #chromatic polynomial of an a by n square in the variable c #For example, try: #SquareSeq(4,c); SquareSeq:=proc(K,c) local k: [seq(Seqkn(k,c,k)[k],k=1..K)]: end: #SquareSeqStory(K,c,C): Inputs a pos. integer K and variable c #and tells you the chromatic polynomials of the n by n grid-graph #for n from 1 to K, and spells out the number of colorings #for the number of colors (c) ranging from 2 to C #SquareSeqStory(5,c,5); SquareSeqStory:=proc(K,c,C) local gu,c1,k: print(`The Number of Ways to Color a square Grid Graph`): print(`By Shalosh B. Ekhad`): gu:=SquareSeq(K,c): for k from 1 to K do print(``): print(`The number of ways of coloring the `, k, `by `, k, `grid graph `): print(`with `, c, `colors , is given by the polynomial`): lprint(gu[k]): od: print(`------------------------------------------------------------`): for c1 from 1 to C do print(`The first`, K, `terms of `): print(`the sequence enumerating the number of ways of legally coloring`): print(`the n by n grid graph for n from 1 to `,K,`with `, c1, ` colors is:`): print(subs(c=c1,gu)): od: end: #LadderG(G,C,k): Given a graph G, on the set of vertices #{1,...m}, expressed as a set of edges #and a subset of GxG (the connections) #constructs the ladder-graph with k copies of G. #For example try: #LadderG({{1,2},{1,3},{2,3}},{[1,1],[2,2],[3,3]},3,5); LadderG:=proc(G,C,m,k) local V,E,i,i1,c: V:={seq(i,i=1..m*k)}: E:={}: for i from 1 to k do E:=E union subs({seq(i1=i1+m*(i-1),i1=1..m)},G): od: for i from 1 to k-1 do E:=E union {seq({subs({seq(i1=i1+m*(i-1),i1=1..m)},c[1]), subs({seq(i1=i1+m*i,i1=1..m)},c[2])},c in C)}: od: [V,E]: end: #GFGG(G,m,C,c,t): Inputs a graph G, on the set of vertices #{1,...m}, given as a set of edges, and a connection graph #C, a subset of [1,m]x[1,m], and symbols c and t #and outputs #the rational function in t and c such that #the coeff. of t^n in its Maclaurin expansion is the #number of ways of c-coloring the Ladder Graph of #G repeated n times with connections C #For example, try: #GFGG({{1,2},{2,3}},3,{[1,1],[2,2],[3,3]},c,t); GFGG:=proc(G,m,C,c,t) local eq,var,x,gu,gu1,eq1,gu2,lu,lu1,lu2,i: gu:=CC([{seq(i,i=1..m)},G]): eq:={}: var:={}: for gu1 in gu do var:=var union {x[gu1]}: eq1:=x[gu1]-t*fp(c,nops(convert(gu1,set))): for gu2 in gu do eq1:=eq1 -t*TS1S2G(gu2,gu1,C,c)*x[gu2]: od: eq:=eq union {eq1}: od: var:=solve(eq,var): lu:=normal(add(subs(var,x[gu1]),gu1 in gu)): lu1:=numer(lu): lu2:=denom(lu): lu1:=add(factor(coeff(lu1,t,i))*t^i,i=0..degree(lu1,t)): lu2:=add(factor(coeff(lu2,t,i))*t^i,i=0..degree(lu2,t)): lu1/lu2: end: #TS1S2G(S1,S2,C,c): the number of ways state S2 can follow state S1 #when there are c colors. For example, try: #TS1S2G([1,2],[1,2],{[1,1],[2,2]},c); TS1S2G:=proc(S1,S2,C,c) local k,mu,mu1: k:=nops(convert(S1,set)): mu:=LegalVectors(OptionsG(S1,S2,C)): expand(add(fp(c-k,NuZ(mu1)),mu1 in mu)): end: #OptionsG(S1,S2,C): the non-Options for state S2 coming right after state S1 #For example, try: #OptionsG([1,2],[1,2],2,{[1,1],[2,2]}); OptionsG:=proc(S1,S2,C) local k,lu,T,lu1,i,mu,c: k:=nops(S1): if nops(S2)<>k then RETURN(FAIL): fi: lu:=convert(S2,set): for lu1 in lu do T[lu1]:={}: od: for c in C do T[S2[c[2]]]:=T[S2[c[2]]] union {S1[c[1]]}: od: mu:=convert(S1,set): [seq(mu minus T[i] union {0},i=1..nops(lu))]: end: #CheckGFGG(G,m,C,N): checks GFGG(G,m,c,t) for n=1..N #For example, try: CheckGFGG({{1,2}},2,{[1,1],[2,2]},4); CheckGFGG:=proc(G,m,C,N) local c,n,t,lu: lu:=GFGG(G,m,C,c,t): lu:=taylor(lu,t=0,N+1): evalb({true}= {seq( evalb( expand(coeff(lu,t,n))=CP(LadderG(G,C,m,n),c) ), n=1..N)}): end: