A350599 Number of ways to partition the set of vertices of a convex n-gon into non-intersecting directed polygons.

2, 2, 2, 14, 30, 50, 170, 462, 1014, 2810, 7906, 19910, 53278, 148514, 397530, 1073918, 2976390, 8172426, 22413266, 62219830, 172846382, 479683762, 1338281802, 3743620974, 10475828630, 29389158426, 82643684034, 232644515366, 655928162878, 1852640651330, 5239096953274

Offset

3,1

Comments

A directed polygon is a polygon with an associated direction (clockwise or counterclockwise).

Equivalently, the polygons can be colored using two colors. - Andrew Howroyd, Jan 09 2022

Links

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

Formula

a(n) = Sum_{k=1..floor(n/3)} 2^k * binomial(n+1, k) * binomial(n-2*k-1, k-1) / (n+1).

a(n) = Sum_{k=1..floor(n/3)} 2^k * A350248(n,k). - Andrew Howroyd, Jan 09 2022

The compositional inverse of x+Sum_{k=1..infinity} a_k x^{k+1} is x(1-x)/(1+x)(1-2x+x^2). Proved at MathOverflow 418996.

Example

a(7) = 2 + 28 = 30 since the 7-gon can be given two directions and the 7-gon can also be partitioned into a triangle and a quadrilateral in 7 different ways giving another 7 * 4 = 28 possibilities.

Mathematica

a[n_] := Sum[2^k * Binomial[n + 1, k] * Binomial[n - 2*k - 1, k - 1]/(n + 1), {k, 1, Floor[n/3]}]; Array[a, 30, 3] (* Amiram Eldar, Jan 08 2022 *)

Prog

(PARI) a(n) = sum(k=1, n\3, 2^k * binomial(n+1, k) * binomial(n-2*k-1, k-1)) / (n+1) \\ Andrew Howroyd, Jan 08 2022

Crossrefs

Cf. A350116, A350248.

Sequence in context: A289068 A063898 A074052 * A361815 A349564 A129409

Adjacent sequences: A350596 A350597 A350598 * A350600 A350601 A350602

Keyword

nonn

Author

Janaka Rodrigo, Jan 08 2022

Status

approved