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-2 of 2 results.

A113882 Number of well-nested drawings of a rooted tree.

Original entry on oeis.org

1, 1, 2, 9, 64, 605, 6996, 94556, 1452928, 24921765, 471091360, 9720039120, 217285778700, 5230874655578, 134929133296972, 3713182459524270, 108605754921052880, 3364866315332574493, 110099293819641466488, 3794219154973411079432, 137375263325254329836460
Offset: 0

Views

Author

Marco Kuhlmann (kuhlmann(AT)ps.uni-sb.de), Jan 27 2006

Keywords

Comments

The value a(n) also gives the number of non-crossing partitions on [n] such that (a) each block of the partition is a non-crossing partition itself (recursively) and (b) every partition in this recursion contains at least one singleton block (see A000108). Omitting the factor n in the equation for a(n) gives A110447.

Examples

			a(5)=605 because there are 605 possibilities to form 5 nodes into a rooted tree and order the nodes of this tree such that no two subtrees interleave. Two subtrees t1, t2 interleave if their roots are (tree-)disjoint and there are four nodes l1, r1 from t1 and l2, r2 from t2 such that l1 < l2 < r1 < r2.
Comment from _Paul D. Hanna_, Aug 08 2007 (revised Apr 28 2012): (Start)
Illustrate a(n) = [x^(n-1)] A(x)^n by the following generating method.
Form a table of coefficients in powers of the g.f. A(x):
A(x)^1: [(1), 1, 2, 9, 64, 605, 6996, 94556, ...];
A(x)^2: [1, (2), 5, 22, 150, 1374, 15539, 206676, ...];
A(x)^3: [1, 3, (9), 40, 264, 2346, 25937, 339294, ...];
A(x)^4: [1, 4, 14, (64), 413, 3568, 38558, 495848, ...];
A(x)^5: [1, 5, 20, 95, (605), 5096, 53840, 680365, ...];
A(x)^6: [1, 6, 27, 134, 849, (6996), 72302, 897558, ...];
A(x)^7: [1, 7, 35, 182, 1155, 9345, (94556), 1152936, ...]; ...
then the coefficients along the main diagonal form the initial terms of this sequence. (End)

References

  • Manuel Bodirsky, Marco Kuhlmann and Mathias Mohl: Well-Nested Drawings as Models of Syntactic Structure, 10th Conference on Formal Grammar and 9th Meeting on Mathematics of Language, Edinburgh, Scotland, UK

Links

Crossrefs

Cf. A000108, A110447, A132070, A361048.

Programs

  • PARI
    {a(n)=my(G=1+x+2*x^2); for(k=0,n,G=1+x*deriv(serreverse(x/(G+x^2*O(x^n) )))); polcoef(G,n)} \\ Paul D. Hanna, Aug 08 2007

Formula

a(0) = a(1) = 1; a(n) = n * F(n-1), where F(0) = F(1) = 1, F(n) = sum_{i=1}^{n} a(i) * F(n-i, i), where F(0, k) = 1; F(n, 1) = F(n), F(n, k) = sum_{i=0}^{n} F(i) * F(n-i, k-1).
Contribution from Paul D. Hanna, Aug 08 2007 (revised Apr 28 2012): (Start)
G.f. A(x) = Sum_{n>=0} a(n)*x^n satisfies:
a(n) = [x^(n-1)] A(x)^n for n>=1;
a(n) = (n+1)*A132070(n+1) for n>=0;
A(x) = x / Series_Reversion(x*G(x)) = G(x/A(x)) where G(x) = A(x*G(x)) is the g.f. of A132070. (End)

Extensions

Initial term added and offset changed to 0 by Paul D. Hanna, Apr 28 2012.

A361049 G.f. satisfies: A(x) = (1/x)*Series_Reversion( x/(1 + x*A(x)^2 + x^2*A(x)*A'(x)) ).

Original entry on oeis.org

1, 1, 4, 28, 269, 3201, 44737, 711691, 12630023, 246594988, 5244025502, 120540052304, 2976918491501, 78601791684495, 2209667973082374, 65901745111752843, 2078619947109354811, 69141776287740239348, 2419303138068147399700, 88842295496847889690405
Offset: 0

Views

Author

Paul D. Hanna, Mar 13 2023

Keywords

Examples

			G.f.: A(x) = 1 + x + 4*x^2 + 28*x^3 + 269*x^4 + 3201*x^5 + 44737*x^6 + 711691*x^7 + 12630023*x^8 + 246594988*x^9 + ...
such that A(x) = G(x*A(x)) where G(x) is given by
G(x) = 1 + d/dx (x^2 * A(x)^2)/2, which begins
G(x) = 1 + x + 3*x^2 + 18*x^3 + 160*x^4 + 1830*x^5 + 25074*x^6 + 395248*x^7 + 6990876*x^8 + ... + A361048(n)*x^n + ...

Links

Crossrefs

Cf. A361048, A132070, A113882.

Programs

  • PARI
    {a(n) = my(A=1); for(i=1,n,
A = (1/x)*serreverse( x/(1 + x*A^2 + x^2*A*A') +x^2*O(x^n) )); polcoeff(A,n)}
for(n=0,30, print1(a(n),", "))

Formula

Given g.f. A(x) = Sum_{n>=0} a(n)*x^n, let G(x) be the g.f. of A361048, then the following formulas hold.
(1) A(x) = (1/x)*Series_Reversion( x/(1 + x*A(x)^2 + x^2*A(x)*A'(x)) ).
(2) A(x) = G(x*A(x)).
(4) A(x) = (1/x)*Series_Reversion(x/G(x)).
(3) G(x) = A(x/G(x)).
(5) G(x) = 1 + d/dx (x^2 * A(x)^2)/2.
a(n) ~ c * n! * n^(3*LambertW(1) - 2 + 3/(1 + LambertW(1))) / LambertW(1)^n, where c = 0.13835030685615842626... - Vaclav Kotesovec, Mar 13 2023
Showing 1-2 of 2 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.