#OK to post homework #Kent Mei, 9/27/20, Assignment 6 #--------------------------------- #Part 1 #In practice the PIE is very inefficient. The number of terms using the PIE is 2^n where n is the number of sets so as the number of sets gets bigger, the number of terms gets exponentially bigger which is not easily handled by computers. #[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] #They give the same output. #time([seq(Pnx(n,x),n=1..8)]) = .328 #time([seq(PnxF(n,x),n=1..8)]) = 0 #Pnx(n,x) takes longer. #time([seq(PnxF(n,x),n=1..30)]) = 0.15e-1 #time([seq(Pnx(n,x),n=1..30)]) probably takes a really long time, like at least several hours if not even days. #--------------------------------- #Part 2 #D(n) is the constant term in PnxF(n,x) because we defined PnxF(n,x) such that the coefficient of x^i is the number of permutations of size n with exactly i fixed points. So, the constant term has to be the number of permutations of size n with no fixed points, which is the definition of what a derangement is. Thus, D(n) has to be the constant term in PnxF(n,x). #--------------------------------- #Part 3 #[seq(coeff(PnxF(n,x),x,i),n=0..12)] for i = 0,1,2,3,... #i = 0: A166 (derangements) #i = 1: No A number. #i = 2: A387 (Recontres numbers, exactly 2 fixed points) #i = 3: No A number. #i = 4: No A number. #i = 5: No A number. #Technically with how the command is defined, any i > 12 results in a sequence of 0s which is in the OEIS but not exactly what we're looking for. #If we look at the sequences starting from the first 1 in the sequence, the largest i for which there is a sequence in the OEIS is i = 12. #i = 0: A166 (derangements) #i = 1: A240 #i = 2: A387 (Recontres numbers, exactly 2 fixed points) #i = 3: A449 #i = 4: A475 #i = 5: A129135 #i = 6: A129136 #i = 7: A129149 #i = 8: A129153 #i = 9: A129217 #i =10: A129218 #i =11: A129238 #i =12: A129255 #--------------------------------- #Part 4 #SumTools[Hypergeometric][ZeilbergerRecurrence](binomial(n,k)*(-1)^k*(n-k)!,n,k,d,0..n); #Output: (-n-1)*d(n)+d(n+1) = -(-1)^n #Equivalently, d(n) = n*d(n-1) + (-1)^n #d(n) = n*d(n-1) + (-1)^n #d(n) = n*d(n-1) + (-1)^n + n*d(n-2) + d(n-2) - n*d(n-2) - d(n-2) #d(n) = n*d(n-1) + n*d(n-2) - d(n-2) + (-n*d(n-2) + d(n-2) + (-1)^n) #d(n) = n*d(n-1) + n*d(n-2) - d(n-2) - ((n-1)*d(n-2) + (-1)^(n-1)) #d(n) = n*d(n-1) + n*d(n-2) - d(n-2) - d(n-1) #d(n) = (n-1)*d(n-1) + (n-1)*d(n-2) #d(n) = (n-1) * (d(n-1) + d(n-2)) #which is the other reccurrence relation as desired. #--------------------------------- #Part 5 #A combinatorial proof of this recurrence is as follows: #Every permutation can be written in cycle-notation and since we are working with derangements, all the cycles have length 2 or more. #Assume we start off with the first element in the set {1,...,n}. For that element 1, it must be mapped to another element k in the set such that k != 1, so there are n - 1 choices for what 1 can be mapped to. #From there, there are two possible distinct cases. The first case is that k is not mapped to 1. Then the elements {2,...,n} each have 1 element in the set they cannot be mapped to which is equivalent to the case of finding derangements for n-1 elements. #The second case is that k is mapped to 1. In this case, the elements {2,...,k-1,k+1,...,n} each have 1 element in that set that they cannot be mapped to which is equivalent to the case of finding derangements for n-2 elements. #Taking all the facts together, we can see that the number of derangements must be d(n) = (n-1) * (d(n-1) + d(n-2)). #--------------------------------- #Part 6 #We proceed by induction. #We establish the base case. Assume x[S] = 1 when S is the empty set. #For n = 1, we have: #1 - x[1] = (-1)^0 * x[{}] + (-1)^1*x[{1}] #1 - x[1] = 1 - x[1] as desired. #Now, we proceed to the inductive step. #Assume that product(1-x[i], i=1..k)= Sum ((-1)^|S|*x[S],S subset of {1, ...,k}) #We need to show that product(1-x[i], i=1..k+1)= Sum ((-1)^|S|*x[S],S subset of {1, ...,k+1}). #product(1-x[i], i = 1..k+1) = (1 - x[k+1]) * product(1-x[i] , i = 1..k) # = (1 - x[k+1]) * Sum ((-1)^|S|*x[S],S subset of {1, ...,k}) # = Sum ((-1)^|S|*x[S],S subset of {1, ...,k} + (-x[k+1]) * Sum ((-1)^|S|*x[S],S subset of {1, ...,k} #4 = Sum ((-1)^|S|*x[S],S subset of {1, ...,k} + Sum ((-1)^(|S|+1)*x[S]*x[k+1],S subset of {1, ...,k} #5 = Sum ((-1)^|S|*x[S],S subset of {1, ...,k+1}) as desired. #To explain the transition from line 4 and line 5, consider T to be a subset of {1,...,k+1}. There are two cases, either T is also a subset of {1,...,k}, or T is (a subset of {1,...,k} union {k+1}). #The first case is represented by the first term on line 4. #The second case is represented by the second term on line 4. To get the terms where k+1 is an element of T, you have to add one to the cardinality to any given set S subset of {1,...,k} and multiply x[S] by x[k+1]. #Note that Product(1-Chi(u in A[i])),i = 1..k) for any u in U can evaluate to two possible answers. #If u is not in any of the A[i], the expression evaluates to 1 since it's a product of k 1s. #However, if u is in any of the A[i], the expression evaluates to 0 since any product including a 0 evaluates to 0. #So, the expression only evaluates to 1 when u is not in any A[i]. #If we take the sum of all the products for u in U, we're essentially adding 1 everytime there is an element not belonging to any of A[1],...,A[k] which is exactly the left side of the PIE. #Sum(Product(1-Chi(u in A[i]), i = 1..k) u in U) = Sum(Sum((-1)^|S|*Chi(u in A[i], i in S), S subset of {1,...,k}),u in U) # = Sum((-1)^|S|*Sum(Chi(u, in A[i], i in S), u in U), S subset of {1,...,k}) # = Sum((-1)^|S|*|intersection of A[i]|, i in S), S subset of {1,...,k}) # = - |A[1]| - |A[2]| - ... - |A[k]| # + |A[1] intersect A[2]| + |A[1] intersect A[3]| + ... + |A[k-1] intersect A[k]| # ... and so on.