#it is ok to post #Dec/16/2020 #1 #(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 basic walks using the atomic steps, thus the best way is to use the explicit formula for this matter #given a=30; b=25; c=20 #answer:= (a+b+c)!/(a!*b!*c!) ((30+25+20)!/(30!*25!*20!)) 2478456799816702091914145225486880 #answer: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 #Another basic problem, #This is easily achieved with NuGW NuGW([30,25,20],{[1,0,0],[0,1,0],[0,0,1]}) 41512613892711511465063226481480 #answer:41512613892711511465063226481480 #(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] #With no "Good" walk conditions, it's best to use NuW NuW([30,25,20],{[1,0,0],[0,1,0],[0,0,1],[1,1,1],[2,2,2]}) 31831650298097356165593942880232160 #answer: 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] 4 #and you must stay in x>=y Union x>=z (but y and z can be anything as long as they are both <=x) #for this, we tweek the procedure NuGW to give a new condition #NuGWf(Pt,A): NuGWf:=proc(Pt,A) local a: option remember: if (Pt[1]<0 or Pt[2]<0 or Pt[3]<0 or Pt[1]y and x>z RETURN(0): elif Pt=[0,0,0] then RETURN(1): else add(NuGWf(Pt-a,A),a in A): fi: end: NuGWf([30,25,20],{[1,0,0],[0,1,0],[0,0,1],[1,1,1],[2,2,2]}) 3818966446210163616599115660989544 #To check we know that NuGWf will be bigger since we lessen the condition. so lets compare with NuGW NuGW([30,25,20],{[1,0,0],[0,1,0],[0,0,1],[1,1,1],[2,2,2]}) 702157829467026190582908694797444 #we can see that NuGWf has 1 digit bigger, which means it follows the assumption #answer: 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] #since we have n^k vertices #for k=2, This is same as catalan's number which is lead by getting the number of restricted walks(classical case) #So generalizing the seq we can deduce that conditions on k-dim hypercubic lattice should give same results as generalized procedure of Catalan for n and k, #Catalan(n,k) = (k*n)! / (n!*(n+1)!*...*(n+k-1)!) #answer: (k*n)!/(n!*(n+1)!*...*(n+k-1)!) ######################################################################################################################################################################## #2, #(a) How many words in the alphabet {0,1,2,3} are there of length 30? # this is basically saying that for each digit in length can be either 0,1,2,3 so 4^30 is the answer #which is analogous of taking cartesian product #answer: 4^30 #(b) How many words in the alphabet {1,2,3,4} are there that add-up to 300? #we devise a GF from given info #W=empty or 1W_1 or 2W_2 or 3W_3 or 4W_3 #f=1+x*f+x^2*f+x^3*f+x^4*f f:=1/(1-x-x^2-x^3-x^4) #coeff(taylor(f,x=0,301),x,300) 18012939919656512113252584133785878056327163962817704791464695718041992634738504938769 #We can check this with lecture functions GFseq(CompsGF({1,2,3,4},x),x,300)[301] 18012939919656512113252584133785878056327163962817704791464695718041992634738504938769 #same, so it is right #answer:18012939919656512113252584133785878056327163962817704791464695718041992634738504938769 #(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. #Wt. Enumerator of all words Sum((x/(1-x))^k,k=0..infinity) = 1/(1-x/(1-x)) = 1-x/(1-2x) #lets take the Wt.Enumerator a kick f:=convert(1/(1-x/(1-x)),parfrac); f := 1/2-(1/2)/(-1+2*x); seq(coeff(taylor(f,x=0,21),x,i),i=1..20) 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288 #here is seq is ultra familiar, So we can easily denote that explicit formula is 2^(n-1) #answer: 2^(n-1) #(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) #Wt. Enum is {1,4,7,10,13,...} #x+x^4+x^7+x^10+ ... = x*(1+x^3+x^6+x^9....) = x*/(1-x^3) #Sum(x*/(1-x^3)^k,k=0..infinity) = 1/(1-x*/(1-x^3)) g:=normal(1/(1-x/(1-x^3))); g := (x^3-1)/(x^3+x-1) seq(coeff(taylor(g,x=0,21),x,i),i=1..20) 1, 1, 1, 2, 3, 4, 6, 9, 13, 19, 28, 41, 60, 88, 129, 189, 277, 406, 595, 872 #From the oeis this is A000930 #we can infer from A-number that The explicit formula for the seq A:=sum(binomial(n-2*i, i),i=0..(n)/3) and initial condition A for n=0 is 1 #analogous to 1-x/(x^3+x-1) #answer: 1-x/(x^3+x-1) #(e) Let a(n) be as in (d). What is the limit of a(n+1)/a(n) as n goes to infinity. #a(n):= sum(binomial(n-2*i, i),i=0..(n)/3) or 1-x/(x^3+x-1) #from the OEIS(A000930), we get the recurrence of the form a(n) = a(n-1) + a(n-3) given a(1)=1, a(2)=1, a(3)=1 #So, a(n+1) = a(n) + a(n-2) #let B be the a(n+1)/a(n) #B:=a(n+1)/a(n) = a(n) + a(n-2) / a(n) = 1 + a(n-2)/a(n) #so we just need to calculate the fractional diff for a(n-2)/a(n) #lets do it for n = 100 Lim:=proc(N) local i,b,L,v,V; V:={}; L:={seq(coeff(taylor((x^3-1)/(x^3+x-1),x=0,N+1),x,i),i=1..N)}: b:=nops(L); for i from 1 to b-2 do v:=evalf(L[i]/L[i+2]): print(v): od: end; Lim(100); .3333333333 .5000000000 .5000000000 .4444444444 .4615384615 .4736842105 .4642857143 .4634146341 .4666666667 .4659090909 .4651162791 .4656084656 .4657039711 .4655172414 .4655462185 .4655963303 .4655712050 .4655632675 .4655737705 .4655729555 .4655698779 .4655711145 .4655716993 .4655711207 .4655711187 .4655713031 .4655712452 .4655712050 .4655712362 .4655712390 .4655712282 .4655712308 .4655712334 .4655712318 .4655712314 .4655712321 .4655712320 .4655712318 .4655712319 .4655712319 .4655712319 .4655712319 .4655712319 .4655712319 .4655712319 .4655712319 .4655712319 .4655712319 .4655712319 .4655712319 .4655712319 .4655712319 .4655712319 .4655712319 .4655712319 .4655712319 .4655712319 .4655712319 .4655712319 .4655712319 .4655712319 .4655712319 .4655712319 .4655712319 .4655712319 .4655712319 .4655712319 .4655712319 .4655712319 .4655712319 .4655712319 .4655712319 .4655712319 .4655712319 .4655712319 .4655712319 .4655712319 .4655712319 .4655712319 .4655712319 .4655712319 .4655712319 .4655712319 .4655712319 .4655712319 .4655712319 .4655712319 .4655712319 .4655712319 .4655712319 .4655712319 .4655712319 .4655712319 .4655712319 .4655712319 .4655712319 .4655712319 #we see that the fraction converges to .4655712319 #so, since a(n+1)/a(n) = 1 + a(n-2)/a(n) = 1+ .4655712319 = 1.4655712319 #This follows the logic, so it would be same for n goes to infinity #answer: 1.4655712319 ##################################################################################################################################### 3. (a) What is the egf enumerating set-partitions. How many are there of the set {1,2,...,51}? #egf of set partition is givien as exp(exp(x)-1) by Fundamental Theorem of Exponential Generating Functions: #SO for {1,2,...,51}, coeff(taylor(exp(exp(x)-1),x=0,52)x,51)*51! 3263983870004111524856951830191582524419255819477 #answer:exp(exp(x)-1, 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}? ##egf: sum((exp(x)-1)^(3*i-2)/(3*i-2)!,i=1..infinity); a := (exp(x)-1)*((1/3)*exp(exp(x)-1)/(exp(x)-1)-(1/3)*exp(-(1/2)*exp(x)+1/2)*cos((1/2)*3^(1/2)*(exp(x)-1))/(exp(x)-1)+(1/3)*3^(1/2)*exp(-(1/2)*exp(x)+1/2)*sin((1/2)*3^(1/2)*(exp(x)-1))/(exp(x)-1)) coeff(taylor(a,x=0,60),x,51)*51! 10890302508247821487203063697386513637342330261601 #answer:(exp(x)-1)*((1/3)*exp(exp(x)-1)/(exp(x)-1)-(1/3)*exp(-(1/2)*exp(x)+1/2)*cos((1/2)*3^(1/2)*(exp(x)-1))/(exp(x)-1)+(1/3)*3^(1/2)*exp(-(1/2)*exp(x)+1/2)*sin((1/2)*3^(1/2)*(exp(x)-1))/(exp(x)-1)) 10890302508247821487203063697386513637342330261601 (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}? ##egf b:=sum((sum(x^(2*n+1)/(2*n+1)!,n=0..infinity))^i/i!,i=0..infinity); b := exp(sinh(x)) coeff(taylor(b,x=0,60),x,51)*51! 101595492022700597152023270326642584710021120 #answer:exp(sinh(x)),101595492022700597152023270326642584710021120 (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}? #egf c:=sum((sum(x^(2*n+1)/(2*n+1)!,n=0..infinity))^(3*i-2)/(3*i-2)!,i=1..infinity); c := sinh(x)*((1/3)*csch(x)*exp(sinh(x))-(1/3)*csch(x)*exp(-(1/2)*sinh(x))*cos((1/2)*3^(1/2)*sinh(x))+(1/3)*csch(x)*3^(1/2)*exp(-(1/2)*sinh(x))*sin((1/2)*3^(1/2)*sinh(x))) coeff(taylor(c,x=0,60),x,51)*51! 30143119660583350838086153637731292910753195 #answer:sinh(x)*((1/3)*csch(x)*exp(sinh(x))-(1/3)*csch(x)*exp(-(1/2)*sinh(x))*cos((1/2)*3^(1/2)*sinh(x))+(1/3)*csch(x)*3^(1/2)*exp(-(1/2)*sinh(x))*sin((1/2)*3^(1/2)*sinh(x))) 30143119660583350838086153637731292910753195 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. #{{{1},{{2}},{{3}}}, {{{1},{2}},{{3}}},{{{1,2}},{{3}}},{{{1,2},3}},{{{1},{3}},{{2}}},{{{1,3}},{{2}}},{{{1,3},2}} #{{{3},{2}},{{1}}},{{{3,2}},{{1}}},{{{3,2},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!, n=0..infinity) = exp(exp(exp(x)-1)-1) #A000258 (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? #5. #(a) How many integer partitions are there of 1000? #using the euler's GF #1/((1-q)*(1-q^2)*(1-q^3)*....*(1-q^1000) -> gf:= mul(1/(1-q^i),i=1..1000): coeff(taylor(gf,q=0,1001),q,1000); 24061467864032622473692149727991 #compare it with pn(1000) pn(1000); 24061467864032622473692149727991 #good #answer:24061467864032622473692149727991 #(b) How many integer partitions of 1000 are there where all the parts are odd? #Calculate Odd partition #We know from our previous excersise,for Odd partitions we know that numbers of 2n are not included #meaning there are no cases for a(2n) #So {[].[1],[11],...[1$k]} for 1,(no case for 2), {[].[3],[33],...[3$k]} for 3, ... ,{[].[k],[kk],...[k$k]}for k=2n+1 from n=0..infin #Then our |Par|_q = (1+q+q^2+q^3+....) * (1+q^3+q^6+...) * (1+q^5+q^10+...)* ... gf2:=mul(1/(1-q^(2*i+1)),i=0..1000/2): coeff(taylor(gf2,q=0,1001),q,1000); 8635565795744155161506 #compare it with pnC, pnC(1000,{1},2) 8635565795744155161506 #true #answer:8635565795744155161506 #(c) How many integer partitions of 1000 are there where all the parts are different than each other? #For distinct partitions given that frequency notation is as 1^a1 2^a2 3^a3 so forth #we know that for each numbers in distinct case a1,a2,a3,...,ak are all 1 #meaning there is only {[].[1]} for 1,{[].[2]} for 2, ... ,{[].[k]} for k.. #=(1+q)*(1+q^2)*(1+q^3)*...*(1+q^k) #=Product(1+q^i,i=1..infinity) but for this case gf is going to be gf3:=mul(1+q^i,i=1..1000): coeff(taylor(gf3,q=0,1001),q,1000); #this should give the same result as pnD(1000,1) pnD(1000,1) 8635565795744155161506 #answer: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. #summing the conditions for b and c we have gf that is explicit as #=(1+q)*(1+q^3)*(1+q^5)*...*(1+q^(2k+1)) #=Product(1_q^(2k+1),k=0..infinity) #for this case up to 1000 gf4:=mul((1+q^(2*i+1)),i=0..500): coeff(taylor(gf4,q=0,1001),q,1000); 517035762467311 #We have devised a similar plot in HW24(pnDC) lets compare with that pnDC(1000,1,{1},2) 517035762467311 #so we are good #answer:517035762467311 #6. #(a) How many rooted labelled trees are there with 31 vertices? #Use TreeSeqL to get the answer sum(coeff((TreeSeqL(31,t)[31]),t,i),i=1..31) 550618520345910837374536871905139185678862401 #answer:550618520345910837374536871905139185678862401 #(b) How many rooted labelled trees are there with 31 vertices where the root has exactly two children. #R(x) = Sum(n^(n-1)*x^n/n!,n=0..infinity) = x * (1+R(x)+R(x)^2/2!+ ... #egf should be x* R(x)^2/2! 31!*coeff(taylor(x*(1+add(n^(n-1)*x^n/n!,n=1..31))^2,x=0,32),x,31) 836833068002473380000000000000000000000000000 #answer:836833068002473380000000000000000000000000000 #(c) How many rooted labelled trees are there with 31 vertices where each vertex must have either zero, one, three, or four children. #So we devise a function for this similar from HW #to have vertex that has only leaf or the number in the set S #first extract numbers from S #then using loop, formulate Functional eq. including leaf and numbers in the S # SeqRTchild:=proc(S,N) local i,L,f,s,z: f:=1+add(z^s/s!,s in S): L:=LIF(f,z,N): for i from 1 to N do: L[i]:=i!*L[i]: od: return(L): end: #So from the given condition SeqRTchild({1,3,4},31)[31] 388391178300656853181332829972846230000000 #answer:388391178300656853181332829972846230000000 #(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. #So since we know R(x) = x* (1+R(x)+...R(x)^k/k!) = exp(R(x)) and subtracting R(x)^1!, R(x)^3/3!, R(x)^4/4! #then R(x) = x*(1+R(x)+...R(x)^k/k! - R(x) - R(x)^3/3! - R(x)^4/4!) = x*(exp(R(x))- R(x) - R(x)^3/3! - R(x)^4/4!) #lets use LIF for easier computation egf:= exp(z)-z-z^3/6-z^4/24 31!*LIF(egf,z,31)[31] 2863465748628395267057869436794752181 #answer:2863465748628395267057869436794752181 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). #from the given, #{[[], [[], []], []] , [[], [[], []], []],[[[], []],[],[]].[ [[], []], [[], []] ],[ [], [], [[], []] ]} #so five #BT(4) =5 (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 #The closest match for the above sequence has to be the catalan numbers and to match with the recurrence, we utilize the general Catalan recurrence C(n+1) = sum(C(k) * C(n-k), k=0..n) for B(x) #We know that b(0)=0, so B(x) = Sum(b(n)*x^n,n=1..infinity) #B(x)^2 = sum(b(n+1)*x^n,n=2..infinity) as B(x)^2 = Sum(b(n)*x^n,n=1..infinity)^2 = sum(b(k)*b(n-k),n=1..infinity)^2 = sum(sum(b(i)*b(n-i),i = 1..n-1), n = 1..infinity) -> sum(b(n+1)*x^n,n=2..infinity) #B(x)^2 + x = sum(b(n+1)*x^n,n=2..infinity) + x #B(x)^2 + x = sum(b(n+1)*x^(n+1),n=0..infinity) as b(1)*x = x, b(1)*x+sum(b(n)*x^n,n=2..infinity) = Sum(b(n)*x^n,n=1..infinity) = B(x) #B(x)^2 + x = B(x) QED.