A390910 Number of noncrossing path sets on n nodes with isolated vertices allowed.

1, 1, 2, 7, 29, 126, 564, 2591, 12171, 58237, 282918, 1391820, 6919788, 34714304, 175505312, 893311991, 4573948519, 23542885643, 121747858590, 632247484031, 3295782688717, 17239401116618, 90457565969620, 476004125634108, 2511411310174548, 13282398218135836

Offset

0,3

Links

Andrew Howroyd, Table of n, a(n) for n = 0..500

Formula

G.f.: (1/x) * Series_Reversion( x*(1 - 2*x)^2/(1 - 3*x + x^2 + 3*x^3) ).

Example

Case n=4: There are 29 possibilities:
   o   o    o   o    o   o    o   o    o   o    o---o    o   o    o---o
                       /      |          /               |   |      /
   o   o    o---o    o   o    o---o    o---o    o---o    o---o    o---o
    (1)      (4)      (2)      (4)      (8)      (2)      (4)      (4)

Prog

(PARI) seq(n) = Vec(serreverse(x*(1 - 2*x)^2/(1 - 3*x + x^2 + 3*x^3) + O(x^(n+2))));

Crossrefs

Row sums of A390909.

Cf. A303730 (no isolated vertices), A303836 (up to rotation), A303835 (up to rotation and reflection).

Sequence in context: A134169 A052961 A150662 * A278391 A126568 A150663

Adjacent sequences: A390907 A390908 A390909 * A390911 A390912 A390913

Keyword

nonn

Author

Andrew Howroyd, Nov 27 2025

Status

approved