A046736 -id:A046736 - cp's OEIS frontend

A054514 Number of ways to place non-crossing diagonals in convex (n+4)-gon so as to create no triangles or quadrilaterals.

1, 1, 1, 5, 10, 16, 45, 109, 222, 540, 1341, 3065, 7328, 18112, 43530, 105390, 260254, 639244, 1570257, 3893805, 9669236, 24014264, 59903650, 149806494, 374982790, 940835404, 2365679689, 5955973237, 15018854005, 37935575685, 95942896837, 242954350457, 616034170069, 1563810857705, 3974000543475

Offset: 1

Len Smiley, Apr 08 2000

nonn

			a(4)=5 because the octagon has the null placement and four ways to place a single diagonal.

Eli Bagno, Estrella Eisenberg, Shulamit Reches, and Moriah Sigron, Blockwise simple permutations, arXiv:2303.13115 [math.CO], 2023.
Eli Bagno, Estrella Eisenberg, Shulamit Reches, and Moriah Sigron, Geometric view of interval poset permutations, arXiv:2411.13193 [math.CO], 2024. See p. 10.
D. Birmajer, J. B. Gil, M. D. Weiner, Colored partitions of a convex polygon by noncrossing diagonals, arXiv preprint arXiv:1503.05242 [math.CO], 2015.
Len Smiley, Generalization and some variants

Cf. A046736, A049124, A003168, A054515.

f[x_] = InverseSeries[Series[(y - y^2 - y^4)/(1 - y), {y, 0, 38}], x];
CoefficientList[(f[x] - x)/x^4, x]
(* Second program: *)
a[n_] := Sum[Binomial[n-2j-1, n-3j-1] Binomial[n+3+j, n+2]/(n+3), {j, 0, (n-1)/3}]; Array[a, 35] (* Jean-François Alcover, Dec 08 2018, after David Callan *)
Table[HypergeometricPFQ[{1/3 - n/3, 2/3 - n/3, 1 - n/3, 4 + n}, {2, 1/2 - n/2, 1 - n/2}, -27/4], {n, 1, 40}] (* Vaclav Kotesovec, Sep 16 2023 *)

a(n) = Sum_{j=0..(n-1)/3} binomial[n-2j-1, n-3j-1] binomial[n+3+j, n+2]/(n+3). This counts the polygon dissections above by number j of diagonals. - David Callan, Jul 15 2004

More terms from Joerg Arndt, Jan 28 2014

A215341 Expansion of series_reversion( x/(1+x^4*sum(k>=0, x^k)) ) / x.

Original entry on oeis.org

1, 0, 0, 0, 1, 1, 1, 1, 5, 10, 16, 23, 53, 118, 232, 411, 813, 1718, 3568, 7012, 13925, 28603, 59533, 121878, 247915, 509136, 1057278, 2194138, 4536943, 9394145, 19552639, 40803472, 85131237, 177640486, 371426592, 778275264, 1632420197, 3425607187, 7195476245, 15134138683, 31866093569

Offset: 0

Joerg Arndt, Aug 19 2012

nonn

Number of Dyck words of semilength n with substrings UUU...UU (ascents) only of lengths >= 4. See A215340 for an explanation. [Joerg Arndt, Apr 16 2013]

Alois P. Heinz, Table of n, a(n) for n = 0..1000

Cf. A000108 (rev. of x/(1+1*sum(k>=1,x^k)) ), A005043 (rev. of x/(1+x*sum(k>=1,x^k)) ), A114997 (rev. of x/(1+x^2*sum(k>=1,x^k)) ).

Cf. A001003 (rev. of x*(1-1*sum(k=1,N,x^k)) ), A046736 (rev. of x*(1-x*sum(k=1,N,x^k)) ), A054514 (rev. of x*(1-x^2*sum(k=1,N,x^k)) ), A215342 (rev. of x*(1-x^3*sum(k=1,N,x^k)) ).

b:= proc(x, y, t) option remember; `if`(y0 and t in [0, 4],
       b(x-1, y, 0), 0) +b(x, y-1, min(t+1, 4))))
    end:
a:= n-> b(n, n, 0):
seq(a(n), n=0..50);  # Alois P. Heinz, Apr 16 2013

InverseSeries[x/(1+x^4/(1-x)) + O[x]^50] // CoefficientList[#, x]& // Rest (* Jean-François Alcover, Mar 29 2017 *)

a(n):=sum(binomial(n+1,i)*binomial(n-3*i-1,n-4*i),i,0,floor(n/4))/(n+1); /* Vladimir Kruchinin, Apr 01 2019 */

N=66; Vec( serreverse(x/(1+x^4*sum(k=0,N,x^k))+O(x^N)) / x )

G.f. A(x) satisfies 0 = -x^4*A(x)^4 - x*A(x)^2 + (x + 1)*A(x) - 1. [Joerg Arndt, Mar 01 2014]
Recurrence: 2*n*(n+1)*(2*n+3)*(16204*n^4 - 82948*n^3 + 139973*n^2 - 85643*n + 10674)*a(n) =  - (n-1)*n*(307876*n^5 - 960260*n^4 + 288863*n^3 + 582749*n^2 + 5406*n + 12696)*a(n-1) + 4*(n-2)*(129632*n^6 - 469136*n^5 + 354226*n^4 + 317255*n^3 - 469674*n^2 + 176517*n - 21420)*a(n-2) - 2*(n-3)*(n-2)*(16204*n^5 - 34336*n^4 + 82943*n^3 - 208775*n^2 + 192120*n - 40656)*a(n-3) + 6*(n-3)*(n-2)*(97224*n^5 - 351852*n^4 + 179198*n^3 + 540009*n^2 - 571727*n + 92968)*a(n-4) + 229*(n-4)*(n-3)*(n-2)*(16204*n^4 - 18132*n^3 - 11647*n^2 + 10275*n - 1740)*a(n-5). - Vaclav Kotesovec, Mar 22 2014
a(n) ~ sqrt((s-1)*s^3/(6-8*s+3*s^2)) / (2*sqrt(Pi)*n^(3/2)*r^n), where r = 0.4577644245749322..., s = 1.232809919151165... are roots of the system of equations 1 + r*s^2 + r^4*s^4 = (1+r)*s, 1+r = 2*r*s + 4*r^4*s^3. - Vaclav Kotesovec, Mar 22 2014
a(n) = (1/(n+1)) * Sum_{i=0..floor(n/4)} C(n+1,i) * C(n-3*i-1,n-4*i). - Vladimir Kruchinin, Apr 01 2019

Modified definition to obtain offset 0 for combinatorial interpretation, Joerg Arndt, Apr 16 2013

A236339 Association types in 2-dimensional algebra.

Original entry on oeis.org

1, 2, 8, 39, 212, 1232, 7492, 47082, 303336, 1992826, 13299624, 89912992, 614474252, 4238138216, 29463047072, 206234876287, 1452319244772, 10281935334928, 73138728191724, 522475643860940, 3746698673538480, 26961197787989220, 194626504416928080

Offset: 1

Murray R. Bremner, Jan 22 2014

A kind of two-dimensional Catalan number.
This sequence has two equivalent descriptions:
(1) This sequence enumerates the number of decompositions of the unit square into n rectangles obtained by the following algorithm.
(a) Start with the unit square.
(b) Perform the following operation n-1 times:
    Choose a rectangle in the current decomposition.
    Bisect this rectangle into two rectangles horizontally or vertically.
Different sequences of bisections can produce the same decomposition.
(2) Consider the universal algebra with two nonassociative binary products *1 and *2 related only by the interchange law from 2-category theory:
( a *1 b ) *2 ( c *1 d ) = ( a *2 c ) *1 ( b *2 d )
This sequence enumerates the number of distinct monomials of degree n.

J.-L. Loday and B. Vallette, Algebraic Operads, Grundlehren 346, Springer, 2012, section 13.10.4, page 544 (for the interchange law)
S. Mac Lane, Categories for the Working Mathematician, second edition, Springer, 1978, equation (5), page 43 (also for the interchange law).

Alois P. Heinz, Table of n, a(n) for n = 1..400
Yu Hin (Gary) Au, Fatemeh Bagherzadeh, Murray R. Bremner, Enumeration and Asymptotic Formulas for Rectangular Partitions of the Hypercube, arXiv:1903.00813 [math.CO], Mar 03 2019.
Murray R. Bremner, Diagrams representing 2-dimensional Catalan numbers for n = 2,3,4,5
Murray Bremner, Sara Madariaga, Permutation of elements in double semigroups, arXiv:1405.2889 [math.RA], 2014-2015.
Murray Bremner, Sara Madariaga, Permutation of elements in double semigroups, Semigroup Forum 92 (2016), no. 2, 335--360. MR3472020.
Elżbieta Liszewska, Wojciech Młotkowski, Some relatives of the Catalan sequence, arXiv:1907.10725 [math.CO], 2019.

Cf. A000108 (Catalan numbers), A236342.
Cf. A001002, A046736.
Column k=2 of A237018.

c := table():
c[1] := 1:
printf( "\n" ):
for n from 2 to 50 do
c[n] := 0:
for ij in combinat[composition](n,2) do
    c[n] := c[n] + 2*c[ij[1]]*c[ij[2]]
od:
for ijkl in combinat[composition](n,4) do
    c[n] := c[n] - c[ijkl[1]]*c[ijkl[2]]*c[ijkl[3]]*c[ijkl[4]]
od:
   printf( "%2d      %d \n", n, c[n] )
od:
# second Maple program:
a:= proc(n) option remember; `if`(n<3, n, (
      8*(2*n-5)*(148*n-243)*(4*n-13)*(4*n-11)*a(n-3)
      +16*(n-2)*(4736*n^3-31456*n^2+68444*n-48609)*a(n-2)
      -32*(n-1)*(n-2)*(148*n^2-613*n+594)*a(n-1)) /
      (5*n*(n-1)*(n-2)*(148*n-391)))
    end:
seq(a(n), n=0..25);  # Alois P. Heinz, Jan 22 2014

max = 30; c[1] = 1; c[2] = 2; g = Sum[c[k]*x^k, {k, 1, max}]; eq = Take[Thread[CoefficientList[g^4 - 2*g^2 + g - x, x] == 0], max+1]; sol = Solve[eq] // First; Array[c, max] /. sol (* Jean-François Alcover, Jan 27 2014 *)
Rest[CoefficientList[InverseSeries[Series[x^4-2*x^2+x, {x, 0, 20}], x],x]] (* Vaclav Kotesovec, Feb 16 2014 *)

Recurrence relation:
C(1) = 1,
C(n) = 2 Sum_{i,j} C(i)C(j) - Sum_{i,j,k,l} C(i)C(j)C(k)C(l).
The first sum is over all 2-compositions of n into positive integers (i+j=n), and the second sum is over all 4-compositions of n into positive integers (i+j+k+l=n).
Generating function G(x) = Sum_{n>=1} C(n) x^n satisfies a quartic polynomial equation: G(x)^4 - 2*G(x)^2 + G(x) - x = 0.
a(n) ~ (1/r)^(n-1/2) / (2 * sqrt(2*Pi*(1-3*s^2)) * n^(3/2)), where s = 0.2695944364054445582... is the root of the equation 4*s*(1-s^2) = 1, and r = s*(1-2*s+s^3) = 0.1295146671633141285... - Vaclav Kotesovec, Feb 16 2014
From Seiichi Manyama, Jan 10 2023: (Start)
G.f.: Series_Reversion( x * (1-x) * (1-x-x^2) ).
a(n+1) = (1/(n+1)) * Sum_{k=0..floor(n/2)} binomial(n+k,k) * binomial(3*n-k+1,n-2*k). (End)

a(17)-a(23) from Alois P. Heinz, Jan 22 2014

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

Original entry on oeis.org

1, 1, 2, 6, 21, 78, 301, 1198, 4888, 20340, 85986, 368239, 1594183, 6965380, 30675399, 136026759, 606848034, 2721783023, 12265670909, 55511013680, 252193872912, 1149742659556, 5258257323304, 24117924005616, 110915268468358, 511334146237807, 2362650323603539

Offset: 0

Len Smiley, Apr 08 2000

nonn

Number of tree interval posets of permutations with n+1 minimal elements. - Mathilde Bouvel, Oct 21 2021

			a(3) = 6 because the pentagon allows null placement and five ways to place two diagonals.

Eli Bagno, Estrella Eisenberg, Shulamit Reches, and Moriah Sigron, Blockwise simple permutations, arXiv:2303.13115 [math.CO], 2023.
Eli Bagno, Estrella Eisenberg, Shulamit Reches, and Moriah Sigron, Geometric view of interval poset permutations, arXiv:2411.13193 [math.CO], 2024. See pp. 3, 8.
Daniel Birmajer, Juan B. Gil, and Michael D. Weiner, Colored partitions of a convex polygon by noncrossing diagonals, arXiv preprint arXiv:1503.05242 [math.CO], 2015
Mathilde Bouvel, Lapo Cioni, and Benjamin Izart, The interval posets of permutations seen from the decomposition tree perspective, arXiv:2110.10000 [math.CO], 2021.
Len Smiley, Generalization and some variants, see Quad-free.
Bridget Eileen Tenner, Interval posets for permutations, arXiv:2007.06142 [math.CO], 2020-2021.

Cf. A046736, A049124, A003168, A054514, A348479 (free interv. posets not necess. trees).

read("transforms") :
taylor( (1-2*y+y^2-y^3)/(1-y),y=0,50) ;
gfun[seriestolist](%) ;
REVERT(%) ; # R. J. Mathar, Nov 04 2021

InverseSeries[Series[(y-2*y^2+y^3-y^4)/(1-y), {y, 0, 24}], x] (* then A(x)=[y(x)-x]/x *)

my(N=28, x='x+O('x^N)); Vec(serreverse((x-2*x^2+x^3-x^4)/(1-x))) \\ Hugo Pfoertner, Jan 26 2024

REVERT transform of (1-2*x+x^2-x^3)/(1-x) [Smiley].
a(n-1) = (1/n) * [binomial(2n-2,n-1) + Sum_{i=1..(n-3)} Sum_{k=1..Min(i,(n-i-1)/2)} binomial(n+i-1,i)*binomial(i,k)*binomial(n-i-k-2,k-1) ] if n>1. Proved in M. Bouvel, L. Cioni, B. Izart (Theorem 21) with offset 1. - Mathilde Bouvel, Oct 21 2021
G.f. A(z) = Sum_{n>=0} a(n)*z^n satisfies A(z) = 1 + z*A^2 + z^3*A^4/(1-z*A). Proved in M. Bouvel, L. Cioni, B. Izart (Equation (6) page 17 with offset 1). - Mathilde Bouvel, Oct 21 2021
Asymptotic behavior of a(n-1) is c*n^(-3/2)*r^n with c approximately 0.0792 and r approximately 4.8920. Proved in M. Bouvel, L. Cioni, B. Izart (Theorem 22). - Mathilde Bouvel, Oct 21 2021
D-finite with recurrence 23 *n *(n-1) *(12869043*n-33144451) *(n+1) *a(n) -n *(n-1) *(1989552043*n^2-6117767430*n+2643232213) * a(n-1) +(n-1) *(3359030609*n^3-15361701516*n^2+20123332181*n-6949961920) *a(n-2) +(-3560897749*n^4+25182507306*n^3-62054513365*n^2 +60006265908*n-16495478980) *a(n-3) +3*(146027817*n^4-1247820696*n^3+3378236999*n^2-2363753280*n-1468123920)*a(n-4) -3*(335627*n+695280) *(3*n-13) *(3*n-11) *(n-4) *a(n-5)=0. - R. J. Mathar, Oct 28 2021
a(n) = (1/(n+1)) * Sum_{k=0..floor(n/3)} binomial(n+k,k) * binomial(2*n-k,n-3*k). - Seiichi Manyama, Jan 26 2024

a(0) = 1 prefixed by R. J. Mathar, Nov 04 2021

A143363 Number of ordered trees with n edges and having no protected vertices. A protected vertex in an ordered tree is a vertex at least 2 edges away from its leaf descendants.

Original entry on oeis.org

1, 1, 1, 3, 6, 17, 43, 123, 343, 1004, 2938, 8791, 26456, 80597, 247091, 763507, 2372334, 7413119, 23271657, 73376140, 232238350, 737638868, 2350318688, 7510620143, 24064672921, 77294975952, 248832007318, 802737926643

Offset: 0

Emeric Deutsch, Aug 20 2008

nonn

The "no protected vertices" condition can be rephrased as "every non-leaf vertex has at least one leaf child". But a(n) is also the number of ordered trees with n edges in which every non-leaf vertex has at most one leaf child. - David Callan, Aug 22 2014
Also the number of locally non-intersecting ordered rooted trees with n edges, meaning every non-leaf subtree has empty intersection. The unordered version is A007562. - Gus Wiseman, Nov 19 2022
a(n) is the number of parking functions of size n-1 avoiding the patterns 123, 132, and 213 . - Lara Pudwell, Apr 10 2023
For n>0, a(n) is the number of ways to place non-intersecting diagonals in convex n+3-gon so as to create no triangles such that none of the dividing diagonals passes through a chosen vertex. (empirical observation) - Muhammed Sefa Saydam, Feb 14 2025 and Aug 05 2025

			From _Gus Wiseman_, Nov 19 2022: (Start)
The a(0) = 1 through a(4) = 6 trees with at least one leaf directly under any non-leaf node:
  o  (o)  (oo)  (ooo)   (oooo)
                ((o)o)  ((o)oo)
                (o(o))  ((oo)o)
                        (o(o)o)
                        (o(oo))
                        (oo(o))
The a(0) = 1 through a(4) = 6 trees with at most one leaf directly under any node:
  o  (o)  ((o))  ((o)o)   (((o))o)
                 (o(o))   (((o)o))
                 (((o)))  ((o)(o))
                          ((o(o)))
                          (o((o)))
                          ((((o))))
(End)

Ayomikun Adeniran and Lara Pudwell, Pattern avoidance in parking functions, Enumer. Comb. Appl. 3:3 (2023), Article S2R17.
Gi-Sang Cheon and Louis W. Shapiro, Protected points in ordered trees, Appl. Math. Letters, 21, 2008, 516-520.
Murray Tannock, Equivalence classes of mesh patterns with a dominating pattern, MSc Thesis, Reykjavik Univ., May 2016.

Cf. A143362.
For exactly one leaf directly under any node we have A006013.
The unordered version is A007562, ranked by A316470.
Allowing lone children gives A319378.
A000108 counts ordered rooted trees, unordered A000081.
A358453 counts transitive ordered trees, unordered A290689.
A358460 counts locally disjoint ordered trees, unordered A316473.
Cf. A318185, A324756, A324767, A324840, A324844.

p:=z^2*G^3-2*z*G^2-2*z^2*G^2+3*z*G+G+z^2*G-1-2*z=0: G:=RootOf(p,G): Gser:= series(G,z=0,33): seq(coeff(Gser,z,n),n=0..28);

a[n_Integer] := a[n] = Round[SeriesCoefficient[2 (x + 1 - Sqrt[x^2 - x + 1] Cos[ArcTan[(3 x Sqrt[12 x^3 - 96 x^2 - 24 x + 15])/(2 x^3 - 30 x^2 - 3 x + 2)]/3])/(3 x), {x, 0, n}]]; Table[a[n], {n, 0, 20}] (* Vladimir Reshetnikov, Apr 10 2022 *)
RecurrenceTable[{25 (n + 5) (n + 6) a[n + 5] - 10 (n + 5) (5 n + 21) a[n + 4] - 2 (77 n^2 + 613 n + 1185) a[n + 3] + 2 (50 n^2 + 253 n + 312) a[n + 2] + 4 (2 n + 1) (7 n + 9) a[n + 1] - 4 n (2 n + 1) a[n] == 0, a[0] == 1, a[1] == 1, a[2] == 1, a[3] == 3, a[4] == 6}, a[n], {n, 0, 27}] (* Vladimir Reshetnikov, Apr 11 2022 *)
ait[n_]:=ait[n]=If[n==1,{{}},Join@@Table[Select[Tuples[ait/@c],MemberQ[#,{}]&],{c,Join@@Permutations/@IntegerPartitions[n-1]}]];
Table[Length[ait[n]],{n,15}] (* Gus Wiseman, Nov 19 2022 *)

a(n) = A143362(n,0) for n>=1.
G.f.: G=G(z) satisfies z^2*G^3-2z(1+z)G^2+(1+3z+z^2)G-(1+2z)=0.
G.f.: (x+1-sqrt(x^2-x+1)*cos(arctan((3*x*sqrt(12*x^3-96*x^2-24*x+15))/(2*x^3-30*x^2-3*x+2))/3))*2/(3*x). - Vladimir Reshetnikov, Apr 10 2022
Recurrence: 25*(n+5)*(n+6)*a(n+5) - 10*(n+5)*(5*n+21)*a(n+4) - 2*(77*n^2+613*n+1185)*a(n+3) + 2*(50*n^2+253*n+312)*a(n+2) + 4*(2*n+1)*(7*n+9)*a(n+1) - 4*n*(2*n+1)*a(n) = 0. - Vladimir Reshetnikov, Apr 11 2022
From Muhammed Sefa Saydam, Jul 12 2025: (Start)
a(n) =  Sum_{k=2..n+2} A046736(k) * A046736(n-k+3) , for n >= 0 and A046736(1) = 1.
a(n) = A049125(n) + Sum_{k=1..n-2} A049125(k) * A046736(n-k+2), for n >= 3.
a(n) = A049125(n) + Sum_{k=1..n-2} a(k) * a(n-k-1), for n >= 3. (End)

A215342 Expansion of series reversion of x(1-x^3sum(k>=1, x^k)).

Original entry on oeis.org

1, 0, 0, 0, 1, 1, 1, 1, 6, 12, 19, 27, 71, 166, 329, 579, 1222, 2756, 5921, 11754, 24179, 52372, 114031, 239726, 502269, 1074961, 2333143, 5017552, 10714567, 23006558, 49861081, 108122488, 233691980, 505329915, 1097463037, 2389325284, 5199960642, 11314793335, 24663217250, 53864633059

Offset: 1

Joerg Arndt, Aug 19 2012

nonn

Dissections (using non-intersecting diagonals) of a convex (n+1)-gon into k-gons where k>=6. [Joerg Arndt, Feb 15 2014]

			Use the Lang and the Abramowitz and Stegun links in A111785. In the A-S list of partitions of the integer n on page 831 null all partitions containing 1, 2, or 3. These correspond to the null coefficients of x^2, x^3, and x^4 in the series to be reverted and to 3-, 4-, and 5-gons not being allowed in the dissections. a(9)=6 corresponds to the A-S partitions (n=8,m=1, partition 1)=8 and (8,2,4)=4^2, and these in turn correspond to one undissected 10-gon + five ways to divide a 10-gon into two 6-gons. a(10)=12 corresponds to (9,1,1)=9 and (9,2,4)=4,5, corresponding to one undissected 11-gon + the eleven ways to divide an 11-gon into a 6-gon and 7-gon. - _Tom Copeland_, Feb 15 2014

Vaclav Kotesovec, Table of n, a(n) for n = 1..250
Alison Schuetz, Gwyneth Whieldon, Polygonal Dissections and Reversions of Series, arXiv:1401.7194 [math.CO]
D. Birmajer, J. B. Gil, M. D. Weiner, Colored partitions of a convex polygon by noncrossing diagonals, arXiv preprint arXiv:1503.05242 [math.CO], 2015.

Cf. A001003 (rev. of x*(1-1*sum(k>=1,x^k)) ), A046736 (rev. of x*(1-x*sum(k>=1,x^k)) ), A054514 (rev. of x*(1-x^2*sum(k>=1,x^k)) ).

Cf. A000108 (rev. of x/(1+1*sum(k>=1,x^k)) ), A005043 (rev. of x/(1+x*sum(k>=1,x^k)) ), A114997 (rev. of x/(1+x^2*sum(k>=1,x^k)) ), A215341 (rev. of x/(1+x^3*sum(k>=1,x^k)) ).

nmax=20; aa=ConstantArray[0,nmax]; aa[[1]]=0; Do[AGF=1+Sum[aa[[n]]*x^n,{n,1,j-1}]+koef*x^j; sol=Solve[Coefficient[1-(1+x)*AGF+x*AGF^2 +x^4*AGF^5,x,j]==0,koef][[1]]; aa[[j]]=koef/.sol[[1]],{j,2,nmax}]; Flatten[{1,aa}] (* Vaclav Kotesovec, Mar 23 2014 *)

N=66; Vec(serreverse(x*(1-x^3*sum(k=1,N,x^k))+O(x^N)))

Recurrence: 283*(n-3)*(n-2)*(n-1)*n*(14438110231*n^6 - 346214993274*n^5 + 3438949212625*n^4 - 18105364836570*n^3 + 53265099505324*n^2 - 82987438028496*n + 53465930027280)*a(n) = (n-3)*(n-2)*(n-1)*(5399853226394*n^7 - 137584187324067*n^6 + 1483504918415939*n^5 - 8763694066910355*n^4 + 30585682233578711*n^3 - 62946796681030518*n^2 + 70573456271906136*n - 33158656683118080)*a(n-1) - (n-3)*(n-2)*(534210078547*n^8 - 14946795065326*n^7 + 180235890644998*n^6 - 1221993860476624*n^5 + 5087726442447403*n^4 - 13295664719568394*n^3 + 21246368278875372*n^2 - 18919520411340456*n + 7154560952974080)*a(n-2) - 5*(n-4)*(n-3)*(28876220462*n^8 - 793496758165*n^7 + 9354947999333*n^6 - 61627542806839*n^5 + 247116200695877*n^4 - 613894185501244*n^3 + 913857055091496*n^2 - 732955177968120*n + 234541607788800)*a(n-3) + 5*(9947857949159*n^10 - 357916425755694*n^9 + 5753280746412201*n^8 - 54388490463504720*n^7 + 334719732595671573*n^6 - 1400557913088383070*n^5 + 4032929135663406319*n^4 - 7886242788829977540*n^3 + 10015113186875731788*n^2 - 7452248915385205056*n + 2464721951024954880)*a(n-4) - 8*(n-5)*(2*n - 9)*(4*n - 21)*(4*n - 19)*(14438110231*n^6 - 259586331888*n^5 + 1924445899720*n^4 - 7522955714190*n^3 + 16337121992089*n^2 - 18661982982042*n + 8745398997120)*a(n-5). - Vaclav Kotesovec, Mar 22 2014
a(n) ~ s*sqrt((3*r*s+r-4)/(5*(3*r*s-2*r-2))) / (2*sqrt(Pi) * n^(3/2) * r^(n-1)), where s = 1.1954869989505368389... is the root of the equation 64 - 897*s + 2460*s^2 - 2787*s^3 + 1442*s^4 - 283*s^5 = 0, and r = (4*s-5)/(s*(3*s-4)) = 0.441061092405258554919... - Vaclav Kotesovec, Mar 23 2014
G.f. A(x) for offset 0 satisfies 1-(1+x)*A(x) + x*A(x)^2 + x^4*A(x)^5 = 0. - Vaclav Kotesovec, Mar 23 2014

A052524 Number of ordered labeled rooted trees on n nodes with non-leaf nodes having more than two children.

Original entry on oeis.org

0, 1, 0, 6, 24, 480, 5760, 126000, 2580480, 69310080, 1959552000, 64505548800, 2292022656000, 90366525849600, 3843167789260800, 177248722210560000, 8758468152225792000, 463225965106544640000, 26058454876652470272000

Offset: 0

encyclopedia(AT)pommard.inria.fr, Jan 25 2000

The correspondence between rooted trees and dissection of (n+1)-gon as in A046736 is just like the case for Catalan numbers and binary trees.

G. C. Greubel, Table of n, a(n) for n = 0..370
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 94

Cf. A046736.

spec := [S,{S=Union(Z,Sequence(S,card >= 3))},labeled]: seq(combstruct[count](spec,size=n), n=0..20);

CoefficientList[InverseSeries[Series[1 + 1/(x-1) + 2*x + x^2, {x,0,20}], x], x] * Range[0,20]! (* Vaclav Kotesovec, Jan 08 2014 *)

a(n)=if(n<1,0,n!*polcoeff(serreverse((x-x^2-x^3)/(1-x) + O(x^(n+2))), n))

a(n) = n! * A046736(n+1) for n>0.
E.g.f.: A(x)=sum_{n>0} a(n)*x^n/n! satisfies A(x)-A(x)^2-A(x)^3 = x*(1-A(x)).
Recurrence: a(0)=0, a(1)=1, a(2)=0, a(3)=6, 8*n*(n+1)*(n+2)*(1-2*n)*a(n) +6*(13*n+10)*(2*n+1)*(n+2)*a(n+1) -24*(2*n+5)*(4*n+7)*a(n+2) -4*(19*n+40)*a(n+3) +35*a(n+4) = 0
a(n) ~ n^(n-1) * sqrt(r*(1-s)/(2+6*s)) / (exp(n) * r^n), where r = 0.2933671276754004454... is the root of the equation 5-8*r-32*r^2+4*r^3 = 0 and s = 0.40303171676268477587... is the root of the equation 1-2*s-2*s^2+2*s^3 = 0. - Vaclav Kotesovec, Jan 08 2014

A222763 Number of n X 2 0..1 arrays with exactly floor(nX2/2) elements unequal to at least one horizontal or antidiagonal neighbor, with new values introduced in row major 0..1 order.

Original entry on oeis.org

1, 0, 3, 4, 20, 48, 175, 512, 1719, 5400, 17776, 57420, 188656, 617176, 2033175, 6697744, 22139780, 73262232, 242931321, 806516560, 2681475048, 8925158440, 29740390672, 99196158144, 331163178475, 1106489052968, 3699881730900, 12380449027324, 41454579098852

Offset: 0

R. H. Hardin, Mar 05 2013

nonn

From Gus Wiseman, Oct 05 2022: (Start)
Conjecture: Also the number of integer compositions of 2n + 1 with the same length as reverse-alternating sum. Here, the reverse-alternating sum of a sequence (y_1,...,y_k) is Sum_i (-1)^i y_i. For example, the a(4) = 20 compositions are:
  (135)    (234)    (333)    (432)    (531)
  (11115)  (21114)  (31113)  (41112)  (51111)
  (11214)  (21213)  (31212)  (41211)
  (11313)  (21312)  (31311)
  (11412)  (21411)
  (11511)
This is the odd-indexed version of A357182, and the corresponding unordered count (partitions) is A357488.
(End)

			All solutions for n=3
..0..1....0..0....0..0....0..0
..0..0....0..0....0..1....1..0
..0..0....1..0....0..0....0..0

Alois P. Heinz, Table of n, a(n) for n = 0..1881 (terms n = 1..210 from R. H. Hardin)

Column k = 2 of A222769.

Cf. A046736, A105422.

a:= proc(n) option remember; `if`(n<3, [1, 0, 3][n+1],
      (4*(n-1)*(74*n^2-153*n+73)*a(n-1) +8*(2*n-3)*
      (74*n^2-153*n+70)*a(n-2) -2*(37*n-21)*(2*n-5)*
      (n-1)*a(n-3))/(5*(37*n-58)*n*(n-1)))
    end:
seq(a(n), n=0..30);  # Alois P. Heinz, Sep 24 2024

a(n) = A105422(2n,n). - Alois P. Heinz, Sep 24 2024

a(n) = (n+1)*A046736(n+2). - Mark van Hoeij, Nov 29 2024

a(0)=1 prepended by Alois P. Heinz, Sep 24 2024

A365690 G.f. satisfies A(x) = 1 + x^2A(x)^4 / (1 - xA(x)).

Original entry on oeis.org

1, 0, 1, 1, 5, 10, 38, 101, 353, 1070, 3659, 11843, 40505, 135873, 468104, 1604375, 5576315, 19386656, 67950717, 238676813, 842797959, 2983745508, 10603445402, 37777263153, 134985354179, 483438728094, 1735527037388, 6243193190117, 22503637842423

Offset: 0

Seiichi Manyama, Sep 16 2023

nonn

Cf. A004148, A005043, A025246, A046736, A365691.

Cf. A365692.

a(n) = sum(k=0, n\2, binomial(n-k-1, n-2*k)*binomial(n+2*k+1, k)/(n+2*k+1));

a(n) = Sum_{k=0..floor(n/2)} binomial(n-k-1,n-2*k) * binomial(n+2*k+1,k) / (n+2*k+1).

A370616 Coefficient of x^n in the expansion of ( (1-x) / (1-x-x^2) )^n.

Original entry on oeis.org

1, 0, 2, 3, 14, 35, 125, 371, 1238, 3909, 12847, 41580, 136577, 447187, 1473341, 4855703, 16053830, 53138243, 176233967, 585202261, 1945964079, 6478043120, 21588979876, 72016891508, 240452892569, 803489258285, 2686964354375, 8991840800136, 30110638705889

Offset: 0

Seiichi Manyama, Apr 30 2024

nonn

Cf. A046736, A213684, A104507, A246437, A386548.

Table[Sum[Binomial[-1 - k + n, -2*k + n] Binomial[-1 + k + n, k], {k, 0, n/2}], {n, 0, 30}] (* Vaclav Kotesovec, Jul 30 2025 *)

a(n, s=2, t=1, u=1) = sum(k=0, n\s, binomial(t*n+k-1, k)*binomial((t-u+1)*n-(s-1)*k-1, n-s*k));

a(n) = Sum_{k=0..floor(n/2)} binomial(n+k-1,k) * binomial(n-k-1,n-2*k).
The g.f. exp( Sum_{k>=1} a(k) * x^k/k ) has integer coefficients and equals (1/x) * Series_Reversion( x * (1-x-x^2) / (1-x) ).
From Peter Bala, 26 Jul 2025: (Start)
a(n) = n * hypergeom([1 + n, 1 - n/2, 3/2 - n/2], [2, 2 - n], -4) for n >= 3.
P-recursive: 5*n*(74*n^3-493*n^2+1075*n-766)*(n-1)*a(n) = 2*(n-1)*(296*n^4-2120*n^3+5393*n^2-5716*n+2100)*a(n-1) + 2*(1184*n^5-10256*n^4+34088*n^3-53995*n^2+40397*n-11250)*a(n-2) - 2*(n-3)*(2*n-5)*(74*n^3-271*n^2+311*n-110)*a(n-3) with a(0) = 1, a(1) = 0 and a(2) = 2.
The Gauss congruences a(n*p^k) == a(n*p^(k-1)) (mod p^k) hold for all primes p and all positive integers n and k. (End)
a(n) ~ sqrt(1/12 + sqrt(10/37)*(sin(arcsin((13*sqrt(37/10))/40)/3)/3)) * (8*((1 + sqrt(34)*cos(arccos(2461/(1088*sqrt(34)))/3))/15))^n / sqrt(Pi*n). - Vaclav Kotesovec, Jul 30 2025

cp's OEIS Frontend

A054514 Number of ways to place non-crossing diagonals in convex (n+4)-gon so as to create no triangles or quadrilaterals.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A215341 Expansion of series_reversion( x/(1+x^4*sum(k>=0, x^k)) ) / x.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Maxima

PARI

Formula

Extensions

A236339 Association types in 2-dimensional algebra.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A143363 Number of ordered trees with n edges and having no protected vertices. A protected vertex in an ordered tree is a vertex at least 2 edges away from its leaf descendants.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A215342 Expansion of series reversion of x*(1-x^3*sum(k>=1, x^k)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A052524 Number of ordered labeled rooted trees on n nodes with non-leaf nodes having more than two children.

Views

Author

A215342 Expansion of series reversion of x(1-x^3sum(k>=1, x^k)).

A365690 G.f. satisfies A(x) = 1 + x^2A(x)^4 / (1 - xA(x)).