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-3 of 3 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.

A361048 Expansion of g.f. A(x) satisfying a(n) = [x^(n-1)] A(x)^(n+1) for n >= 1.

Original entry on oeis.org

1, 1, 3, 18, 160, 1830, 25074, 395248, 6990876, 136464705, 2906040280, 66938704602, 1656963703434, 43848218457953, 1235194571623950, 36905133359883240, 1165832901366137184, 38830278855693956931, 1360186936717777641747, 49995325008141402758320
Offset: 0

Views

Author

Paul D. Hanna, Mar 13 2023

Keywords

Comments

A variant of A113882 (number of well-nested drawings of a rooted tree).

Examples

			G.f.: A(x) = 1 + x + 3*x^2 + 18*x^3 + 160*x^4 + 1830*x^5 + 25074*x^6 + 395248*x^7 + 6990876*x^8 + 136464705*x^9 + ...
The table of coefficients in the successive powers of g.f. A(x) begins:
n = 1: [1, 1,  3,  18,  160,  1830,  25074,  395248, ...];
n = 2: [1, 2,  7,  42,  365,  4088,  55092,  857384, ...];
n = 3: [1, 3, 12,  73,  624,  6855,  90885, 1396236, ...];
n = 4: [1, 4, 18, 112,  947, 10224, 133410, 2023028, ...];
n = 5: [1, 5, 25, 160, 1345, 14301, 183765, 2750560, ...];
n = 6: [1, 6, 33, 218, 1830, 19206, 243205, 3593406, ...];
n = 7: [1, 7, 42, 287, 2415, 25074, 313159, 4568131, ...];
n = 8: [1, 8, 52, 368, 3114, 32056, 395248, 5693528, ...];
n = 9: [1, 9, 63, 462, 3942, 40320, 491304, 6990876, ...];
...
in which the secondary diagonal equals this sequence (shift left one position).
RELATION TO A361049.
The main diagonal in the above table,
[1, 2, 12, 112, 1345, 19206, 313159, 5693528, ...],
can be used to obtain the coefficients of the g.f. B(x) of A361049 like so:
[1, 2/2, 12/3, 112/4, 1345/5, 19206/6, 313159/7, 5693528/8, ...]
= [1, 1, 4, 28, 269, 3201, 44737, 711691, ..., A361049(n), ...].
Further, the coefficients in B(x)^2, which begins
[1, 2, 9, 64, 610, 7164, 98812, 1553528, 27292941, ...],
can in turn be used to generate the terms of this sequence:
[1*2/2, 2*3/2, 9*4/2, 64*5/2, 610*6/2, 7164*7/2, 98812*8/2, ...]
= [1, 3, 18, 160, 1830, 25074, 395248, ...].

Links

Crossrefs

Cf. A361049, A113882, A132070.

Programs

  • PARI
    {a(n) = my(A=[1]); for(i=1,n, A = concat(A,0);
A[#A] = -polcoeff( Ser(A) - x*Ser(A)^(#A), #A-1)); A[n+1]}
for(n=0,30,print1(a(n),", "))

Formula

Given g.f. A(x) = Sum_{n>=0} a(n)*x^n, let B(x) be the g.f. of A361049, then the following formulas hold.
(1) a(n) = [x^(n-1)] A(x)^(n+1) for n >= 1.
(2) a(n) = (n+1)/2 * [x^(n-1)] B(x)^2 for n >= 1.
(3) A(x) = 1 + x*B(x)^2 + x^2*B(x)*B'(x).
(4) A(x) = B(x/A(x)).
(5) A(x) = x / Series_Reversion(x*B(x)).
(6) B(x) = A(x*B(x)).
a(n) ~ c * n! * n^(3*LambertW(1) - 2 + 3/(1 + LambertW(1))) / LambertW(1)^n, where c = 0.078464448259604971209... - Vaclav Kotesovec, Mar 13 2023

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-3 of 3 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.