Polynomial sequence?

[franktaw at netscape.net]

Actually, that's off by one.  The number of labelled rooted trees is 
n^(n-1), not (n+1)^n.

What it actually is is something better.  n! is the number of 
increasing rooted trees on n+1 nodes - that is, trees where each node 
label is greater than the label of its parent.  So a(n) is the number 
of labelled rooted trees on n+1  nodes that are not increasing.

Based on this and your original description, I would recommend changing 
the offset:  a(n) = n^(n-1) - (n-1)!.  Then a(n) = f(n) in the original 
exposition,  not f(n+1), and a(n) is the number of labelled rooted 
trees on n nodes that are not increasing.  You want to add an initial 
a(1) = 0.

Franklin T. Adams-Watters


-----Original Message-----
From: joshua.zucker at gmail.com

If I understand correctly, the observation below also means that it is 
the number of labeled rooted trees with n nodes except for the ones 
that are some particular tree (say the one where the nodes are all in 
a straight line)? 
 
--Joshua Zucker 
 
On 12/17/06, Jonathan Post <jvospost3 at gmail.com> wrote: 
> a(n) = (n+1)^n - n! = A000169(n) - A000142(n). 
> 
> Since A000169 is the number of labeled rooted trees with n nodes, you 
> should be able to come up with a pure graph enumeration description 
of your 
> sequence. When you do, I agree that it is nice. 
> 


________________________________________________________________________
Check Out the new free AIM(R) Mail -- 2 GB of storage and 
industry-leading spam and email virus protection.