cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-4 of 4 results.

A000081 Number of unlabeled rooted trees with n nodes (or connected functions with a fixed point).

Original entry on oeis.org

0, 1, 1, 2, 4, 9, 20, 48, 115, 286, 719, 1842, 4766, 12486, 32973, 87811, 235381, 634847, 1721159, 4688676, 12826228, 35221832, 97055181, 268282855, 743724984, 2067174645, 5759636510, 16083734329, 45007066269, 126186554308, 354426847597, 997171512998
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

Also, number of ways of arranging n-1 nonoverlapping circles: e.g., there are 4 ways to arrange 3 circles, as represented by ((O)), (OO), (O)O, OOO, also see example. (Of course the rules here are different from the usual counting parentheses problems - compare A000108, A001190, A001699.) See Sloane's link for a proof and Vogeler's link for illustration of a(7) as arrangement of 6 circles.
Take a string of n x's and insert n-1 ^'s and n-1 pairs of parentheses in all possible legal ways (cf. A003018). Sequence gives number of distinct functions. The single node tree is "x". Making a node f2 a child of f1 represents f1^f2. Since (f1^f2)^f3 is just f1^(f2*f3) we can think of it as f1 raised to both f2 and f3, that is, f1 with f2 and f3 as children. E.g., for n=4 the distinct functions are ((x^x)^x)^x; (x^(x^x))^x; x^((x^x)^x); x^(x^(x^x)). - W. Edwin Clark and Russ Cox, Apr 29 2003; corrected by Keith Briggs, Nov 14 2005
Also, number of connected multigraphs of order n without cycles except for one loop. - Washington Bomfim, Sep 04 2010
Also, number of planted trees with n+1 nodes.
Also called "Polya trees" by Genitrini (2016). - N. J. A. Sloane, Mar 24 2017

Examples

			G.f. = x + x^2 + 2*x^3 + 4*x^4 + 9*x^5 + 20*x^6 + 48*x^7 + 115*x^8 + ...
From _Joerg Arndt_, Jun 29 2014: (Start)
The a(6) = 20 trees with 6 nodes have the following level sequences (with level of root = 0) and parenthesis words:
  01:  [ 0 1 2 3 4 5 ]    (((((())))))
  02:  [ 0 1 2 3 4 4 ]    ((((()()))))
  03:  [ 0 1 2 3 4 3 ]    ((((())())))
  04:  [ 0 1 2 3 4 2 ]    ((((()))()))
  05:  [ 0 1 2 3 4 1 ]    ((((())))())
  06:  [ 0 1 2 3 3 3 ]    (((()()())))
  07:  [ 0 1 2 3 3 2 ]    (((()())()))
  08:  [ 0 1 2 3 3 1 ]    (((()()))())
  09:  [ 0 1 2 3 2 3 ]    (((())(())))
  10:  [ 0 1 2 3 2 2 ]    (((())()()))
  11:  [ 0 1 2 3 2 1 ]    (((())())())
  12:  [ 0 1 2 3 1 2 ]    (((()))(()))
  13:  [ 0 1 2 3 1 1 ]    (((()))()())
  14:  [ 0 1 2 2 2 2 ]    ((()()()()))
  15:  [ 0 1 2 2 2 1 ]    ((()()())())
  16:  [ 0 1 2 2 1 2 ]    ((()())(()))
  17:  [ 0 1 2 2 1 1 ]    ((()())()())
  18:  [ 0 1 2 1 2 1 ]    ((())(())())
  19:  [ 0 1 2 1 1 1 ]    ((())()()())
  20:  [ 0 1 1 1 1 1 ]    (()()()()())
(End)

References

  • F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Camb. 1998, p. 279.
  • N. L. Biggs et al., Graph Theory 1736-1936, Oxford, 1976, pp. 42, 49.
  • Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, pages 305, 998.
  • A. Cayley, On the analytical forms called trees, with application to the theory of chemical combinations, Reports British Assoc. Advance. Sci. 45 (1875), 257-305 = Math. Papers, Vol. 9, 427-460 (see p. 451).
  • J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 526.
  • F. Harary, Graph Theory. Addison-Wesley, Reading, MA, 1969, p. 232.
  • F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, pp. 54 and 244.
  • Alexander S. Karpenko, Łukasiewicz Logics and Prime Numbers, Luniver Press, Beckington, 2006, p. 82.
  • D. E. Knuth, The Art of Computer Programming, Vol. 1: Fundamental Algorithms, 3d Ed. 1997, pp. 386-388.
  • D. E. Knuth, The Art of Computer Programming, vol. 1, 3rd ed., Fundamental Algorithms, p. 395, ex. 2.
  • D. E. Knuth, TAOCP, Vol. 4, Section 7.2.1.6.
  • G. Polya and R. C. Read, Combinatorial Enumeration of Groups, Graphs and Chemical Compounds, Springer-Verlag, 1987, p. 63.
  • R. C. Read and R. J. Wilson, An Atlas of Graphs, Oxford, 1998. [Comment from Neven Juric: Page 64 incorrectly gives a(21)=35224832.]
  • J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 138.
  • 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).

Links

Crossrefs

Cf. A000041 (partitions), A000055 (unrooted trees), A000169, A001858, A005200, A027750, A051491, A051492, A093637, A187770, A199812, A255170, A087803 (partial sums).
Row sums of A144963. - Gary W. Adamson, Sep 27 2008
Cf. A209397 (log(A(x)/x)).
Cf. A000106 (self-convolution), A002861 (rings of these).
Column k=1 of A033185 and A034799; column k=0 of A008295.

Programs

  • Haskell
    import Data.List (genericIndex)
a000081 = genericIndex a000081_list
a000081_list = 0 : 1 : f 1 [1,0] where
   f x ys = y : f (x + 1) (y : ys) where
     y = sum (zipWith (*) (map h [1..x]) ys) `div` x
     h = sum . map (\d -> d * a000081 d) . a027750_row
-- Reinhard Zumkeller, Jun 17 2013
  • Magma
    N := 30; P := PowerSeriesRing(Rationals(),N+1); f := func< A | x*&*[Exp(Evaluate(A,x^k)/k) : k in [1..N]]>; G := x; for i in [1..N] do G := f(G); end for; G000081 := G; A000081 := [0] cat Eltseq(G); // Geoff Bailey (geoff(AT)maths.usyd.edu.au), Nov 30 2009
  • Maple
    N := 30: a := [1,1]; for n from 3 to N do x*mul( (1-x^i)^(-a[i]), i=1..n-1); series(%,x,n+1); b := coeff(%,x,n); a := [op(a),b]; od: a; A000081 := proc(n) if n=0 then 1 else a[n]; fi; end; G000081 := series(add(a[i]*x^i,i=1..N),x,N+2); # also used in A000055
spec := [ T, {T=Prod(Z,Set(T))} ]; A000081 := n-> combstruct[count](spec,size=n); [seq(combstruct[count](spec,size=n), n=0..40)];
# a much more efficient method for computing the result with Maple. It uses two procedures:
a := proc(n) local k; a(n) := add(k*a(k)*s(n-1,k), k=1..n-1)/(n-1) end proc:
a(0) := 0: a(1) := 1: s := proc(n,k) local j; s(n,k) := add(a(n+1-j*k), j=1..iquo(n,k)); # Joe Riel (joer(AT)san.rr.com), Jun 23 2008
# even more efficient, uses the Euler transform:
with(numtheory): a:= proc(n) option remember; local d, j; `if`(n<=1, n, (add(add(d*a(d), d=divisors(j)) *a(n-j), j=1..n-1))/ (n-1)) end:
seq(a(n), n=0..50); # Alois P. Heinz, Sep 06 2008
  • 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_] := a[n] = If[n <= 1, n, Sum[Sum[d*a[d], {d, Divisors[j]}]*a[n-j], {j, 1, n-1}]/(n-1)]; Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Feb 17 2014, after Alois P. Heinz *)
a[n_] := a[n] = If[n <= 1, n, Sum[a[n - j] DivisorSum[j, # a[#] &], {j, n - 1}]/(n - 1)]; Table[a[n], {n, 0, 30}] (* Jan Mangaldan, May 07 2014, after Alois P. Heinz *)
(* first do *) << NumericalDifferentialEquationAnalysis`; (* then *)
ButcherTreeCount[30] (* v8 onward Robert G. Wilson v, Sep 16 2014 *)
a[n:0|1] := n; a[n_] := a[n] = Sum[m a[m] a[n-k*m], {m, n-1}, {k, (n-1)/m}]/(n-1); Table[a[n], {n, 0, 30}] (* Vladimir Reshetnikov, Nov 06 2015 *)
terms = 31; A[] = 0; Do[A[x] = x*Exp[Sum[A[x^k]/k, {k, 1, j}]] + O[x]^j // Normal, {j, 1, terms}]; CoefficientList[A[x], x] (* Jean-François Alcover, Jan 11 2018 *)
  • Maxima
    g(m):= block([si,v],s:0,v:divisors(m), for si in v do (s:s+r(m/si)/si),s);
r(n):=if n=1 then 1 else sum(Co(n-1,k)/k!,k,1,n-1);
Co(n,k):=if k=1  then g(n)  else sum(g(i+1)*Co(n-i-1,k-1),i,0,n-k);
makelist(r(n),n,1,12); /*Vladimir Kruchinin, Jun 15 2012 */
  • PARI
    {a(n) = local(A = x); if( n<1, 0, for( k=1, n-1, A /= (1 - x^k + x * O(x^n))^polcoeff(A, k)); polcoeff(A, n))}; /* Michael Somos, Dec 16 2002 */
  • PARI
    {a(n) = local(A, A1, an, i); if( n<1, 0, an = Vec(A = A1 = 1 + O(x^n)); for( m=2, n, i=m\2; an[m] = sum( k=1, i, an[k] * an[m-k]) + polcoeff( if( m%2, A *= (A1 - x^i)^-an[i], A), m-1)); an[n])}; /* Michael Somos, Sep 05 2003 */
  • 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, d*A[d]) * A[n-k+1] ) );
concat([0], A) \\ Joerg Arndt, Apr 17 2014
  • Python
    from functools import lru_cache
from sympy import divisors
@lru_cache(maxsize=None)
def divisor_tuple(n): # cached unordered tuple of divisors
    return tuple(divisors(n,generator=True))
@lru_cache(maxsize=None)
def A000081(n): return n if n <= 1 else sum(sum(d*A000081(d) for d in divisor_tuple(k))*A000081(n-k) for k in range(1,n))//(n-1) # Chai Wah Wu, Jan 14 2022
  • Sage
    @CachedFunction
def a(n):
    if n < 2: return n
    return add(add(d*a(d) for d in divisors(j))*a(n-j) for j in (1..n-1))/(n-1)
[a(n) for n in range(31)] # Peter Luschny, Jul 18 2014 after Alois P. Heinz
  • Sage
    [0]+[RootedTrees(n).cardinality() for n in range(1,31)] # Freddy Barrera, Apr 07 2019

Formula

G.f. A(x) satisfies A(x) = x*exp(A(x)+A(x^2)/2+A(x^3)/3+A(x^4)/4+...) [Polya]
Also A(x) = Sum_{n>=1} a(n)*x^n = x / Product_{n>=1} (1-x^n)^a(n).
Recurrence: a(n+1) = (1/n) * Sum_{k=1..n} ( Sum_{d|k} d*a(d) ) * a(n-k+1).
Asymptotically c * d^n * n^(-3/2), where c = A187770 = 0.439924... and d = A051491 = 2.955765... [Polya; Knuth, section 7.2.1.6].
Euler transform is sequence itself with offset -1. - Michael Somos, Dec 16 2001
For n > 1, a(n) = A087803(n) - A087803(n-1). - Vladimir Reshetnikov, Nov 06 2015
For n > 1, a(n) = A123467(n-1). - Falk Hüffner, Nov 26 2015

A087803 Number of unlabeled rooted trees with at most n nodes.

Original entry on oeis.org

1, 2, 4, 8, 17, 37, 85, 200, 486, 1205, 3047, 7813, 20299, 53272, 141083, 376464, 1011311, 2732470, 7421146, 20247374, 55469206, 152524387, 420807242, 1164532226, 3231706871, 8991343381, 25075077710, 70082143979, 196268698287, 550695545884, 1547867058882
Offset: 1

Views

Author

Hugo Pfoertner, Oct 12 2003

Keywords

Comments

Number of equations (order conditions) that must be satisfied to achieve order n in the construction of a Runge-Kutta method for the numerical solution of an ordinary differential equation. - Hugo Pfoertner, Oct 12 2003

References

  • Butcher, J. C., The Numerical Analysis of Ordinary Differential Equations, (1987) Wiley, Chichester
  • See link for more references.

Links

Crossrefs

a(n) = Sum_(k=1..n) A000081(k).
Cf. A255170, A187770, A051491.

Programs

  • Maple
    with(numtheory):
b:= proc(n) option remember; local d, j; `if`(n<=1, n,
      (add(add(d*b(d), d=divisors(j))*b(n-j), j=1..n-1))/(n-1))
    end:
a:= proc(n) option remember; b(n) +`if`(n<1, 0, a(n-1)) end:
seq(a(n), n=1..50);  # Alois P. Heinz, Aug 21 2012
  • Mathematica
    b[0] = 0; b[1] = 1; b[n_] := b[n] = Sum[b[n - j]* DivisorSum[j, # *b[#]&], {j, 1, n-1}]/(n-1); a[1] = 1; a[n_] := a[n] = b[n] + a[n-1]; Table[a[n], {n, 1, 50}] (* Jean-François Alcover, Nov 10 2015, after Alois P. Heinz *)
t[1] = a[1] = 1; t[n_] := t[n] = Sum[k t[k] t[n - k m]/(n-1), {k, n}, {m, (n-1)/k}]; a[n_] := a[n] = a[n-1] + t[n]; Table[a[n], {n, 40}] (* Vladimir Reshetnikov, Aug 12 2016 *)
Needs["NumericalDifferentialEquationAnalysis`"]
Drop[Accumulate[Join[{0},ButcherTreeCount[20]]],1] (* Peter Luschny, Aug 18 2016 *)
  • PARI
    a000081(k) = local(A = x); if( k<1, 0, for( j=1, k-1, A /= (1 - x^j + x * O(x^k))^polcoeff(A, j)); polcoeff(A, k));
a(n) = sum(k=1, n, a000081(k)) \\ Altug Alkan, Nov 10 2015
  • Sage
    def A087803_list(len):
    a, t = [1], [0,1]
    for n in (1..len-1):
        S = [t[n-k+1]*sum(d*t[d] for d in divisors(k)) for k in (1..n)]
        t.append(sum(S)//n)
        a.append(a[-1]+t[-1])
    return a
A087803_list(20) # Peter Luschny, Aug 18 2016

Formula

a(n) ~ c * d^n / n^(3/2), where d = A051491 = 2.9557652856519949747148..., c = 0.664861031240097088000569... . - Vaclav Kotesovec, Sep 11 2014
In the asymptotics above the constant c = A187770 / (1 - 1 / A051491). - Vladimir Reshetnikov, Aug 12 2016

Extensions

Corrected and extended by Alois P. Heinz, Aug 21 2012
Renamed (old name is in comments) by Vladimir Reshetnikov, Aug 23 2016

A174145 Number of rooted forests with n nodes in which each component contains at least two nodes.

Original entry on oeis.org

1, 0, 1, 2, 5, 11, 28, 67, 171, 433, 1123, 2924, 7720, 20487, 54838, 147570, 399466, 1086312, 2967517, 8137552, 22395604, 61833349, 171227674, 475442129, 1323449661, 3692461865, 10324097819, 28923331940, 81179488039, 228240293289, 642744665401, 1812762839702
Offset: 0

Views

Author

N. J. A. Sloane, Nov 26 2010

Keywords

Comments

Row sums of A174135.

Links

Crossrefs

Cf. A000081, A051491, A187770, A255170.

Programs

  • Maple
    with(numtheory):
t:= proc(n) option remember; local d, j; `if`(n<=1, n,
      (add(add(d*t(d), d=divisors(j))*t(n-j), j=1..n-1))/(n-1))
    end:
b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<2, 0,
      add(b(n-i*j, i-1)*binomial(t(i)+j-1, j), j=0..n/i)))
    end:
a:= n-> b(n, n):
seq(a(n), n=0..32);  # Alois P. Heinz, May 17 2013
  • Mathematica
    t[n_] := t[n] = If[n <= 1, n, Sum[Sum[d*t[d], {d, Divisors[j]}]*t[n-j], {j, 1, n-1}]/(n-1)]; b[n_, i_] := b[n, i] = If[n == 0, 1, If[i<2, 0, Sum[b[n-i*j, i-1]*Binomial[t[i]+j-1, j], {j, 0, n/i}]]]; a[n_] := b[n, n]; Table[a[n] // FullSimplify, {n, 0, 32}] (* Jean-François Alcover, Mar 19 2014, after Alois P. Heinz *)
t[1] = 1; t[n_] := t[n] = Sum[k t[k] t[n - k m]/(n-1), {k, n-1}, {m, (n-1)/k}]; a[n_] := t[n+1] - t[n]; Table[a[n], {n, 0, 32}] (* Vladimir Reshetnikov, Aug 12 2016 *)

Formula

a(n) ~ c * d^n / n^(3/2), where d = A051491 = 2.9557652856519949747148..., c = 0.8603881121111431... . - Vaclav Kotesovec, Sep 10 2014
In the asymptotics above the constant c = A187770 * (A051491 - 1). - Vladimir Reshetnikov, Aug 12 2016
a(n) = A000081(n+1) - A000081(n). - Vladimir Reshetnikov, Nov 06 2015

A199812 Number of distinct values taken by w^w^...^w (with n w's and parentheses inserted in all possible ways) where w is the first transfinite ordinal omega.

Original entry on oeis.org

1, 1, 2, 5, 13, 32, 79, 193, 478, 1196, 3037, 7802, 20287, 53259, 141069, 376449, 1011295, 2732453, 7421128, 20247355
Offset: 1

Views

Author

Vladimir Reshetnikov, Nov 10 2011

Keywords

Comments

Any transfinite ordinal can be used instead of omega, yielding the same sequence.
It appears that 2nd differences of this sequence give A174145 (starting from offset 2).
Conjectured extension of this sequence is given by A255170.

Examples

			For n=5 there are 14 possible parenthesizations, but only 13 of them produce distinct ordinals: (((w^w)^w)^w)^w < ((w^w)^w)^(w^w) < ((w^w)^(w^w))^w < ((w^(w^w))^w)^w < (w^(w^w))^(w^w) < (w^w)^((w^w)^w) < (w^((w^w)^w))^w < w^(((w^w)^w)^w) < (w^w)^(w^(w^w)) = w^((w^w)^(w^w)) < (w^(w^(w^w)))^w < w^((w^(w^w))^w) < w^(w^((w^w)^w)) < w^(w^(w^(w^w))). So, a(5)=13.

Links

Crossrefs

Cf. A000108 (upper bound), A174145 (2nd differences?), A255170 (conjectured extension), A005348, A002845, A198683, A000081 (similar asymptotics), A051491.

Programs

  • Mathematica
    (* Slow exhaustive search *)
_ \[Precedes] {} = False;
{} \[Precedes] {} = True;
{a_ \[Diamond] , __} \[Precedes] {b_ \[Diamond] , __} := a \[Precedes] b /; a =!= b;
{a_ \[Diamond] m_, _} \[Precedes] {a_ \[Diamond] n_, _} := m < n /; m != n;
{z_, x___} \[Precedes] {z_, y___} := {x} \[Precedes] {y};
m_ \[CirclePlus] {} := m;
{} \[CirclePlus] n_ := n;
{x___, a_ \[Diamond] m_} \[CirclePlus] {a_ \[Diamond] n_, y___} := {x, a \[Diamond] (m + n), y};
{x___, a_ \[Diamond] m_} \[CirclePlus] z : {b_ \[Diamond] n_, y___} := If[a \[Precedes] b, {x} \[CirclePlus] z, {x, a \[Diamond] m, b \[Diamond] n, y}];
{} \[CircleTimes] _ = {};
_ \[CircleTimes] {} = {};
{a_ \[Diamond] m_, x___} \[CircleTimes] {b_ \[Diamond] n_} := If[b === {}, {a \[Diamond] (m n), x}, {(a \[CirclePlus] b) \[Diamond] n}];
x_ \[CircleTimes] {y_, z__} := x \[CircleTimes] {y} \[CirclePlus] x \[CircleTimes] {z};
f[1] = {{{} \[Diamond] 1}};
f[n_] := f[n] = Union[Flatten[Table[Outer[#1 \[CircleTimes] {#2 \[Diamond] 1} &, f[k], f[n - k], 1], {k, n - 1}], 2]];
Table[Length[f[n]], {n, 1, 17}]

Formula

Conjecture: a(n) ~ c * d^n * n^(-3/2), where c = 0.664861... and d = A051491 = 2.955765... - Vladimir Reshetnikov, Aug 11 2016

Extensions

a(18)-a(20) from Robert G. Wilson v, Sep 15 2012
Showing 1-4 of 4 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.