Using symbolic method to calculate number of particular plane trees

128 Views Asked by At

I was asked to use the symbolic method for calculate the number of plane rooted trees with $n$ vertices such that each inner vertex have exactly three leaves or a sequence of at least two trees.

So I stated $$\mathcal{T}=\mathcal{Z}\times (\mathcal{Z}^3+\mathcal{T}^2\times SEQ(\mathcal{T})),$$ where $\mathcal{Z}$ is the atomic class. The problem was that, solving it, I got $$T(x)=\frac{x^4+1\pm\sqrt{(x^4+1)^2-4x^4(x+1)}}{x+1}$$ which seems impossible to solve. I think I did an important misstake in the equation for $\mathcal{T}$, but I can't see it.

1

There are 1 best solutions below

0
On

I would start with the following combinatorial class:

$$\def\textsc#1{\dosc#1\csod} \def\dosc#1#2\csod{{\rm #1{\small #2}}} \mathcal{T} = \mathcal{Z} \times \mathcal{U} + \mathcal{Z} \times \textsc{SEQ}_{\ge 2}(\mathcal{T})$$

which gives the functional equation

$$T(z) = uz + z \frac{T(z)^2}{1-T(z)}$$

so that

$$z = \frac{T(z) (1-T(z))}{T^2(z) - uT(z) + u}$$

We then have

$$n \times T_n = [z^{n-1}] T'(z)$$

and from the Cauchy Coefficient Formula

$$[z^{n-1}] T'(z) = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^n} T'(z) \; dz.$$

Now put $T(z) = w$ so that $T'(z) \; dz = dw$ and we obtain

$$\frac{1}{2\pi i} \int_{|w|=\gamma} \frac{(w^2-uw+u)^n}{w^n (1-w)^n} \; dw \\ = \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{(w^2+u(1-w))^n}{w^n (1-w)^n} \; dw.$$

Next for trees having $k$ leaves of type $\mathcal{U}$ we get (we must evidently have $0\le k\le n$)

$${n\choose k} \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{w^{2n-2k}(1-w)^k}{w^n (1-w)^n} \; dw \\ = {n\choose k} \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{1}{w^{2k-n} (1-w)^{n-k}} \; dw.$$

Observe what happens when $k=n,$ we find

$$\frac{1}{2\pi i} \int_{|w|=\gamma} \frac{1}{w^{n}} \; dw = [[n=1]].$$

This means we have one tree consisting of a node of type $\mathcal{Z}$ with a single child node of type $\mathcal{U}.$ When $n\gt 1$ we must have $k\le n-1,$ a refinement. Continuing,

$${n\choose k} {2k-n-1+n-k-1\choose n-k-1} = {n\choose k} {k-2\choose n-k-1}.$$

The total contribution where a node of type $\mathcal{U}$ has weight three and of type $\mathcal{Z}$ has weight one is $n+3k.$ Letting $m=n+3k$ be the total number of nodes by weight, the condition $k\le n-1$ then implies $k\le m-3k-1$ or $4k\le m-1.$ For the residue not to vanish we must also have $2k\gt n$ or $5k\gt m.$ Hence the number of trees with $m$ nodes is

$$\bbox[5px,border:2px solid #00A000]{ \sum_{k=\lfloor m/5 \rfloor+1}^{\lfloor (m-1)/4\rfloor} \frac{1}{m-3k} {m-3k\choose k} {k-2\choose m-4k-1}.}$$

This holds when $n\ge 2$ or at least two nodes of type $\mathcal{Z}.$ We get a single tree on four nodes total when $n=1.$ Due to the sequence constraint $\textsc{SEQ}_{\ge 2}$ the next tree to appear is when $n=3$ with $m=9.$