# A peculiar numerical coincidence

One of the questions I put on a recent take-home exam is to determine a generating function for the number of $n$-vertex trees where the children of each vertex occur a specific order, and there is no vertex with precisely one child. For example, there are $6$ such trees on $6$ vertices.

.

The first few values of this sequence are

1, 0, 1, 1, 3, 6, 15, 36, 91 …

When I started computing these, I noticed a strange pattern: they were all triangular numbers. And that’s not all; they were:
1
0
1
1
2+1
3+2+1
5+4+3+2+1
8+7+6+5+4+3+2+1
13+12+11+10+9+8+7+6+5+4+3+2+1

Fibonacci triangular numbers!

I recounted the next term several times, in different ways. I finally confirmed that the pattern fails, by the smallest bit: The next Fibonnaci triangular is 231, and the number of trees on 8 elements is 232. This is one of the most persuasive false patterns I’ve encountered.

Keeping going, the sequences separate from each other: the tree sequence continues 603, 1585, 4213, 11298, 30537 while the Fibonacci triangulars are 595, 1540, 4005, 10440. The difference between the sequences is 1, 8, 45, 208, 858, 3276 … These are suspiciously round numbers, though I don’t see a pattern in them yet.

Consider this a thread either to discuss the patterns above, or to discuss your own favorite false patterns.

## 11 thoughts on “A peculiar numerical coincidence”

1. Oliver Nash says:

Nice find!

I think the sequence of Perrin pseudoprimes is spookily misleading and one of the best counterexamples to engineers’ induction.

2. Ben, can you think of a “bijective” proof of this fact? In other words, can you take a class of combinatorial objects counted by Fibonacci triangular numbers and use them to construct the kind of trees you’re looking at, and maybe even show that this construction gives all such trees for small n?

3. It’s kind of like “Benford’s law meets Ramsey theory”: there aren’t enough distinct small structures to go around so there’s going to be misleading overlaps like this now and again.

4. Tracy Hall says:

When a pair of sequences track each other so closely before diverging, often it’s because there is some natural restriction (e.g. planarity, non-crossing, realizable, etc.) whose counterexamples are complicated enough not to occur for small n. The obvious question, then, is: What is the unique “bad” tree on 8 vertices? (And the 8 “bad” trees on 9 vertices, etc.)

Another possibility is subtly different ways of counting equivalence, in which case the question is: What pair of trees on 8 vertices are really the “same” if you look at them in the right way?

5. David Speyer says:

OK, here is a partial algebraic explanation. The generating function for these trees is

$\displaystyle{\frac{1+x-\sqrt{1-2x-3x^3}}{2(1+x)}}.$

The corresponding continued fraction is

$\displaystyle{\frac{1}{x^{-1} + \frac{1}{-x^{-1} + 1 + \frac{1}{x^{-1} -1 + \frac{1}{\cdots}}}}}$

where $x^{-1}-1$ and $-x^{-1}+1$ alternate indefinitely. If I truncate the continued fraction after $2$ rounds of repetition, I get a rational function which simplifies to

$\displaystyle{\frac{x(1-3x + 3x^3)}{(1+x)(1-3x+x^2)(1-x-x^2)}}.$

I haven’t checked carefully, but this rational function appears to be the generating function for Fibonacci triangulars.

Obviously, this doesn’t satisfy the way that a combinatorial proof would; I’m still curious to find one.

6. A bit of self promotion: I blogged about continued fractions for power series last year. In general, the continued fraction of $\sqrt{D(x)}$ need not be periodic; this only happens when a certain class in the Jacobian of $y^2=D(x)$ is torsion. If $D$ has degree $2$, as in this example, then the curve in question has genus $0$, so the Jacobian is trivial. Thus, it is not a surprise that this continued fraction repeats.

7. If you’re still interested in this problem, here’s an observation that might help. The exponential generating function $y$ for this sequence satisfies $y = x \left( \frac{1}{1 - y} - y \right)$, which can be rearranged to give $y = x + (1 + x) y^3$. This recurrence describes trees in which every vertex has 0 or 3 children and in which some of the vertices, including any vertex with 0 children, are colored black. (The power of $x$ counts the number of black vertices.) It might be easier to get an injection from here. Restricting the depth of both types of trees (which works in the Catalan case) doesn’t seem to work here, though.

8. Er, I mean the ordinary generating function.

9. Dave Penneys says:

These numbers are the multiplicity of the trivial representation in the tensor powers of the adjoint representation of su(2). Over the summer, a group of us were calculating the left-regular von Neumann algebra generated by the fusion algebra of $M-M$ bimodules of the Temperley-Lieb subfactor $N\subset M$ of index $\geq 4$. We found this sequence to be the moments of the operator given by left multiplication by the Jones-Wenzl projection $f^{(2)}$. It was pretty misleading for a few hours!

10. Allan says:

The number of conjugacy classes
of commutative ordered pairs in S_N:

1 4 8 21 39 92 170 360

The number of nonzero elements
in the character table of S_N:

1 4 8 21 39 92 170 331