[seqfan] New sequence given by David Speyer, as difference of two known seqs

Jonathan Post jvospost3 at gmail.com
Sat Oct 9 05:09:47 CEST 2010

1, 8, 45, 208, 858, 3276, ...


"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:

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

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.

More information about the SeqFan mailing list