0,5

Also n-node binary rooted trees (every node has out-degree <= 2) where root has degree 0 (only for n=1) or 1.

a(n+1) is The number of rooted trees with n nodes where the out-degree of every node is <=2, see example. These trees are obtained by removing the root of the trees in the comment above. - Joerg Arndt, Jun 29 2014

Number of interpretations of x^n (or number of ways to insert parentheses) when multiplication is commutative but not associative. E.g. a(4) = 2: x(x.x^2) and x^2.x^2. a(5) = 3: (x.x^2)x^2, x(x.x.x^2) and x(x^2.x^2).

Number of ways to place n stars in a single bound stable hierarchical multiple star system; i.e. taking only the configurations from A003214 where all stars are included in single outer parentheses. - Piet Hut, Nov 07 2003

Number of colorations of Kn (complete graph of order n) with n-1 colors such that no triangle is three-colored. Two edge-colorations C1 and C2 of G are isomorphic iff exists an automorphism f (isomorphism between G an G) such that: f sends same-colored edges of C1 on same-colored edges of C2 and f^(-1) sends same-colored edges of C2 on same-colored edges of C1. - Abraham Gutiérrez, Nov 12 2012

For n>1, a(n) is the number of (not necessarily distinct) unordered pairs of free unlabeled trees having a total of n nodes.  See the first entry in formula section. - Geoffrey Critzer, Nov 09 2014

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 55.

I. M. H. Etherington, Non-associate powers and a functional equation. The Mathematical Gazette, 21 (1937): 36-39; addendum 21 (1937), 153.

I. M. H. Etherington, On non-associative combinations, Proc. Royal Soc. Edinburgh, 59 (Part 2, 1938-39), 153-162.

I. M. H. Etherington, Some problems of non-associative combinations (I), Edinburgh Math. Notes, 32 (1940), pp. i-vi. Part II is by A. Erdelyi and I. M. H. Etherington, and is on pages vii-xiv of the same issue.

S. R. Finch, Mathematical Constants, Cambridge, 2003, pp. 295-316.

A. Gutiérrez-Sánchez, Shen-colored tournaments, thesis, UNAM, 2012.

F. Sievers, G. M. Hughes, D. G. Higgins, Systematic Exploration of Guide-Tree Topology Effects for Small Protein Alignments, BMC Bioinformatics 2014, 15:338; http://www.biomedcentral.com/1471-2105/15/338 (Mentions A001190)

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 6.52.

T. D. Noe, Table of n, a(n) for n = 0..200

H. Bottomley, Illustration of initial terms

M. Bremner, S. Madariaga, L. A. Peresi, Structure theory for the group algebra of the symmetric group, with applications to polynomial identities for the octonions, arXiv:1407.3810 [math.RA], 2014.

P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.

Peter J. Cameron, Some treelike objects, Quart. J. Math. Oxford Ser. (2) 38 (1987), no. 150, 155--183. MR0891613 (89a:05009).  See p. 155. - N. J. A. Sloane, Apr 18 2014

S. J. Cyvin, J. Brunvoll, B. N. Cyvin, Enumeration of constitutional isomers of polyenes, J. Molec. Struct. (Theochem) 357, no. 3 (1995) 255-261.

N. G. de Bruijn, D. A. Klarner, Multisets of aperiodic cycles, SIAM J. Algebraic Discrete Methods 3 (1982), no. 3, 359--368. MR0666861(84i:05008) . See p. 367. - N. J. A. Sloane, Mar 25 2014

Filippo Disanto and Thomas Wiehe, Some combinatorial problems on binary rooted trees occurring in population genetics, arXiv preprint arXiv:1112.1295, 2011

I. M. H. Etherington, Non-associate powers and a functional equation, Math. Gaz. 21 (1937), 36-39 and 153.

I. M. H. Etherington, On non-associative combinations, Proc. Royal Soc. Edinburgh, 59 (Part 2, 1938-39), 153-162. [Annotated scanned copy]

V. Fack, S. Lievens, J. Van der Jeugt, On the diameter of the rotation graph of binary coupling trees. Discrete Math. 245 (2002), no. 1-3, 1--18. MR1887046 (2003i:05047).

S. R. Finch, Otter's Tree Enumeration Constants

P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 72

J. N. Franklin and S. W. Golomb, A Function-Theoretic Approach to the Study of Nonlinear Recurring Sequences, Pacific J. Math., Vol. 56, p. 467, 1975.

Piet Hut, Home Page

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 43

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 45

V. P. Johnson, Enumeration Results on Leaf Labeled Trees, Ph. D. Dissertation, Univ. Southern Calif., 2012.

F. Murtagh, Counting dendrograms: a survey, Discrete Applied Mathematics, 7 (1984), 191-199.

C. D. Olds, Problem 4277, Amer. Math. Monthly, 56 (1949), 697-699.

C. D. Olds (Proposer) and H. W. Becker (Discussion), Problem 4277, Amer. Math. Monthly 56 (1949), 697-699. [Annotated scanned copy]

J. H. M. Wedderburn, The functional equation g(x^2) = 2ax + [g(x)]^2, Ann. Math., 24 (1922-23), 121-140.

Eric Weisstein's World of Mathematics, Weakly Binary Tree

Eric Weisstein's World of Mathematics, Strongly Binary Tree

Index entries for "core" sequences

Index entries for sequences related to rooted trees

Index entries for sequences related to trees

Index entries for sequences related to parenthesizing

G.f. satisfies A(x) = x + (1/2)*(A(x)^2 + A(x^2)) [de Bruijn and Klarner].

G.f. also satisfies A(x) = 1 - sqrt(1 - 2*x - A(x^2)). - Michael Somos, Sep 06 2003

a(2n-1) = a(1)a(2n-2) + a(2)a(2n-3) + ... + a(n-1)a(n), a(2n) = a(1)a(2n-1) + a(2)a(2n-2) + ... + a(n-1)a(n+1) + a(n)(a(n)+1)/2.

Given g.f. A(x), then B(x) = -1 + A(x) satisfies 0 = f(B(x), B(x^2), B(x^4)) where f(u, v, w)= (u^2 + v)^2 + 2*(v^2 + w). - Michael Somos, Oct 22 2006

The radius of convergence of the g.f. is 1/A086317 ~ 0.4026975... - Jean-François Alcover, Jul 28 2014, after Steven R. Finch.

G.f. = x + x^2 + x^3 + 2*x^4 + 3*x^5 + 6*x^6 + 11*x^7 + 23*x^8 + 46*x^9 + 98*x^10 + ...

From Joerg Arndt, Jun 29 2014: (Start)

The a(6+1) = 11 rooted trees with 6 nodes as described in the comment are:

:           level sequence       out-degrees (dots for zeros)

:     1:  [ 0 1 2 3 4 5 ]    [ 1 1 1 1 1 . ]

:  O--o--o--o--o--o

:

:     2:  [ 0 1 2 3 4 4 ]    [ 1 1 1 2 . . ]

:  O--o--o--o--o

:           .--o

:

:     3:  [ 0 1 2 3 4 3 ]    [ 1 1 2 1 . . ]

:  O--o--o--o--o

:        .--o

:

:     4:  [ 0 1 2 3 4 2 ]    [ 1 2 1 1 . . ]

:  O--o--o--o--o

:     .--o

:

:     5:  [ 0 1 2 3 4 1 ]    [ 2 1 1 1 . . ]

:  O--o--o--o--o

:  .--o

:

:     6:  [ 0 1 2 3 3 2 ]    [ 1 2 2 . . . ]

:  O--o--o--o

:        .--o

:     .--o

:

:     7:  [ 0 1 2 3 3 1 ]    [ 2 1 2 . . . ]

:  O--o--o--o

:        .--o

:  .--o

:

:     8:  [ 0 1 2 3 2 3 ]    [ 1 2 1 . 1 . ]

:  O--o--o--o

:     .--o--o

:

:     9:  [ 0 1 2 3 2 1 ]    [ 2 2 1 . . . ]

:  O--o--o--o

:     .--o

:  .--o

:

:    10:  [ 0 1 2 3 1 2 ]    [ 2 1 1 . 1 . ]

:  O--o--o--o

:  .--o--o

:

:    11:  [ 0 1 2 2 1 2 ]    [ 2 2 . . 1 . ]

:  O--o--o

:     .--o

:  .--o--o

:

(End)

A001190 := proc(n) option remember; local s, k; if n<=1 then RETURN(n); elif n <=3 then RETURN(1); else s := 0; if n mod 2 = 0 then s := A001190(n/2)*(A001190(n/2)+1)/2; for k from 1 to n/2-1 do s := s+A001190(k)*A001190(n-k); od; RETURN(s); else for k from 1 to (n-1)/2 do s := s+A001190(k)*A001190(n-k); od; RETURN(s); fi; fi; end;

N := 40: G001190 := add(A001190(n)*x^n, n=0..N);

spec := [S, {S=Union(Z, Prod(Z, Set(S, card=2)))}, unlabeled]: seq(combstruct[count](spec, size=n), n=0..20);

n = 32; c[0] = 0; f[x_] = Sum[c[k]*x^k, {k, 0, n}]; eq[0] = Rest[ Thread[ CoefficientList[(-2x + 2f[x] - f[x]^2 - f[x^2])/2, x] == 0]]; s[1] = First[ Solve[ First[eq[0]], c[1]]]; Do[eq[k-1] = Rest[eq[k-2]] /. s[k-1]; s[k] = First[ Solve[ First[eq[k-1]], c[k]]], {k, 2, n}]; Table[c[k], {k, 0, n}] /. Flatten[ Table[s[k], {k, 1, n}]] (* Jean-François Alcover, Jul 22 2011 *)

a[n_?OddQ] := a[n] = Sum[a[k]*a[n-k], {k, 1, (n-1)/2}]; a[n_?EvenQ] := a[n] = Sum[a[k]*a[n-k], {k, 1, n/2-1}] + (1/2)*a[n/2]*(1+a[n/2]); a[0]=0; a[1]=1; Table[a[n], {n, 0, 32}] (* Jean-François Alcover, Jun 13 2012, after recurrence formula *)

a[ n_] := If[ n < 0, 0, SeriesCoefficient[ Nest[ 1 - Sqrt[1 - 2 x - (# /. x -> x^2)] &, 0, BitLength @ n], {x, 0, n}]]; (* Michael Somos, Apr 25 2013 *)

(PARI) {a(n) = local(A, m); if( n<0, 0, m=1; A = O(x); while( m<=n, m*=2; A = 1 - sqrt(1 - 2*x - subst(A, x, x^2))); polcoeff(A, n))}; /* Michael Somos, Sep 06 2003 */

(PARI) {a(n) = local(A); if( n<4, n>0, A = vector(n, i, 1); for( i=4, n, A[i] = sum( j=1, (i-1)\2, A[j] * A[i-j]) + if( i%2, 0, A[i/2] * (A[i/2] + 1)/2)); A[n])}; /* Michael Somos, Mar 25 2006 */

Cf. A000108, A001699, A002658, A006894, A006961, A003214, A088325.

Sequence in context: A036591 A036592 * A036656 A199142 A090344 A198662

Adjacent sequences:  A001187 A001188 A001189 * A001191 A001192 A001193

easy,core,nonn,nice,eigen

N. J. A. Sloane.

approved