###################################################################### ##TRIANGULATIONS: Save this file as TRIANGULATIONS # ## To use it, stay in the # ##same directory, get into Maple (by typing: maple ) # ##and then type: read TRIANGULATIONS # ##Then follow the instructions given there # ## # ##Written by Doron Zeilberger, Rutgers University , # #zeilberg at math dot rutgers dot edu # ###################################################################### #Created: Dec. 2013 print(`Created: Dec. 18, 2013`): print(` This is TRIANGULATIONS `): print(`written by Alon Regev and Doron Zeilberger `): print(`may lead to a joint paper`): print(`by Shalosh B. Ekhad, Alon Regev, 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(`For a list of the procedures type ezra();, for help with`): print(`a specific procedure, type ezra(procedure_name); .`): print(``): with(combinat): ezra1:=proc() if args=NULL then print(` The supporting procedures are: PlotDP `): print(``): else ezra(args): fi: end: ezra:=proc() if args=NULL then print(`The main procedures are: DP, Ears, EarsDP, HTset, HTsetN, NPT, Tn, TnE, TtoD `): print(` `): elif nops([args])=1 and op(1,[args])=DP then print(`DP(n): the set of Dyck paths of length 2n`): elif nops([args])=1 and op(1,[args])=Ears then print(`Ears(T1) : set of ears of T1`): elif nops([args])=1 and op(1,[args])=EarsDP then print(`EarsDP(n) : the images under TtoD of the triangulations with various ears `): elif nops([args])=1 and op(1,[args])=HTset then print(`HTset(n): The list of length n-3 whose (i+1)-ith entry`): print(`is the set of pairs of triangulations of an n-gon`): print(`that share i diagonals.`): print(`Try: HTset(5);`): elif nops([args])=1 and op(1,[args])=HTsetN then print(`HTsetN(n): The list of length n-3 whose (i+1)-ith entry`): print(`is the number of pairs of triangulations of an n-gon`): print(`that share i diagonals. `): print(`Try: HTsetN(5);`): elif nops([args])=1 and op(1,[args])=NPT then print(`NPT(n): the set of triangulations of an n-gon without parallel diagonals`): elif nops([args])=1 and op(1,[args])=PlotDP then print(`PlotDP(L): plots a Dyck path `): elif nops([args])=1 and op(1,[args])=TtoD then print(`TtoD(T,n): inputs a triangulation of an n-gon and outputs a Dyck path`): elif nops([args])=1 and op(1,[args])=Tn then print(`Tn(n): the set of triangulations of a convect n-gon, try: Tn(6);`): print(``): elif nops([args])=1 and op(1,[args])=TnE then print(`TnE(n): the list whose i-th item is the set of triangulations of an n-gon with i ears`): print(`try: TnE(6);`): else print(`There is no ezra for`,args): fi: end: #Tn(n): the set of triangulations of a convect n-gon, try: Tn(6); Tn:=proc(n) local k,gu,gu1,gu2,gu11,gu21,i: option remember: if n<1 then RETURN(FAIL): fi: if n=2 or n=3 then RETURN({{}}): fi: gu:={}: for k from 3 to n do gu1:=Tn(k-1): gu1:=subs({seq(i=i+1,i=1..k-1)},gu1): gu2:=Tn(n-k+2): gu2:=subs({seq(i=i+k-1,i=1..n-k+1),n-k+2=1},gu2): if k=3 then gu:=gu union {seq(seq(gu11 union gu21 union {{1,3}},gu11 in gu1),gu21 in gu2)}: elif k=n then gu:=gu union {seq(seq(gu11 union gu21 union {{2,n}},gu11 in gu1),gu21 in gu2)}: else gu:=gu union {seq(seq(gu11 union gu21 union {{1,k},{2,k}},gu11 in gu1),gu21 in gu2)}: fi: od: gu: end: #Ears(T1) : set of ears of T1 Ears:=proc(T1) local n,i: n:=nops(T1)+3: {seq(i,i=1..n)} minus {seq(op(T1[i]),i=1..nops(T1))}: end: #TnE(n): the list whose i-th item is the set of triangulations of an n-gon with i ears #try: TnE(6); TnE:=proc(n) local mu,mu1,T,i: option remember: mu:=Tn(n): for i from 1 to trunc(n/2) do T[i]:={}: od: for mu1 in mu do T[nops(Ears(mu1))]:= T[nops(Ears(mu1))] union {mu1}: od: [seq(T[i],i=1..trunc(n/2))]: end: #DP(n): the set of Dyck paths of length 2n DP:=proc(n) local m,gu,gu1,gu2,gu11,gu21: option remember: if n=0 then RETURN({[]}): fi: gu:={}: for m from 0 to n-1 do gu1:=DP(m): gu2:=DP(n-1-m): gu:=gu union {seq(seq([1,op(gu11),-1,op(gu21)],gu11 in gu1),gu21 in gu2)}: od: gu: end: #TtoD(T,n): inputs a triangulation of an n-gon T and outputs a Dyck path TtoD:=proc(T,n) local k,N1,N2,t,N,T1,T2,gu1,gu2,i: if n=2 then if T<>{} then RETURN(FAIL): else RETURN([]): fi: fi: if n=3 then if T<>{} then RETURN(FAIL): else RETURN([1,-1]): fi: fi: if member({1,3},T) then k:=3: elif member({2,n},T) then k:=n: else N1:={}: N2:={}: for t in T do if member(1,t) then N1:=N1 union {(t minus {1})[1]}: fi: if member(2,t) then N2:=N2 union {(t minus {2})[1]}: fi: od: N:=N1 intersect N2: if nops(N)<>1 then RETURN(FAIL): fi: k:=N[1]: fi: if k=3 then T1:={}: T2:=T minus {{1,3}}: T2:=subs({seq(i=i-1,i=3..n)},T2): elif k=n then T2:={}: T1:=T minus {{2,n}}: T1:=subs({seq(i=i-1,i=2..n)},T1): else T1:={}: T2:={}: for t in T do if t minus {seq(i,i=2..k)}={} then T1:=T1 union {t}: else T2:=T2 union {t}: fi: od: T1:=T1 minus {{2,k}}: T2:=T2 minus {{1,k}}: T1:=subs({seq(i=i-1,i=2..k)},T1): T2:=subs({seq(i=i-(k-2),i=k..n)},T2): fi: #RETURN(T1,T2): #print(` n is`, n): #print(` k is`,k): #print(`T1 is`, T1): #print(`T2 is`, T2): gu1:=TtoD(T1,k-1): gu2:=TtoD(T2,n-k+2): #print(`gu1 is`, gu1): #print(`gu2 is`, gu2): [1,op(gu1),-1,op(gu2)]: end: #TtoDS(S,n): the images under TtoD of the various triangulations with 2,3,...ears TtoDS:=proc(S,n) local T: {seq(TtoD(T,n),T in S)}: end: #EarsDP(n) EarsDP:=proc(n) local gu,i: gu:=TnE(n): [seq(TtoDS(gu[i],n),i=1..nops(gu))]: end: #IsPara(T,n): does T has a pair of parallel edges? IsPara:=proc(T,n) local i,j,t,s: for i from 1 to nops(T) do t:=T[i]: for j from i+1 to nops(T) do s:=T[j]: if t[1]+t[2]-s[1]-s[2] mod n =0 then RETURN(true): fi: od: od: false: end: #NPT(n): the set of triangulations of an n-gon without parallel diagonals NPT:=proc(n) local mu,gu,mu1: mu:=Tn(n): gu:={}: for mu1 in mu do if not IsPara(mu1,n) then gu:=gu union {mu1}: fi: od: gu: end: with(plots): #PlotDP(L), plots the Dyck path L PlotDP:=proc(L) local i: plot([seq([[i,convert([op(1..i,L)],`+`)],[i+1,convert([op(1..i+1,L)],`+`)]],i=0..nops(L)-1)]): end: #HTset(n): The list of length n-3 whose (i+1)-ith entry #is the set of pairs of triamgulations of an n-gon #that share i diagonals. It also returns the counts #Try: HTset(5); HTset:=proc(n) local k,T,i,j,mu: option remember: mu:=Tn(n): for k from 0 to n-3 do T[k]:={}: od: for i from 1 to nops(mu) do for j from i+1 to nops(mu) do k:=nops(mu[i] intersect mu[j]): T[k]:= T[k] union {{mu[i],mu[j]}}: od: od: [seq(T[k],k=0..n-3)]: end: #HTsetN(n): The list of length n-3 whose (i+1)-ith entry #is the number of pairs of triamgulations of an n-gon #that share i diagonals. It also returns the counts #Try: HTsetN(5); HTsetN:=proc(n) local gu,k: option remember: gu:=HTset(n): [seq(nops(gu[k]),k=1..nops(gu))]: end: