cp's OEIS Frontend

A004111 Number of rooted identity trees with n nodes (rooted trees whose automorphism group is the identity group).

%I A004111 M0796 #118 Jul 06 2024 09:23:36
%S A004111 0,1,1,1,2,3,6,12,25,52,113,247,548,1226,2770,6299,14426,33209,76851,
%T A004111 178618,416848,976296,2294224,5407384,12780394,30283120,71924647,
%U A004111 171196956,408310668,975662480,2335443077,5599508648,13446130438,32334837886,77863375126,187737500013,453203435319,1095295264857,2649957419351
%N A004111 Number of rooted identity trees with n nodes (rooted trees whose automorphism group is the identity group).
%C A004111 The nodes are unlabeled.
%C A004111 There is a natural correspondence between rooted identity trees and finitary sets (sets whose transitive closure is finite); each node represents a set, with the children of that node representing the members of that set. When the set corresponding to an identity tree is written out using braces, there is one set of braces for each node of the tree; thus a(n) is also the number of sets that can be made using n pairs of braces. - _Franklin T. Adams-Watters_, Oct 25 2011
%C A004111 Shifts left under WEIGH transform. - _Franklin T. Adams-Watters_, Jan 17 2007
%C A004111 Is this the sequence mentioned in the middle of page 355 of Motzkin (1948)? - _N. J. A. Sloane_, Jul 04 2015. Answer from _David Broadhurst_, Apr 06 2022: The answer is No. Motzkin was considering a sequence asymptotic to Catalan(n)/(4*n), namely A006082, which begins 1, 1, 1, 2, 3, 6, 12, 27, ... but he miscalculated and got 1, 1, 1, 2, 3, 6, 12, 25, ... instead! - _N. J. A. Sloane_, Apr 06 2022
%D A004111 F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Camb. 1998, p. 330.
%D A004111 S. R. Finch, Mathematical Constants, Cambridge, 2003, p. 301 and 562.
%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 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 Alois P. Heinz, <a href="/A004111/b004111.txt">Table of n, a(n) for n = 0..2500</a> (first 201 terms from T. D. Noe)
%H A004111 Joerg Arndt, <a href="/A004111/a004111.txt">All identity trees for n = 1..11</a>.
%H A004111 P. J. Cameron, <a href="http://dx.doi.org/10.1016/0012-365X(89)90081-2">Some sequences of integers</a>, Discrete Math., 75 (1989), 89-102; also in "Graph Theory and Combinatorics 1988", ed. B. Bollobas, Annals of Discrete Math., 43 (1989), 89-102.
%H A004111 A. Genitrini, <a href="http://arxiv.org/abs/1605.00837">Full asymptotic expansion for Polya structures</a>, arXiv:1605.00837 [math.CO], May 03 2016, p. 8.
%H A004111 Bernhard Gittenberger, Emma Yu Jin, Michael Wallner, <a href="https://arxiv.org/abs/1707.02144">On the shape of random Pólya structures</a>, arXiv|1707.02144 [math.CO], 2017-2018; Discrete Math., 341 (2018), 896-911.
%H A004111 Frank Harary and Geert Prins, <a href="http://dx.doi.org/10.1007/BF02559543">The number of homeomorphically irreducible trees and other species</a>, Acta Math., 101 (1959), 141-162.
%H A004111 F. Harary, R. W. Robinson and A. J. Schwenk, <a href="http://dx.doi.org/10.1017/S1446788700016190">Twenty-step algorithm for determining the asymptotic number of trees of various species</a>, J. Austral. Math. Soc., Series A, 20 (1975), 483-503.
%H A004111 F. Harary, R. W. Robinson and A. J. Schwenk, <a href="http://dx.doi.org/10.1017/S1446788700033760">Corrigenda: Twenty-step algorithm for determining the asymptotic number of trees of various species</a>, J. Austral. Math. Soc., Series A 41 (1986), p. 325.
%H A004111 INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=56">Encyclopedia of Combinatorial Structures 56</a>.
%H A004111 P. Leroux and B. Miloudi, <a href="/A000081/a000081_2.pdf">Généralisations de la formule d'Otter</a>, Ann. Sci. Math. Québec, Vol. 16, No. 1, pp. 53-80, 1992. (Annotated scanned copy)
%H A004111 T. Motzkin, <a href="http://dx.doi.org/10.1090/S0002-9904-1945-08486-9">The hypersurface cross ratio</a>, Bull. Amer. Math. Soc., 51 (1945), 976-984.
%H A004111 T. S. Motzkin, <a href="http://dx.doi.org/10.1090/S0002-9904-1948-09002-4 ">Relations between hypersurface cross ratios and a combinatorial formula for partitions of a polygon, for permanent preponderance and for non-associative products</a>, Bull. Amer. Math. Soc., 54 (1948), 352-360.
%H A004111 N. J. A. Sloane, <a href="/A004111/a004111_1.pdf">Sketch showing trees with 2 through 6 nodes</a>.
%H A004111 <a href="/index/Ro#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. satisfies A(x) = x*exp(A(x) - A(x^2)/2 + A(x^3)/3 - A(x^4)/4 + ...). [Harary and Prins]
%F A004111 Also A(x) = Sum_{n >= 1} a(n)*x^n = x * Product_{n >= 1} (1+x^n)^a(n).
%F A004111 a(n) ~ c * d^n / n^(3/2), where d = A246169 = 2.51754035263200389079535..., c = 0.3625364233974198712298411097408713812865256408189512533230825639621448038... . - _Vaclav Kotesovec_, Aug 22 2014, updated Dec 26 2020
%e A004111 The 2 identity trees with 4 nodes are:
%e A004111      O    O
%e A004111     / \   |
%e A004111    O   O  O
%e A004111        |  |
%e A004111        O  O
%e A004111           |
%e A004111           O
%e A004111 These correspond to the sets {{},{{}}} and {{{{}}}}.
%e A004111 G.f.: x + x^2 + x^3 + 2*x^4 + 3*x^5 + 6*x^6 + 12*x^7 + 25*x^8 + 52*x^9 + ...
%p A004111 A004111 := proc(n)
%p A004111         spec := [ A, {A=Prod(Z,PowerSet(A))} ]:
%p A004111         combstruct[count](spec, size=n) ;
%p A004111 end proc:
%p A004111 # second Maple program:
%p A004111 with(numtheory):
%p A004111 a:= proc(n) a(n):= `if`(n<2, n, add(a(n-k)*add(a(d)*d*
%p A004111        (-1)^(k/d+1), d=divisors(k)), k=1..n-1)/(n-1))
%p A004111     end:
%p A004111 seq(a(n), n=0..50);  # _Alois P. Heinz_, Jul 15 2014
%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} ] (* _Robert A. Russell_ *)
%t A004111 a[ n_] := If[ n < 2, Boole[n == 1], Nest[ CoefficientList[ Normal[ Times @@ (Table[1 + x^k, {k, Length@#}]^#) + x O[x]^Length@#], x] &, {}, n - 1][[n]]]; (* _Michael Somos_, Jul 10 2014 *)
%t A004111 a[n_] := a[n] = Sum[a[n-k]*Sum[a[d]*d*(-1)^(k/d+1),{d, Divisors[k]}], {k, 1, n-1}]/(n-1); a[0]=0; a[1]=1; Table[a[n], {n, 0, 40}] (* _Jean-François Alcover_, Feb 02 2015 *)
%o A004111 (Haskell)
%o A004111 import Data.List (genericIndex)
%o A004111 a004111 = genericIndex a004111_list
%o A004111 a004111_list = 0 : 1 : f 1 [1] where
%o A004111    f x zs = y : f (x + 1) (y : zs) where
%o A004111             y = (sum $ zipWith (*) zs $ map g [1..]) `div` x
%o A004111    g k = sum $ zipWith (*) (map (((-1) ^) . (+ 1)) $ reverse divs)
%o A004111                            (zipWith (*) divs $ map a004111 divs)
%o A004111                            where divs = a027750_row k
%o A004111 -- _Reinhard Zumkeller_, Apr 29 2014
%o A004111 (PARI)
%o A004111 N=66;  A=vector(N+1, j, 1);
%o A004111 for (n=1, N, A[n+1] = 1/n * sum(k=1, n, sumdiv(k, d, (-1)^(k/d+1) * d * A[d]) * A[n-k+1] ) );
%o A004111 concat([0], A)
%o A004111 \\ _Joerg Arndt_, Jul 10 2014
%Y A004111 Cf. A000009, A000081, A000220, A196118, A196154, A196161, A227819.
%Y A004111 Cf. A027750, A035056, A246169.
%Y A004111 Column k=1 of A255517, A316074, A316101, A318757.
%K A004111 nonn,easy,nice,eigen
%O A004111 0,5
%A A004111 _N. J. A. Sloane_