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

Author

David Callan, Mar 23 2004

Keywords

• easy
• nonn
• changed

Comments

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

Examples

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

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)

Crossrefs

Row sums of A093127.

Programs

Magma

R:=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

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

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

Sage

def A093128_list(prec):
    P. = 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

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

Extensions

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