A004111 Number of rooted identity trees with n nodes (rooted trees whose automorphism group is the identity group).
0, 1, 1, 1, 2, 3, 6, 12, 25, 52, 113, 247, 548, 1226, 2770, 6299, 14426, 33209, 76851, 178618, 416848, 976296, 2294224, 5407384, 12780394, 30283120, 71924647, 171196956, 408310668, 975662480, 2335443077, 5599508648, 13446130438, 32334837886, 77863375126, 187737500013, 453203435319, 1095295264857, 2649957419351
Offset: 0
Examples
The 2 identity trees with 4 nodes are:
O O
/ \ |
O O O
| |
O O
|
O
These correspond to the sets {{},{{}}} and {{{{}}}}.
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 + ...
References
- F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Camb. 1998, p. 330.
- S. R. Finch, Mathematical Constants, Cambridge, 2003, p. 301 and 562.
- F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 64, Eq. (3.3.15); p. 80, Problem 3.10.
- D. E. Knuth, Fundamental Algorithms, 3rd Ed., 1997, pp. 386-388.
- N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
Links
- Alois P. Heinz, Table of n, a(n) for n = 0..2500 (first 201 terms from T. D. Noe)
- Joerg Arndt, All identity trees for n = 1..11.
- 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.
- A. Genitrini, Full asymptotic expansion for Polya structures, arXiv:1605.00837 [math.CO], May 03 2016, p. 8.
- Bernhard Gittenberger, Emma Yu Jin, Michael Wallner, On the shape of random Pólya structures, arXiv|1707.02144 [math.CO], 2017-2018; Discrete Math., 341 (2018), 896-911.
- Frank Harary and Geert Prins, The number of homeomorphically irreducible trees and other species, Acta Math., 101 (1959), 141-162.
- 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.
- F. Harary, R. W. Robinson and A. J. Schwenk, Corrigenda: Twenty-step algorithm for determining the asymptotic number of trees of various species, J. Austral. Math. Soc., Series A 41 (1986), p. 325.
- INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 56.
- P. Leroux and B. Miloudi, Généralisations de la formule d'Otter, Ann. Sci. Math. Québec, Vol. 16, No. 1, pp. 53-80, 1992. (Annotated scanned copy)
- T. Motzkin, The hypersurface cross ratio, Bull. Amer. Math. Soc., 51 (1945), 976-984.
- T. S. Motzkin, Relations between hypersurface cross ratios and a combinatorial formula for partitions of a polygon, for permanent preponderance and for non-associative products, Bull. Amer. Math. Soc., 54 (1948), 352-360.
- N. J. A. Sloane, Sketch showing trees with 2 through 6 nodes.
- Index entries for sequences related to rooted trees
Crossrefs
Programs
-
Haskell
import Data.List (genericIndex) a004111 = genericIndex a004111_list a004111_list = 0 : 1 : f 1 [1] where f x zs = y : f (x + 1) (y : zs) where y = (sum $ zipWith (*) zs $ map g [1..]) `div` x g k = sum $ zipWith (*) (map (((-1) ^) . (+ 1)) $ reverse divs) (zipWith (*) divs $ map a004111 divs) where divs = a027750_row k -- Reinhard Zumkeller, Apr 29 2014 -
Maple
A004111 := proc(n) spec := [ A, {A=Prod(Z,PowerSet(A))} ]: combstruct[count](spec, size=n) ; end proc: # second Maple program: with(numtheory): a:= proc(n) a(n):= `if`(n<2, n, add(a(n-k)*add(a(d)*d* (-1)^(k/d+1), d=divisors(k)), k=1..n-1)/(n-1)) end: seq(a(n), n=0..50); # Alois P. Heinz, Jul 15 2014
-
Mathematica
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 *) 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 *) 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 *) -
PARI
N=66; A=vector(N+1, j, 1); 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] ) ); concat([0], A) \\ Joerg Arndt, Jul 10 2014
Formula
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
G.f. satisfies A(x) = x*exp(A(x) - A(x^2)/2 + A(x^3)/3 - A(x^4)/4 + ...). [Harary and Prins]
Also A(x) = Sum_{n >= 1} a(n)*x^n = x * Product_{n >= 1} (1+x^n)^a(n).
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
Comments