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

hw6FirstLast.txt

OK to Post

# 1)Read and understand the Maple code for Lecture 6. Explain why PIE is (usually) only of theoretical interest. 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. Now try to do time([seq(Pnx(n,x),n=1..8)]); and time([seq(PnxF(n,x),n=1..8)]);   What takes longer? What is time([seq(PnxF(n,x),n=1..30)]); Estimate roughly (but don't run it!) time([seq(Pnx(n,x),n=1..30)]); 

#A:PIE has so much theoretical interst as PIE usually can explain something general about cardinality of finte sets and with PIE you can prove things about combinatorial structures. [seq(Pnx(n,x),n=1..7)] and [seq(PnxF(n,x),n=1..7)] output identical ouputs. However  time([seq(Pnx(n,x),n=1..8)]); and time([seq(PnxF(n,x),n=1..8)]); output different times where  time([seq(Pnx(n,x),n=1..8)]); outputs 0.312 and time([seq(PnxF(n,x),n=1..8)]); outputs 0. When executing time([seq(PnxF(n,x),n=1..30)]);, we get a time of 0.015. Estimating the time for time([seq(PnxF(n,x),n=1..30)]);, we get roughly 5*10^28 using a exponential line best fit with data points of  time([seq(Pnx(n,x),n=1..10)]).

###########################################################################################################################################################################
# 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) n PnxF(n,x) 

#A:Using PIE, there is usally only one possible way to display the intersection of every set of PIE. Thus the coefficient of is a constant term.

###########################################################################################################################################################################
# 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? [Corrected Sept. 24, 2020, thanks to Tifany Tong who won a dollar]

#A:The highest number that starts at with the sequence is when i is 3 (A000387 = [0, 1, 0, 6, 20, 135, 924, 7420, 66744, 667485, 7342280, 88107426]). However i of 12 gives us an output of ([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]) which has this sequence in the middle of the original A010815 sequence.

###########################################################################################################################################################################
# 4)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); 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. 

#A:
d(n-1)=(n-1)*d(n-2)+(-1)^(n-1)
(d(n-1)+(-1)^(n))/(n-1) = d(n-2) (flipped (-1^(n-1) parity after subtraction)

d(n)=n*d(n-1)+(-1)^n
d(n)=n*[(n-1)*d(n-2)+(-1)^(n-1)]+(-1)^n
d(n)=n*(n-1)*d(n-2)+n(-1)^(n-1)+(-1)^n
d(n)=n*(n-1)*d(n-2)-n(-1)^(n)+(-1)^n (flipped parity and brought out negative)

d(n)=(n^2)*d(n-2)-n*(d(n-1)+(-1)^(n))/(n-1)+(n-1)(-1)^(n)).