# [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, ...

http://sbseminar.wordpress.com/2010/10/06/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.

```