{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 }