##########################################################################
## Fibonacci: Save this file as  Fibonacci  to use it,                   #
## stay in the same directory, get into Maple                            #
## (by typing: maple <Enter> )                                           #
## and then type:  read Fibonacci: <Enter>                               #
## 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(`######################################################################`):


print(`First Written: Jan. 09, 2007: tested for Maple 10 `):
print(`Version of Jan. 09, 2007:  `):
print():
print(`This is Fibonacci, 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(`Fn(n), FibDef(n), FibLex(A,B), ZeckSort(A,B)`):
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)`): 
end:


with(ListTools):

#Fn(n): builds the set Fn(n) of fibonnacci numbers.
Fn:=proc(n) local i:
option remember:

if n = 0 then
	return {[]}:
elif n=1 then
	return {[1]}:
elif n<0 then 
	return Fneg(n):
fi:

return {seq([1,op(Fn(n-1)[i])], i=1..nops(Fn(n-1))),
seq([2,op(Fn(n-2)[i])],i=1..nops(Fn(n-2)))}:

end:

# Fneg(n): produces the "set" for negative fibonacci numbers.  if n is an odd
# negative number, then this should be an "anti-set", which means that
# setminus-ing it from another set results in disjoint union.  
## NOTE: this function does _not_ do anything special for the anti-sets---it
## returns them in _positive_ form.  So you have to deal with the "anti" part
## on your own.
Fneg:=proc(n) local PnB:
if n >=0 then 
	print(`Called Fneg(n) with a _non-negative_ value of n.`):
	return FAIL:
elif n = -1 then
	return {}:
elif n = -2 then 
	return {[-2]}: #note: here we chose to represent the choped two by -2
fi:

# Build FibPosNegBij(n), which sends Fn(n) to Fn(-(n+2)).
PnB:=FibPosNegBij(-(n+2)):

{EntriesSeq(PnB)}:

end:


# FibPosNegBij(n), which sends Fn(n) to Fn(-(n+2)) by the bijection described
# below.
FibPosNegBij:=proc(n) local B,x,y,i,Ind:
B:= table():
Ind:=Fn(n):
for x in Ind do
	y:=[-2]:
	for i from 1 to nops(x) do
		if x[i] = 2 then 
			y:= [op(y),-2]:
		elif x[i] = 1 then 
			y:= [op(y),-1]:
		else 
			return FAIL:
		fi:
	od:
	B[x]:=y:
od:

B:
end:

# FibDef(n):  returns the bijection that takes in tiling of  n  by squares and
# dominoes and chops the last square or domino.
FibDef:=proc(n) local Fnbij,x:
#option remember: This is unnecessary---there is no recursion here!!!
Fnbij:=table():

# first we deal with non-positive numbers.
if n <= 0 then
	if n mod 2 = 1 then # the n odd case
		for x in Fn(n-2) do
			Fnbij[x]:=[op(1..nops(x)-1,x)]:
		od:	
		return Fnbij:
	else # the n even case
		for x in Fn(n)  do
			Fnbij[x]:=[op(x),-2]: 
		od:
		for x in Fn(n-1) do
			Fnbij[x]:=[op(x),-1]:
		od:
		return Fnbij:
	fi:
fi:

# chop-the-last---this deals with n >0.
Fnbij:= table(
	[seq(Fn(n)[i] = [op(1..(nops(Fn(n)[i])-1),Fn(n)[i])], i=1..nops(Fn(n)))]
):
return Fnbij:
end:

# FibDefInv(n): bijection from Fn(n-1) + Fn(n-2) to Fn(n), so it appends a 1
# or 2 depending on what is needed to get the element up to n.
## *  NOTE: only works for n >=1  *
FibDefInv:=proc(n) local S,L,Fnbijinv,s:
option remember:

#S:= Fn(n-1) union Fn(n-2):
#L:=convert(S,list):

Fnbijinv:=table():
for s in Fn(n-1) do
	Fnbijinv[s]:= [op(s),1]:
od:
for s in Fn(n-2) do 
	Fnbijinv[s]:= [op(s),2]:
od:

Fnbijinv:
end:

# FibLex(A,B):  This procedure gives a order (lexicographic) on the
# elements of Fn(n).  First it sorts by sum (from highest to lowest), then it
# sorts lexicographically.  Note that A and B should be lists of 1's and 2's.
## NOTE: there are many other natural ways to do the sorting, say putting in 
##       nops(A) and nops(B) as a higher priority.
FibLex:=proc(A,B) local m,n,i:
m:=sum(A[i],i=1..nops(A)):
n:=sum(B[i],i=1..nops(B)):
if m<n then 
	return true:
elif n<m then
	return false:
fi: 

# so now we have m=n and use Lex order.
for i from 1 to min(nops(A),nops(B)) do
	if A[i] < B[i] then 
		return true:
	elif B[i] < A[i] then
		return false:
	fi:
od:

# now we must have A[i]=B[i] for i from 1 to min(nops(A),nops(B))., so the
# longer wins
if nops(A) < nops(B) then 
	return true:
elif nops(B) < nops(A) then 
	return false:
fi:

# at this point, A = B everywhere. 
return false: # since it is a strict ordering.
end:



# ZeckSort(A,B)
#   Gives an order relation on elements in {1,2,...,k} X F_n to make the
#   output of the bijection nice when calling
#         BijOut(Id7,3,5,ZeckSort);
#   First it sorts by the first argument (which is an interger from 1 to k),
#   then it uses FibLex on the second argument.
ZeckSort:=proc(A,B)
if A[1] < B[1] then
    return true:
elif B[1] < A[1] then
    return false:
fi:
# if we get here, the first arguments must be the same.

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:




###############################################################################
########## Help function defined below # ######################################

Help:=proc()
if args=NULL then

print(` Fibonacci: A Maple package implementing the`):
print(`interpretation of the Fibonacci numbers as sets in the paper:`):
print(`A translation method for finding combinatorial bijections`):
print(`by Philip Matchett Wood and Doron Zeilberger.`):
print(`The MAIN procedures are`):
print(`Fn, FibDef, FibLex, ZeckSort`):
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(`For help with a specific procedure, type Help(Procedure);`):
print(`For example, for help with FibLex, type: Help(FibLex);`):

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 then  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.`):


#########--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(`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-------- --------#############################


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

fi:
end:


#EOF