#OK to post homework
#TaerimKim,9/26/2020,Assignment 6

#1.
#PIE is an powerful tool to prove a lot of useful mathematic theorems; However, 
#solving problems with PIE itself is very inefficient due to its tedious and slow 
#process. So, we are mostly interested in its theoretical aspect. 
evalb([seq(Pnx(n, x), n = 1 .. 7)] = [seq(PnxF(n, x), n = 1 .. 7)]);
                              true 
#From understanding the logical process of Pnx and PnxF, we know that they
#produce the same sequence but Pnx search by expanding the whole sets, which
#will take tremendous time in large n.

time([seq(Pnx(n, x), n = 1 .. 8)]);
                             0.717
time([seq(PnxF(n, x), n = 1 .. 8)]);
                               0.
#the time command shows us that PnxF is faster as it takes less than 0. second 
#to process

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

#when n becomes greater, the time difference becomes immense.
#My prediction of time for Pnx on n = 1 .. 30 is practically impossible
#to process.


#2.
#This is because the formula Pnx(n,x) notes that for x^0, coefficient is the # of 
#permutation that has 0 fixed point, in other words, # of derangement. So, 
#intuitively, D(n) should be the constant for Pnx formula


#3. 
#A166 for i=0
#A387 for i=2
#for higher i's there is no matching sequence and above i=12, the set converges 
#to numerous 0's, which are fragments of largers sequence but not the sequence 
#itself. So, i=2 is the highest i that gives us the complete Sequence and above i=
#12, we do not get any significant matching sets.

#4.
#From the given formula
#d(n)=nd(n-1)+(-1)^n: then,
#d(n-1)=(n-1)d(n-2)+(-1)^(n-1):
#we can use the idea that (-1)^n is equal to -(-1)^n-1
#then, d(n) = nd(n-1)+(-(d(n-1)-(n-1)d(n-2))):
#=(n-1)d(n-1)+(n-1)d(n-2)
#=(n-1)(d(n-1)+d(n-2)
#So, d(n) = (n-1)*(d(n-1) + d(n-2)); QED