## A peculiar numerical coincidence October 6, 2010

Posted by David Speyer in Uncategorized.

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.

1. Oliver Nash - October 7, 2010

Nice find!

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

2. FelixCQ - October 7, 2010

Very nice false pattern indeed. One can always cheat and lookup the On-Line Encyclopedia of Integer Sequences, which gives various interpretations of the ‘tree’ sequence:
http://www.research.att.com/~njas/sequences/?q=signed:1,1,3,6,15,36,91

Not sure it actually qualifies at a false pattern, but i also like the example of the Borwein integral (http://en.wikipedia.org/wiki/Borwein_integral). Of course the explanation at the bottom makes things both clearer and less intriguing.

3. Qiaochu Yuan - October 7, 2010

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?

4. owen maresh - October 7, 2010

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.

5. Tracy Hall - October 7, 2010

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?

6. David Speyer - October 7, 2010

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.

7. David Speyer - October 7, 2010

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.

8. Qiaochu Yuan - October 13, 2010

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.

9. Qiaochu Yuan - October 13, 2010

Er, I mean the ordinary generating function.

10. Dave Penneys - October 22, 2010

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!

11. Allan - November 12, 2010

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