%I A004111 M0796
%S A004111 0,1,1,1,2,3,6,12,25,52,113,247,548,1226,2770,6299,14426,33209,
%T A004111 76851,178618,416848,976296,2294224,5407384,12780394,30283120,71924647,
%U A004111 171196956,408310668,975662480,2335443077,5599508648,13446130438
%N A004111 Number of rooted identity trees with n nodes (trees with distinct subtrees).
%C A004111 Shifts left under WEIGH transform. - Franklin T. Adams-Watters (FrankTAW(AT)Netscape.net), 
               Jan 17 2007
%D A004111 F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like 
               Structures, Camb. 1998, p. 330.
%D A004111 P. J. Cameron, Some sequences of integers, Discrete Math., 75 (1989), 
               89-102; also in "Graph Theory and Combinatorics 1988", ed. B. Bollobas, 
               Annals of Discrete Math., 43 (1989), 89-102.
%D A004111 F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 
               1973, p. 64, Eq. (3.3.15); p. 80, Problem 3.10.
%D A004111 F. Harary, R. W. Robinson and A. J. Schwenk, Twenty-step algorithm for 
               determining the asymptotic number of trees of various species, J. 
               Austral. Math. Soc., Series A, 20 (1975), 483-503. Errata: Vol. A 
               41 (1986), p. 325.
%D A004111 D. E. Knuth, Fundamental Algorithms, 3rd Ed., 1997, pp. 386-388.
%D A004111 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, 
               Academic Press, 1995 (includes this sequence).
%H A004111 T. D. Noe, <a href="b004111.txt">Table of n, a(n) for n=0..200</a>
%H A004111 INRIA Algorithms Project, <a href="http://algo.inria.fr/bin/encyclopedia?Search=ECSnb&argsearch=56">
               Encyclopedia of Combinatorial Structures 56</a>
%H A004111 <a href="Sindx_Ro.html#rooted">Index entries for sequences related to 
               rooted trees</a>
%F A004111 Recurrence: a(n+1) = (1/n) * sum_{k=1..n} ( sum_{d|k} (-1)^(k/d+1) d*a(d) 
               ) * a(n-k+1). - Mitchell Harris, Dec 02, 2004
%F A004111 G.f.: A(x) = x exp(A(x)-A(x^2)/2+A(x^3)/3-A(x^4)/4+...)
%F A004111 Also A(x) = Sum_{n >= 1} a(n)*x^n = x * Product_{n >= 1} (1+x^n)^a(n).
%p A004111 spec := [ A, {A=Prod(Z,PowerSet(A))} ]: [ seq(combstruct[count](spec, 
               size=n), n=0..52) ];
%t A004111 s[ n_, k_ ] := s[ n, k ]=a[ n+1-k ]+If[ n<2k, 0, -s[ n-k, k ] ]; a[ 1 
               ]=1; a[ n_ ] := a[ n ]=Sum[ a[ i ]s[ n-1, i ]i, {i, 1, n-1} ]/(n-1); 
               Table[ a[ i ], {i, 1, 30} ] (from Robert A. Russell)
%Y A004111 Cf. A000009, A000081, A000220.
%Y A004111 Sequence in context: A038087 A116379 A116380 this_sequence A032235 A162985 
               A052523
%Y A004111 Adjacent sequences: A004108 A004109 A004110 this_sequence A004112 A004113 
               A004114
%K A004111 nonn,easy,nice,eigen
%O A004111 0,5
%A A004111 N. J. A. Sloane (njas(AT)research.att.com).