A peculiar numerical coincidence October 6, 2010Posted 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 -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 such trees on 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:
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.