|
| |
|
|
A004111
|
|
Number of rooted identity trees with n nodes (rooted trees whose automorphism group is the identity group).
(Formerly M0796)
|
|
30
| |
|
|
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
(list; graph; refs; listen; history; 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 (FrankTAW(AT)Netscape.net), Jan 17 2007
|
|
|
REFERENCES
| F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Camb. 1998, p. 330.
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.
F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 64, Eq. (3.3.15); p. 80, Problem 3.10.
Harary, Frank and Prins, Geert, 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. Errata: Vol. A 41 (1986), p. 325.
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, Table of n, a(n) for n=0..200
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 56
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).
|
|
|
EXAMPLE
| The 2 identity trees with 4 nodes are:
..O....O
./.\...|
O...O..O
....|..|
....O..O
.......|
.......O
These correspond to the sets {{},{{}}} and {{{{}}}}.
|
|
|
MAPLE
| A004111 := proc(n)
spec := [ A, {A=Prod(Z, PowerSet(A))} ]:
combstruct[count](spec, size=n) ;
end proc:
|
|
|
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} ] (from Robert A. Russell)
|
|
|
CROSSREFS
| Cf. A000009, A000081, A000220, A196118, A196154, A196161.
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 (njas(AT)research.att.com).
|
| |
|
|
