|
|
A001190
|
|
Wedderburn-Etherington numbers: unlabeled binary rooted trees (every node has outdegree 0 or 2) with n endpoints (and 2n-1 nodes in all).
(Formerly M0790 N0298)
|
|
123
|
|
|
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, 18632325319, 44214569100
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,5
|
|
COMMENTS
|
Also number of n-node binary rooted trees (every node has outdegree <= 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 outdegree 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). [If multiplication is non-commutative then the answer is A000108(n-1). - Jianing Song, Apr 29 2022]
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
Named after the English mathematician Ivor Etherington (1908-1994) and the Scottish mathematician Joseph Wedderburn (1882-1948). - Amiram Eldar, May 29 2021
|
|
REFERENCES
|
Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 307.
Louis Comtet, Advanced Combinatorics, Reidel, 1974, p. 55.
Steven R. Finch, Mathematical Constants, Cambridge, 2003, pp. 295-316.
A. Gutiérrez-Sánchez, Shen-colored tournaments, thesis, UNAM, 2012.
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).
Richard P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 6.52.
Richard P. Stanley, Catalan Numbers, Cambridge, 2015, p. 133.
|
|
LINKS
|
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]
|
|
FORMULA
|
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
|
|
EXAMPLE
|
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 + ...
The a(6+1) = 11 rooted trees with 6 nodes as described in the comment are:
: level sequence outdegrees (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)
|
|
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);
# alternative Maple program:
a:= proc(n) option remember; `if`(n<2, n, `if`(n::odd, 0,
(t-> t*(1-t)/2)(a(n/2)))+add(a(i)*a(n-i), i=1..n/2))
end:
|
|
MATHEMATICA
|
terms = 35; A[_] = 0; Do[A[x_] = x + (1/2)*(A[x]^2 + A[x^2]) + O[x]^terms // Normal, terms]; CoefficientList[A[x], x] (* Jean-François Alcover, Jul 22 2011, updated Jan 10 2018 *)
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 */
(Python)
from functools import lru_cache
@lru_cache(maxsize=None)
if n <= 1: return n
m = n//2 + n % 2
|
|
CROSSREFS
|
|
|
KEYWORD
|
easy,core,nonn,nice,eigen
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|