A362786 Number of unordered triples 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, 0, 0, 5, 63, 476, 2772, 13680, 60060, 241472, 906048, 3214848, 10890880, 35481600, 111794176, 342171648, 1021031424, 2979102720, 8520171520, 23934468096, 66156625920, 180198047744, 484304486400, 1285790105600, 3375480176640, 8769899593728, 22567515586560, 57557594931200

Offset

1,6

Links

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

Index entries for linear recurrences with constant coefficients, signature (16,-112,448,-1120,1792,-1792,1024,-256).

Formula

a(n) = 2^(n-12)*n*(n-1)*(n-2)*(n-4)*(n-5)*(n+2)*(n+9)/90 for n != 3.

G.f.: x^6*(1 - x)*(5 - 12*x + 16*x^2 - 12*x^3 + 4*x^4)/(1 - 2*x)^8. - Andrew Howroyd, Nov 14 2025

Example

For n=7 we have one 3-node path and two 2-node paths. Call two paths adjacent if we can choose one node from each path so that the two nodes are adjacent vertices of the n-gon. Then either each pair of paths is adjacent, or the two 2-node paths are not adjacent, or a 2-node path is not adjacent to the 3-node path. In each of these three cases there are 7 choices for the set of nodes for the 3-node path and 3 ways to connect them, and then the 2-node paths are uniquely determined. Thus a(7) = 3*7*3 = 63.

Mathematica

A362786[n_] := Quotient[2^(n-13)*n*(n-1)*(n-2)*(n-4)*(n-5)*(n+2)*(n+9), 45];
Array[A362786, 30] (* Paolo Xausa, Jun 26 2026 *)

Prog

(PARI) a(n) = if(n<6, 0, 2^(n-12)*n*(n-1)*(n-2)*(n-4)*(n-5)*(n+2)*(n+9)/90) \\ Andrew Howroyd, Nov 27 2025

Crossrefs

Column k=3 of A390908.

The number of unordered pairs of disjoint self-avoiding paths with nodes that cover all vertices of a convex n-gon is A308914(n). The number of unordered triples of (not necessarily disjoint) self-avoiding paths with nodes that cover all vertices of a convex n-gon is A359404(n).

Sequence in context: A209117 A238087 A063079 * A222376 A243218 A112788

Adjacent sequences: A362783 A362784 A362785 * A362787 A362788 A362789

Keyword

nonn,easy,changed

Author

Ivaylo Kortezov, May 04 2023

Extensions

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

Status

approved