Two Recurrences for Counting Rooted Trees

A rooted tree is a tree with a special node called the root. The number of rooted trees with $n$ nodes is given by the sequence A000081 in the OEIS. They provide the following recurrence relation: $$a_{n+1} = \frac{1}{n} \sum_{k=1}^n \left( \sum_{d \mid k} d \cdot a_d \right) a_{n-k+1}$$ I came up with a different one. I was surprised that they can produce the same sequence despite appearing so different. $$a_{n+1} = \sum_{\left( p_1^{r_1} \, \ldots \, p_\ell^{r_\ell} \right) \, \vdash \, n} \left( \prod_{i=1}^{\ell} \left(\!\!\binom{a_{p_i}}{r_i}\!\!\right) \right)$$

The sum is over all partitions of $n$, and $\left( p_1^{r_1} \ldots p_\ell^{r_\ell} \right)$ is the frequency representation of a partition. $\left(\!\binom{n}{k}\!\right)$ is the multiset coefficient. It represents the number of ways to choose $k$ elements out of $n$ allowing repetition, and is equal to $\binom{n+k-1}{k}$.

The image below shows how the second formula can be derived with an example for $a_{25}$. Every node that is directly attached to the root is the root of a subtree, and the subtrees are arranged in a partition. Changing the partition changes the tree. You can switch out subtrees for another subtree with the same number of nodes, to get a new tree without changing the partition.

Using the program below I have verified that both recurrence relations are correct up to at least the $30^\text{th}$ term.

	public class RootedTrees {
	static long[] a = new long[100];
	static long[] b = new long[100];
	public static void main(String []args) {
	a[1] = 1;
	b[1] = 1;
	for (int n = 1; n < 30; n++) {
	System.out.print(afunc(n) + ", ");
	}
	System.out.println();
	for (int n = 1; n < 30; n++) {
	System.out.print(bfunc(n) + ", ");
	}
	}
	public static long afunc(int n) {
	if (a[n] != 0) return a[n];
	long sum = 0;
	for (int k = 1; k <= n-1; k++) {
	long innerSum = 0;
	int[] divs = getDivisors(k);
	for (int i = 0; i < divs.length; i++) {
	innerSum += divs[i] * afunc(divs[i]);
	}
	sum += innerSum * afunc(n - k);
	}
	a[n] = sum / (n-1);
	if (sum % (n-1) != 0) System.out.print("OUCH ");
	return a[n];
	}
	public static int[] getDivisors(int k) {
	int[] tmp = new int[k];
	int ind = 0;
	for (int i = 1; i <= k; i++) {
	if (k % i == 0) {
	tmp[ind] = i;
	ind++;
	}
	}
	int[] ret = new int[ind];
	for (int i = 0; i < ind; i++) {
	ret[i] = tmp[i];
	}
	return ret;
	}
	public static long bfunc(int n) {
	if (b[n] != 0) return b[n];
	long sum = 0;
	int[][][] partitions = new Partition(n-1).get();
	for (int p = 0; p < partitions.length; p++) {
	long product = 1;
	for (int i = 0; i < partitions[p][0].length; i++) {
	product *=
	comboRep(bfunc(partitions[p][0][i]),
	(long) partitions[p][1][i]);
	}
	sum += product;
	}
	b[n] = sum;
	return sum;
	}
	public static long comboRep(long n, long k) {
	long product = 1;
	for (long i = n; i <= n+k-1; i++) {
	product *= i;
	}
	long ans = product / factorial(k);
	if (product % factorial(k) != 0) System.out.print("OUCH ");
	return ans;
	}
	public static long factorial(long n) {
	if (n == 0) return 1L;
	return n * factorial(n-1);
	}
	public static class Partition {
	private int n;
	private String part;
	public Partition(int n) {
	this.n = n;
	}
	public int[][][] get() {
	part = "";
	partition(n, n, "");
	String[] x = part.trim().split("\n");
	int[][][] y = new int[x.length][][];
	for (int i = 0; i < x.length; i++) {
	String[] xs = x[i].trim().split(" ");
	int curr = -1;
	int ind = -1;
	int[][] tempArr = new int[2][xs.length];
	for (int j = 0; j < xs.length; j++) {
	int par = Integer.parseInt(xs[j]);
	if (par != curr) {
	ind++;
	tempArr[0][ind] = par;
	tempArr[1][ind] = 1;
	curr = par;
	} else {
	tempArr[1][ind]++;
	}
	}
	y[i] = new int[2][ind+1];
	for (int j = 0; j <= ind; j++) {
	y[i][0][j] = tempArr[0][j];
	y[i][1][j] = tempArr[1][j];
	}
	}
	return y;
	}
	public void partition(int n, int max, String prefix) {
	if (n == 0) {
	part = part + prefix + "\n";
	return;
	}
	for (int i = Math.min(max, n); i >= 1; i--) {
	partition(n-i, i, prefix + " " + i);
	}
	}
	}
	}

view raw RootedTrees.java hosted with ❤ by GitHub