|
| |
|
|
A001190
|
|
Wedderburn-Etherington numbers: binary rooted trees (every node has out-degree 0 or 2) with n endpoints (and 2n-1 nodes in all).
(Formerly M0790 N0298)
|
|
33
|
|
|
|
0, 1, 1, 1, 2, 3, 6, 11, 23, 46, 98, 207, 451, 983, 2179, 4850, 10905, 24631, 56011, 127912, 293547, 676157, 1563372, 3626149, 8436379, 19680277, 46026618, 107890609, 253450711, 596572387, 1406818759, 3323236238, 7862958391
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,5
|
|
|
COMMENTS
|
Also n-node binary rooted trees (every node has out-degree <= 2) where root has degree 0 or 1.
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
|
|
|
REFERENCES
|
L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 55.
S. J. Cyvin et al., Enumeration of constitutional isomers of polyenes, J. Molec. Structure (Theochem), 357 (1995), 255-261.
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.
Fack, V.; Lievens, S.; Van der Jeugt, J. 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, Mathematical Constants, Cambridge, 2003, pp. 295-316.
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.
V. P. Johnson, Enumeration Results on Leaf Labeled Trees, Ph. D. Dissertation, Univ. Southern Calif., 2012; http://www.math.sc.edu/~czabarka/JohnsonThesis.pdf. - From N. J. A. Sloane, Dec 22 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.
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.
J. H. M. Wedderburn, The functional equation g(x^2) = 2ax + [ g(x) ]^2, Ann. Math., 24 (1922-23), 121-140.
A. Gutiérrez-Sánchez, Shen-colored tournaments, thesis, UNAM, 2012.
|
|
|
LINKS
|
T. D. Noe, Table of n, a(n) for n = 0..200
H. Bottomley, Illustration of initial terms
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
S. R. Finch, Otter's Tree Enumeration Constants
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 72
Piet Hut, Home Page
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 43
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 45
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
|
|
|
FORMULA
|
G.f.: A(x) = x + (1/2)*(A(x)^2 + A(x^2)).
G.f. A(x) = 1 - sqrt(1 - 2*x - A(x^2)) satisfies 0 = A(x)^2 - 2*A(x) + 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
|
|
|
EXAMPLE
|
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 + ...
|
|
|
MAPLE
|
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);
|
|
|
MATHEMATICA
|
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}]] (* From 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 *)
|
|
|
PROG
|
(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 */
|
|
|
CROSSREFS
|
Cf. A000108, A001699, A002658, A006894, A003214, A088325.
Sequence in context: A036591 A036592 * A036656 A199142 A090344 A198662
Adjacent sequences: A001187 A001188 A001189 * A001191 A001192 A001193
|
|
|
KEYWORD
|
easy,core,nonn,nice,eigen
|
|
|
AUTHOR
|
N. J. A. Sloane.
|
|
|
STATUS
|
approved
|
| |
|
|
