#Please do not post this exam #Ravali Bommanaboina # Final for Math 454(2), Fall 2020, Dr. Z. #Start: Dec. 15, 9:00am #Due: Dec. 16, 9:00am. EMAIL to ShaloshBEkhad@gmail.com #Subject: ComboFinal #with an attachment called #ComboFinalFirstLast.txt: e.g. ComboFinalDoronZeilberger.txt (PLEASE observe capitalization) #INDICATE WHETHER IT IS OK to POST YOUR TEST #Each bunch of problems is with increasing difficulty. Full answers to all parts (a) would be needed to pass the class with a C #(provided that all the homework, attendance quizzes and projects have been submitted). Parts (b),(c), (d), ... are more challenging. #Some of the (harder) problems may require coding. Some of the problems are really challenging, and I don't expect #every one to do all of them (even the A students). #YOU CAN USE Maple, of course, the Lectures, Maple code, posted solutions, and more generally the internet, EXCEPT #you have to do it by yourself, and EXPLAIN EVERYTHING! #FIRST DO THE (a) questions, then the (b) questions, etc., so you won't run out of time. #1. #Functions were used from ComboProject3.txt (a) In how many ways can you walk from [0,0,0] to [30,25,20] where the allowed steps are [1,0,0] or [0,1,0], or [0,0,1] # This is the number of walks from [0,0,0] to [a,b,c]. (a+b+c)!/(a!*b!*c!) = (30+25+20)! / (30!*25!*20!) # We devide by the factorials to avoid duplicate paths. # NuW([30, 25, 20], {[0, 0, 1], [0, 1, 0], [1, 0, 0]}); -> 2478456799816702091914145225486880 # 2478456799816702091914145225486880 # (b) In how many ways can you walk from [0,0,0] to [30,25,20] where the allowed steps are [1,0,0] or [0,1,0], or [0,0,1] # and you MUST stay in the region x>=y>=z # NuGW([30, 25, 20], {[0, 0, 1], [0, 1, 0], [1, 0, 0]}); -> 41512613892711511465063226481480 # 41512613892711511465063226481480 $ [Hint: this is part of the 3D ballot problem, you are welcome to look it up.] # # (c) In how many ways can you walk from [0,0,0] to [30,25,20] where the allowed steps are [1,0,0] or [0,1,0],[0,0,1], [1,1,1], or [2,2,2] # NuW([30, 25, 20], {[0, 0, 1], [0, 1, 0], [1, 0, 0], [1, 1, 1], [2, 2, 2]}); -> 31831650298097356165593942880232160 # (d) In how many ways can you walk from [0,0,0] to [30,25,20] where the allowed steps are [1,0,0] or [0,1,0],[0,0,1], [1,1,1], or [2,2,2] # and you must stay in x>=y Union x>=z (but y and z can be anything as long as they are both <=x) # NuBW(Pt,A) works like the function NuGW(Pt,A) however instead of staying within x>=y>=z # this function returns paths that must stay within x>=y Union x>=z NuBW:=proc(Pt,A) local a: option remember: if (Pt[1]<0 or Pt[2]<0 or Pt[3]<0 or Pt[1] 3818966446210163616599115660989544 # (e) In how many ways can you walk, in the k-dimensional hyper-cubic lattice (the k-DIm Manhattan) from [0,0,..., 0] (with k 0's) to # [n,n,....n] (with k n's) always staying in the region x[1]>=x[2]>=... >=x[k]. For example with n=1 there is only one way # [0,0,...0]->[1,0,...0]->[1,1,0,...]->...->[1,1,1,1,1] # Give an explicit formula in terms of n and k. #2. (a) How many words in the alphabet {0,1,2,3} are there of length 30? # Since there are 4 different numbers we can do 4^30 # This equals 1152921504606846976 which is the number of words in the alphabet {0,1,2,3} of length 30. # (b) How many words in the alphabet {1,2,3,4} are there that add-up to 300? # (c) How many words are there in the alphabet {1,2,3,....} (all positive integers) that add-up to n? For general n. Give an explicit formula. # (d) Let a(n) be the number of words in the alphabet {1,4,7,10,....} (all positive integers that give remainder 1 when divided by 3) # that add-up to n. Find an explicit expression for # Sum(a(n)*x^n,n=0..infinity) # (e) Let a(n) be as in (d). What is the limit of a(n+1)/a(n) as n goes to infinity. #3.Functions used were from M20.txt # (a) What is the egf enumerating set-partitions. # exp(exp(x)-1) # How many are there of the set {1,2,...,51}? # Bell3(51); -> # 3263983870004111524856951830191582524419255819477 # (b) What is the egf enumerating set partitions where the number of components belongs to {1,4,7,10,...}, # but the components themselves can be of any (positive, of course) size. # # How many are there of the set {1,2,...,51}? # Bell3(151) -> # 276951220131838602763225769474305251685659064788401763614316690685042911767559610923922889755393743966265915125237481780225696695885837687199121628988946212139343871299182815816808884049980402941 #(c) What is the egf enumerating set partitions where the number of components can be any non-negative integer # but the components themselves must be of odd size. # How many are there of the set {1,2,...,51}? #(d) What is the egf enumerating set partitions are there where the number of components belongs to {1,4,7,10,... and # and the components themselves must be of odd size. # How many are there of the set {1,2,...,51}? #4. Define a super-set-partition of order 2 to be a set of set partitions {P1,P2, ...,Pk} where k can be any positive integer and # P1,P2,..., Pk are set partitions such that the labels in each of P1,P2,..,Pk are all different and altogether there # n members. For example {{{2,4},{6}}, {{1},{5},{3}}} is such a creature with n=6, as is {{1}}, {{2}},{{3}},{{4}},{{5}},{{6}}}, # and many others. Let s[2](n) be the number of such creatures. # (a) Write all super-set partitions with n=3. # There are 5 Super-set partitions when n=3 # {{1}},{{2}},{{3}} # {{1},{2}},{{3}} # {{1},{3}},{{2}} # {{2},{3}},{{1}} # {{1},{2},{3}} # (b) What is Sum(s[2](n)*x^n/n!, n=0..infinity)? Is s[2](n) in the OEIS? # Sum(s[2](n)*x^n/n! is the recurrence and can be used to find the number of set partitions # s[2](n) is in OEIS it is the Bell or exponential numbers # The A-number is A000110 # (c) Define a super-set-partition of order m to be a set of set-partitions of order m-1 all with different labels such that total of # individuals is n. Let s[m](n) be the number of such creatures. What is the smallest m for which it is NOT in the OEIS? # Bell numbers 0..12 where m=2 # 1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, 678570, 4213597 # For m=3 we added all previous of bell numbers to get the nth term of for m=3 # seq(add(seq(Bell3(i), i = 0 .. j)), j = 0 .. 10); -> # 1, 2, 4, 9, 24, 76, 279, 1156, 5296, 26443, 142418 # The above sequence is in OEIS and its A-number is A005001 # m=4 seq(add(seq(add(seq(Bell3(i), i = 0 .. j)), j = 0 .. k)), k = 0 .. 10); -> # 1, 3, 7, 16, 40, 116, 395, 1551, 6847, 33290, 175708 # A-number for the above sequence is A029761 # m=5 seq(add(seq(add(seq(add(seq(Bell3(i), i = 0 .. j)), j = 0 .. k)), k = 0 .. p)), p = 0 .. 10); # 1, 4, 11, 27, 67, 183, 578, 2129, 8976, 42266, 217974 # This sequence is not in OEIS so the smallest m=5 #5. (a) How many integer partitions are there of 1000? # Maple Lecture 24 # pnFast(1000); -> # 24061467864032622473692149727991 # (b) How many integer partitions of 1000 are there where all the parts are odd? # Maple Lecture 24 # pnOddSeq(1000)[1000]-> # 8635565795744155161506 # (c) How many integer partitions of 1000 are there where all the parts are different than each other? # The number of partitions of 1000 where all the parts are odd is the same as the number of partitions of 1000 using distinct parts. # Maple Lecture 24 # pnOddSeq(1000)[1000]-> # 8635565795744155161506 # (d) How many integer partitions of 1000 are there where all the parts are different than each other and all the parts are odd. # The number of partitions of 1000 where all the parts are odd is the same as the number of partitions of 1000 using distinct parts. # Maple Lecture 24 # pnOddSeq(1000)[1000]-> # 8635565795744155161506 #6. (a) How many rooted labelled trees are there with 31 vertices? # Maple lecture 22 TreeSeq # 17761887753093897979823770061456102763834271 # (b) How many rooted labelled trees are there with 31 vertices where the root has exactly two children. # Maple lecture 22 TreeSeq # 17761887753093897979823770061456102763834271 # All rooted labelled trees with 31 vertices must have exactly 2 children at the root or else it would not have 31 vertices. # (c) How many rooted labelled trees are there with 31 vertices where each vertex must have either zero, one, three, or four children. # There can only be 1 tree where all vertices have either zero or one because you can have at most 2 children per vertex. # Since 2 children is excluded from the list we only have 1 tree which is shaped like a string of vertices. # (d) How many rooted labelled trees are there with 31 vertices where each vertex can have any number of children (including no children, of course) # # EXCEPT that it can't have one, three, or four children. # Maple lecture 22 TreeSeq # 17761887753093897979823770061456102763834271 #7. A complete (unlabelled, ordered) BINARY tree is defined recursively by # T= [] (denoting a single vertex, just the root) or otherwise # T=[T1,T2] # where T1, T2, are smaller such creatues. Let BT(n) be the number of such creatues with n leaves. For example #BT(1)= {[]}; BT(2)={[[],[]]}; BT(3)= {[[], [[], []]], [[[], []], []]} . # (a) Either by hand, or with Maple, find BT(4). # BT(4) # 5 possible binary trees # 1st tree # [[[],[]],[[],[]]] # 2nd tree # [[],[[],[[],[]]]] # 3rd tree # [[[[],[]],[]],[]] # 4th tree # [[[],[[],[]]],[]] # 5th tree # [[],[[[],[]],[]]] # BT(4) = {[[[],[]],[[],[]]],[[],[[],[[],[]]]],[[[[],[]],[]],[]],[[[],[[],[]]],[]],[[],[[[],[]],[]]]} # (b) Let b(n) be the number of complete binary trees with n leaves. For example b(1)=1, b(2)=1, b(3)=2. Let # B(x)=Sum(b(n)*x^n,n=0..infinity) # Prove that # B(x)=x+ B(x)^2