Lecture 8: Due Oct. 4, 9:00pm. Email ShaloshBEKhad@gmail.com an attachment
hw8FirstLast.txt
Ok to Post

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

	There are zero possible ways to use the given alphabet that add-up to 201
	
    (ii) The number of words in the alphabet {2,3,7} of ANY length, that add-up to 411

	GFseq(CompsGF({2, 3, 7}, x), x, 411) = 4741685087960650685822461715671211099459856575685906645393

    (iii) The number of sequenes of any length whose entries are either 1 (mod 5) or 4 (mod 5) and that add up to 341
	
	GFseq(CompsGFcon(5, {1, 4}, x), x, 341) = 234303065886413369536085349033389448858104244347193374824719

2)  In a compositon the order matters. For example the set of compositions of 3 is {111,12,21,3}. In a partition the order does not matter, hence we agree to list it in weakly-decreasing order. For example, the set of partitions of 3 is {3,21, 111} (since 12 is the same as 21). Using the convention of representing partitions as weakly-decreasing sequences, write a procedure, call it 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. For example,

    Pnk(5,1)={[1,1,1,1,1]} , Pnk(5,2)={[2,2,1], [2,1,1,1]} , Pnk(5,3)={[3,1,1], [3,2]} , Pnk(5,4)={[4,1]]}, Pnk(5,5)={[5]}. -REMEMBER to use "option remember". Hint: When you take a partition [a1,a2,, .., ar] whose largest part is k (i.e.) a1=k and remove the first component (that is k), you get the partition [a2,.., ar] of n-k whose largest part a2, is <=k , so it is in natural bijection with. Pnk(n-k,k) Union Pnk(n-k,k-1) Union ... Union Pnk(n-k,1). Another hint: Pnk(n,k) is the Empty Set if k>n

	Pnk:=proc(n,k) local S,i,s:
	option remember:
	
	if k>n then 
	  return {}:
	fi:
	
	S:={}:
	
	for i from 0 to k-1 do 
	  S:=S union {seq([op(s),k], s in Pnk(n-k,k-i))}:
	end do:
	
	S:
	end:


3) Adapt the above to write a procedure, pnk(n,k), that inputs non-negative integers n and k and outputs the NUMBER of all partitions of n whose largest part is k. For example,

    pnk(5,1)=1 , pnk(5,2)=2 , pnk(5,3)=2 , Pnk(5,4)=1, Pnk(5,5)=1
    REMEMBER to use "option remember"

	Pnk:=proc(n,k) local: S,i,j:
	option remember:
	
	if k>n then 
	  return {}:
	fi:
	
	S:={}:
	
	for i from 1 to k do 
	  S:=S union {seq([op(j),k], j in Pnk(n-k,k-i-1))}:
	end do:
	
	nops(S):
	end:
	

4)By using pnk(n,k) write a procedure pn(n), that inputs a positive integer n and outputs the NUMBER of partitions of n. What is the OEIS A number of the integer sequence

    seq(pn(n),n=0...30);
    Hint: The set of partitions of n is Pnk(n,1) Union Pnk(n,2) Union ... Union Pnk(n,n)
    
    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
    A000041

5)What are
    [seq(p(5*n+4) mod 5, n=1..50)]= [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
    [seq(p(7*n+5) mod 7, n=1..50)]= [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
    [seq(p(11*n+6) mod 11, n=1..50)]= [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]