########################################################################## ## Examples: Save this file as Examples to use it, # ## stay in the same directory, get into Maple # ## (by typing: maple ) # ## and then type: read Examples: # ## Then follow the instructions given there # ## # ## Written by Philip Matchett Wood, Rutgers University , # ## matchett@math.rutgers.edu. # ########################################################################## ##-------------------------------------------------------------------------## # Loading BijTools # print(`######################################################################`): print(`##-------LOADING BijTools-------------------------------------------##`): read `BijTools`: print(`##----FINISHED LOADING BijTools-------------------------------------##`): print(`######################################################################`): ##-------------------------------------------------------------------------## # Loading Fibonacci # print(`######################################################################`): print(`##-------LOADING Fibonacci------------------------------------------##`): read `Fibonacci`: print(`##----FINISHED LOADING Fibonacci------------------------------------##`): print(`######################################################################`): print(`First Written: Jan. 09, 2007: tested for Maple 10 `): print(`Version of Jan. 09, 2007: `): print(): print(`This is Examples, A Maple package`): print(`accompanying the article: `): print(`A translation method for finding combinatorial bijections`): print(` by Philip Matchett Wood and Doron Zeilberger`): print(`Available from:`): print(`http://www.math.rutgers.edu/~matchett/Publications/`): print( ): print(`The most current version of this program is available on WWW at:`): print(`http://www.math.rutgers.edu/~matchett/Publications/`): print(`Please report all bugs to: matchett at math dot rutgers dot edu .`): print(): print(`For general help, and a list of the MAIN functions,`): print(`type "Help();". For specific help type "Help(procedure_name);" `): print(): ## NOTE: the Help() function is defined at the end of this file. # the function Hlp lists the main functions Hlp:=proc(): print(`Id7eg(n), Id7Direct(n)`): print(`Id8(n), Id8Direct(n), CassiniSort(A,B)`): print(`IdRec(n), IdDirect(n), IdRecSort(A,B)`): print(`Id7(n)`): print(`###############################################`): print(`#### ALSO INCLUDED (from Bijtools): #####`): print(`IndicesSeq(B), EntriesSeq(B), MultSet(S1,S2),`): print(`IdBij(S), BuildBij(L1,L2), InvBij(B)`): print(`ComposeBij(B1,B2), MultBij(B1,B2), AddBij(B1,B2), SumBij(L), SubtBij(B1,B2),`): print(`BijOut(B,a,b,AnOrder), BijEqual(B1,B2), IsBij(B,Domain,Range),`): print(`SplitProdBij(B1xB2), SwitchProdBij(B1xB2)`): print(`###############################################`): print(`#### ALSO INCLUDED (from Fibonacci): ####`): print(`Fn(n), FibDef(n), FibLex(A,B), ZeckSort(A,B)`): end: # ================================================================== # # ================================================================== # # Identity 7 (= Identity 17) from _Proofs that Really Count_ # This is a simple example of a Zeckendorf Family Identity # FIRST, we do the example from the paper, with base cases n=1 and n=2 Id7egBase1:=proc() local B: B:=table([ [1,[1]] = [1,1,1], [2,[1]] = [2,1], [3,[1]] = [1,2] ]); B: end: Id7egBase2:=proc() local B: B:= table([ [1,[1,1]] = [1,1,1,1], [1,[2]] = [1,1,2], [2,[1,1]] = [2,1,1], [2,[2]] = [2,2], [3,[1,1]] = [1,2,1], [3,[2]] = [] ]); B: end: # Id7eg(n): produces a bijection for Identity 7 in Proofs that Really Count. # This bijection is the same as the bijection in the book, except that the # output is reversed (this meets the condition of formally equivalent---see # paper on Zeckendorf-style Bijections). # # HERE we start with the base cases of n=1 and n=2, as in the first example of # the paper (later in Id7 below, we will use n=-1 and n=0 for the base cases, # which is more complicated but produces a unique bijection). Id7eg:=proc(n) local B; if n=1 then return Id7egBase1(): elif n=2 then return Id7egBase2(): elif n>2 then ## Induction Step ## # $ 3 f_n = 3 f_{n-1} + 3 f_{n-2} $ B[1]:=MultBij(IdBij({1,2,3}), FibDef(n)); # $ 3 f_{n-1} + 3 f_{n-2} = f_{n+1} + f_{n-3} + f_n + f_{n-4} $ B[3]:=AddBij(Id7eg(n-1), Id7eg(n-2)): # $ f_{n-3} + f_{n-4} + f_n + f_{n+1} = f_{n-2} + f_{n+2} $ B[4]:=InvBij(AddBij(FibDef(n-2),FibDef(n+2))): # 3 f_n = 3 f_{n-1} + 3 f_{n-2} \\ # = f_{n+1} + f_{n-3} + f_n + f_{n-4} \\ # = f_{n-2} + f_{n+2} B[5]:=ComposeBij(B[4],ComposeBij(B[3],B[1])): return B[5]: fi: # function should never reach this point. return FAIL: end: # Id7Direct(n): this function returns a directly-defined bijection that is the # same as Id7eg (which is for Identity 7 in Proofs that Really Count). One can # check that Id7Direct is the same as Id7 using the BijEqual command from # BijTools, for example # BijEqual(Id7eg(4), Id7Direct(4)) # (which returns true iff the bijections are equal). # This bijection is _also_ the same as Id7. Id7Direct:=proc(n) local i, X, B: B:= table(): for i from 1 to 3 do for X in Fn(n) do if i = 1 then B[[i,X]]:= [1,1,op(X)]: elif i=2 then B[[i,X]]:= [2,op(X)]: elif i=3 and X[1] = 1 then B[[i,X]]:= [1,2,op(2..nops(X),X)]: elif i=3 and X[1] = 2 then B[[i,X]]:= [op(2..nops(X),X)]: fi: od: od: return B: end: # ================================================================== # # ================================================================== # # Cassini's Identity (aka Simson's Formula): f_n^2 = f_{n+1} f_{n-1} + (-1)^n. # NOTE: this is Identity 8 in _Proofs that Really Count_. Id8Base0:=proc() local B: B:=table([ [[],[]] = 1 ]); B: end: # We will construct the bijection in two cases, based on whether n is even # or odd (that way we can put (-1)^n on the side of the equation so that it is # positive). Id8:=proc(n) local B: if n = 0 then return Id8Base0(): elif (n mod 2 = 1) then # n is odd # f_n^2 +1 = f_n(f_{n-1} + f_{n-2}) + 1 B[1]:= AddBij( MultBij(IdBij(Fn(n)),FibDef(n)) , IdBij({1}) ): # # the below is an identity of sets, so no bijection needed. # f_n(f_{n-1} + f_{n-2}) + 1 = f_n f_{n-1} + f_n f_{n-2} + 1 # f_n f_{n-1} + f_n f_{n-2} + 1 = f_n f_{n-1} + f_{n-1}^2 B[2]:= AddBij( MultBij(IdBij(Fn(n)),IdBij(Fn(n-1))), InvBij(Id8(n-1)) ): # # the below is an identity of sets, so no bijection needed. # f_n f_{n-1} + f_{n-1}^2 = (f_n + f_{n-1}) f_{n-1} # (f_n + f_{n-1}) f_{n-1} = f_{n+1} f_{n-1} B[3]:= MultBij( InvBij(FibDef(n+1)), IdBij(Fn(n-1)) ): # f_n^2 +1 = f_n(f_{n-1} + f_{n-2}) + 1 # = f_n f_{n-1} + f_{n-1}^2 # = f_{n+1} f_{n-1} B[4]:= ComposeBij(B[3],ComposeBij(B[2],B[1])): return(B[4]): elif (n mod 2 = 0) then # n is even # f_n^2 = f_n(f_{n-1} + f_{n-2}) B[1]:= MultBij(IdBij(Fn(n)),FibDef(n)): # # the below is an identity of sets, so no bijection needed. # f_n(f_{n-1} + f_{n-2}) = f_n f_{n-1} + f_n f_{n-2} # f_n f_{n-1} + f_n f_{n-2} = f_n f_{n-1} + f_{n-1}^2 + 1 B[2]:= AddBij( MultBij(IdBij(Fn(n)),IdBij(Fn(n-1))), InvBij(Id8(n-1)) ): # # the below is an identity of sets, so no bijection needed. # f_n f_{n-1} + f_{n-1}^2 + 1 = (f_n + f_{n-1}) f_{n-1} + 1 # (f_n + f_{n-1}) f_{n-1} +1 = f_{n+1} f_{n-1} + 1 B[3]:= AddBij( MultBij( InvBij(FibDef(n+1)), IdBij(Fn(n-1)) ), IdBij({1}) ): # f_n^2 = f_n(f_{n-1} + f_{n-2}) # = f_n f_{n-1} + f_{n-1}^2 + 1 # = f_{n+1} f_{n-1} + 1 B[4]:= ComposeBij(B[3],ComposeBij(B[2],B[1])): return(B[4]): fi: return FAIL: # function should never reach this point. end: # Id8Direct(n): this function returns a directly-defined bijection for # Cassini's Identity (Identity 8 in Proofs that Really Count). One can check # that this identity is the same as Id8 using the BijEqual command from # BijTools, for example # BijEqual(Id8(4), Id8Direct(4)) # (which returns true iff the bijections are equal). Id8Direct:=proc(n) local X1,X2,B,i,one1,one2,marker: B:=table(): for X1 in Fn(n) do for X2 in Fn(n) do #dealing with (-1)^n if n is even if (n mod 2) = 0 and X1=[ seq(2, i=1..n/2) ] and X2=X1 then B[[X1,X2]]:= 1: else # we now know that at least one of X1 or X2 contains a 1. # finding the last 1 in X1 and X2 one1:=nops(X1): while one1 > 0 do if X1[one1]=1 then break; fi: one1:= one1-1: od: one2:=nops(X2): while one2 > 0 do if X2[one2]=1 then break; fi: one2:= one2-1: od: # defining B by moving the last 1---equiv to ``tail-swapping'' if nops(X2)-one2 <= nops(X1)-one1 then # here, the last 1 in X2 is at least as close to the end of the # list as the last one in X1. marker:=nops(X1)-nops(X2)+one2: B[[X1,X2]]:= [ [op(1..marker,X1), 1, op(marker+1..nops(X1),X1)], [op(1..one2-1,X2), op(one2+1..nops(X2),X2)] ]: elif nops(X2)-one2 > nops(X1)-one1 then # here, the last 1 in X1 is closer to the end of the # list as the last 1 in X2. marker:=nops(X2)-nops(X1)+one1: B[[X1,X2]]:= [ [op(1..one1-1,X1), 2,op(one1+1..nops(X1),X1)], [op(1..marker-1,X2),1,op(marker+1..nops(X2),X2)] ]: fi: fi: od: od: # dealing with (-1)^n if n is odd if (n mod 2) = 1 then B[1]:= [ [seq(2, i=1..floor(n/2)+1)], [seq(2, i=1..floor(n/2))] ]: fi: return B: end: # CassiniSort(A,B) # # a way o sort the domain side of the bijection for Cassini's Identity so that # the output looks nice when called like: # BijOut(Id8,2,3,CassiniSort); CassiniSort:=proc(A,B) if A = 1 then return true: elif B = 1 then return false: fi: if FibLex(A[1],B[1]) then return true: elif FibLex(B[1],A[1]) then return false: fi: # we are now in the case where A[1] = B[1], so we decide based on the second # coordinate: if FibLex(A[2],B[2]) then return true: elif FibLex(B[2],A[2]) then return false: fi: return false: # this is for the case of equality, since it is a strict order. end: # ================================================================== # # ================================================================== # # A recently open bijection published in _Proofs that Really Count_: # f_{n+4} + f_1 + 2 f_2 + 3 f_3 + ... + n f_n = (n+1) f_{n+2} + 3 IdRecBase_n1:=proc() local B: # the n = -1 case B:=table([ [1,1,1] = 1, [1,2] = 2, [2,1] = 3 ]); B: end: IdRec:=proc(n) local B,i,k, L, BookKeepingMap: if n = -1 then return IdRecBase_n1(): elif n >=0 then # f_{n+4} + f_1 + 2 f_2 + 3 f_3 + ... + n f_n # = f_{n+3} + f_{n+2} + f_1 + 2 f_2 + 3 f_3 + ... + n f_n B[1]:= AddBij( FibDef(n+4), SumBij([seq(MultBij(IdBij({seq(i,i=1..k)}), IdBij(Fn(k)) ), k=1..n)] ) ): # # Below is an equality of sets # f_{n+3} + f_{n+2} + f_1 + 2 f_2 + 3 f_3 + ... + n f_n # = (f_{n+3} + f_1 + 2 f_2 + 3 f_3 + ... + (n-1) f_{n-1} ) + n f_n + f_{n+2} # (f_{n+3} + f_1 + 2 f_2 + 3 f_3 + ... + (n-1) f_{n-1} ) + n f_n + f_{n+2} # = n f_{n+1) + 3 + n f_n + f_{n+2} B[2]:= SumBij([ IdRec(n-1), MultBij(IdBij({seq(i,i=1..n)}), IdBij(Fn(n))), IdBij(Fn(n+2)) ]); # # Below is an equality of sets # n f_{n+1) + 3 + n f_n + f_{n+2} = n (f_{n+1} + f_n) + f_{n+2} + 3 # n (f_{n+1} + f_n) + f_{n+2} + 3 = n f_{n+2} + f_{n+2} + 3 B[3]:= SumBij([ MultBij( IdBij({seq(i,i=1..n)}), InvBij(FibDef(n+2)) ), IdBij(Fn(n+2)), IdBij({1,2,3}) ]): # We need to define a Book Keeping Bijection from Fn(n+2) to {n+1} X Fn(n+2), # via the inverse of the projection map. I.e. L |--> (n+1, L). BookKeepingMap:=table([ seq( L = [ n+1, L ], L in Fn(n+2)) ]): # n f_{n+2} + f_{n+2} + 3 = (n+1) f_{n+2} + 3 B[4]:= SumBij([ MultBij(IdBij({seq(i,i=1..n)}), IdBij(Fn(n+2))), BookKeepingMap, IdBij({1,2,3}) ]): # # Now, we just compose the four bijections above # f_{n+4} + f_1 + 2 f_2 + 3 f_3 + ... + n f_n # = f_{n+3} + f_{n+2} + f_1 + 2 f_2 + 3 f_3 + ... + n f_n # = n f_{n+1) + 3 + n f_n + f_{n+2} # = n f_{n+2} + f_{n+2} + 3 # = (n+1) f_{n+2} + 3 B[5]:= ComposeBij(B[4], ComposeBij(B[3], ComposeBij(B[2], B[1]))): return B[5]: fi: return FAIL: # the function should never reach this point. end: # IdDirect(n): Outputs a directly defined bijection that is the same as IdRec # (which is recursively defined). The code follows the paper # Wood, Philip Matchett. A bijective proof of # $f\sb {n+4}+f\sb 1+2f\sb 2+\cdots+nf\sb n=(n+1)f\sb {n+2}+3$. # \emph{Integers} \textbf{6} (2006), A2, 4 pp. # with a slight improvement leading to 3 special cases instead of 5. # # One can check that this identity is the same as IdRec using the BijEqual # command from # BijTools, for example # BijEqual(IdRec(4), IdDirect(4)) # (which returns true iff the bijections are equal). IdDirect:=proc(n) local B, X, Xhat, Xtilde, ell, i, k: B:=table(): # defining B for the 3 special cases B[[seq(1,j=1..n+4)]] := 1: B[[1,2,seq(1,j=1..n+1)]]:= 2: B[[2,1,seq(1,j=1..n+1)]]:= 3: # defining the bijection B for X in Fn(n+4)\{special cases} for X in ( Fn(n+4) minus {[seq(1,j=1..n+4)], [1,2,seq(1,j=1..n+1)], [2,1,seq(1,j=1..n+1)]} ) do ell:=0: while X[nops(X)-ell] <> 2 and ell < nops(X)-1 do ell:=ell+1: od: # ell is now the number of 1's in X following the last 2. Xhat:= [ op(1..nops(X)-ell-1,X), op(nops(X)-ell+1..nops(X),X) ]: # defining B for this particular X B[X]:= [n-ell+1 , Xhat]: od: # defining the bijection B for X in [k] cross Fn(k), where k=1..n for k from 1 to n do for i from 1 to k do for X in Fn(k) do # defining where (i, X) is mapped by B Xtilde:= [op(X), 2, seq(1, j=1..n-k)]: B[[i, X]]:= [i, Xtilde]: od: od: od: return B: end: # IdRecSort(A,B): An order function for the domain of IdRec, so that the # output looks nice when calling, for example, # BijOut(IdRec,2,5,IdRecSort); IdRecSort:=proc(A,B) if nops(A) <> nops(B) then return evalb(nops(A) < nops(B)): elif nops(A) = 2 then # we know also that nops(B) = 2 return ZeckSort(A,B): else return FibLex(A,B): fi: return false: # this is for the case of equality, since it is a strict order. end: # ================================================================== # # ================================================================== # # We now construct a bijection Identity 7 starting with the base cases of # n = -1 and n = 0, for which there are no arbitrary choices possible. # This part of the code impliments an example from the final section of the # paper # `A translation method for finding combinatorial bijections` Id7Base_n1:=proc() local B: B:=table([ [-2,-1] = [1] ]); B: end: Id7Base0:=proc() local B: B:= table([ [1,[]] = [1,1], [2,[]] = [2], [3,[]] = [-2] ]); B: end: # Id7(n): produces a bijection for Identity 7 in Proofs that Really Count. # This bijection is the same as the bijection in the book, except that the # output is reversed (this meets the condition of formally equivalent---see # paper on Zeckendorf-style Bijections). Id7:=proc(n) local B; if n=-1 then return Id7Base_n1(): elif n=0 then return Id7Base0(): elif n=1 then # $ 3 f_1 = 3 f_{0} + 3 f_{-1} $ B[1]:=MultBij(IdBij({1,2,3}), FibDef(n)); # $ 3 f_1 - f_{-3}= 3 f_{0} + 3 f_{-1} - f_{-3}$ ## note f_{-3} < 0. B[2]:=AddBij(B[1],IdBij(Fn(-3))): # $ 3 f_{0} + 3 f_{-1} - f_{-3} = f_{2} + f_{-2} + f_1 $ B[3]:=AddBij(Id7(n-1), Id7(n-2)): # $ f_2 + f_1 + f_{-2} = f_3 + f_{-1} - f_{-3} $ B[4]:=InvBij(AddBij(FibDef(n-2),FibDef(n+2))): # 3 f_1 - f_{-3} = 3 f_{0} + 3 f_{-1} - f_{-3} \\ # = f_{2} + f_{-2} + f_1 \\ # = f_3 + f_{-1} - f_{-3} B[5]:=ComposeBij(B[4],ComposeBij(B[3],B[2])): # $ 3 f_1 = f_3 + f_{-1}$ B[6]:=SubtBij(B[5],IdBij(Fn(-3))): return B[6]: elif n>1 then ## Induction Step ## # $ 3 f_n = 3 f_{n-1} + 3 f_{n-2} $ B[1]:=MultBij(IdBij({1,2,3}), FibDef(n)); # $ 3 f_{n-1} + 3 f_{n-2} = f_{n+1} + f_{n-3} + f_n + f_{n-4} $ B[3]:=AddBij(Id7(n-1), Id7(n-2)): # $ f_{n-3} + f_{n-4} + f_n + f_{n+1} = f_{n-2} + f_{n+2} $ B[4]:=InvBij(AddBij(FibDef(n-2),FibDef(n+2))): # 3 f_n = 3 f_{n-1} + 3 f_{n-2} \\ # = f_{n+1} + f_{n-3} + f_n + f_{n-4} \\ # = f_{n-2} + f_{n+2} B[5]:=ComposeBij(B[4],ComposeBij(B[3],B[1])): return B[5]: fi: # function should never reach this point. return FAIL: end: ############################################################################### ########## Help function defined below # ###################################### Help:=proc() if args=NULL then print(`Examples: A Maple package implementing the`): print(`basic examples of translation method described in `): print(`A translation method for finding combinatorial bijections`): print(`by Philip Matchett Wood and Doron Zeilberger.`): print(`The MAIN procedures are`): print(`Id7eg, Id7Direct`): print(`Id8, Id8Direct, CassiniSort`): print(`IdRec, IdDirect, IdRecSort`): print(`Id7,`): print(`###############################################`): print(`### ALSO INCLUDED (from BijTools): ###`): print(`IndicesSeq,EntriesSeq,MultSet,IdBij,BuildBij,InvBij,ComposeBij,MultBij,`): print(`AddBij,SumBij,SubtBij,BijOut,BijEqual,IsBij,SplitProdBij,SwitchProdBij`): print(`###############################################`): print(`### ALSO INCLUDED (from Fibonacci): ###`): print(`Fn, FibDef, FibLex, ZeckSort`): print(): print(`For help with a specific procedure, type Help(Procedure);`): print(`For example, for help with Id7eg, type: Help(Id7eg);`): elif nargs=1 and args[1]=Id7eg then print(`Id7eg(n): Produces a recursive bijection for the identity`): print(`3f_n = f_{n+2} + f_{n-2}`): print(`using the translation method with the base cases of n=1 and n=2`): print(`For example, try B:= Id7eg(3): and op(B);`): print(`Or for better viewing, just type BijOut(Id7eg,3,3,ZeckSort);`): print(`Also note that Id7eg is the same as Id7Direct, for example try`): print(`seq( BijEqual(Id7eg(j),Id7Direct(j)), j=1..6);`): elif nargs=1 and args[1]=Id7Direct then print(`Id7Direct(n): Produces a direct bijection for the identity`): print(`3f_n = f_{n+2} + f_{n-2}`): print(`that is defined in a non-recursive way for any n>=1.`): print(`For example, try B:= Id7Direct(3): and op(B);`): print(`Or for better viewing, just type BijOut(Id7Direct,3,3,ZeckSort);`): print(`Also note that Id7Direct is the same as both Id7eg and Id7,`): print(`for example try`): print(`seq( BijEqual(Id7eg(j),Id7Direct(j)), j=1..6); and also`): print(`seq( BijEqual(Id7(j),Id7Direct(j)), j=1..6);`): elif nargs=1 and args[1]=Id8 then print(`Id8(n): Produces a recursive bijection for Cassini's Identity`): print(` f_n^2 = f_{n+1} f_{n-1} + (-1)^n `): print(`via the translation method with the base case of n=0`): print(`For example, try BijOut(Id8,0,2,CassiniSort); `): print(`Also note that Id8 is the same as Id8Direct, for example try`): print(`seq( BijEqual(Id8(j),Id8Direct(j)), j=1..6);`): elif nargs=1 and args[1]=Id8Direct then print(`Id8direct(n): Produces a direct bijection for Cassini's Identity`): print(` f_n^2 = f_{n+1} f_{n-1} + (-1)^n `): print(`defined in a non-recursive way for all n>=1`): print(`For example, try BijOut(Id8,0,2,CassiniSort); `): print(`Also note that Id8Direct is the same as Id8, for example try`): print(`seq( BijEqual(Id8(j),Id8Direct(j)), j=1..6);`): elif nargs=1 and args[1]=CassiniSort then print(`CassiniSort(A,B): Given A and B in the set Fn(n)^2, this function`): print(`provides a total order that makes the output look nice when calling`): print(`BijOut(Id8,2,3,CassiniSort): (for example)`): elif nargs=1 and args[1]=IdRec then print(`IdRec(n): This function gives a recursive bijection for the identity`): print(`f_{n+4} + f_1 + 2 f_2 + 3 f_3 + ... + n f_n = (n+1) f_{n+2} + 3`): print(`using the translation method starting with the base case n=-1.`): print(`For example, try BijOut(IdRec,-1,2,IdRecSort); `): print(`Also note that IdRec is the same as IdDirect, for example try`): print(`seq( BijEqual(IdRec(j),IdDirect(j)), j=0..6);`): elif nargs=1 and args[1]=IdDirect then print(`IdDirect(n): This function gives a direct bijection for the identity`): print(`f_{n+4} + f_1 + 2 f_2 + 3 f_3 + ... + n f_n = (n+1) f_{n+2} + 3`): print(`defined in a non-recursive way for all n>=-1.`): print(`For example, try BijOut(IdDirect,-1,2,IdRecSort); `): print(`Also note that IdDirect is the same as IdRec, for example try`): print(`seq( BijEqual(IdRec(j),IdDirect(j)), j=0..6);`): elif nargs=1 and args[1]=IdRecSort then print(`IdRecSort(A,B): Given A and B in the set `): print(`Fn(n+4) + Fn(1) + [2] x Fn(2) + [3] x Fn(3) + ... + [n] x Fn(n)`): print(`where x is Cartesian product (this is just the domain for IdRec),`): print(`this function gives a total order makeing it look good when calling`): print(`BijOut(IdRec,2,3,IdRecSort): (for example)`): elif nargs=1 and args[1]=Id7 then print(`Id7(n): Produces a recursive bijection for the identity`): print(`3f_n = f_{n+2} + f_{n-2}`): print(`using the translation method with the base cases of n=-1 and n=0.`): print(`The n=-1 case illustrates the use of negative Fibonacci numbers.`): print(`For example, try B:= Id7(3): and op(B);`): print(`Or for better viewing, just type BijOut(Id7,3,3,ZeckSort);`): print(`Also note that Id7 is the same as Id7Direct, for example try`): print(`seq( BijEqual(Id7(j),Id7Direct(j)), j=1..6);`): #########--INCLUDED FROM BijTools-----------------############################# elif nargs=1 and args[1]=IndicesSeq then print(`IndicesSeq(B): outputs the domain of a bijection B as a sequence`): print(`Note that a bijection is simply a table in Maple.`): elif nargs=1 and args[1]=EntriesSeq then print(`EntriesSeq(B): outputs the range of a bijection B as a sequence`): print(`Note that a bijection is simply a table in Maple.`): elif nargs=1 and args[1]=MultSet then print(`MultSet(S1,S2): given two set S1 and S2, returns the Cartesian product`): print(`$ S1 \\cross S2 $. For example, try typing S1:={1,2}; S2:={a,b}; `): print(`followed by S1xS2:=MultSet(S1,S2);`): elif nargs=1 and args[1]=IdBij then print(`IdBij(S): given a set S, returns the bijection sending x |-> x`): print(` for every x in S`): print(`For example, try B:= IdBij({1,2,3}):`): print(`Note that a bijection is just a table, so to see how B is defined`): print(`try typing op(B): or B[2]:`): elif nargs=1 and args[1]=BuildBij then print(`BuildBij(L1,L2): given two lists L1 and L2, returns a bijection`): print(`sending the k-th element of L1 to teh k-th element of L2.`): print(`For example, try B:=BuildBij([a,b,c], [1,2,3]):`): print(`Note that a bijection is just a table, so to see how B is defined`): print(`try typing op(B): or B[c]:`): elif nargs=1 and args[1]=InvBij then print(`InvBij(B): given a bijection B returns the inverse bijection.`): print(`For example, try B:=BuildBij([a,b,c], [1,2,3]): followed by`): print(`Binv:=InvBij(B):`): print(`Note that a bijection is just a table, so to see how Binv is defined`): print(`try typing op(Binv): or Binv[2]:`): elif nargs=1 and args[1]=ComposeBij then print(`ComposeBij(B1,B2): given two bijections B1 and B2, this function`): print(`checks that the range of B2 equals the domain of B1 and then`): print(`returns the bijection B1 applied to B2.`): print(`For example, try B1:=BuildBij([1,2,3], [a,b,c]): followed by`): print(`B2:=BuildBij([a,b,c],[101,102,103]): followed by`): print(`B1ofB2:= ComposeBij(B1,B2):`): print(`Note that a bijection is just a table, so to see how B1ofB2 is defined`): print(`try typing op(B1ofB2): or B1ofB2[2]:`): elif nargs=1 and args[1]=MultBij then print(`MultBij(B1,B2): given two bijections B1: S1->T1 and B2: S2->T2,`): print(`this function returns the natural bijection F: S1 x S2 -> T1 x T2`): print(`where x denotes Cartesian product.`): print(`For example, try B1:=BuildBij([1,2,3], [a,b,c]): followed by`): print(`B2:=BuildBij([w,y,z],[23,25,26]): followed by`): print(`B1xB2:= MultBij(B1,B2):`): print(`Note that a bijection is just a table, so to see how B1xB2 is defined`): print(`try typing op(B1xB2): or B1xB2[[2,t]]:`): elif nargs=1 and args[1]=AddBij then print(`AddBij(B1,B2): given two bijections B1: S1->T1 and B2: S2->T2,`): print(`this function returns the natural bijection F: S1 union S2 -> T1 union T2`): print(`where union denotes disjoint union. If S1 intersects S2 or`): print(`T1 intersects T2, the function returns FAIL`): print(`For example, try B1:=BuildBij([1,2,3], [a,b,c]): followed by`): print(`B2:=BuildBij([w,y,z],[23,25,26]): followed by`): print(`B1uB2:= AddBij(B1,B2):`): print(`Note that a bijection is just a table, so to see how B1uB2 is defined`): print(`try typing op(B1uB2); or B1uB2[2]; or B1uB2[z]; `): elif nargs=1 and args[1]=SumBij then print(`SumBij(L): Given a list of bijections L, successively applies the`): print(`function AddBij. For example, if B1, B2, and B3 are bijections,`): print(`then SumBij([B1,B2,B3]); returns AddBij(AddBij(B3,B2),B1).`): elif nargs=1 and args[1]=SubtBij then print(`SubtBij(B1,B2): given two bijections B1 and B2, this function`): print(`uses combinatorial inversion to find the bijection B1-B2.`): print(`here $B1: A \to B$ and $B2: C \to D$ where`): print(`$C \subset A$ and $D \subset B$, and so SubtBij returns the`): print(`bijection sending $A\setminus C \to B\setminus D$ given by `): print(`the "alternating pairs algorithm".`): elif nargs=1 and args[1]=BijOut then print(`BijOut(B,a,b,AnOrder): A general output function for bijecions that`): print(`depend on a single parameter. Outputs the bijection for n=a to n=b.`): print(`AnOrder is a total order relation defined on the domain of the bijection.`): print(`Note that B *must* be a Maple function of an integer.`): print(`For example, type Help(phi5rec) and follow the instuructions`): print(`after typing read TransMethodZeck: `): elif nargs=1 and args[1]=BijEqual then print(`BijEqual(B1,B2): given two bijections B1 and B2, returns `): print(`true if the bijections are the same and false otherwise.`): elif nargs=1 and args[1]=IsBij then print(`IsBij(B,Domain,Range): given a bijection B and two sets Domain and Range`): print(`this function returns true if B is a bijection from Domain to Range`): print(`and returns false otherwise`): elif nargs=1 and args[1]=SplitProdBij then print(`SplitProdBij(B1xB2): separates the two component bijections B1 and B2`): print(`of a bijection that is the product of B1 and B2.`): print(`NOTE: this function checks to make sure that B1xB2 is indeed`): print(`a product bijection to start with.`): elif nargs=1 and args[1]=SwitchProdBij then print(`SwitchProdBij(B1xB2): given a product bijection,`): print(`say B1:A --> B and B2:C-->D, returns the corresponding bijection`): print(`from A x C to D x B`): print(`NOTICE the switch: the range of the returned bijection is _not_ B x D.`): ###### END INCLUDED FROM BijTools-----------------############################# #########--INCLUDED FROM Fibonacci----------------############################# elif nargs=1 and args[1]=Fn then print(`Fn(n): given an integer n (possibly negative), returns a set that is`): print(`an interpretation for the n-th Fibonacci number.`): print(`For example, Fn(3): returns the set`): print(`{ [1,1,1], [1,2], [2,1] }`): elif nargs=1 and args[1]=FibDef then print(`FibDef(n): returns the defining bijection for the Fibonacci numbers`): print(`as defined in the paper `): print(`A translation method for finding combinatorial bijections`): print(`by Philip Matchett Wood and Doron Zeilberger.`): print(`For example, try B:= FibDef(3): and the op(B): `): elif nargs=1 and args[1]=FibLex then print(`FibLex(A,B): given two lists A and B, each consisting only of 1's and 2's`): print(`this function returns true if`): print(`(1) the sum of elements in A is smaller than the sum of elements in B, or`): print(`(2) the two sums are equal and A preceeds B lexicographically.`): print(`Otherwise FibLex returns false.`): print(`For example, try FibLex([1,1,1],[2,1]); or FibLex([2],[1,1,1]); `) elif nargs=1 and args[1]=ZeckSort then print(`ZeckSort(A,B): Gives a total order on elements in {1,2,...,k} X F_n`): print(`to make the output of the bijection nice when calling`): print(`BijOut(phi5rec,3,5,ZeckSort);`): print(`First it sorts by the first argument (which is an int from 1 to k),`): print(`then it uses FibLex on the second argument.`): ###### END INCLUDED FROM Fibonacci----------------############################# else print(`There is no such thing as`, args): fi: end: #EOF