A332426 -id:A332426 - cp's OEIS frontend

A359404 Number of unordered triples of self-avoiding paths with nodes that cover all vertices of a convex n-gon.

0, 0, 15, 315, 4200, 45360, 433440, 3825360, 31944000, 256164480, 1991877888, 15117822720, 112519680000, 824063385600, 5953789181952, 42518284701696, 300588079104000, 2106258635980800, 14642876032942080, 101081482775691264, 693338799538176000, 4728258324725760000, 32074214121878323200

Offset: 4

Ivaylo Kortezov, Dec 30 2022

The paths considered here cover at least 2 vertices and have segments that do not intersect each other. Although each path is self-avoiding, the different paths are allowed to intersect.

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

			a(6) = 6!/(2!2!2!3!) = 5*3 = 15 is the number of ways to pair each vertex with another.
a(7) = 7!*3/(2!*2!*3!*2!) = 315 since the 7 vertices must be split into two pairs and one triple, the order of the two pairs is irrelevant, and there are 3 choices of the segment in the triple not connected by a segment.

Andrew Howroyd, Table of n, a(n) for n = 4..500
Ivaylo Kortezov, Sets of Non-self-intersecting Paths Connecting the Vertices of a Convex Polygon, Mathematics and Informatics, Vol. 65, No. 6, 2022.
Index entries for linear recurrences with constant coefficients, signature (48,-1040,13440,-115296,691200,-2967296,9185280,-20336896,31395840, -32071680,19464192,-5308416).

Cf. A001792, A332426 (unordered pairs of paths).

Table[n*(n-1)*(n-2)*2^(n-10)*(3^(n-4) - 2^(n-3) + 1),{n,4,26}] (* Stefano Spezia, Dec 30 2022 *)

a(n) = {if(n<=3, 0, n*(n-1)*(n-2)*2^(n-10)*(3^(n-4) - 2^(n-3) + 1))} \\ Andrew Howroyd, Jan 10 2023

a(n) = n*(n-1)*(n-2)*2^(n-10)*(3^(n-4) - 2^(n-3) + 1).

E.g.f.: (1/6)*((x*exp(2*x) - x)/4)^3. - Andrew Howroyd, Jan 10 2023

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

Original entry on oeis.org

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

Ivaylo Kortezov, Feb 12 2020

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

			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.

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

Cf. A001792, A332426.

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

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

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)

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

Original entry on oeis.org

3, 15, 70, 330, 1596, 7840, 38592, 188640, 911680, 4350720, 20507136, 95560192, 440724480, 2014003200, 9128476672, 41074384896, 183618256896, 816062464000, 3607813816320, 15874289958912, 69544309424128, 303465643376640, 1319414897049600, 5717462509158400, 24699433622962176, 106397550709309440

Offset: 3

Ivaylo Kortezov, Dec 30 2022

The paths considered here have segments that do not intersect each other. Although each path is self-avoiding, the different paths are allowed to intersect.

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

Ivaylo Kortezov, Sets of Non-self-intersecting Paths Connecting the Vertices of a Convex Polygon, Mathematics and Informatics, Vol. 65, No. 6, 2022.
Index entries for linear recurrences with constant coefficients, signature (18,-132,504,-1056,1152,-512).

A332426 is the case with paths having at least 2 nodes each.

Cf. A001792.

LinearRecurrence[{18,-132,504,-1056,1152,-512},{3,15,70,330,1596,7840},26] (* Stefano Spezia, Dec 30 2022 *)

a(n) = {if(n < 3, 0, n*(n - 1)*2^(n-6)*(2^(n-3) + 3))} \\ Andrew Howroyd, Jan 10 2023

a(n) = n * (n-1) * 2^(n-6) * (2^(n-3) + 3).
From Stefano Spezia, Dec 30 2022: (Start)
G.f.: x^3*(3 - 39*x + 196*x^2 - 462*x^3 + 504*x^4 - 224*x^5) / ((1 - 2*x)^3*(1 - 4*x)^3).
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)
E.g.f.: ((x*exp(2*x) + 3*x)/4)^2/2 - x^2/2. - Andrew Howroyd, Jan 10 2023

A360716 Number of unordered pairs of self-avoiding paths whose sets of nodes are disjoint subsets of a set of n points on a circle; one-node paths are not allowed.

Original entry on oeis.org

0, 0, 0, 3, 45, 435, 3465, 24794, 165942, 1061730, 6578550, 39796053, 236309931, 1382504669, 7989938775, 45704622660, 259155482652, 1458298435572, 8151155034300, 45290328792695, 250308998693145, 1376766613411959, 7539656755416885, 41126122248463038, 223513887538508850, 1210707873300202550, 6537847299012919890

Offset: 1

Ivaylo Kortezov, Feb 18 2023

Although each path is self-avoiding, the different paths are allowed to intersect.

			a(5)=30+15=45: the first summand corresponds to the case when one of the paths has three nodes (5*4*3/2=30 variants; division by 2 is due to directional independence) and the second to the case when both paths have two nodes (5!/(2!2!2!)=15 variants).

Ivaylo Kortezov, Sets of Paths between Vertices of a Polygon, Mathematics Competitions, Vol. 35 (2022), No. 2, ISSN:1031-7503, pp. 35-43.
Index entries for linear recurrences with constant coefficients, signature (27,-312,2016,-7986,19998,-31472,29880,-15525,3375).

If there is only one path, we get A261064. If all n points need to be used, we get A332426.

a(n) = n*(n-1)*2^(-5)*(5^(n-2) - 2*3^(n-2) + 1).
From Andrew Howroyd, Feb 19 2023: (Start)
Binomial transform of A332426.
a(n) = 27*a(n-1) - 312*a(n-2) + 2016*a(n-3) - 7986*a(n-4) + 19998*a(n-5) - 31472*a(n-6) + 29880*a(n-7) - 15525*a(n-8) + 3375*a(n-9) for n > 9.
G.f.: x^4*(3 - 36*x + 156*x^2 - 288*x^3 + 197*x^4)/((1 - x)*(1 - 3*x)*(1 - 5*x))^3.
E.g.f.: exp(x)*(exp(2*x) - 1)^2*x^2/32.
(End)

A360275 Number of unordered quadruples of self-avoiding paths with nodes that cover all vertices of a convex n-gon.

Original entry on oeis.org

0, 0, 0, 0, 0, 105, 3780, 81900, 1386000, 20207880, 266666400, 3277354080, 38198160000, 427365818880, 4629059635200, 48842864179200, 504335346278400, 5114054709319680, 51064119467827200, 503151159589478400, 4900668252598272000, 47248486914198011904, 451429610841538560000

Offset: 3

Ivaylo Kortezov, Feb 01 2023

nonn

The paths considered here cover at least 2 vertices. Although each path is self-avoiding, the different paths are allowed to intersect.

			a(9) = 9!*3/(2!2!2!3!3!) = 3780 since we have to split the 9 vertices into three pairs and one triple, the order of the three pairs is irrelevant, and there are 3 ways of connecting the triple.

Ivaylo Kortezov, Sets of Non-self-intersecting Paths Connecting the Vertices of a Convex Polygon, Mathematics and Informatics, Vol. 65, No. 6, 2022.

Cf. A001792, A332426 (unordered pairs of paths), A359404 (unordered triples of paths).

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

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.

Original entry on oeis.org

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

Ivaylo Kortezov, Jun 30 2023

nonn

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.

			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.

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

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

cp's OEIS Frontend

A359404 Number of unordered triples of self-avoiding paths with nodes that cover all vertices of a convex n-gon.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A360716 Number of unordered pairs of self-avoiding paths whose sets of nodes are disjoint subsets of a set of n points on a circle; one-node paths are not allowed.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A360275 Number of unordered quadruples of self-avoiding paths with nodes that cover all vertices of a convex n-gon.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

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.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula