1
$\begingroup$

Recently I worked on a problem that involved finding the total possible rooted, labeled ternary trees with n vertices. After doing some math and using Lagrange inversion I found a formula for the total possible ternary trees with n vertices. I found great joy in exploring this problem as it took me on a small journey through a lot of combinatorial mathematics that I had not yet explored or experienced in school. I then posed the question, if we generalize the trees to be k-ary trees, is there some general formula?

Does such a formula exist? Im familiar with Cayley's formula, but this is slightly different since the trees in this case are rooted.

Can anyone explain to me the process of enumerating trees in such a way that you can generalize a formula for k-ary trees on n vertices? Where do you even start?

$\endgroup$
  • $\begingroup$ This perhaps ? math.stackexchange.com/questions/145515/… $\endgroup$ – darij grinberg Apr 8 '19 at 2:03
  • $\begingroup$ @darijgrinberg close, but not quite. Those are for unlabelled trees. If our trees are labeled, the math gets more...involved. $\endgroup$ – attemptwasmade Apr 8 '19 at 2:35
  • $\begingroup$ To make the trees rooted, it seems like you just need a factor of $n$. Is the idea with $k$-ary trees that all vertices have degree $1$ or $k$? $\endgroup$ – Misha Lavrov Apr 8 '19 at 2:57
  • $\begingroup$ Are your trees plane (i.e., does a vertex distinguish between its children)? $\endgroup$ – darij grinberg Apr 8 '19 at 3:04
  • $\begingroup$ @darijgrinberg Yes, each child of a given vertex are all distinct paths to a further subforest. $\endgroup$ – attemptwasmade Apr 8 '19 at 20:23
1
$\begingroup$

The combinatorial class of $k$-ary rooted unlabeled trees is

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

Which gives the functional equation

$$T(z) = z + z \times T(z)^k$$

so that

$$z = \frac{T(z)}{1+T(z)^k}$$

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{(1+w^k)^n}{w^n} \; dw.$$

This is

$$T_n = [[n\equiv 1 \bmod k]] \frac{1}{n} [w^{n-1}] (1+w^k)^n \\ = [[n\equiv 1 \bmod k]] \frac{1}{n} [w^{k\times (n-1)/k}] (1+w^k)^n \\ = [[n\equiv 1 \bmod k]] \frac{1}{n} [w^{(n-1)/k}] (1+w)^n.$$

We thus have for the answer

$$\bbox[5px,border:2px solid #00A000]{ [[n\equiv 1 \bmod k]] \frac{1}{n} {n\choose (n-1)/k}.}$$

With this answer we observe however that we can get a better formula by adhering to the convention that the size of the tree is the number of internal nodes rather than the total number of nodes. This yields the class

$$\mathcal{T} = \mathcal{E} + \mathcal{Z} \times \textsc{SEQ}_{=k}(\mathcal{T})$$

or $$T(z) = 1 + z \times T(z)^k$$

so that

$$z = \frac{T(z)-1}{T(z)^k}$$

We get

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

We thus have for the answer in terms of the number of internal nodes

$$\bbox[5px,border:2px solid #00A000]{ \frac{1}{n} {kn\choose n-1}.}$$

We then have for $k=3$ (ternary trees) the sequence

$$1, 3, 12, 55, 273, 1428, 7752, 43263, 246675, 1430715, \ldots$$

which points to OEIS A001764, where we find confirmation. Similarly, $k=4$ (quartic trees) gives

$$1, 4, 22, 140, 969, 7084, 53820, 420732, 3362260, 27343888, \ldots$$

which points to OEIS A002293.

We may re-write the binomial coefficient as follows:

$$\frac{(kn)!}{n! \times ((k-1)n+1)!}$$

or

$$\bbox[5px,border:2px solid #00A000]{ \frac{1}{(k-1)n+1} {kn\choose n}.}$$

This form is sometimes preferred because it is defined when $n=0$, where it yields the value one (one empty tree). It also happens to match the standard Catalan number formula when $k=2.$

Addendum. I did not read the question properly and answered for rooted ordered unlabeled k-ary plane trees instead of rooted labeled k-ary trees. The combinatorial class now becomes

$$\mathcal{T} = \mathcal{Z} + \mathcal{Z} \times \textsc{SET}_{=k}(\mathcal{T})$$

or

$$T(z) = z + z \times \frac{1}{k!} T(z)^k$$

so that

$$z = \frac{T(z)}{1+T(z)^k/k!}.$$

The computation is the same as before and we obtain (multiply by $n!$ for an EGF)

$$\bbox[5px,border:2px solid #00A000]{ [[n\equiv 1 \bmod k]] \frac{(n-1)!}{k!^{(n-1)/k}} {n\choose (n-1)/k}.}$$

We get for binary trees on $n=2m+1$ nodes

$$1, 3, 60, 3150, 317520, 52390800, 12843230400, 4382752374000, \\ 1986847742880000, 1155153277710432000, 838011196011749760000, \ldots $$

which is OEIS A036770. For ternary trees on $n=3m+1$ nodes we find

$$1, 4, 420, 201600, 264264000, 734557824000, 3723191087616000, \\ 31125877492469760000, 399532678960326912000000, \ldots $$

which is OEIS A036771. Quartic trees on $n=4m+1$ nodes then yield

$$1, 5, 2520, 9909900, 150089940000, 6217438242015000, \\ 574985352122181000000, 103753754577643425255000000, \ldots$$

which is OEIS A036772.

For convenience we may write $n=mk+1$ to do without the Iverson bracket and get

$$\bbox[5px,border:2px solid #00A000]{ \frac{(mk)!}{k!^m} {mk+1\choose m}.}$$

Concluding remark. The permutation group acting on the children may sensibly be taken to be the one consisting of the identity permutation, the cyclic group or the symmetric group. These correspond to the operators $\textsc{SEQ},$ $\textsc{CYC}$ and $\textsc{SET}.$ The cyclic case signifies that the tree is being embedded in three-space and rooted at the origin so that we may rotate the children. Children at a given depth are all in the same horizontal plane parallel to the plane at $z=0$ and children of the same parent are located on a circle in their plane separated by an angle of $2\pi /k$ radians.

A recent comment by OP indicates what is being asked for is the operator $\textsc{SEQ}$ (plane trees). We get in the labeled case

$$\bbox[5px,border:2px solid #00A000]{ [[n\equiv 1 \bmod k]] (n-1)! {n\choose (n-1)/k}.}$$

These are not in the OEIS. I suspect this is because the labeled case is obtained from the unlabeled case by trivially distributing the $n$ labels in $n!$ ways into the nodes of an unlabeled source tree. What happens here is that the $\textsc{SEQ}$ operator is the same algebraically in the labeled and the unlabeled case, which does not hold for $\textsc{CYC}$ and $\textsc{SET}.$ The sequence operator admits no symmetries, which is why all $n!$ distributions of the labels are different, forming an orbit of order one.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ This is an awesome explanation. Sorry for the confusion on the unlabeled property. Thanks so much!! $\endgroup$ – attemptwasmade Apr 9 '19 at 17:09
  • $\begingroup$ Thank you, I hope you find it useful. $\endgroup$ – Marko Riedel Apr 9 '19 at 17:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.