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.

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.

A361359 Number of nonequivalent noncrossing caterpillars with n edges up to rotation.

Original entry on oeis.org

1, 1, 1, 4, 11, 49, 196, 868, 3721, 16306, 70891, 309739, 1350831, 5897934, 25740386, 112368153, 490489041, 2141121271, 9346382981, 40799215354, 178097506051, 777437032059, 3393689486976, 14814237183658, 64667544141561, 282288713218896, 1232255125682671
Offset: 0

Views

Author

Andrew Howroyd, Mar 09 2023

Keywords

Comments

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

Links

Crossrefs

Cf. A296532 (noncrossing trees), A361356, A361358, A361360 (up to rotation and reflection).

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 + x*subst((1 + 2*x*f)/(1-x)^2, x, x^2)/2 }
{ Vec(G(x) + O(x^30)) }

Formula

G.f.: (1 - 5*x - 2*x^2 + 27*x^3 - 20*x^4 - 13*x^5 + 23*x^6 - 5*x^7 - 6*x^8 + 3*x^9)/((1 - x)*(1 - 5*x + 3*x^2 - x^3)*(1 - 5*x^2 + 3*x^4 - x^6)).
a(n) = 6*a(n-1) - 3*a(n-2) - 26*a(n-3) + 36*a(n-4) - 2*a(n-5) - 18*a(n-6) + 6*a(n-7) + 5*a(n-8) - 4*a(n-9) + a(n-10) for n >= 10.

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.

A361357 Triangle read by rows: T(n,k) is the number of noncrossing caterpillars with n edges and diameter k, 0 <= k <= n.

Original entry on oeis.org

1, 0, 1, 0, 0, 3, 0, 0, 4, 8, 0, 0, 5, 30, 20, 0, 0, 6, 75, 144, 48, 0, 0, 7, 154, 595, 504, 112, 0, 0, 8, 280, 1848, 2896, 1536, 256, 0, 0, 9, 468, 4788, 12060, 11268, 4320, 576, 0, 0, 10, 735, 10920, 40700, 58760, 38480, 11520, 1280
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 diameter of a tree is also the length of the longest path.

Examples

			Triangle begins:
  1;
  0, 1;
  0, 0,  3;
  0, 0,  4,   8;
  0, 0,  5,  30,    20;
  0, 0,  6,  75,   144,    48;
  0, 0,  7, 154,   595,   504,   112;
  0, 0,  8, 280,  1848,  2896,  1536,   256;
  0, 0,  9, 468,  4788, 12060, 11268,  4320,   576;
  0, 0, 10, 735, 10920, 40700, 58760, 38480, 11520, 1280;
  ...

Links

Crossrefs

Row sums are A361356.
Main diagonal is A001792(n-1).

Programs

  • PARI
    T(n) = {my(f=x*y*(2 - x)/(1 - (3 + 2*y)*x + 3*x^2 - x^3), g = 1 + x*y + (x*y)^2*((3 - 2*x) + (4 - 3*x + x^2)*f + (1 + 2*x)*f^2)/(1 - x)^2); [Vecrev(p) | p<-Vec(g + O(x*x^n))]}
{ my(A=T(9)); for(i=1, #A, print(A[i])) }

Formula

T(n,2) = n + 1 for n >= 2.
G.f.: A(x,y) = 1 + x*y + (x*y)^2*((3 - 2*x) + (4 - 3*x + x^2)*F(x,y) + (1 + 2*x)*F(x,y)^2)/(1 - x)^2 where F(x,y) = x*y*(2 - x)/(1 - (3 + 2*y)*x + 3*x^2 - x^3).
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.