{VERSION 2 3 "DEC ALPHA UNIX" "2.3" } {USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier" 0 1 255 0 0 1 0 1 0 0 1 0 0 0 0 }{CSTYLE "2D Math" -1 2 "Times" 0 1 0 0 0 0 0 0 2 0 0 0 0 0 0 }{CSTYLE "Hyperlink" -1 17 "" 0 1 0 128 128 1 0 0 1 0 0 0 0 0 0 } {CSTYLE "2D Comment" 2 18 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "2 D Output" 2 20 "" 0 1 0 0 255 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 256 " " 0 24 0 0 0 0 0 2 0 0 0 0 0 0 0 }{CSTYLE "" -1 257 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 258 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 259 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 260 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 261 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 262 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 } {CSTYLE "" -1 263 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 264 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 265 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 266 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 267 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 268 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 269 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 270 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 271 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 272 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 273 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 274 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 275 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 276 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 277 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 278 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 279 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 280 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 281 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 282 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 283 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 284 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 285 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 286 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 287 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 288 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 289 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 290 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 291 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 292 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 293 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 294 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 295 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 296 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 297 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 298 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 299 "" 1 24 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 300 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 301 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 302 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 303 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 304 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 305 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{PSTYLE "Normal" -1 0 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "T ext Output" -1 2 1 {CSTYLE "" -1 -1 "Courier" 1 10 0 0 255 1 0 0 0 0 0 1 3 0 0 }1 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Heading 1" 0 3 1 {CSTYLE "" -1 -1 "" 1 18 0 0 0 0 0 1 0 0 0 0 0 0 0 }1 0 0 0 6 6 0 0 0 0 0 0 -1 0 }{PSTYLE "Heading 2" 3 4 1 {CSTYLE "" -1 -1 "" 1 14 0 0 0 0 0 0 0 0 0 0 0 0 0 }0 0 0 -1 4 4 0 0 0 0 0 0 -1 0 }{PSTYLE "Heading 3 " 4 5 1 {CSTYLE "" -1 -1 "" 1 12 0 0 0 0 1 0 0 0 0 0 0 0 0 }0 0 0 -1 0 0 0 0 0 0 0 0 -1 0 }{PSTYLE "Warning" 2 7 1 {CSTYLE "" -1 -1 "" 0 1 0 0 255 1 0 0 0 0 0 0 1 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Error" 7 8 1 {CSTYLE "" -1 -1 "" 0 1 255 0 255 1 0 0 0 0 0 0 0 0 0 } 0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Maple Output" 0 11 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }3 3 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 11 12 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }1 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 3 256 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }3 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 257 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }3 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }} {SECT 0 {EXCHG {PARA 256 "" 0 "" {TEXT 256 44 "MORE EXAMPLES OF MARKIN G COMBSTRUCT GRAMMARS" }{TEXT 299 1 " " }}{PARA 257 "" 0 "" {TEXT 300 22 "Marni Mishna July 1997" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 205 "This worksheet continues to explore the possibil ities with combstruct[mark]. There is an introductory worksheet that e xplains the idea of marking and contains some basic examples which are built upon here." }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "with(combstruc t);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#71%+allstructsG%&countG%%drawG% )finishedG%'gfeqnsG%)gfseriesG%(gfsolveG%,iterstructsG%%markG%'momentG %+nextstructG%,prog_gfeqnsG%.prog_gfseriesG%-prog_gfsolveG%)varianceG " }}}{SECT 0 {PARA 3 "" 0 "" {TEXT -1 38 "Lowest Common Ancestor in Bi nary Trees" }}{PARA 0 "" 0 "" {TEXT -1 449 "Given any two nodes in a \+ tree there is a shortest distance between them through a nearest commo n ancestor. Determining the average distance between two points (simil arly, the average distance to the nearest common ancestor) is a fundam ental problem in combinatorics with applications in combinatorial opti mization, compiling and parrallelism. We can determine this value fo r binary trees by considering a method similar to determining pathleng th." }}{SECT 0 {PARA 4 "" 0 "" {TEXT -1 40 "Average Distance Between e xternal Nodes " }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 111 "Let us ease int o the topic with a specialisation of the problem: nearest common ances tor among external nodes. " }}{PARA 0 "" 0 "" {TEXT -1 164 "First cons ider the case where the nearest common ancestor is the root. We can gr aft the solution into the leaf of a larger tree to represent the more \+ general case. " }}{PARA 0 "" 0 "" {TEXT -1 699 "We wish to describe a \+ bijection that counts all distances between the left children of the r oot and the right. We will do this by first considering a tree as stre tched out, thus the product of a sequence of trees, and a node (the ro ot). Based on our restriction, the two end trees of the sequence will be trees consisting of only a leaf. The root can occur anywhere along the sequence and to mark its place we use a sequence with one tree ma rked. We will say that the root appears after this node. (We will add \+ separately the case where it occurs before). We will use a bivariate g enerating function to do the counting of the length of the sequence (a nd hence the distance between the two leaves). " }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 173 "Bintree:=\{T=Union(L, Prod(N, T, T)), L=Epsil on, N=Atom, \nChain=Prod(A, Sequence(B), A), A=Prod(len,L), B= Prod(le n, N,Union(Prod(Epsilon,T),Prod(T,Epsilon))), len=Epsilon\}: " }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 72 "We mark the point in the sequence \+ where the lowest common ancestor goes:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 43 "B1:= mark(Bintree, unlabelled, [B,m1], 1): " }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 54 "We mark the leaves of the trees for grafting pu rposes:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 40 "B2:= mark(B1, unlabelled , [L[0],m2], 1):" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 257 "Next, we cre ate the bijection. It is a product of the tree to graft into (with a l eaf marked telling us where), the ancestor node, and the sequence with either a spot marked for the ancestor node or none (indicating it is \+ at the beginning of the sequence) :" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 84 "BCount:= B2 union\n\{AncTree=Prod(T[0][1], N[0][0], Union(Chain[1] [0], Chain[0][0]))\}:" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 43 "If we co unt the number of AncTrees of size " }{TEXT 278 1 "n" }{TEXT -1 88 " i t will be the number of ways to choose two external nodes in all binar y trees of size " }{TEXT 279 2 "n." }{TEXT -1 4 " " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 46 "count([AncTree, BCount, unlabelled] , size =3);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"#I" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 63 "To count the distance we can sum up all of the \+ occurrences of \"" }{TEXT 303 3 "len" }{TEXT -1 87 "\" in all of the A ncTrees. We do this by determining the bivariate generating function. \+ " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 54 "BGF:=gfsolve(BCount, unlabelled , x, [[u, len[0][0]]]):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 27 "AT:=subs (BGF,AncTree(x,u));" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#ATG**%\"uG\" \"#%\"xG\"\"\",&F)F)F(!\"%#!\"\"F',*F)F)*&F&F),&F)F)*$F*#F)F'F-F)!\"#* &F&F'F(F)F+*&F&F'F0F)F'F-" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 13 "To g ive each " }{TEXT 276 1 "u" }{TEXT -1 52 " the corresponding weight, w e differentiate and set " }{TEXT 277 2 "u=" }{TEXT -1 3 "1. " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 42 "CountLength:=eval(subs(u=1, diff(AT, u))) ;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%,CountLengthG,&*&%\"xG\"\"\",&F (F(F'!\"%#!\"$\"\"#F-*(F'F(F)#!\"&F-,(F-F(*$F)#F(F-!\"#F'!\")F(!\"\"" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 217 "This is the generating functio n for the sum of all shortest paths between leaves. We can find the co efficients with the series expansion, and in fact we can determine the closed form for the coefficients, using gfun. " }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 27 "series(CountLength, x, 10);" }}{PARA 11 "" 1 " " {XPPMATH 20 "6#+7%\"xG\"\"#\"\"\"\"#;\"\"#\"#'*\"\"$\"$7&\"\"%\"%gD \"\"&\"&)G7\"\"'\"&Wt&\"\"(\"'W@E\"\")\"(['z6\"\"*-%\"OG6#\"\"\"\"#5" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 99 "with(gfun):\nT1:= expand( rsolve(diffeqtorec(holexprtodiffeq(CountLength, y(x)), y(x), u(n)), u( n)));" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#T1G,$*&)\"\"%%\"nG\"\"\"F) F*#F*\"\"#" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 74 "To find the average sum per tree we divide by the number of trees of size " }{TEXT 280 1 "n" }{TEXT -1 148 ". This is represented in the grammar as T[0][0]. T o find the average distance we also need to divide by the number of pa irs of leaves. A tree with " }{TEXT 282 1 "n" }{TEXT -1 12 " nodes ha s " }{TEXT 281 2 "n+" }{TEXT -1 25 "1 leaves and thus this is" } {XPPEDIT 18 0 "(n+1)*Choose*(2)=(n+1)*n/2" "/*(,&%\"nG\"\"\"\"\"\"F&F& %'ChooseGF&\"\"#F&*(,&F%F&\"\"\"F&F&F%F&\"\"#!\"\"" }{TEXT -1 2 " ." } }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 92 "Total:=rsolve(diffeqtorec( holexprtodiffeq(subs(BGF,T[0][0](x,u)), y(x)), y(x), u(n)), u(n));" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%&TotalG**)\"\"%%\"nG\"\"\"-%&GAMMAG6 #,&F(F)#F)\"\"#F)F)-F+6#,&F(F)F/F)!\"\"%#PiG#F3F/" }}}{EXCHG {PARA 0 " > " 0 "" {MPLTEXT 1 0 37 "simplify(T1/Total/((n+1)*n/2),GAMMA);" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#*(%#PiG#\"\"\"\"\"#-%&GAMMAG6#,&%\"nGF &F&F&F&-F)6#,&F,F&F%F&!\"\"" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 42 "He re are the values for a few small trees:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 42 "seq(evalf(T1/Total/((n+1)*n/2)), n=1..10);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6,$\"\"#\"\"!$\"+nmmmE!\"*$\"+++++KF($\"+dG9dO F($\"+j?\\jSF($\"+L/!HV%F($\"+uF*Qx%F($\"+#H_@4&F($\"+i1p\"R&F($\"+bQY vcF(" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 114 "The distance to the nea rest common ancestor is half of this value since the trees have a symm etric construction. " }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 23 "Asymptoti cally we have:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 51 "map(combi ne, asympt(T1/Total/((n+1)*n/2), n), exp);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,,*&%#PiG#\"\"\"\"\"#*$%\"nG!\"\"#F+F(F'*&F%F&F)F&#F'\" \")*&F%F&F)#\"\"$F(#F'\"$G\"*&F%F&F)#\"\"&F(#!\"&\"%C5-%\"OG6#*$F)#\" \"(F(F'" }}}{PARA 11 "" 1 "" {TEXT -1 0 "" }}}{SECT 0 {PARA 4 "" 0 "" {TEXT -1 38 "Average Distance Between any two Nodes" }}{PARA 0 "" 0 " " {TEXT -1 219 "To extend the problem to nearest common ancestor betwe en any two nodes we need to allow the end bits of our sequence to be m ore than just leaves, but in fact trees. This is attained with a simpl e substitution. We allow " }{TEXT 283 1 "A" }{TEXT -1 453 " to be a tr ee. This omits the case when one of the nodes is the ancestor. This c ase is omitted since it is not possible for a node to be both an ances tor of a second node and a leaf of the same tree, and this is precisel y what is needed. To account for this, we add the possibility of a se cond chain, much like the first except it is terminated on the top end by a node (not a tree). To avoid over counting by one we do not add \+ a tag on the end tree." }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 218 "B intree:=\{T=Union(L, ST), ST= Prod(N, T, T), L=Epsilon, N=Atom, \nChai n=Prod(A, Sequence(B), A), A=Prod(len,T), B= Prod(len, N,Union(Prod(Ep silon,T),Prod(T,Epsilon))), Chain2=Prod(T, Sequence(B, card>0)), len=E psilon\}: " }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 54 "We mark the point i n the sequence where the node goes:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 43 "B1:= mark(Bintree, unlabelled, [B,m1], 1): " }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 54 "We mark the leaves of the trees for grafting purpose s:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 40 "B2:= mark(B1, unlabelled, [L[ 0],m2], 1):" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 331 "Next, we create t he bijection. It is a product of the tree to graft into (with a leaf m arked telling us where), the ancestor node, the sequence with either a spot marked for the ancestor or none (indicating it is at the beginni ng of the sequence). Or it is the chain that represents the case when one of the nodes is the ancestor." }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 128 "BCount:= B2 union\n\{AncTree=Union(Prod(T[0][1], N[0][0], Union(C hain[1][0], Chain[0][0])),PL), \n PL=Prod(T[0][1], Chain2[0][0])\}:" } }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 43 "If we count the number of AncTre es of size " }{TEXT 284 1 "n" }{TEXT -1 88 " it will be the number of \+ ways to choose two nodes or leaves from a binary tree of size " } {TEXT 285 1 "n" }{TEXT -1 5 ". " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 48 "count([AncTree, BCount, unlabelled], size = 2); " }} {PARA 11 "" 1 "" {XPPMATH 20 "6#\"#?" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 74 "As before, to count the distance we can sum up all of the occur rences of \"" }{TEXT 301 3 "len" }{TEXT -1 73 "\" in all of the AncTre es. We can solve the bivariate generating function." }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 54 "BGF:=gfsolve(BCount, unlabelled, x, [[u, len[0][0] ]]):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 27 "AT:=subs(BGF,AncTre e(x,u));" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%#ATG*,%\"uG\"\"\",4*&F& \"\"#,&F'F'*$,&F'F'%\"xG!\"%#F'F*!\"\"F'\"\"(F&!\"(F*F'*&F&F'F+F'F/*&F &F*F.F'!\")*$F&F*\"\"'*(F&F*F.F1F+F'!\"$*(F&F'F.F1F+F'#F2F**&F.F1F+F'F 1F'F-#F1F*,*F'F'F4!\"#F5F/F)F*F1,&F1F'F4F'F1" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 42 "CountLength:=eval(subs(u=1, diff(AT, u)));" }} {PARA 12 "" 1 "" {XPPMATH 20 "6#>%,CountLengthG,**&,*\"\"%\"\"\"*$,&F) F)%\"xG!\"%#F)\"\"#!\"$F,!\")*&F,!\"\",&F)F)F*F3F)#F3F/F)F+!\"#F3*&,* \"#:F)F*!#5F,!#;F2#!\"&F/F)F+F6F3*(F'F)F+F0,(F/F)F*F6F,F1F)F)*(F'F)F+F " 0 "" {MPLTEXT 1 0 27 "series(CountLeng th, x, 10);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#+5%\"xG\"\"%\"\"\"\"#O \"\"#\"$K#\"\"$\"%+8\"\"%\"%Wn\"\"&\"&?L$\"\"'\"'%=f\"\"\"(\"'o?u\"\") -%\"OG6#\"\"\"\"\"*" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 65 "Again, we \+ can find a closed form for the coefficients using gfun:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 79 "T1:=rsolve(diffeqtorec(holexprtodif feq(CountLength, y(x)), y(x), u(n)), u(n));\n" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#T1G,(*.)\"\"%%\"nG\"\"\")#F*\"\"#F)F*)F-F)F*-%&GAMMA G6#,&#\"\"$F-F*F)F*F*-F06#,&F)F*F*F*!\"\"%#PiG#F8F-!\"%F'F-*&F'F*F)F*F -" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 201 "To find the the average, we again need to divide by the number of trees of size n and the number \+ of ways of choosing two nodes. In this case, since we are including in ternal nodes there are a total of " }{TEXT 257 4 "2n+1" }{TEXT -1 27 " nodes, and thus there are " }{TEXT 258 7 "n(2n+1)" }{TEXT -1 23 " way s of choosing two. " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 93 "Tota l:=rsolve(diffeqtorec(holexprtodiffeq(subs(BGF,T[0][0](x,u)), y(x)), y (x), u(n)), u(n)):\n" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 45 "AVG := simplify(T1/Total/n/(2*n+1), symbolic);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%$AVGG**,&%\"nG\"\"\"F(F(F(,&-%&GAMMAG6#,&#\"\"$\"\"#F (F'F(!\"#*&%#PiG#F(F0-F+6#,&F'F(F0F(F(F(F(F'!\"\"F*F8" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 25 "seq(evalf(AVG), n=1..10);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6,$\"+LLLL8!\"*$\"+++++=F%$\"+5Q_4AF%$\"+z]OzD F%$\"+>0[>HF%$\"+O#3iB$F%$\"+M$))Q`$F%$\"+&*>l:QF%$\"+G([Q3%F%$\"+UkHS VF%" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 122 "Notice that these values \+ are smaller than when leaves alone were considered. We can also examin e the asymptotic behaviour:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 41 "map( simplify, asympt(AVG, n), symbolic);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,0*&%#PiG#\"\"\"\"\"#%\"nGF&F'!\"#F'*&F%F&F)#!\"\"F(#\" #8\"\")*$F)F-F**&F%F&F)#!\"$F(#\"#d\"$G\"*&F%F&F)#!\"&F(#!#*)\"%C5-%\" OG6#*$F)#!\"(F(F'" }}}}}{SECT 0 {PARA 3 "" 0 "" {TEXT -1 27 "Non-Cross ing Configurations" }}{PARA 0 "" 0 "" {TEXT -1 162 "To better understa nd the capabilities for determining mean and variance, we now consider the enumeration of planar configurations defined on vertices of a con vex " }{TEXT 286 1 "n" }{TEXT -1 476 "-gon. We will look at six basic \+ non-crossing configurations: trees and forests, graphs and connected g raphs, dissections and partitions. We will use marking directly and in directly via the commands combstruct[mean] and combstruct[variance] to determine properties of these figures. The simpler constructions offe r more information, however we can determine specific moments and vari ances for sub-objects when the bivariate generating function is not av ailable in closed form. " }}{SECT 0 {PARA 4 "" 0 "" {TEXT -1 17 "Trees and Forests" }}{SECT 0 {PARA 5 "" 0 "" {TEXT -1 5 "Trees" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 66 "First we consider non-crossing trees and \+ non-crossing forests. A " }{TEXT 260 4 "tree" }{TEXT -1 58 " is a seq uence of butterflies attached to a root, where a " }{TEXT 261 9 "butte rfly" }{TEXT -1 199 " is an ordered pair of trees whose roots have bee n merged into a single node. This merge step may duplicate the root, \+ so a butterfly is expressed as the product of two forests and a root, where a " }{TEXT 262 6 "forest" }{TEXT -1 97 " is a sequence of butt erflies. We are interested in the average number of leaves in such a t ree. " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 131 "nctree:=\{T=Union (L, Prod(Z, Sequence(B, card>0))), F=Sequence(B, card>0), B=Union(Prod (F,Z,F), Prod(F, Z), Prod(Z, F), L), L=Atom\}:" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 49 "marked_trees:= mark(nctree, labelled, [L, m], \+ 2):" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 15 "We can use the " } {HYPERLNK 17 "moment" 2 "combstruct, moment" "" }{HYPERLNK 17 "" 2 "co mbstruct, moment" "" }{TEXT -1 70 " command to give us specific moment s. The first moment is the average." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 56 "evalf(moment([T, nctree, labelled], size =25, L, 1)/2 5);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#$\"+39!pT%!#5" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 40 "Notice that this value is equal to the \{" } {TEXT 304 21 "number trees of size " }{TEXT -1 1 "n" }{TEXT 287 21 " w ith one leaf marked" }{TEXT -1 3 "\}/\{" }{TEXT 305 24 "number of tree s of size " }{TEXT -1 4 "n\}. " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 103 "evalf(count([T[1], marked_trees, labelled] ,size=25)/count([T [0], marked_trees,labelled], size=25))/25;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#$\"+39!pT%!#5" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 195 " We can determine the general form of the coefficients of the generati ng functions of the marked productions and hence determine a closed fo rm for the mean percentage of leaves in a tree of size " }{TEXT 259 1 "n" }{TEXT -1 3 ". " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 39 "TT: =gfsolve(marked_trees, labelled, z):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 109 "T1:=rsolve(diffeqtorec(holexprtodiffeq(subs(TT, T[1] (z)), y(z)), y(z), u(n)) minus \{u(1) = 1, u(0)=0\}, u(n));" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#T1G,$*.)\"#F%\"nG\"\"\"\"\"$#F*\"\"#%#PiG !\"\"-%&GAMMAG6#,&F)F-!\"#F*F/-F16#,&F)F*#F4F+F*F*-F16#,&F)F*#!\"%F+F* F*#F*\"$'[" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 98 "T0:=rsolve(di ffeqtorec(holexprtodiffeq(subs(TT, T[0](z)), y(z)), y(z), u(n)) minus \{u(0)=0\}, u(n));" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#T0G,$*.)\"#F% \"nG\"\"\"\"\"$#F*\"\"#%#PiG!\"\"-%&GAMMAG6#,$F)F-F/-F16#,&F)F*#F/F+F* F*-F16#,&F)F*#!\"#F+F*F*#F*\"#a" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 114 "T2:=rsolve(diffeqtorec(holexprtodiffeq(subs(TT, T[2](z)), y(z )), y(z), u(n)) minus\{u(2)=0, u(1)=0, u(0)=0\}, u(n));" }}{PARA 11 " " 1 "" {XPPMATH 20 "6#>%#T2G,$*.)\"#F%\"nG\"\"\"\"\"$#F*\"\"#%#PiG!\" \"-%&GAMMAG6#,&F)F-!\"%F*F/-F16#,&F)F*#F4F+F*F*-F16#,&F)F*#!\"&F+F*F*# F*\"%[()" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 53 "The mean number of le aves in the tree is determined:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 25 "simplify(T1/T0/n, GAMMA);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,$**,&%\"nG\"\"\"!\"\"F'F',&F&\"\"#F(F'F',&F&\"\"$!\"%F 'F(F&F(#F*F," }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "asympt(\", \+ n);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,0#\"\"%\"\"*\"\"\"*$%\"nG!\"\" #!\"#\"#F*$F)F,#\"#5\"#\")*$F)!\"$#\"#S\"$V#*$F)!\"%#\"$g\"\"$H(*$F)! \"&#\"$S'\"%(=#-%\"OG6#*$F)!\"'F'" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 69 "Notice that 4/9 is near the value we had determined for the value \+ at " }{TEXT 289 6 "n=25. " }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 53 "We c an also determine a closed form for the variance:" }}}{EXCHG {PARA 0 " > " 0 "" {MPLTEXT 1 0 55 "evalf(variance([T, nctree, labelled], size = 25, L)/25);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#$\"+AzS<6!#5" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 49 "var:=simplify(((2*T2+T1)/T0- (T1/T0)^2)/n, GAMMA);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%$varG,$*.,& %\"nG\"\"\"!\"\"F)F),&F(\"\"#F*F)F),(*$F(F,\"\"(F(!#D\"#AF)F),&F(\"\"$ !\"&F)F*,&F(F3!\"%F)!\"#F(F*#F,\"\"*" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "asympt(var, n);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,, #\"#G\"$V#\"\"\"*$%\"nG!\"\"#!#i\"$H(*$F)!\"##!$1\"\"%(=#*$F)!\"$#!$!e \"%hl-%\"OG6#*$F)!\"%F'" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 84 "The as ymptotic forms tell us that both the mean and the variance tend to a c onstant." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "evalf(28/243); " }}{PARA 11 "" 1 "" {XPPMATH 20 "6#$\"+uLE_6!#5" }}}{EXCHG {PARA 0 " " 0 "" {TEXT -1 38 "This is similar to the value found at " }{TEXT 290 4 "n=25" }{TEXT -1 10 " as well. " }}}}{SECT 0 {PARA 5 "" 0 "" {TEXT -1 7 "Forests" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 240 "A non-cros sing forest is a collection of non-crossing trees. We can obtain a for est by substituting in for each vertex of a tree a vertex and a forest , (possibly empty). We are interested in the average number of compon ents in a forest on " }{TEXT 288 1 "n" }{TEXT -1 105 " nodes. Thus, w e must distinguish the occurrence of a new, non-empty forest, marked b y the non-terminal " }{TEXT 291 4 "comp" }{TEXT -1 2 ". " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 115 "fo:=\{B=Prod(Sequence(B),V,Sequenc e(B)),\n V=Prod(Z, F),\n F=Union(Epsilon, comp), comp=Prod(V, \+ Sequence(B))\}:" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 78 "First, let us \+ determine the variance and moments for a large class of forests:" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 55 "evalf(moment([F, fo, labelle d], size =30, comp, 1))/30;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#$\"+!fN 89#!#5" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 54 "evalf(variance([F , fo, labelled], size =30, comp))/30;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#$\"+4)G\"H9!#5" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 80 "We have less success determining the general form with marking in this instance:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 37 "mf:=mark(fo, labelled, [c omp, m], 1):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 29 "FF:=gfsolve (mf, labelled, z):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 84 "F1:=r solve(diffeqtorec(holexprtodiffeq(subs(FF, V[1](z)), y(z)), y(z), u(n) ), u(n));" }}{PARA 8 "" 1 "" {TEXT -1 64 "Error, (in LREtools[polysols ]) Only linear equations are handled" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 62 "However, we do have the generating functions at our disposal. \+ " }}}}}{SECT 0 {PARA 4 "" 0 "" {TEXT -1 28 "Connected and General Grap hs" }}{SECT 0 {PARA 5 "" 0 "" {TEXT -1 16 "Connected graphs" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 206 "We now alleviate the constraint of tree \+ and consider more general graphs. We build the graphs in a similar way , with a few added precautions to avoid double counting of nodes. Cons ider the set of children \{" }{XPPEDIT 18 0 "v[i], v[1+i]" "6$&%\"vG6# %\"iG&F$6#,&\"\"\"\"\"\"F&F+" }{TEXT -1 4 ",..," }{XPPEDIT 18 0 "v[j] " "&%\"vG6#%\"jG" }{TEXT -1 23 "\} attached to the root " }{XPPEDIT 18 0 "v[1]" "&%\"vG6#\"\"\"" }{TEXT -1 79 ". This set divides the grap h into several parts. We have the graphs built on \{" }{XPPEDIT 18 0 "v[2]" "&%\"vG6#\"\"#" }{TEXT -1 7 ", ..., " }{XPPEDIT 18 0 "v[i]" "&% \"vG6#%\"iG" }{TEXT -1 7 "\} and \{" }{XPPEDIT 18 0 "v[j]" "&%\"vG6#% \"jG" }{TEXT -1 6 ", .., " }{XPPEDIT 18 0 "v[n-1]" "&%\"vG6#,&%\"nG\" \"\"\"\"\"!\"\"" }{TEXT -1 87 "\} which are connected themselves by hy pothesis, and between any two adjacent children " }{XPPEDIT 18 0 "v[k ]" "&%\"vG6#%\"kG" }{TEXT -1 5 " and " }{XPPEDIT 18 0 "v[k+1]" "&%\"vG 6#,&%\"kG\"\"\"\"\"\"F'" }{TEXT -1 75 " there either one connected gra ph, or two neighbouring connected graphs. " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 260 "Any graph built from a sequenc e of successive vertices of the circle is a system of arches since the edges of the graphs, or arcs, are not allowed to cross. The endpoin ts of these arches are shared by the graphs built to the left and to t he right of a given " }{XPPEDIT 18 0 "v[k]" "&%\"vG6#%\"kG" }{TEXT -1 57 ", so that we shall say that the size of an arch built on " }{TEXT 264 1 "n" }{TEXT -1 18 " points has size " }{TEXT 263 2 "n-" }{TEXT -1 29 "1. We are interested here in " }{TEXT 265 17 "Elementary Arches " }{TEXT -1 129 ", that is arches that always contain an arch between \+ the first and last points. General arches are easily obtained by seque ncing " }{TEXT 268 3 "EAs" }{TEXT -1 2 ". " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 95 "From this, we have the followin g combstruct specification. In particular, the 5 arguments of a " } {TEXT 266 8 "congraph" }{TEXT -1 23 " entity are as follows:" }}{PARA 0 "" 0 "" {TEXT -1 33 "1. First Z: the root of the graph" }}{PARA 0 " " 0 "" {TEXT -1 45 "2. Second Z: the leftmost point of the first " } {TEXT 267 2 "EA" }}{PARA 0 "" 0 "" {TEXT -1 17 "3 and 4. the two " } {TEXT 269 2 "EA" }{TEXT -1 12 "s built on \{" }{XPPEDIT 18 0 "v[2]" "& %\"vG6#\"\"#" }{TEXT -1 7 ", ..., " }{XPPEDIT 18 0 "v[i]" "&%\"vG6#%\" iG" }{TEXT -1 8 "\} and \{" }{XPPEDIT 18 0 "v[j]" "&%\"vG6#%\"jG" } {TEXT -1 6 ", .., " }{XPPEDIT 18 0 "v[n-1]" "&%\"vG6#,&%\"nG\"\"\"\"\" \"!\"\"" }{TEXT -1 1 "\}" }}{PARA 0 "" 0 "" {TEXT -1 19 "5. The sequen ce of " }{TEXT 270 2 "EA" }{TEXT -1 44 "s found between two consecutiv e children of " }{XPPEDIT 18 0 "v[1]" "&%\"vG6#\"\"\"" }{TEXT -1 36 ". The first term corresponds to one " }{TEXT 271 2 "EA" }{TEXT -1 1 ", " }}{PARA 0 "" 0 "" {TEXT -1 26 "and the second one to two " }{TEXT 273 2 "EA" }{TEXT -1 85 "s. For the latter case, the Z in the Prod sta nds for the lefmost point of the second " }{TEXT 272 2 "EA" }{TEXT -1 1 "." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 206 " The component of interest here is edges. We are interested in the ave rage number of edges in a connected graph. Every arch is an edge, plus the original edges to the children. Thus we distinguish these as " } {TEXT 275 2 "EA" }{TEXT -1 5 " and " }{TEXT 274 6 "conseq" }{TEXT -1 3 ". " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 279 "ar:=\{EA = Union (Sequence(EA, card >= 2), \n Prod(Z, Sequence(EA), Seque nce(EA))\n ),\n congraph = Prod(Z,Z,Sequence(EA), Seq uence(EA),Sequence(conseq)\n ),\n conseq = Union(Sequ ence(EA,card>=1), Prod(Z,Sequence(EA),Sequence(EA)))\}: " }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 56 "marked_edges:= mark(ar, labe lled, [[conseq, EA], m], 2):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 37 "ME:=gfsolve(marked_edges,labelled,z):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 44 "simplify(subs(ME, congraph[1](z)),symbolic);" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#,$*(%\"zG\"\"\",.F%\"\"#*$F%F(\"#=*&-% 'RootOfG6#,**&%#_ZG\"\"$F%F&F&*&,&F&F&F%F2F&F1F(F&*&,&!\"\"F&F%F2F&F1F &F&F%F&F&F%F&!\"&F,!\"#*&F%F(F,F&\"$E\"*&F,F(F%F&F7F&,&F)\"$3\"F7F&F7F 7" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 91 "P0:=rsolve(diffeqtorec(holexprtodiffeq(subs(ME , congraph[0](z)), y(z)), y(z),u(n)), u(n));\n" }{XPPMATH 20 "6#>%#P0G -%'rsolveG6$<(/-%\"uG6#\"\"\"\"\"!/-F+6#F.F.,**&,(\"$K%F-*$%\"nG\"\"# \"%W>F7!%W>F--F+6#F7F-F-*&,(!$o\"F-F6!$3\"F7!$;#F--F+6#,&F7F-F-F-F-F-* &,&F6!#=F7!#OF--F+6#,&F7F-F8F-F-F-*&,(F6F-F7\"\"&\"\"'F-F--F+6#,&F7F- \"\"$F-F-F-/-F+6#FS\"\"%/-F+6#FW\"#B/-F+6#F8F-F;" }}}{EXCHG {PARA 0 " " 0 "" {TEXT -1 57 "We also have moments for any size class available \+ to us: " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 68 "evalf(variance([ congraph, ar, labelled],size =30, [conseq, EA])/30);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#$\"+Z9[0B!#5" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 68 "evalf(moment([congraph, ar, labelled],size =50, [conseq, EA],1 )/50);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#$\"+04&fI\"!\"*" }}}}{SECT 0 {PARA 5 "" 0 "" {TEXT -1 14 "General Graphs" }}{EXCHG {PARA 0 "" 0 " " {TEXT -1 398 "We create general graphs from connected graphs the sam e way we obtained forests from trees. A general graph is obtained from a connected one by the substitution Z -> Prod(Z, G). So that we just have to rewrite the previous grammar by adding a new symbol which mak es this substitution. \nHowever the decomposition of a connected graph misses a configuration for general graphs: the one where vertex " } {XPPEDIT 18 0 "v[1]" "&%\"vG6#\"\"\"" }{TEXT -1 120 " has no child. We are interested in two parameters in this instance: the number of edge s and the number of components. " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 334 "br:=\{EA = Union(Sequence(EA, card >= 2), \n \+ Prod(V, Sequence(EA), Sequence(EA))\n ),\n V =Union(Z,Comp), Comp=Prod(Z, G),\n G=Union(Z,\n Comp, \+ \n Prod(V,V,Sequence(EA), Sequence(EA),Sequence(F))),\n \+ F=Union(Sequence(EA,card>=1), Prod(V,Sequence(EA),Sequence(EA))) \+ \n \}:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 45 "marked_edge s:= mark(br, labelled, [G, m], 2):" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 44 "We attempt to solve the generating function:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 40 "GE:= gfsolve(marked_edges, labelled, z):" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "subs(GE, G[1](z));" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#,$*.,fn%\"zG\"(M2)\\*$F&\"\"%\"+S0SC9*$F&\" \"#!)9h'='*(,&\"\"\"F0F&\"\"$!\"\",(F1F0F&F,*$,(F+F)F&!#7F0F0#F0F,F2F0 F&\"\"*\")W&GC&*(F/F2F3F0F&\"#8\"(O*RK*(F/F2F3F0F&\"\")\")/VnO*(F/F2F3 F0F&\"#6\")wT.E*(F/F2F3F0F&F,#\"),DKmF,*(F/F2F3F0F&F1!*Z$467*(F/F2F3F0 F&\"#5\")o.8V*(F/F2F3F0F&\"#9\"'g0X*(F/F2F3F0F&\"\"&\"+qF[,i*(F/F2F3F0 F&F)!*:'\\\"*o*(F/F2F3F0F&F0#!(2=6&F,*(F/F2F3F0F&\"\"'!,[$p+>9*(F/F2F3 F0F&\"\"(\"+o\"Q9E**(F/F2F3F0F&\"#7\")%y#Q6*$F&F1\"*+\"Gr>*$F&F;!'?6!* *$F&FI!)GT)f&*$F&FA!)Gh@B*$F&Fgn!(s)zk*$F&FO!,!G'R()4\"*$F&FW\",#zn#[C #*$F&FZ!,g0Z?E\"*$F&F>!*saqh\"*$F&F8!*Wx'R5*&F/F2F3F0\"&Ob'!'s58F0F0F& F0,8F]p#\"#jF,FS!#:FC!#=FFF)FQ\"#C!#iF0F&F6F+!#CFin!#[F(!#KFN\"#;F2F/F 2,0F]p#\"#:F,FSFOFCFW!#9F0F&F6F+!\")FFF)F2,BFY\"&7!yFgo!'w\\5Feo\"'[QS FV!'u#y#FN\"'V(>\"Fco!'OCCFQ#\"'H(z\"F,F(!']'Q\"Fin\"&]o$FF#!&pO$F,FC# !%X#*F,F+\"%AzF&!%)f\"FS#\"%j;F,\"#kF0F]pFipF2F2" }}}{EXCHG {PARA 0 " " 0 "" {TEXT -1 132 "Unfortunately, again rsolve is unable to determin e an expression for the coefficients. However, we can solve for specif ic instances:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 113 "evalf(variance([G , br, labelled],size =30, [F, EA])/30);\nevalf(moment([G, br, labelled ],size =30, [F, EA],1)/30);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#$\"+i'[ 01&!#5" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#$\"+IbLy5!\"*" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 48 "Next, we handle components. Each occurre nce of " }{TEXT 302 4 "comp" }{TEXT -1 24 " marks a new component. " } }{PARA 0 "> " 0 "" {MPLTEXT 1 0 47 "marked_comps:= mark(br, labelled, \+ [Comp,m], 2):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 41 "GC:= gfsolve(marke d_comps, labelled, z):\n" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "subs(GC, G[1](z));" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#**,D*(,&\"\"\"F '%\"zG\"\"$!\"\",(F)F'F(\"\"#*$,(*$F(F,\"\"%F(!#7F'F'#F'F,F*F'F(\"\") \"&wX#*$F(\"\"(!&_\"\\*(F&F*F+F'F(F6\"'!GD#*(F&F*F+F'F(\"\"'!*!3-45*$F (F;\"*O$)fN\"*(F&F*F+F'F(\"\"&\"*'*G')*>*$F(F@!*wPS3$*$F(F0\"*!Gd&*=*( F&F*F+F'F(F0!*OxJ4\"*$F(F)!)kOpP*(F&F*F+F'F(F)\")#*f!*>*(F&F*F+F'F(F,! (C%\\5F/\"('4+@*(F&F*F+F'F(F'!#HF(\"$3\"*&F&F*F+F'#F*F,F,F'F'F(F,,BF8 \"'#R\\*F5!(7(f7F:!(;'=?F=\"(k+9$F?!'K!=#FB!&Ko&FF\"'?\"=&FD!'C#o*FJ\" &z-'FH!&WI)FL#!&dN$F,F/\"&US$FO!#?F(\"#sFRFSF,F'F*,0FR#\"#:F,FOF@FLF;! #9F'F(F1F/!\")FJF0F*" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 111 "Again, t he closed form for coefficients is beyond the capabilities of rsolve. \+ So, we look at specific examples:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 107 "evalf(variance([G, br, labelled],size =30, Comp)/30);\nevalf(mome nt([G, br, labelled],size =30, Comp,1)/30);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#$\"+FW.,5!#5" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#$\"+Pr& 38\"!#5" }}}}}{SECT 0 {PARA 4 "" 0 "" {TEXT -1 26 "Dissections and Par titions" }}{SECT 0 {PARA 5 "" 0 "" {TEXT -1 11 "Dissections" }}{PARA 0 "" 0 "" {TEXT -1 33 "A dissection of a convex polygon " }{XPPEDIT 18 0 "P[n]" "&%\"PG6#%\"nG" }{TEXT -1 2 "=\{" }{XPPEDIT 18 0 "v[1]" "& %\"vG6#\"\"\"" }{TEXT -1 7 ", ..., " }{XPPEDIT 18 0 "v[n]" "&%\"vG6#% \"nG" }{TEXT -1 348 "\} is a partition of the polygon into polygonal r egions by means of non-intersecting diagonals. Our representation is t he same as non-crossing graphs whose connected components are points \+ (polygons on one point) , edges (polygons on two points) and cycles \+ (all polygons). We are curious to determine the average number of par ts in a dissection. " }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 52 "diss G:=\{Di=Union(Z, P), P=Sequence(Di, card >= 2)\}:" }}{PARA 0 "> " 0 " " {MPLTEXT 1 0 87 "marked_dp:= mark(dissG, labelled, [[Z, P], m], 2): \nMD:=gfsolve(marked_dp, labelled, z);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#MDG%%FAILG" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 132 "A more ca reful look at this failure shows that it is actually due to a weakness in series. This can be overcome by increasing Order:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "Order:=20:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 36 "MD:=gfsolve(marked_dp, labelled, z):" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 65 "Unfortunately the recurrence set up by gfun is unsolveabl e using " }{TEXT 0 6 "rsolve" }{TEXT -1 102 ", so we cannot attain a c losed form for the coefficients. However, we do have the generating fu nction:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 36 "simplify(subs(MD , Di[1](z)), power);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#,$*&,4!\"\"\" \"\"%\"zG\"\"#*$,(F'F'F(!\"'*$F(F)F'#F'F)F'F-\"\"%*&F(F'F+F.F'*$F(\"\" $F,*&F(F)F+F.F2*$F(F/F'*&F(F2F+F.F&F',0F'F'F(!\"&F*F&F-F7F0F)F1F'F3F&F &#F'F/" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 61 "evalf(variance([D i, dissG, labelled], size =75, [P, Z])/75);\n" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#$\"+Wl!4t\"!#5" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 57 "evalf(moment([Di, dissG, labelled], size =75, P, 1)/75);\n" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#$\"+r3K2q!#5" }}}}{SECT 0 {PARA 5 "" 0 "" {TEXT -1 11 "Partitions " }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 55 "A non crossing partition of size n is a partition of [" }{TEXT 292 1 " n" }{TEXT -1 14 "]=\{1, 2, ..., " }{TEXT 293 1 "n" }{TEXT -1 15 "\} su ch that if " }{TEXT 294 13 "a < b < c < d" }{TEXT -1 22 " and a block \+ contains " }{TEXT 295 1 "a" }{TEXT -1 5 " and " }{TEXT 296 1 "c" } {TEXT -1 25 ", then no block contains " }{TEXT 297 1 "b" }{TEXT -1 5 " and " }{TEXT 298 1 "d" }{TEXT -1 332 ". Thus, if we consider each par tition block as a polygon, partitions are the \"forest\" version of d issections. Given a partition block, possibly empty, one gets a bigger partition by substituting to each vertex the product between\nZ and a nother partition. We are interested in the average number of partition blocks in a partition. " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 62 "partG:=\{P=Sequence(V, card>0), V = Prod(Z,Union(P, Epsilon))\}:" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 88 "marked_parts:= mark(partG, labelled , [P, m], 2):\nMP:=gfsolve(marked_parts, labelled, z):" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 48 "We try to solve for the coefficients expl icitly:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 312 "P1:=rsolve(diff eqtorec(holexprtodiffeq(subs(MP, P[1](z)), y(z)), y(z),u(n)) minus\{u( 0)=0\}, u(n)); \nP0:=rsolve(diffeqtorec(holexprtodiffeq(subs(MP, P[0]( z)), y(z)), y(z),u(n)) minus\{u(0)=0\}, u(n));\nP2:=rsolve(diffeqtorec (holexprtodiffeq(subs(MP, P[2](z)), y(z)), y(z), u(n)) minus\{u(2)=0, \+ u(1)=0, u(0)=0\}, u(n));\n" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#P1G,$ **)\"\"%%\"nG\"\"\"-%&GAMMAG6#,&F)F*#F*\"\"#F*F*-F,6#,&F)F*F*F*!\"\"%# PiG#F4F0F/" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#P0G**)\"\"%%\"nG\"\" \"-%&GAMMAG6#,&F(F)#F)\"\"#F)F)-F+6#,&F(F)F/F)!\"\"%#PiG#F3F/" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%#P2G,$**)\"\"%%\"nG\"\"\"-%&GAMMAG6# ,&F)F*#!\"\"\"\"#F*F*-F,6#,&F)F*F0F*F0%#PiGF/#F*\"\")" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 39 "simplify(P1/P0/n, GAMMA);\nasympt( \", n);" }}{PARA 11 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 36 "The mean tends to the constant 1/2. " }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,$*&,&%\"nG\"\"\"F'F'F'F&!\"\"#F'\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,&#\"\"\"\"\"#F%*$%\"nG!\"\"F$" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 65 "var:=simplify(((2*P2+P1)/P0-(P1/P0)^2)/n, GAMMA) ;\nasympt(var, n);" }}{PARA 0 "" 0 "" {TEXT -1 40 "The variance tends \+ to the constant 1/8. " }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%$varG,$**,& %\"nG\"\"\"!\"\"F)F)F(F*,&F(F)F)F)F),&F(\"\"#F*F)F*#F)\"\"%" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#,L#\"\"\"\"\")F%*$%\"nG!\"\"#F%\"#;*$F(!\"## !\"$\"#K*$F(F/#F/\"#k*$F(!\"%#F/\"$G\"*$F(!\"&#F/\"$c#*$F(!\"'#F/\"$7& *$F(!\"(#F/\"%C5*$F(!\")#F/\"%[?*$F(!\"*#F/\"%'4%*$F(!#5#F/\"%#>)*$F(! #6#F/\"&%Q;*$F(!#7#F/\"&oF$*$F(!#8#F/\"&Ob'*$F(!#9#F/\"'s58*$F(!#:#F/ \"'W@E*$F(!#;#F/\"')GC&*$F(!#<#F/\"(w&[5*$F(!#=#F/\"(_r4#*$F(!#>#F/\"( /V>%-%\"OG6#*$F(!#?F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" } }}}}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{MARK "0 4 0" 17 }{VIEWOPTS 1 1 0 1 1 1803 }