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.

A361356 Number of noncrossing caterpillars with n edges.

Original entry on oeis.org

1, 1, 3, 12, 55, 273, 1372, 6824, 33489, 162405, 779801, 3713436, 17560803, 82553597, 386105790, 1797803248, 8338313697, 38539754649, 177581276639, 815982230060, 3740047627071, 17103604731961, 78054858200448, 355541644914072, 1616688603539025
Offset: 0

Views

Author

Andrew Howroyd, Mar 09 2023

Keywords

Comments

A noncrossing caterpillar is a noncrossing tree that is a caterpillar tree (also called a caterpillar graph).
The number of nodes is n + 1. All trees up to 5 edges (or 6 nodes) are caterpillars.

Links

Crossrefs

Row sums of A361357.
Cf. A001764 (noncrossing trees), A005418 (unlabeled), A245012 (labeled).
Cf. A361358, A361359 (up to rotations), A361360 (up to rotations and reflections).

Programs

  • PARI
    Vec((1 - 11*x + 43*x^2 - 76*x^3 + 77*x^4 - 37*x^5 + 6*x^6)/((1 - x)^2*(1 - 5*x + 3*x^2 - x^3)^2) + O(x^30))

Formula

a(n) = 12*a(n-1) - 52*a(n-2) + 104*a(n-3) - 114*a(n-4) + 76*a(n-5) - 32*a(n-6) + 8*a(n-7) - a(n-8) for n >= 8.
G.f.: (1 - 11*x + 43*x^2 - 76*x^3 + 77*x^4 - 37*x^5 + 6*x^6)/((1 - x)^2*(1 - 5*x + 3*x^2 - x^3)^2).
G.f.: 1 + x + x^2*(3 - 2*x + (4 - 3*x + x^2)*F(x) + (1 + 2*x)*F(x)^2)/(1 - x)^2 where F(x) = x*(2 - x)/(1 - 5*x + 3*x^2 - x^3).

A361358 Expansion of x*(2 - x)/(1 - 5*x + 3*x^2 - x^3).

Original entry on oeis.org

2, 9, 39, 170, 742, 3239, 14139, 61720, 269422, 1176089, 5133899, 22410650, 97827642, 427040159, 1864128519, 8137349760, 35521403402, 155059096249, 676868620799, 2954687218650, 12897889327102, 56302253600359, 245772287239139, 1072852564721720
Offset: 1

Views

Author

Andrew Howroyd, Mar 09 2023

Keywords

Comments

This sequence arises in the enumeration of noncrossing caterpillar graphs (A361356). Given a directed edge (A,B) on the spine of the caterpillar where B is not a leaf node, then a(n) is the number of ways to complete the caterpillar using at most n nodes. Nodes cannot be added to A. Equivalently, a(n) is the number of ways to complete the caterpillar using exactly n nodes allowing leaves to be added to the left of A (but not to the right).

Examples

			In the following examples, o is a leaf and 1..n+1 is the spine.
a(1) = 2, a leaf can be added to the left or to the right of the spine:
   1---2    1  o
       |     \ |
       o       2
.
a(2) = a(1) + 7:
   1---2   1---2    1---2    1   o    1   3    1   o   1   o
     /         |      / |      \ |    | / |    |   |   | /
   3---o   o---3    o   o    o---2    2   o    2---3   2---o

Links

Crossrefs

Cf. A361356, A361359, A361360.

Programs

  • Mathematica
    LinearRecurrence[{5, -3, 1}, {2, 9, 39}, 30] (* Paolo Xausa, Jul 20 2024 *)
  • PARI
    Vec(x*(2 - x)/(1 - 5*x + 3*x^2 - x^3) + O(x^25))

Formula

a(n) = 5*a(n-1) - 3*a(n-2) + a(n-3) for n > 3.
a(n) = 2*A200676(n+2) - A200676(n+1).
G.f. A(x) satisfies A(x) = x*(2 - x + 2*A(x))/(1 - x)^3.

A361360 Number of nonequivalent noncrossing caterpillars with n edges up to rotation and relection.

Original entry on oeis.org

1, 1, 1, 3, 7, 28, 104, 448, 1886, 8212, 35556, 155124, 675897, 2950074, 12872294, 56188904, 245253691, 1070581703, 4673231521, 20399699635, 89048927767, 388718917440, 1696845506274, 7407120344070, 32333775400516, 141144364258374, 616127577376396
Offset: 0

Views

Author

Andrew Howroyd, Mar 10 2023

Keywords

Comments

The number of all noncrossing caterpillars with n edges is given by A361356.

Links

Crossrefs

Cf. A296533 (noncrossing trees), A361356, A361358, A361359 (up to rotation only).

Programs

  • PARI
    G(x)={ my(f = x*(2 - x)/(1 - 5*x + 3*x^2 - x^3), g = 1 + x + x^2*(3 - 2*x + (4 - 3*x + x^2)*f + (1 + 2*x)*f^2)/(1 - x)^2); (intformal(g) - 3)/x/2 + x*subst((3 + 2*x*(3-x)*f)/(1-x)^2, x, x^2)/4 + subst(1/(1-x) + x*f/(1-x), x, x^2)/2}
{ Vec(G(x) + O(x^30)) }

Formula

G.f.: (1 - 4*x - 8*x^2 + 28*x^3 + 15*x^4 - 55*x^5 - 2*x^6 + 46*x^7 - 11*x^8 - 19*x^9 + 10*x^10 + 2*x^11 - 2*x^12)/((1 - x)^2*(1 + x)^2*(1 - 5*x + 3*x^2 - x^3)*(1 - 5*x^2 + 3*x^4 - x^6)).
a(n) = 5*a(n-1) + 4*a(n-2) - 34*a(n-3) + 7*a(n-4) + 63*a(n-5) - 30*a(n-6) - 46*a(n-7) + 31*a(n-8) + 13*a(n-9) - 14*a(n-10) + 3*a(n-12) - a(n-13) for n >= 13.
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.