#OK to post homework
#Michael Yen, 9/27/20, Assignment 6

#1. Read and understand the Maple code for Lecture 6. Explain why PIE is (usually) only of theoretical #interest.
#PIE is usually only of theoretical interest because it is just verifying the Principle of Inclusion-#Exclusion. A and B will always be the same number in the result, [A,B]. 

#Also read and understand procedures Pnx(n,x) and PnxF(n,x). Test whether
#[seq(Pnx(n,x),n=1..7)]
#and
#[seq(PnxF(n,x),n=1..7)]
#give you the same output.
#They do give you the same output.

#Now try to do
#time([seq(Pnx(n,x),n=1..8)]); 0.578
#and
#time([seq(PnxF(n,x),n=1..8)]); 0.0

#What takes longer? Pnx takes longer than PnxF.
#What is time([seq(PnxF(n,x),n=1..30)]); 0.015

#Estimate roughly (but don't run it!)
#time([seq(Pnx(n,x),n=1..30)]);
#It will take a long time, I'm not sure how to estimate it though. I think hours?

#2. In the Lecture, PIE was used to prove the formula
#D(n)=add(binomial(n,k)*(-1)^k*(n-k)!,k=0..n)
#for the number of derargment of n objects, called D(n). Explain why this is the constant term (the 
#coefficient of x^0) in PnxF(n,x)
#For any polynomial P(x) from PnxF(n,x), the coeff. of x^0 is D(n) because it represents the number of 
#permutations of the n objects with 0 fixed points. This is equivalent to the number of 
#derangements of n objects, D(n), since none of the n objects can be in their original spot.


#3. The fact that Pnx(n,x) equals PnxF(n,x) will be proved later, when we do generating functions. 
#Meanwhile search the OEIS for
#[seq(coeff(PnxF(n,x),x,i),n=0..12)] for i=0,1,2,3, ...

#List their A numbers (if they exist). What is the largest i for which there is a sequence in the OEIS?
#i=0: A000166
#i=1: A182390
#i=2: A000387
#i=3: Does not exist.
#i=4: Does not exist.
#i=2 is the largest for which there is a sequence.

#4. [Corrected Sept. 24, 2020, thanks to Tifany Tong who won a dollar]
#Euler proved two recurrences for the number of derangements of an n-element set, let's call it d(n) 
#[Note that D is a resereved symbol in Maple]
#One of them can be gotten from (Do it!)

#SumTools[Hypergeometric][ZeilbergerRecurrence](binomial(n,k)*(-1)^k*(n-k)!,n,k,d,0..n);
#(-n-1)d(n)+d(n+1)=-(-1)^n

#which tells you that

#d(n)=n*d(n-1)+(-1)^n

#The OEIS gives another recurrence relating d(n) to d(n-1) and d(n-2). Use the above recurrence to find 
#this other recurrence.

#The other recurrence is that Euler proved is:
#d(n)=(n-1)*(d(n-1)+d(n-2))

#5. [Optional challenge] Give a combinatorial proof/explanation of this recurrence. Hint: Every permuation 
#can be be written in cycle-notation. Since there are no fixed points, all the cycles have length 2 or more.

#6. [Optional challenge]
#A. Prove by induction on n, that if x[1], ..., x[n] are any numbers (or symbols)

#product(1-x[i], i=1..n)= Sum ((-1)^|S|*x[S],S subset of {1, ...,n})

#where x[S]=Product (x[s], s in S). For example x[{3,6,7}]=x[3]*x[6]*x[7]

#B. Let Chi(statemnet)=1 if it is true and 0 if it is false. Explain why the left side of PIE (of the 
#new version that finds the number of elements in U that does not belong to any of A[1], ..., A[k]) can 
#be written as

#Sum ( Prodcut( 1-Chi( u in A[i])),i=1..k), u in U)

#Use the above identity to give a new proof of the PIE, by showing that it equals to the right side.