A093128 Number of dissections of a polygon using strictly disjoint diagonals.

1, 1, 3, 6, 13, 29, 65, 148, 341, 793, 1860, 4395, 10452, 24999, 60097, 145130, 351916, 856502, 2091599, 5123437, 12585354, 30995031, 76516348, 189310421, 469335998, 1165790119, 2900870597, 7230320746, 18049387617, 45123390441, 112963369113, 283162526640, 710664478791, 1785645155847, 4491596869206

Offset

0,3

Comments

a(n) is the number of dissections of a regular (n+2)-gon using 0 or more strictly disjoint diagonals.

Links

G. C. Greubel, Table of n, a(n) for n = 0..1000

Jean-Luc Baril, Sergey Kirgizov, Rémi Maréchal, and Vincent Vajnovszki, Grand Dyck paths with air pockets, arXiv:2211.04914 [math.CO], 2022.

Samuele Giraudo, Combalgebraic structures on decorated cliques, Formal Power Series and Algebraic Combinatorics, Séminaire Lotharingien de Combinatoire, 78B.15, 2017, p. 8; arXiv:1709.08416 [math.CO], 2017.

Giovanni Resta, Illustration of a(3)-a(10)

Formula

G.f.: 1 + (1+x)*( 1 -2*x -x^3 - sqrt((1 -3*x+ x^2)*(1-x)*(1-x^3)) )/(2*x^4).

a(n) = A004148(n+2) - A004148(n) for n>=1.

Logarithmic derivative yields A132461. - Paul D. Hanna, Nov 09 2013

G.f.: exp( Sum_{n>=1} A132461(n)*x^n/n ), where A132461(n) = Sum_{k=0..[n/2]} (C(n-k,k) + C(n-k-1,k-1))^2. - Paul D. Hanna, Nov 09 2013

Example

a(3)=6 because there are 5 ways to insert a single diagonal into a pentagon plus the empty dissection.

Maple

seq(coeff(series(1 + (1+x)*( 1 -2*x -x^3 - sqrt((1 -3*x+ x^2)*(1-x)*(1-x^3)) )/(2*x^4), x, n+2), x, n), n = 0..40); # G. C. Greubel, Dec 28 2019

Mathematica

CoefficientList[Series[1 +(1+x)*(1-2*x-x^3 -Sqrt[(1-3*x+x^2)*(1-x)*(1-x^3)])/( 2*x^4), {x, 0, 40}], x] (* G. C. Greubel, Dec 28 2019 *)

Prog

(PARI) {A132461(n)=sum(k=0, n\2, (binomial(n-k, k)+binomial(n-k-1, k-1))^2)}
{a(n)=polcoeff(exp(sum(m=1, n, A132461(m)*x^m/m)+x*O(x^n)), n)} \\ Paul D. Hanna, Nov 09 2013
(Magma) R<x>:=PowerSeriesRing(Rationals(), 40); Coefficients(R!( 1 + (1+x)*( 1 -2*x -x^3 - Sqrt((1 -3*x+ x^2)*(1-x)*(1-x^3)) )/(2*x^4) )); // G. C. Greubel, Dec 28 2019
(Sage)
def A093128_list(prec):
    P.<x> = PowerSeriesRing(ZZ, prec)
    return P( 1 + (1+x)*( 1 -2*x -x^3 - sqrt((1 -3*x+ x^2)*(1-x)*(1-x^3)) )/(2*x^4) ).list()
A093128_list(40) # G. C. Greubel, Dec 28 2019

Crossrefs

Row sums of A093127.

Sequence in context: A214260 A078061 A018909 * A005313 A213674 A108639

Adjacent sequences: A093125 A093126 A093127 * A093129 A093130 A093131

Keyword

easy,nonn

Author

David Callan, Mar 23 2004

Extensions

Terms a(26) onward added by G. C. Greubel, Dec 28 2019

Status

approved