login
A350599
Number of ways to partition the set of vertices of a convex n-gon into non-intersecting directed polygons.
0
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
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
Sequence in context: A289068 A063898 A074052 * A361815 A349564 A129409
KEYWORD
nonn
AUTHOR
Janaka Rodrigo, Jan 08 2022
STATUS
approved