and then increasing binary trees. How many different binary trees are there
with increasing labels on every path? and so these are all the possibilities
for a small number of trees. there's more binary trees because every
node has the order is significant, every node has 0 or 2 children.
and so any, anyway, these are the possibilities in there's actually n
factorial different binary trees of size n.
And again, this is an easy result that has all this structure behind it.
it suggests a bijection and actually there is a bijection between increasing
binary trees and permutations. that's quite easy.
So let's look at the analytic commonotorics of increasing trees, and in
order to do that, we're going to introduce another construction called the
boxed product construction. And this is just an example that the
operations that we use in the symbolic method They're not necessarily a closed
set. it's not difficult to add more operations
to respond to the needs of different applications.
So in this case, the increasing facet of the application means that we need some
combinatorial operation that takes that into account, and that's what boxed
product is. So we're going to use the notation A
equals B box star C, it means the same as star except that we're only going to
consider the subset where the smallest element goes into B, goes into the first
one. So, our little example of 1, 2 box star,
1, 2, 3. out of these ten possibilities, this is
only four of them that have the smallest element in in the, from the first
product. So, and again the transfer theorem which
I'll give a proof in a second. if you do the box product and you have
the generating functions for b and c the enter, the generating function equation
is a prime equals b prime c. and so here's the proof of that.
so just with commonatorics. so the number of elements in a, you can
pick You have to pick the smallest one, for b, and then, you can pick the other k
minus one from n minus one and any one of these n minus one just came out one ways.
And then there's however many elements there are in b.
If there's of em, then there's gotta be n minus k and c.
So that's an equation convolution that gives a number of elements in a.
divide both sides by n factorial and multiply it by z to the n minus 1 and sum
and do the convolution and rearrange terms.
then we can separate into two different sums.
and that's a prime of z on the left, and b prime z, c of z on the right.
so and it's not the proof that's important.
It's how simple the transfer is. So let's check it for a small example.
So, again, this is 1 2 box star, 1 2 1 2 3 is those four things.
A generating function for that is 4 z to the 5th over 5 factorial.
A generating function for B of z is z squared over 2 factorial, and C of z is z
3 over 3, like that. so a prime of z is multiplied by 5.
5 times 4 is either is either 4th over 3 factorial b prime of z is z and that
checks. a prime of z equals b prime of z, times c
of c. So, we have a operation and we have a
transfer theorem. so then we can use that to enumerate
increasing trees, like increasing Cayley trees or increasing binary trees.
So for, Cayley trees, it's, a Cayley tree is z-box-star, a set of Cayley trees.
That just means z box star means the 1 has to go as the label of the root, and
the rest of them are labeled increasing trees.
So, from the transfer theorem, we immediately get the generating function
equation, q prime of z equals e to the q of z.
The b, in this case, the first one, generating function z, its derivative is
1, so it goes away, and then sets all left.
Q parameter is equal to q of z. That's an equation that the exponential
generating function of labeled increasing Cayley trees has to satisfy.
and you can solve that differential equation log 1 over 1 minus z works.
so its derivative is 1 over 1 minus z, and e to that power is 1 over 1 minus z.
so that means that the counting sequence is n factorial times the coefficient of z
to the n in that. which is just n minus 1 factorial.
so, that these a simple proof of the number of Cayley trees is n minus 1
factorial, using analytic commonatorics. Similarly for binary trees it's z box
times b times b, and that transfer's to b prime of z equals b of z squared.
And we can solve that one and get 1 over 1 minus z for that, which is a proof that
the number of labeled increasing binary trees is just an n factorial.
Again, analytic combinatorics provides simple proof of these results without any
kind of, counting arguments. and not only that, but it can be extended
to handle situations where there's restrictions on the degree of the nodes
and and many other things. and by the way increasing binary trees of
bijection with permutations again, we don't always find bijections like this
but this one's an easy one If you take a increasing binary tree in then you just
flatten it, then you get a permutation. Or if you take a permutation, you take
the smallest element, make it the root, and then do the same thing for the left
and the right, you get an increasing binary tree.
so that's an easy proof, that increasing tree's n factorial.
Not so easy for Cayley trees. That's a classical problem in
combinatorics, actually. okay, so again we start with a base, a
basic set of combinatorial constructs and we can consider the analysis of all kinds
of tree structures. and these are just a few of many many,
examples of the study of labelled trees. It's a classical topic in, combinatorics
but analytic combinatorics, allows us to handle all of these things in uniform
manner. That's an introduction to the study of
labelled trees using, combinatorial contstructions, and symbollic method.
How to derive equations by generating functions.