A363964 Number of unordered pairs of non-intersecting non-self-intersecting paths, singletons included, with nodes that cover all vertices of a convex labeled n-gon.

3, 14, 55, 195, 644, 2016, 6048, 17520, 49280, 135168, 362752, 955136, 2472960, 6307840, 15876096, 39481344, 97124352, 236584960, 571146240, 1367539712, 3249799168, 7669284864, 17983078400, 41916825600, 97165246464, 224076496896, 514272002048, 1174992322560

Offset: 3

Author

Ivaylo Kortezov, Jun 30 2023

Keywords

• nonn

Comments

For each such path there is a sequence of distinct vertices of the n-gon, each (except the last one) connected by a segment with the next vertex in the sequence; the segments have no common internal points. The path itself is the union of the set of these segments and is thus direction-independent: reversing the order of the vertices leads to the same path. If the sequence of vertices has length 1 then there are no segments; we call such a path a singleton.

Examples

			a(4)=14 since if one of the paths is a singleton (4 choices), then there are A001792(3)=3 choices for the other path, and otherwise for the two paths there are A308914(4)=2 choices, so a(4)=4*3+2=14.
		

Crossrefs

Cf. A001792, A308914, A332426, A360716, A360717.

Formula

a(n) = n*(n-1)*(n^2+n+36)*2^(n-8)/3.