A308914 Number of unordered pairs of disjoint self-avoiding paths with nodes that cover all vertices of a convex n-gon; one node paths are not allowed.

0, 0, 0, 2, 15, 75, 308, 1120, 3744, 11760, 35200, 101376, 282880, 768768, 2042880, 5324800, 13647872, 34467840, 85917696, 211681280, 516096000, 1246429184, 2984509440, 7090470912, 16724787200, 39190528000, 91276443648, 211392921600, 487025803264, 1116607610880

Offset

1,4

Comments

Paths must have at least two nodes. Paths may not cross themselves or other paths.

The number of self-avoiding paths that cover all vertices of a convex n-gon is given by A001792(n-2).

Links

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

Index entries for linear recurrences with constant coefficients, signature (10,-40,80,-80,32).

Formula

a(n) = (1/3)*n*(n-1)*(n-3)*(n+4)*2^(n-8) for n != 2.

a(n) = (n/2)*Sum_{k=2..n-2} A001792(k-2)*A001792(n-k-2).

From Stefano Spezia, Feb 12 2020: (Start)

O.g.f.: x^4*(-2 + 5*x - 5*x^2 + 2*x^3)/(-1 + 2*x)^5.

E.g.f.: x^2*(3 + exp(2*x)*(-3 + 6*x + 2*x^2))/96.

a(n) = 10*a(n-1) - 40*a(n-2) + 80*a(n-3) - 80*a(n-4) + 32*a(n-5) for n > 8. (End)

Example

a(5) = 15 since one of the self-avoiding paths has to be a segment connecting two adjacent vertices (5 choices) and the other path will connect the remaining vertices in one of three ways.

Maple

gf := x^2*(3 + exp(2*x)*(-3 + 6*x + 2*x^2))/96: ser := series(gf, x, 36):
seq(n!*coeff(ser, x, n), n=4..30); # Peter Luschny, Mar 01 2020

Mathematica

Array[(1/3) # (# - 1) (# - 3) (# + 4)*2^(# - 8) &, 27, 4] (* Michael De Vlieger, Feb 25 2020 *)

Prog

(PARI) a(n) = if(n < 4, 0, n*(n-1)*(n-3)*(n+4)*2^(n-8)/3); \\ Andrew Howroyd, Nov 27 2025

Crossrefs

Column k=2 of A390908.

Cf. A001792, A332426.

Sequence in context: A268644 A178321 A007232 * A099743 A283842 A344215

Adjacent sequences: A308911 A308912 A308913 * A308915 A308916 A308917

Keyword

easy,nonn

Author

Ivaylo Kortezov, Feb 12 2020

Extensions

a(1)-a(3)=0 prepended by Andrew Howroyd, Nov 27 2025

Status

approved