A256752 Number of ways to place non-intersecting diagonals in a convex (n+2)-gon so as to create no hexagons.

1, 3, 11, 44, 190, 859, 4015, 19248, 94117, 467575, 2353443, 11975568, 61505088, 318406927, 1659801852, 8704865907, 45898065978, 243163198928, 1293769867676, 6910165762943, 37036898772008, 199140325574519, 1073849938338566

Offset

1,2

Links

Table of n, a(n) for n=1..23.

D. Birmajer, J. B. Gil, and M. Weiner, Colored partitions of a convex polygon by noncrossing diagonals, arXiv:1503.05242 [math.CO], 2015.

Formula

a(n) = (1/(n+1))*Sum_{i=0..floor(n/4)} Sum_{k=i+1..n-3*i} (-1)^i*binomial(n+k,k)*binomial(k,i)*binomial(n-4*i-1,k-i-1), n !== 0 (mod 4),

a(n) = ((-1)^(n/4)/(n+1))*binomial(5*n/4,n/4) + (1/(n+1))*Sum_{i=0..(n/4)-1} Sum_{k=i+1..n-3*i} (-1)^i*binomial(n+k,k)*binomial(k,i)*binomial(n-4*i-1,k-i-1), n == 0 (mod 4).

Example

a(3)=11 because all 11 dissections of the pentagon are allowed, i.e., the null placement, 5 placements of 1 diagonal and 5 placements of two diagonals.

Mathematica

Rest[CoefficientList[(InverseSeries[Series[(y-2*y^2+y^5-y^6)/(1-y), {y, 0, 24}], x]-x)/x, x]]

Crossrefs

Cf. A046736, A054515, A253194.

Sequence in context: A063018 A293468 A151108 * A018963 A217886 A234627

Adjacent sequences: A256749 A256750 A256751 * A256753 A256754 A256755

Keyword

nonn

Author

Michael D. Weiner, Apr 09 2015

Status

approved