#OK to post
# Soham Palande, Assignment 6, 09/27/2020


# PART 1
# The principle of inclusion exclusion (PIE) is only of theoretical interest because it helps us to prove other 
# theorems and identities. Otherwise, it is much easier to directly compute the elements of the intersection of 
# the complement of the subsets of some universal set U because PIE is computationally expensive- If we have k 
# sets, we need 2^k terms which has an exponential runtime. 

[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]
The commands give the same output.

time([seq(Pnx(n,x),n=1..8)]);
	#.312
time([seq(PnxF(n,x),n=1..8)]);
	#0.
# The procedure Pnx(n,x) takes longer than PnFX(n,x)

time([seq(PnxF(n,x),n=1..30)]);
	#0.15e-1
# time([seq(Pnx(n,x),n=1..30)]); will take very long!

# PART 2
# The procedure PnxF(n,x) gives a polynomial of degree n in terms of a variable x where the coefficient of x^i is 
# the number of permutations with exactly i fixed points. Thus the coefficient of x^(0) gives the number
# of permutations with 0 fixed points i.e. the number of derangements of {1,..n}. Since D(n) gives the number
# of derangements of n objects, and hence D(n) is the coefficient of the constant term in PnxF(n,x).


#PART 3
#[seq(coeff(PnxF(n,x),x,0),n=0..12)] : A000166
#[seq(coeff(PnxF(n,x),x,1),n=0..12)] :DNE
#[seq(coeff(PnxF(n,x),x,2),n=0..12)] : A000387
# The largest i for which there is a sequence in the OEIS is i=2.


#PART 4

SumTools[Hypergeometric][ZeilbergerRecurrence](binomial(n,k)*(-1)^k*(n-k)!,n,k,d,0..n);
	# (-n-1)*d(n)+d(n+1) = -(-1)^n

# The other recurrence that Euler proved was d(n) = (n-1)*(d(n-1) + d(n-2))

#PART 5