Ok to post

#-------------------------------
Question 

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)]);


# Answer 1

They do give you the same answer. This is the following code I ran on maple to test that:

[seq(Pnx(n, x), n = 1 .. 7)];
[seq(PnxF(n, x), n = 1 .. 7)];
verify(%, `%%`);
                              true


time([seq(Pnx(n, x), n = 1 .. 8)]);

0.692

time([seq(PnxF(n, x), n = 1 .. 8)]);
0.


Pnx takes way longer that PnxF

time([seq(PnxF(n, x), n = 1 .. 30)]);
0.008
This is ridiculously fast

Pnx would take just too long to do it


#------------------------------------------------
Question 2

In the Lecture, PIE was used to prove the formula
D(n)=add(binomial(n,k)*(-1)^k*(n-k)!,k=0..n)

Answer 2
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)
or any polynomial P(x), the coeff. of x^0 is P(0),
The coefficient of x^0 is the number of derargments of in the set permute(n)

#---------------------------------------------------
Question 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?

A166; i =0
A240; 1
A387; 2
A449; 3
A475; 4
A129135; 5
A129136; 6
A129149; 7

I guess I could keep going


#-----------------------------------
Question 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.



d(n) = n*d(n-1) +(-1)^n
d(n-1) = (n-1)*d(n-2) +(-1)^)n-1)
Adding both these equations
d(n)+d(n-1) = n*d(n-1) +(-1)^n +(n-1)*d(n-2) +(-1)^)n-1)
d(n) = (n-1)*d(n-1)+(n-1)*d(n-2) + (-1)^n + (-1)^(n-1)
Case 1: n is even then n-1 is odd hence -1^n = 1 and -1^(n-1) = -1 hence -1^n + (-1)^(n-1) is 0
Case 2: n-1 is even then n is odd hence -1^(n-1) = 1 and -1^(n) = -1 hence -1^n + (-1)^(n-1) is 0

hence d(n) = (n-1) * (d(n-1)+d(n-2))
As used to compute *successfully* by this maple code
derangement := proc(n) 
option remember; 
if n = 0 then 
return 0; 
end if; 
if n = 1 then 
return 0; 
end if; 
if n = 2 then return 1; 
end if; 
(n - 1)*(derangement(n - 1) + derangement(n - 2)); end proc