Lecture 5: Due Sept. 27, 9:00pm. Email ShaloshBEKhad@gmail.com an attachment

hw5FirstLast.txt

OK to Post
# 1) The lecture gave a full proof of the fact that if P(n) denotes the set of permutation of {1,...n} and p(n):=|P(n)|, then p(n)=n*p(n-1) (and hence p(n)=n!) It used the # decompostion of P(n) into subsets according to the LOCATION of n. Find a new proof, explaining everything, of the same fact but breaking-up P(n) into the sets P_j(n)={All # permutations pi in P(n) such that pi[1]=j, j=1..n

#A:
# Base case:
# p(0) = 0 (alphabet is empty, therefore p(n) will result with no items inside)
# p(1) = 1 (alphabet only has one word inside, thus the number of words possible is 1)
# p(2) = 2 (alphabet has only two words (i.e. if {1,2}, then the two possible perumtations are {1,2} and {2,1}
#
# Induction Step: (Assuming that p(n) = n*p(n-1))
#           p(n)  =  n*p(n-1)
#          |P(n)| = |n*p(n-1)|
#           P(n)  =  P_j[1] U P_j[2] U ... U P_j[n]
# P_J[n+1] U P(n) =  P_j[1] U P_j[2] U ... U P_j[n] U P_J[n+1]
#        |P(n+1)| = (n+1)*n*|P(n-1)|
#          p(n+1) = (n+1)*p(n)
# Thus, 
# p(n) = n*p(n-1)

###########################################################################################################################################################################

#2) Let a1,a2,a3, be distinct positive integers, and let P(n;a1,a2,a3) be the set of words in the alphabet {a1,a2,a3}, of ANY length that add-up to n. For example P(3; # 1,2,3)={111,12,21,3} Decompose P(n;a1,a2,a3) into smaller sets, and deduce a recurrence relation for p(n)=p(n;a1,a2,a3):= |P(n;a1,a2,a3)|

#A:
p(n) = p(n-a) + p(n-b) + p(n-c)

###########################################################################################################################################################################
# 3) Write a Maple procedure (don't forget to use option remember)
# SEQP(a1,a2,a3,N) That inputs a1,a2,a3, as above, and a positive integer N, and outputs the first N+1 terms, starting at n=0 of p(n,a1,a2,a3), n=1..N What are SEQP# (1,2,3,40)? SEQP(1,2,4,40)? are they in the OEIS?


Help:=proc():print(`p(a,b,c,n) SEQP(a,b,c,n)`): end:

with(combinat):

p := proc(a, b, c, n) local sum; 
sum := 0; 

if a < n then 
sum := sum + p(a, b, c, n - a); 
end if; 

if b < n then 
sum := sum + p(a, b, c, n - b); 
end if; 

if c < n then 
sum := sum + p(a, b, c, n - c); 
end if; 

if n = a or n = b or n = c then 
sum := sum + 1; 
return sum; 
end if; 

if n < a and n < b and n < c then 
return 0; 
end if; 
return sum; 
end:

SEQP := proc(a, b, c, N) local n:
[seq(P(a,b,c,n), n=0..N)]:
end:

#A:SEQP is (A73) however SEQP(1,2,4,40) is not in OEIS.



###########################################################################################################################################################################
# In a given class, let C be the set of clever students, S be the set of strong students, L be the set of good-looking students, K be the set of kind-hearted students, # The Principle of Inclusion-Exclusion for four sets says
# |C union S union L union K|=
# |C| + |S|+ |L| + |K|
# -( |C interset S| + |C interset L| + |C interset K| + |S interset L| + |S interset K| + +|L interset K| )
# +( |C interset S intersect L| +|C interset S intersect K| +|C interset K intersect L| +|S interset K intersect L| )
# -|C intersect S intersect L intersect K| 
# If some one is clever and good-looking bit neither strong nor kind, make sure that he or she are counted exactly once, by finding out
#   How many time he is INCLUDED in line 1
#   How many time he is EXCLUDED in line 2
#   How many time he is INCLUDED (again) in line 3 (possibly none)
#   How many time he is EXCLUDED (again) in line 4 (possibly none) 
# Do the analogous thing for a lucky person who is lucky to be clever AND strong AND good-looking AND kind-hearted. 

#A:

#for an individual who is clever and good-looking bit neither strong nor kind, we get that
# |C union L|=
# 1 + 0 + 1 + 0
# -( 0 + 1 + 0 + 0 + 0 + 0 )
# +( 0 + 0 + 0 + 0)
# -0  = 2 - 1 = 1

#for an individual who is lucky to be clever AND strong AND good-looking AND kind-hearted, we get that
#|C union S union L union K|=
# 1 + 1 + 1 + 1
# -( 1 + 1 + 1 + 1 + 1 + 1 )
# +( 1 + 1 + 1 + 1)
# - 1  = 4 - 6 + 4 -1 = 1