> #Please do not post
;
> #Yifan Zhang, 10/1/2020, hw8
;
> 
;
> 
;
> #Q1. 
;
> #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:
> CompsGFk({1,4,6},x,10);
x^60+10*x^58+45*x^56+10*x^55+120*x^54+90*x^53+210*x^52+360*x^51+297*x^50+840*x^
49+570*x^48+1260*x^47+1380*x^46+1380*x^45+2565*x^44+1680*x^43+3160*x^42+2880*x^
41+2731*x^40+4290*x^39+2520*x^38+4210*x^37+3510*x^36+2772*x^35+4245*x^34+2100*x
^33+3150*x^32+2640*x^31+1470*x^30+2520*x^29+1050*x^28+1260*x^27+1260*x^26+372*x
^25+840*x^24+360*x^23+210*x^22+360*x^21+45*x^20+120*x^19+90*x^18+45*x^16+10*x^
15+10*x^13+x^10

;
> #The number of 10-letter words in the alphabet {1,4,6} that add-up to 201 is 0.
;
> 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:
> 
;
> CompsGF({2,3,7},x);
-1/(x^7+x^3+x^2-1)

;
> GFseq:=proc(f,x,N) local  f1,i:
> f1:=taylor(f,x=0,N+1):
> [seq(coeff(f1,x,i),i=0..N)]:
> end:
> GFseq(-1/(x^7+x^3+x^2-1),x,411)[412]
4741685087960650685822461715671211099459856575685906645393

;
> CompsGFcon:=proc(a,C,x) local c:
> factor( 1/(1-add(x^c, c in C)/(1-x^a))):
> end: 
> CompsGFcon(5, {1,4},x)
(x-1)*(x^4+x^3+x^2+x+1)/(x^5+x^4+x-1)

;
> GFseq((x-1)*(x^4+x^3+x^2+x+1)/(x^5+x^4+x-1),x,341)[342]
234303065886413369536085349033389448858104244347193374824719

;
> 
;
> 
;
> 
;
> #Q2. 
;
> #Pnk(n,k) that inputs non-negative integers n and k and outputs the SET of all partitions of n whose LARGET part is k.
;
> Pnk:= proc(n,k) local  i,S:
> option remember:
> S:={[]}:
> if k>n then RETURN({}): fi:
>  
> if k=n then RETURN ({n}): fi:
> if k=1 and n =1 then RETURN({1}): fi:
> {seq(op(Pnk(n-i, i)), i=1..k)}:
> 
> #[op(Pnk(n-k,k)),k]
> 
> end:
> 
> 
;
> #Pnk(5,2)={2111,221}; Pnk(3,2)={21, 111};                     Pnk(1,1)={1}
;
> 
;
> 
;
> 
;
> 
;
> #Q3.
;
> pnk:= proc(n,k) 
> option remember:
> nops(Pnk(n,k)):
> end:
> pnk(5,5);
1

;
> 
;
> #Q4.
;
> pn:= proc(n) local i,S:
> option remember:
> 
> S:=0:
> 
> for i from 1 to n do
> S:= S+pnk(n,i):
> od:
> 
> S:
> end:
> 
;
> 
;