Counting rooted bushes

Combinatorial issues could be fascinating for their very own sake, however they’re extra fascinating when there’s a connection to an issue exterior combinatorics, and the extra surprising the connection the higher.

Counting the variety of unlabeled rooted bushes [1] with n nodes is a pure arithmetic drawback. Designing numerical strategies for fixing differential equations is an utilized arithmetic drawback. And but the 2 are intently linked.

Let t(n) be the variety of distinct unlabeled rooted bushes with n nodes. The diagram beneath reveals that the primary few phrases of this sequence are 1, 1, 2, and 4.

In an earlier put up I confirmed that designing a 4-stage specific Runge-Kutta technique required fixing a system of 8 equations in 10 unknowns, leaving two levels of freedom within the options.

The variety of constraints c(s) wanted to design an s-stage specific RK technique is the same as the variety of rooted bushes with as much as s nodes:

c(s) = t(1) + t(2) + t(3) + … + t(s)

It is because there’s a one-to-one correspondence between constraints on the nth by-product of an RK components and rooted bushes, and an s stage technique has to fulfill the constraints of all phases as much as s. Within the instance of the 4th order RK technique, we now have

c(4) = t(1) + t(2)  + t(3) + t(4) = 1 + 1 + 2 + 4 = 8.

The primary few values [2] of t(n) are

1, 1, 2, 4, 9, 20, 48, 115, 286, 719, 1842, 4766, 12486, 32973, …

and so you possibly can see that t(n) grows rapidly. In actual fact, it grows exponentially [3].

Nevertheless, the variety of parameters in an s stage RK technique is s(s + 1)/2. The variety of equations grows exponentially and the variety of variables grows solely quadratically, so sooner or later you’ve got extra equations than variables. That’s already the case for s = 5 as a result of you’ve got 17 constraints on 15 variables. The system has an answer as a result of symmetry concerns render a number of the equations redundant.

A tenth order RK technique requires 17 phases. (See the earlier put up for why the variety of phases exceeds the order when the order is bigger than 4.) Designing such a way would require fixing over one million equations in 153 variables, and but it may be completed. [4]

Associated posts

[1] This can be a barely contradictory time period. Unlabeled means the we don’t distinguish the nodes. However we do distinguish one node, specifically the foundation.

[2] See OEIS A000081.

[2] Richard Otter proved in 1948 that the variety of unlabeled rooted bushes with n nodes is asymptotically C αⁿ / n^−3/2 the place C = 0.4399… and α = 2.9557…. The cumulative sum is not less than this massive since Otter’s estimate offers the dimensions of the final time period within the sum.

[3] E. Hairer. A Runge-Kutta Methodology of Order 10. J. Inst. Maths Applics (1978) 21, 47-59