A088342 - OEIS

%I #10 Oct 23 2016 20:54:31

%S 1,3,14,93,837,9742,140449,2420297,48506250,1107465929,28354713349,

%T 804166591614,25016362993529,846770894729841,30978110173770106,

%U 1217913727100939785,51206137142679936933,2292551430448659630790,108888041255668778897857,5468436908124359403377993

%N Let T = Sum_{k >= 1} k^(k-1)*x^k be the g.f. for rooted labeled trees (A000169); sequence has g.f. T/(1-T).

%C a(n)=number of forests of rooted trees on [n] whose vertex sets partition [n] into intervals of integers, that is, such that if i<j<k and i,k are vertices in the same component tree, then so is j. For example with n=3, a(n)=14 counts all (n+1)^(n-1)=16 rooted forests on [3] except the 2 forests consisting of a rooted tree on vertex set {1,3} and another on vertex set {2}. - _David Callan_, Oct 24 2004

%e G.f.: A(x) = x + 3*x^2 + 14*x^3 + 93*x^4 + 837*x^5 + 9742*x^6 + 140449*x^7 +...

%e such that A(x) = T(x)/(1 - T(x)), where

%e T(x) = x + 2*x^2 + 9*x^3 + 64*x^4 + 625*x^5 + 7776*x^6 +...+ k^(k-1)*x^k +...

%K nonn

%O 1,2

%A _N. J. A. Sloane_, Nov 13 2003

%E Name changed slightly to match offset of 1 by _Paul D. Hanna_, Oct 23 2016.