#M8.txt: Maple Code for Lecture 8 of Math 454,Combinatorics, Rutgers University, taught by Dr. Z. (Doron Zeilberger)
Help8:=proc():print(` GFseq(f,x,N), CompsGFk(S,x,k) , CompsGF(S,x), CompsGFcon(a,C, x) `): end:


with(combinat):


#GFseq(f,x,N): Given a rational function f in the variable x, (whose denominator does not vanish at 0) [or a more general function/expression)
#returns the first N+1 terms, starting at n=0 of the coefficients of the sequence that has it has a GENERATING FUNCTION
#Equivalently, returns the first n+1 terms. stating at n=0 of its Taylor coefficients. Try:
#GFseq(x/(1-x-x^2),x,100);
GFseq:=proc(f,x,N) local  f1,i:
f1:=taylor(f,x=0,N+1):
[seq(coeff(f1,x,i),i=0..N)]:
end:

#CompsGFk(S,x,k): inputs a FINITE set of INTEGERS (0 and negative integers are OK!) and a variable x, and
#a non-negative integer k, outputs the POLYNOMIAL (possibly Laurent polynomial, i.e. negative powers OK)
#whose coefficient of x^n is the EXACT number of words of length k, in the finite alphabet S
#that add-up to n. For example to get the generating function of all 4-letter words in {0,1} according to the
#sum (alias "number of 1s") try:
#CompsGFk({0,1},x,4); 
CompsGFk:=proc(S,x,k) local s:
sort(expand((add(x^s, s in S))^k)):
end:


#CompsGF(S,x): inputs a FINITE set of POSITIVE INTEGERS (0 and negative integers are NOT WELCOME) and a variable x,
#OUTPUTS THE RATIONAL FUNCTION
#whose coefficient of x^n (in the Taylor expansion around x=0) is the EXACT number of words of length k, in the finite alphabet S
#that add-up to n. For example to get the generating function of all k-letter words in {0,1} according to the
#sum (alias "number of 1s") try:
#CompsGF(S,x);
CompsGF:=proc(S,x) local s:
if not (type(S,set) and min(op(S))>0 ) then
 print(`Bad input`):
 RETURN(FAIL):
fi:

factor(1/(1-add(x^s,s in S))):

end:


#CompsGFcon(a,C, x): Inputs a positive integer a, and a finite set of {1,2,..,a}, C, and a variable x
#outputs the RATIONAL FUNCTIONS whose coefficient of x^n in the Taylor expansion around x=0
#is the EXACT number of words in the infinite alphabet of POSITIVE integers that when divided by a
#give a remainder in C, that add-up to n. For example for the classical compositions, try:
#CompsGFcon(1,{1},x);
CompsGFcon:=proc(a,C,x) local c:
factor( 1/(1-add(x^c, c in C)/(1-x^a))):
end: