#OK to post homework #Karnaa Mistry, 09/27/20, Assignment HW #6 with(combinat): # 1. # PIE is (usually) only of theoretical interest because implementing the PIE method for larger and larger numbers # of sets becomes too much to handle, and it becomes easier to have a computer determine all those sets, and find # the intersections, unions, complemenets, etc. and give the answer, rather than go through the concepts of # PIE, which is really only manageable for smaller numbers of sets (2,3,4, etc.). # [seq(Pnx(n,x),n=1..7)] & [seq(PnxF(n,x),n=1..7)] do give the same output # time([seq(Pnx(n,x),n=1..8)]); gives 0.390 (running Pnx takes longer) # time([seq(PnxF(n,x),n=1..8)]); gives 0. (essentially no time at all) # time([seq(PnxF(n,x),n=1..30)]); gives 0. as well # plotting the resultant times for n=7,8,9,10 logarithmically base 10 gives a (relatively) linear curve, so if we project # for n = 30, it's possible that time([seq(Pnx(n,x),n=1..30)]); would be at LEAST 10^30 seconds, though it may be # significantly more than that. All in all, it'll be a very, very, very, very, very long time. # 2. # D(n) is the constant term in PnxF(n,x) because by the definition of Pnx(n,x) (and thus PnxF(n,x), too), it gives the # polynomial in x of degree n whose coefficients of x^i is the number of permutations with exactly i fixed points. # We know derangements have 0 fixed points, and so i = 0 gives us the coefficient of x^0 (the constant term). # Furthermore, the formula add(binomial(n,k)*(-1)^k*(n-k)!,k=0..n) is close to the formula of PnxF, which is # add(binomial(n,k)*(x-1)^k*(n-k)!,k=0..n). The difference is that for the derangements, x = 0 eliminates all # x terms with nonzero powers in our polynomial expansion. Substituting x = 0 for the formula in PnxF(n,x) gives # our D(n) formula, and so the derangements does not depend on x, since x = 0 isolates the constant term for us. # 3. # (Some are found by omitting the first i 0's of the sequence, and some need n to be larger to preserve uniqueness) # i = 0 => A000166 # i = 1 => A000240 # i = 2 => A000387 # i = 3 => A000449 # i = 4 => A000475 # i = 5 => A129135 # i = 6 => A129136 # i = 7 => A129149 # i = 8 => A129153 # i = 9 => A129217 # i = 10 => A129218 # i = 11 => A129238 # i = 12 => A129255 # It seems that i = 12 is the largest i for which there is a sequence in the OEIS # 4. # Show that d(n) = n*d(n-1) + (-1)^n IMPLIES d(n) = (n-1)*d(n-1) + (n-1)*d(n-2) # Note that d(n) = n*d(n-1) + (-1)^n, d(0) = 1 (definition of d(n)) # d(n) - n*d(n-1) = (-1)^n (subtracting n*d(n-1) from both sides of d(n)) # d(n-1) - (n-1)*d(n-2) = (-1)^(n-1) = -(-1)^n (substitution of n-1 for n) # Find a homogenous recurrence also satisfied by d(n) # (-1)^n + (-(-1)^n) = 0 (achieve 0 in the RHS) # d(n) - n*d(n-1) + d(n-1) - (n-1)*d(n-2) = 0 (substitution) # d(n) = n*d(n-1) - d(n-1) + (n-1)*d(n-2) (isolate d(n)) # d(n) = (n-1)*d(n-1) + (n-1)*d(n-2) (factor d(n-1) out from n*d(n-1) - d(n-1)) # We have successfully obtained d(n) = (n-1)*d(n-1) + (n-1)*d(n-2) using d(n) = n*d(n-1) + (-1)^n # 5. (optional) attempt # If we take a particular value of n, we are dealing with permutations of {1,2,3,...,n}, and to achieve d(n), # we may imagine assigning the first element (say, "1") and choose it to map to the position of another # element other than itself in the permutation - this way, it will not be a fixed point. There are n-1 ways # to assign 1 to another position posA, following derangement restrictions. As for the element whose position # was posA, there are also n-1 positions that this element can be assigned to. # However, it would be easier if this element was assigned to 1's former position, because then that guarantees # no violation of the derangement restrictions, and leaves us with d(n-2) ways to arrange the rest (the number # of derangements of n-2 elements), since the position of 1 and posA are taken care of. If the element whose position was # posA was not assigned to 1's former position, there are d(n-1) possibilities afterward, since we have to # consider where the position of the element displaced by the posA element will be, as to adhere to the # derangement restrictions. # So, by multiplication of choices, we have (n-1)*d(n-2) possibilities for the first case plus (n-1)*d(n-1) # possibilities for the second case = (n-1)*d(n-1) + (n-1)*d(n-2). # 6. (optional) attempt # A. # Q(n): "if x[1], ..., x[n] are any numbers (or symbols), product(1-x[i], i=1..n) = Sum ((-1)^|S|*x[S],S subset of {1, ...,n}) # where x[S]=Product (x[s], s in S)" # Prove: Q(1) & [Q(n) => Q(n+1)] => Q(n) is true for all n >= 1. # Base case: # Q(1) just has x[1] as a symbol, and so product(1-x[1]) = sum((-1)^|S|*x[S],S as {} and {1}) # This just simplifies to 1-x[1] = (-1)^|0|*x[{}] + (-1)^|{1}|*x[{1}] => 1-x[1] = 1+(-1)*x[1] # Since both sides are equal, the base case Q(1) is true. # Inductive Step: # Assume Q(n) to find truth in Q(n+1), so assume "product(1-x[i], i=1..n = sum((-1)^|S|*x[S],S subset of {1, ...,n})" is true. # **NOTE** From direct substution, Q(n+1) should be "product(1-x[i], i=1..n+1 = sum((-1)^|S|*x[S],S subset of {1, ...,n+1})" # For the LHS, welcoming an (n+1)th element just multiplies the LHS by 1-x[n+1]. # For the RHS, welcoming an (n+1)th element adds sum((-1)^|T|*x[T],T subset of {1, ...,n+1} MINUS (subsets of {1,...,n})) to # the existing sum, because only new subsets should be added and counted (those subsets that include element n+1). # We want the element of summation for the RHS to match between the nth and (n+1)th scenarios. # |T| = 2^(n+1) - |S| = 2^(n+1) - 2^n = 2^n # Because |T| = |S|, (-1)^|T| = (-1)^|S|, and so this part of the summation already matches. # As for x[T], this is product(x[t], t in T), and since T is a subset of {1,...,n+1} MINUS (subsets of {1,...,n}), and t is # a subset of T, it is not possible for t to overlap with any s subset of S. # Since the RHS will have a seamless addition to the summation, we can rewrite it as sum((-1)^|S|*x[S],S subset of # {1, ...,n+1}) because T UNION ((subsets of {1, ...,n+1}) MINUS (subsets of {1,...,n})) gives our S from the **NOTE** line. # So: product(1-x[i], i=1..n)*(1-x[n+1]) = product(1-x[i], i=1..n+1) # And: sum((-1)^|S|*x[S],S subset of {1,...,n})+sum((-1)^|T|*x[T],T subset of {1,...,n+1} MINUS (subsets of {1,...,n}) # = sum((-1)^|S|*x[S],S subset of {1, ...,n+1}) # Since we assumed Q(n), we have obtained our Q(n+1) from substitution by conceptually adding the (n+1)th terms for both # sides. So, Q(n) --> Q(n+1). # Since the base case and inductive step are true, Q(n) is true for all n >= 1. # B. # It seems that 1-Chi(a in A[i]) evaluates to 0 if a is in A[i], and so Product(1-Chi(a in A[i])),i=1..k) evaluates to 0 # if any particular a is in A[i], since 0 times any quantity is 0. So, for a particular u in U, if any element u shared # is in any of the A's, that u is not counted (evaluates to 0). Only adding 1 whenever Chi(a in A[i]) is false will sum # 1 for each of the elements in U that are not in any of the A's. So, this will give us the exact number of elements in # U that do not belong to any of A[1],...,A[k]. # Sum(Product(1-Chi(a in A[i])),i=1..k), u in U) = # 0th line: |U| # 1st line: - (|A1| + ... + |Ak|) # 2nd line: + (|A1 intersect A2| + ... + |A[i1] intersect A[i2]| + ...) 1 <= i1 < i2 <= k # 3rd line: - (|A1 int A2 int A3| + ... + |Ai1 int Ai2 int Ai3| + ...) 1 <= i1 < i2 < i3 <= k # ... # rth line (-1)^r * (Sum(Ai1 int Ai2 int ... int Air, 1<=i1