# Please do not post homework.

#Guy Adami, 2026-03-01, Assignment 11

#-------------------------

with(combinat):

#-------------------------

#GenCompsGF(a,b,A,B,x): The rational function whose Taylor series is such that
#the coeff. of x^n is the EXACT number of compositions whose
#parts all obey i mod a belongs to A
#number of parts k obey k mod b belongs to B

#GF of i mod a: x^i+x^(i+a)+ x^(i+2*a)+... =x^i/(1-x^a)


GenCompsGF:=proc(a,b,A,B,x) local f,i,j:
	f:=add(x^i, i in A)/(1-x^a):
	normal(add(f^j, j in B)/(1-f^b)):
end:

#-------------------------

##Comps(n): The set of compositions of n. For example,
#Comps(3) is {[3],[1,2],[2,1],[1,1,1]}.

Comps:=proc(n) local S,i,S1,s1:
	option remember:

	if n<0 then
 		RETURN({}):
	fi:
	if n=0 then
  		RETURN({[]}):
	fi:

	S:={}:

	for i from 1 to n do
 		S1:=Comps(n-i):
 		S:=S union {seq([i,op(s1)],s1 in S1)}:
	od:
	S:
end:

#---------------------------------------

#Question 1


CountNuCompsClever:= proc(a,b,A,B,N) local x, Comps,n:
	
	Comps:= GenCompsGF(a,b,A,B,x):

	seq(coeff(taylor(Comps, x = 0, N+2), x, n), n = 1 .. N);

end:

#-------------------------

#Question 2


CountNuCompsStupid1 := proc(a, b, A, B, n) local L, l, C; 
	L := Comps(n):
	C := {}:

	if member(nops(L) mod b, B) then 
		for l in L do 
			if ({op(l)} mod~ a) minus A = {} then 
				C := {op(C), l}:
			fi: 
		od:
	fi:
	nops(C);
end:


#-----

CountNuCompsStupid := proc(a, b, A, B, N) local n; 
	[seq(CountNuCompsStupid1(a, b, A, B, n), n = 1 .. N)]; 
end: