#OK to post homework
#Sam Minkin, 10/04, Assignment 8

Problem 1:

(i) The number of 10-letter words in the alphabet {1,4,6} that add up to 201.

This is equivalent to running: GFseq(CompsGFk({1,4,6},x,10), x, 201);
The last term of the sequence output is 0. So there 0 10-letter words in {1,4,6} adding up to 201.

(ii) The number of words in the alphabet {2,3,7} of ANY length, that add-up to 411

This can be found by running: GFseq(CompsGF({2,3,7}, x), x, 411);
The last term of the sequence gives the number of k-letter words of any length, which is 4741685087960650685822461715671211099459856575685906645393. 

(iii) The number of sequences of any length whose entries are either 1 (mod 5) or 4 (mod 5) that add up to 341.

This can be found by running: GFseq(CompsGFcon(5,{1,4},x), x, 341);
The last term of this sequences gives the exact number of words in the infinite alphabet of positive integers such that when divided by a give a remainder in c and add up ton n.
This number is 234303065886413369536085349033389448858104244347193374824719.


Problem 2:

helper:=proc(n,k) local S,i,T,l,j,sum,a:
option remember:

if n < k then
	return({[]}):
fi:

S:={}:
T:=[seq(i,i=0..k-1)]:

for i in T do
	S:=S union {seq( [k,op(s)], s in Pnk(n-k,k-i))}:
od:

S:

end:

Pnk:=proc(n,k) local i,sum,s,S,l:
option remember:

S:=helper(n,k):

for s in S do
	l:=nops(s):
	sum:=0:
	for i from 1 to l do
		sum:=sum+s[i]:
	od:
	if sum <> n then
		S:=S minus {s}:
	fi:
od:

S:

end:

Problem 3:

helper1:=proc(n,k) local S,s,i:
option remember:

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

if n < 0 then
	return({}):
fi:

S:={}:

for i from 1 to n do
	S:=S union Pnk(n,i):
od:

S:

end:

pnk:=proc(n,k) local S,i,s,l,max,t:

if n < 0 or k < 0 then
	return({}):
fi:

S:=helper(n,k):

t:=0:

for s in S do
	l:=nops(s):
	if l > 0 then
		max:=s[1]:
		for i from 2 to l do
			if s[i] > max then
				max:=s[i]:
			fi:
		od:
		if max = k then
			t:=t+1:
		fi:
	fi:
od:

t:

end:


Problem 4:

pn:=proc(n) local t,i:
option remember:

t:=0:

for i from 1 to n do
	t:=t+pnk(n,i):
od:

t:

end:


Output of seq(pn(n),n=0..30);
1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, 56, 77, 101, 135, 176, 231, 297, 385, 490, 627, 792, 1002, 1255, 1575, 1958, 2436, 3010, 3718, 4565, 5604

The A number for this sequence is A000041


Problem 5:


(1) [seq(pn((5*n + 4) mod 5), n = 1 .. 50)];

[5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5]

(2) [seq(pn(7*n + 5) mod 7, n = 1 .. 50)];
[7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7]

(3) [seq(pn((11*n+6) mod 11), n=1..50)];
[11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11]