#Yusra Naqvi #HW 23 #OK to post ################################################################################ #SplitUp(L):inputs a list, L, and outputs it as a list of lists [L1,L2,L3, ...], #where L=[op(L1),op(L2), op(L3), ...] and L1,L2,L3, are atoms SplitUp:=proc(L) local i: option remember: if nops(L)=0 or nops(L)=1 then return([L]): fi: for i from 1 to nops(L)-1 do if split(L[1..i],L[i+1..nops(L)]) then return([L[1..i],op(SplitUp(L[i+1..nops(L)]))]): fi: od: [L]: end: ################################################################################ #split(w1,w2):returns true if and only if [w1,w2] splits into [w1].[w2] split:=proc(L,R) local n,m: if nops(L)=0 or nops(R)=0 then RETURN(1): fi: n:=op(nops(L),L): m:=op(1,R): if n=m then RETURN(false): fi: if n>=4 and m<=3 then RETURN(true): fi: if n=2 then if m=1 and nops(R)>2 and op(2,R)<>1 and op(3,R)<>op(2,R) then RETURN(true): fi: if m=1 and nops(R)=2 and op(2,R)<>1 then RETURN(true): fi: if m=1 and nops(R)>=3 and op(2,R)=1 and op(3,R)=1 then RETURN(true): fi: if m=3 and nops(R)>=2 and op(2,R)<>3 and not(nops(R)>=4 and op(2,R)=op(3,R) and op(3,R)=op(4,R)) then RETURN(true): fi: if m=3 and nops(R)=1 then RETURN(true): fi: if m>=4 then RETURN(true): fi: fi: if n<>2 then if nops(R)>=5 and op(1,R)=2 and op(2,R)=2 and op(3,R)=1 and op(4,R)<>1 and op(5,R)<>op(4,R) then RETURN(true): fi: if nops(R)=4 and op(1,R)=2 and op(2,R)=2 and op(3,R)=1 and op(4,R)<>1 then RETURN(true): fi: if nops(R)>=5 and op(1,R)=2 and op(2,R)=2 and op(3,R)=1 and op(4,R)=1 and op(5,R)=1 then RETURN(true): fi: if nops(true)>=4 and op(1,R)=2 and op(2,R)=2 and op(3,R)=3 and op(4,R)<>op(3,R) and not(nops(R)>=6 and op(4,R)=op(5,R) and op(5,R)=op(6,R)) then RETURN(true): fi: if nops(R)=2 and op(1,R)=2 and op(2,R)=2 then RETURN(true): fi: if nops(R)=3 and op(1,R)=2 and op(2,R)=2 and op(3,R)>=4 then RETURN(true): fi: if nops(R)>=3 and op(1,R)=2 and op(2,R)=2 and op(3,R)>=4 and op(4,R)<>op(3,R) then RETURN(true): fi: fi: false: end: ################################################################################ #JC1(w): nonrecursive version of JC(w) JC1:=proc(w) local a1,i,c1,w1,J1,L: if w=[] then return(w): fi: L:=[]: w1:=w: while w1<>[] do a1:=w1[1]: for i from 1 to nops(w1) while w1[i]=a1 do od: c1:=i-1: L:=[op(L),c1,a1]: w1:=w1[c1+1..nops(w1)]: od: L: end: ################################################################################ #Lagrange Inversion applied to tree enumeration of ordered trees #LIF(P,u,N): inputs an expression P(u) that possesses a Maclaurin expansion in u #and outputs the first N terms of the series expansion of the unique f.p.s u(t) #satisfying the functional equation u(t)=t*P(u(t)). #For example: #LIF(1+u^2,u,12); #should return #[1,0,1,0,2,0,5,0,14,0,42,0] LIF:=proc(P,u,N) local n: [seq(coeff(taylor(P^n,u=0,n),u,n-1)/n,n=1..N)]: end: ################################################################################ #1 #PT(): inputs nothing, and outputs the set of Conway's 92 elements PT:=proc() local L,S,N,i,a,b: L:=[[3]]: S:={}: N:=[]: for i from 1 while nops(S)<92 do for a in L do if not member(a,S) then S:=S union {a}: N:=[op(N),JC1(a)] fi: od: L:=[]: for b in N do L:=[op(L),op(SplitUp(b))]: od: od: S: end: ################################################################################ #2 #Mat(): inputs nothing and outputs the 92x92 matrix such that Mat(i,j) is #the number of times that atom j appears in SplitUp(JC1(atom i)) Mat:=proc() local A,S,i,j: with(linalg): A:= matrix(92,92): S:= PT(): for i from 1 to 92 do for j from 1 to 92 do A[i,j]:=numboccur(SplitUp(JC1(S[i])),{S[j]}): od: od: evalm(A): end: ################################################################################ #3 #Using the commands: #A:=Mat(): #S:=eigenvalues(A): #S2:={seq(evalf(s),s in S)}: #S3:={seq(evalf(abs(s)),s in S2)}: #max(S3); #we get Conway's constant: #1.30357726903430 ################################################################################ #4 #RLT1(S,N): the first N terms of the enumerating sequence for the number of #labelled rooted trees with n vertices, where each vertex either has outdegree 0 #or an outdegree that belongs to S RLT1:=proc(S,N) local S1,P,s,u,L: S1:=S union {0}: P:=0: for s in S1 do P:=P+u^s/s!: od: L:=LIF(P,u,N): [seq(L[i]*i!,i=1..nops(L))]: end: ### #We get: #RLT1({1},20); #[1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600, 6227020800, 87178291200, 1307674368000, 20922789888000, 355687428096000, 6402373705728000, 121645100408832000, 2432902008176640000] #A142 in OEIS #RLT1({1,2},20) #[1, 2, 9, 60, 540, 6120, 83790, 1345680, 24811920, 516650400, 11992503600, 307069963200, 8598348158400, 261387760233600, 8573572885878000, 301809119163552000, 11349727401396384000, 454104511068656448000, 19261139319649202976000, 863322072620761353600000] #A36774 in OEIS #RLT1({1,2,3},20) #[1, 2, 9, 64, 620, 7620, 113610, 1992480, 40194000, 916927200, 23341071600, 655922836800, 20169411662400, 673645440468000, 24285190867938000, 939899116892736000, 38870133445791648000, 1710655202853140544000, 79826043011286892320000, 3936948118406837614080000] #A36775 in OEIS #RLT1({1,3},20) #[1, 2, 6, 28, 200, 1920, 22260, 299040, 4596480, 80035200, 1558972800, 33556723200, 790404014400, 20220183984000, 558377964144000, 16556553965952000, 524646641046528000, 17693631589810176000, 632750850059328000000, 23917010504518010880000] #Not in OEIS ################################################################################ #5 #RLT2(S,N): the first N terms of the enumerating sequence for the number of #labelled rooted trees with n vertices, where each vertex either has outdegree 0 #or an outdegree that does not belong to S RLT2:=proc(S,N) local S1,P,s,u,L: S1:=S minus {0}: P:=0: for s in S1 do P:=P+u^s/s!: od: L:=LIF(exp(u)-P,u,N): [seq(L[i]*i!,i=1..nops(L))]: end: ### #We get: #RLT2({1},20); #[1, 0, 3, 4, 65, 306, 4207, 38424, 573057, 7753510, 134046671, 2353898196, 47602871329, 1013794852266, 23751106404495, 590663769125296, 15806094859299329, 448284980183376078, 13515502344669830287, 430050399901131972780] #A60356 in OEIS #RLT2({1,2},20) #[1, 0, 0, 4, 5, 6, 427, 1968, 6561, 220510, 2129171, 13847736, 337904437, 5156062926, 54298310445, 1192150218496, 24147409593089, 364887230459454, 8145781717395223, 197451127561855320] #Not in OEIS #RLT2({1,2,3},20) #[1, 0, 0, 0, 5, 6, 7, 8, 2529, 11350, 36971, 104556, 10182757, 99054970, 632882265, 3303250096, 165364954369, 2689602118254, 28186612549255, 233809699635780] #Not in OEIS #RLT2({1,3},20) #[1, 0, 3, 0, 65, 6, 3787, 1184, 427905, 286750, 79563671, 92894616, 22050773329, 39814849270, 8526143835315, 22030869781696, 4386817826347009, 15360562101209598, 2898552816857784799, 13208608054252514040] #Not in OEIS ################################################################################