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.