#OK to post homework
#Sam Minkin, 9/27, Assignment 6

Problem 1:

The principle of inclusion and exclusion has been used in proving a lot of theorems and lemma. As a result, it had a lot of theoretical use and became in popular use by theoretical combinatorics professors.

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

Time to run...
time([seq(Pnx(n, x), n = 1 .. 8)]);
                             0.515

Time to run...
time([seq(PnxF(n, x), n = 1 .. 8)]);
                               0.

It was much faster using PnxF.

Time to...
time([seq(PnxF(n, x), n = 1 .. 30)]);
                             0.031

In Pnx, we compute all of the permutations of 1,..,n. We have proved that the number of permutations is n!, so I would expect that this algorithm runs proportionally to n!. For n = 8, time([seq(Pnx(n, x), n = 1 .. 8)]) ran in 0.515 seconds -> 0.515 = k*(8!) -> k = 1.27728x10^-5. So, we would expect for n=30 to run in k*(30!) = 3.388x10^27 seconds.


Problem 2:

When i = 0, we get the coefficient equal to the number of permutations with exactly i fixed points. But since i = 0 in this case, we have the definition of derangement. Therefore, we would expect the coefficient for x^i = x^0 would be equal to the number of derangement of n objects.


Problem 3:

For i=0:
We have the sequence:
[1, 0, 1, 2, 9, 44, 265, 1854, 14833, 133496, 1334961, 14684570, 176214841]
The corresponding A number is A000166.

For i=1:
We have the sequence:
[0, 1, 0, 3, 8, 45, 264, 1855, 14832, 133497, 1334960, 14684571, 176214840]
There is no A number.

For i=2:
We have the sequence:
[0, 0, 1, 0, 6, 20, 135, 924, 7420, 66744, 667485, 7342280, 88107426]
The corresponding A number is A000387
This is also the highest i which produces a sequence that has an A number in OEIS.


Problem 4:

We have, d(n) = n*d(n-1) + (-1)^n
d(n-1) = (n-1)*d(n-2) - (-1)^n
d(n-2) = (n-2)*d(n-3) + (-1)^n

Plugging in d(n-1) into the first equation we get:
d(n) = n*( (n-1)*d(n-2) - (-1)^n ) + (-1)^n.

Adding this equation to the first equation will allow use to relate d(n) to d(n-1) and d(n-2).

d(n) = 0.5 * (n*d(n-1) + (-1)^n + n*((n-1)*d(n-2) - (-1)^n) + (-1)^n) =
0.5*n*(d(n-1) + (n-1)d(n-2)) + (-1)^n.