#Ok to post homework
#Tifany Tong, September 27th, 2020, HW #6

# Question 1
# PIE is usually only of theoretical interest because for example, if you have 100 specific sets and you want to find the number of elements
# in the unions, then it is not efficient to use PIE. It is better to use something like Maple to get the unions and then find the number
# of elements. There are 2^100 terms if you use PIE. When we have structured sets with explicit formulas and applications, then we will
# use PIE. 

# [seq(Pnx(n,x),n=1..7)] and [seq(PnxF(n,x),n=1..7)] give you the same output. 
# time([seq(Pnx(n,x),n=1..8)]) and time([seq(PnxF(n,x),n=1..8)]) do not give you the same output. I get 0.468 for time([seq(Pnx(n, x), n = 1 .. 8)]).
# For time([seq(PnxF(n, x), n = 1 .. 8)]), I get 0. 

# For time([seq(PnxF(n,x),n=1..30)]), I get 0.031. I estimate that time([seq(Pnx(n,x),n=1..30)]) will take significantly longer because it already 
# takes 0.468 seconds for n = 1..8. In PnX, all the permutations are created, which is very time consuming.  

# Question 2

# P(0)= Coeff. of x^0 in P(x) because when x = 0, all the all other terms will cancel out because you are multiplying all other terms by
# some factor of x. Thus, the only term that will remain is the one that doesn't involve x (the x^0 term). 


# Question 3

#[seq(coeff(PnxF(n, x), x, 0), n = 0 .. 12)] =
#[1, 0, 1, 2, 9, 44, 265, 1854, 14833, 133496, 1334961, 14684570, 176214841] --> A166


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


#[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] --> A449


#[seq(coeff(PnxF(n, x), x, 4), n = 0 .. 12)] = 
# [0, 0, 0, 0, 1, 0, 15, 70, 630, 5544, 55650, 611820, 7342335] --> A475

#[seq(coeff(PnxF(n, x), x, 5), n = 0 .. 12)] =
#  [0, 0, 0, 0, 0, 1, 0, 21, 112, 1134, 11088, 122430, 1468368] --> A129135

#[seq(coeff(PnxF(n, x), x, 6), n = 0 .. 12)] =
#     [0, 0, 0, 0, 0, 0, 1, 0, 28, 168, 1890, 20328, 244860] --> A129136

#[seq(coeff(PnxF(n, x), x, 7), n = 0 .. 12)] =
#       [0, 0, 0, 0, 0, 0, 0, 1, 0, 36, 240, 2970, 34848] --> A129149

#[seq(coeff(PnxF(n, x), x, 8), n = 0 .. 12)] =
#         [0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 45, 330, 4455] --> A129153

#[seq(coeff(PnxF(n, x), x, 9), n = 0 .. 12)] =
#           [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 55, 440] --> A129217

#[seq(coeff(PnxF(n, x), x, 10), n = 0 .. 12)] =
#            [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 66] --> A129218

#[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]

# The largest i for which there is a sequence in the OEIS is 10. The rest don't exist or show up in other unrelated
# sequences. 

# Question 4

# d(n) = n*d(n-1) - (-1)^(n-1)
# d(n-1) = (n-1)*d(n-2) - (-1)^(n-2) 

# d(n) - n*d(n-1) - (-1)^(n-1) = d(n-1) - (n-1)*d(n-2) - (-1)^(n-2)
# d(n) = n * d(n-1) + d(n-1) - (n-1)*d(n-2) + (-1)^(n-1) - (-1)^(n-2)
# d(n) = (n+1) * d(n-1) - (n-1)*d(n-2) + (-1)^(n-2)[(-1) - 1] 
# d(n) = (n+1)*d(n-1) - (n-1)*d(n-2) - 2(-1)^(n-2)