A332426 Number of unordered pairs of non-selfintersecting paths with nodes that cover all vertices of a convex n-gon.

0, 3, 30, 210, 1260, 6944, 36288, 182880, 897600, 4316928, 20427264, 95373824, 440294400, 2013020160, 9126248448, 41069371392, 183607050240, 816037560320, 3607758766080, 15874168848384, 69544044134400, 303465064562688

Offset

3,2

Comments

Although each path is non-selfintersecting, the two paths are allowed to intersect.

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

Given a sequence of two or more different vertices of the n-gon, if we connect each vertex after the first one by a segment to the preceding vertex, then the union of these segments is a path (the direction does not matter).

Links

Table of n, a(n) for n=3..24.

Index entries for linear recurrences with constant coefficients, signature (18,-132,504,-1056,1152,-512).

Formula

a(n) = n*(n-1)*2^(n-6)*(2^(n-3)-1).

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

From Stefano Spezia, Feb 12 2020: (Start)

O.g.f.: x^4*(3 - 24*x + 66*x^2 - 72*x^3 + 32*x^4)/(1 - 6*x + 8*x^2)^3.

E.g.f.: (exp(2*x) - 1)^2*x^2/32.

a(n) = 18*a(n-1) - 132*a(n-2) + 504*a(n-3) - 1056*a(n-4) + 1152*a(n-5) - 512*a(n-6) for n > 8.

(End)

Example

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

Maple

gf := ((exp(2*x)-1)*x)^2/32: ser := series(gf, x, 32):
seq(n!*coeff(ser, x, n), n=3..24); # Peter Luschny, Mar 01 2020

Crossrefs

Cf. A001792, A308914.

Sequence in context: A203366 A130546 A051133 * A043030 A178015 A120689

Adjacent sequences: A332423 A332424 A332425 * A332427 A332428 A332429

Keyword

easy,nonn

Author

Ivaylo Kortezov, Feb 12 2020

Status

approved