> #Please do not post
;
> #Yifan Zhang, hw6, 09/27/2020
;
> 
;
> with(combinat):
> #Q1.
;
> #because PIE is the principle of inclusion-exclusion
;
> FP:=proc(pi) local i:
> coeff(add(evalb(pi[i]=i),i=1..nops(pi)),true,1):
> end:
> Pnx:=proc(n,x) local S,pi:
> S:=permute(n):
> add(x^FP(pi),pi in S):
> end:
> [seq(Pnx(n,x),n=1..7)];
[x, x^2+1, x^3+3*x+2, x^4+6*x^2+8*x+9, x^5+10*x^3+20*x^2+45*x+44, x^6+15*x^4+40
*x^3+135*x^2+264*x+265, x^7+21*x^5+70*x^4+315*x^3+924*x^2+1855*x+1854]

;
> PnxF:=proc(n,x) local k:
> expand(add(binomial(n,k)*(x-1)^k*(n-k)!,k=0..n)):
> end:
> [seq(PnxF(n,x),n=1..7)]
[x, x^2+1, x^3+3*x+2, x^4+6*x^2+8*x+9, x^5+10*x^3+20*x^2+45*x+44, x^6+15*x^4+40
*x^3+135*x^2+264*x+265, x^7+21*x^5+70*x^4+315*x^3+924*x^2+1855*x+1854]

;
> evalb([seq(Pnx(n,x),n=1..7)] = [seq(PnxF(n,x),n=1..7)]);
true

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

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

0.

;
> #Pnx() takes longer
;
> time([seq(PnxF(n,x),n=1..30)]);
.16e-1

;
> #so time([seq(Pnx(n,x),n=1..30)]) should be much larger.
;
> 
;
> 
;
> 
;
> #Q2. 
;
> for any polynomial P(x), the coefficient of x^0 is P(0) which is constant. 
;
> 
;
> 
;
> 
;
> #Q3.
;
> [seq(coeff(PnxF(n,x),x,0),n=0..12)]
[1, 0, 1, 2, 9, 44, 265, 1854, 14833, 133496, 1334961, 14684570, 176214841]

;
> #A1066
;
> 
;
> [seq(coeff(PnxF(n,x),x,1),n=0..12)]
[0, 1, 0, 3, 8, 45, 264, 1855, 14832, 133497, 1334960, 14684571, 176214840]

;
> #no A number
;
> 
;
> [seq(coeff(PnxF(n,x),x,2),n=0..12)]
[0, 0, 1, 0, 6, 20, 135, 924, 7420, 66744, 667485, 7342280, 88107426]

;
> #A387
;
> 
;
> [seq(coeff(PnxF(n,x),x,3),n=0..12)]
[0, 0, 0, 1, 0, 10, 40, 315, 2464, 22260, 222480, 2447445, 29369120]

;
> #no A number
;
> 
;
> [seq(coeff(PnxF(n,x),x,3),n=0..12)]
[0, 0, 0, 1, 0, 10, 40, 315, 2464, 22260, 222480, 2447445, 29369120]

;
> #no A number
;
> 
;
> #The greatest i is 13. After i > =13, all element of the list should be 0.
;
> 
;
> 
;
> 
;
> #Q4.
;
> SumTools[Hypergeometric][ZeilbergerRecurrence](binomial(n,k)*(-1)^k*(n-k)!,n,k,d,0..n)
(-n-1)*d(n)+d(n+1) = -(-1)^n

;
> #d(n+1) = -1(-1)^n-(-n-1)*d(n)
;
> #d(n) = -1(-1)^(n-1)-(-n-2)*d(n-1) 
;
> #=> -1(-1)^(n-1) = d(n)+(-n-2)*d(n-1)
;
> #=> (-1)^n = d(n)+(-n-2)*d(n-1)
;
> #d(n+1) = -(d(n)+(-n-2)*d(n-1)) -(n-1)*d(n)
;
> #d(n+1) = -d(n) - (-n-2)*d(n-1) - (n-1) *d(n)
;
> #d(n+1) = -n*d(n) + (n+2)*d(n-1) 
;
> 
;
> 
;
> 
;