login
This site is supported by donations to The OEIS Foundation.

 

Logo

"Email this user" was broken Aug 14 to 9am Aug 16. If you sent someone a message in this period, please send it again.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A004111 Number of rooted identity trees with n nodes (rooted trees whose automorphism group is the identity group).
(Formerly M0796)
56
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,5

COMMENTS

The nodes are unlabeled.

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.

Shifts left under WEIGH transform. - Franklin T. Adams-Watters, Jan 17 2007

Is this the sequence mentioned in the middle of page 355 of Motzkin (1948)? - N. J. A. Sloane, Jul 04 2015

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

T. D. Noe and Alois P. Heinz, Table of n, a(n) for n = 0..1000 (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.

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

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

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.362536423397419871229841109741... . - Vaclav Kotesovec, Aug 22 2014

EXAMPLE

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 + ...

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 *)

PROG

(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

(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

CROSSREFS

Cf. A000009, A000081, A000220, A196118, A196154, A196161, A227819.

Cf. A027750, A035056, A246169.

Column k=1 of A255517.

Sequence in context: A038087 A116379 A116380 * A032235 A192805 A162985

Adjacent sequences:  A004108 A004109 A004110 * A004112 A004113 A004114

KEYWORD

nonn,easy,nice,eigen

AUTHOR

N. J. A. Sloane

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified August 19 23:35 EDT 2017. Contains 290821 sequences.