> #Weiji Zheng, 09/27/2020, Assignment 6
> #OK to post homework
;
> 
;
> #Q1
;
> 
;
> Help6:=proc():print(` RSS(n,k,l), PIE(U,L), FP(pi), Pnx(n,x)  `): end:
> 
> with(combinat):
> 
;
> PIE:=proc(U,L) local a,b,i,SS,s:
> a:=nops(`intersect`(seq(U minus L[i],i=1..nops(L)))):
> 
> SS:=powerset(L) minus {{}}:
> 
> b:=nops(U):
> 
> for s in SS do
>  b:=b+(-1)^nops(s)*nops(`intersect`(op(s))):
> od:
> 
> [a,b]:
> end:
> PIE({1,2,3,4,5},{{1,2,3},{5}})
[1, 1]
;
> #Because PIE returns the number of the cardianltiy of the intersection of U\L[i] in two different ways, which only prove the answer gotten by the Principal of Inclusion-Exclusion is the same as what we get directly. It seems to have no useful meaning but satisfy our theoretical interest.
;
> 
;
> Pnx:=proc(n,x) local S,pi:
> S:=permute(n):
> add(x^FP(pi),pi in S):
> end:
> PnxF:=proc(n,x) local k:
> expand(add(binomial(n,k)*(x-1)^k*(n-k)!,k=0..n)):
> end:
> FP:=proc(pi) local i:
> coeff(add(evalb(pi[i]=i),i=1..nops(pi)),true,1):
> 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]
;
> [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]
;
> #Same
;
> time([seq(Pnx(n,x),n=1..8)]);
.328
;
> time([seq(PnxF(n,x),n=1..8)]);
0.
;
> #PnxF takes longer
;
> #Maybe it takes 1376592.082s to do time([seq(Pnx(n,x),n=1..30)]);
> 
;
> #Q2
;
> 
;
> PnxF(5,x)
x^5+10*x^3+20*x^2+45*x+44
;
> 
;
> Dn := n->n!*add((-1)^t/t!,t=0..n);
Dn := proc (n) local t; options operator, arrow; factorial(n)*add((-1)^t/factorial(t), t = 0 .. n) end proc
;
> Dn(5)
44
;
> #Because PnxF uses not the thinking of directly compute it, but uses the Principle of Inclusion-Exclusion, which need to expand x with the derargment of n object.
;
> 
;
> #Q3
;
> 
;
> [seq(coeff(PnxF(n,x),x,1),n=0..12)]
[0, 1, 0, 3, 8, 45, 264, 1855, 14832, 133497, 1334960, 14684571, 176214840]
;
> [seq(coeff(PnxF(n,x),x,2),n=0..12)]
[0, 0, 1, 0, 6, 20, 135, 924, 7420, 66744, 667485, 7342280, 88107426]
;
> [seq(coeff(PnxF(n,x),x,3),n=0..12)]
[0, 0, 0, 1, 0, 10, 40, 315, 2464, 22260, 222480, 2447445, 29369120]
;
> [seq(coeff(PnxF(n,x),x,4),n=0..12)]
[0, 0, 0, 0, 1, 0, 15, 70, 630, 5544, 55650, 611820, 7342335]
;
> [seq(coeff(PnxF(n,x),x,5),n=0..12)]
[0, 0, 0, 0, 0, 1, 0, 21, 112, 1134, 11088, 122430, 1468368]
;
> [seq(coeff(PnxF(n,x),x,6),n=0..12)]
[0, 0, 0, 0, 0, 0, 1, 0, 28, 168, 1890, 20328, 244860]
;
> [seq(coeff(PnxF(n,x),x,7),n=0..12)]
[0, 0, 0, 0, 0, 0, 0, 1, 0, 36, 240, 2970, 34848]
;
> [seq(coeff(PnxF(n,x),x,8),n=0..12)]
[0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 45, 330, 4455]
;
> [seq(coeff(PnxF(n,x),x,9),n=0..12)]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 55, 440]
;
> [seq(coeff(PnxF(n,x),x,10),n=0..12)]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 66]
;
> [seq(coeff(PnxF(n,x),x,11),n=0..12)]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0]
;
> [seq(coeff(PnxF(n,x),x,12),n=0..12)]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
;
> [seq(coeff(PnxF(n,x),x,13),n=0..12)]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
;
> #A number is A010815 for i >= 12
;
> [seq(coeff(PnxF(n,x),x,100000),n=0..12)]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
;
> #the largest i for this sequence in the OEIS seems to be infinity since there are always totally zero when i >= 12
;
> 
;
> #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(2) = 2*d(1) +1
;
> #d(3) = 3*d(2) -1
;
> #d(4) = 4*d(3) +1
;
> #d(5) = 5*d(4) -1
;
> #Assume d(1)=1, then we have seq {1,3,8,33,164...} search on OEIS I get A001120,a(0) = a(1) = 1; for n > 1, a(n) = n*a(n-1) + (-1)^n.
;
> #Then I found the recurrence relation a(n) = (n-1)*(a(n-1)+a(n-2)), n>2
;
> 
;