A308914 Number of unordered pairs of non-intersecting non-selfintersecting paths with nodes that cover all vertices of a convex n-gon, n > 3.

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

4,1

Comments

Paths must have at least two nodes.

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

Links

Table of n, a(n) for n=4..30.

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).

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 non-selfintersecting 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 *)

Crossrefs

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

Status

approved