login

Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.

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

%I #34 Mar 27 2022 13:29:56

%S 2,2,2,14,30,50,170,462,1014,2810,7906,19910,53278,148514,397530,

%T 1073918,2976390,8172426,22413266,62219830,172846382,479683762,

%U 1338281802,3743620974,10475828630,29389158426,82643684034,232644515366,655928162878,1852640651330,5239096953274

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

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

%C Equivalently, the polygons can be colored using two colors. - _Andrew Howroyd_, Jan 09 2022

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

%F a(n) = Sum_{k=1..floor(n/3)} 2^k * A350248(n,k). - _Andrew Howroyd_, Jan 09 2022

%F 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.

%e 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.

%t 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 *)

%o (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

%Y Cf. A350116, A350248.

%K nonn

%O 3,1

%A _Janaka Rodrigo_, Jan 08 2022