A213684 -id:A213684 - cp's OEIS frontend

A001002 Number of dissections of a convex (n+2)-gon into triangles and quadrilaterals by nonintersecting diagonals.

1, 1, 3, 10, 38, 154, 654, 2871, 12925, 59345, 276835, 1308320, 6250832, 30142360, 146510216, 717061938, 3530808798, 17478955570, 86941210950, 434299921440, 2177832612120, 10959042823020, 55322023332420, 280080119609550, 1421744205767418, 7234759677699954

Offset: 0

N. J. A. Sloane

a(n+1) is number of (2,3)-rooted trees on n nodes.
This sequence appears to be a transform of the Fibonacci numbers A000045. This sequence is to the Fibonacci numbers as the Catalan numbers A000108 is to the all ones sequence. See link to Mathematica program. - Mats Granvik, Dec 30 2017
a(n) is the number of parking functions of size n avoiding the patterns 231, 312, and 321. - Lara Pudwell, Apr 10 2023

			a(3)=10 because a convex pentagon can be dissected in 5 ways into triangles (draw 2 diagonals from any of the 5 vertices) and in 5 ways into a triangle and a quadrilateral (draw any of the 5 diagonals).

F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Cambridge, 1998, p. 211 (3.2.73-74)
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Alois P. Heinz, Table of n, a(n) for n = 0..1372 (first 101 terms from T. D. Noe)
Ayomikun Adeniran and Lara Pudwell, Pattern avoidance in parking functions, Enumer. Comb. Appl. 3:3 (2023), Article S2R17.
Paul Barry, On the Central Coefficients of Bell Matrices, J. Int. Seq. 14 (2011) # 11.4.3, example 7.
D. Birmajer, J. B. Gil, and M. D. Weiner, Colored partitions of a convex polygon by noncrossing diagonals, arXiv preprint arXiv:1503.05242 [math.CO], 2015.
I. M. H. Etherington, Non-associate powers and a functional equation, Math. Gaz. 21 (1937), 36-39; addendum 21 (1937), 153.
I. M. H. Etherington, On non-associative combinations, Proc. Royal Soc. Edinburgh, 59 (Part 2, 1938-39), 153-162.
I. M. H. Etherington, Some problems of non-associative combinations, Edinburgh Math. Notes, 32 (1940), 1-6.
I. M. H. Etherington, Some problems of non-associative combinations (I), Edinburgh Math. Notes, 32 (1940), pp. i-vi. [Annotated scanned copy].
A. Erdelyi and I. M. H. Etherington, Some problems of non-associative combinations (II), Edinburgh Math. Notes, 32 (1940), pp. vii-xiv.
Mats Granvik, Mathematica program to compute the sequence as a transform of the Fibonacci numbers.
Nancy S. S. Gu, Nelson Y. Li, and Toufik Mansour, 2-Binary trees: bijections and related issues, Discr. Math., 308 (2008), 1209-1221.
Aoife Hennessy, A Study of Riordan Arrays with Applications to Continued Fractions, Orthogonal Polynomials and Lattice Paths, Ph. D. Thesis, Waterford Institute of Technology, Oct. 2011.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 395
Elżbieta Liszewska and Wojciech Młotkowski, Some relatives of the Catalan sequence, arXiv:1907.10725 [math.CO], 2019.
T. Motzkin, The hypersurface cross ratio, Bull. Amer. Math. Soc., 51 (1945), 976-984.
T. S. Motzkin, Relations between hypersurface cross ratios and a combinatorial formula for partitions of a polygon, for permanent preponderance and for non-associative products, Bull. Amer. Math. Soc., 54 (1948), 352-360.
Thomas M. Richardson, The three 'R's and Dual Riordan Arrays, arXiv:1609.01193 [math.CO], 2016.
A. Schuetz and G. Whieldon, Polygonal Dissections and Reversions of Series, arXiv preprint arXiv:1401.7194 [math.CO], 2014.
Index entries for reversions of series

n*a(n) = A038112(n-1), n > 0.

Cf. A104978, A181997, A181998, A209441, A209442, A213684 (log).

List([0..25], n->Sum([0..Int(n/2)],k->Binomial(2*n-k,n+k)*Binomial(n+k,k)/(n+1))); # Muniru A Asiru, Mar 30 2018

a:= proc(n) option remember; `if`(n<2, 1, (n*(22*n-11)*
      a(n-1) + (9*n-6)*(3*n-4)*a(n-2))/(5*n*(n+1)))
    end:
seq(a(n), n=0..25);  # Alois P. Heinz, Jan 21 2021

Rest[CoefficientList[InverseSeries[Series[y - y^2 - y^3, {y, 0, 30}], x], x]]
a[n_] := CatalanNumber[n]*Hypergeometric2F1[1/2-n/2, -n/2, -2n, -4]; Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Jan 20 2015, after Peter Luschny *)
a[n_] := a[n] = If[n == 0, 1, Sum[a[i] a[n - 1 - i], {i, 0, n - 1}] + Sum[a[i] a[j] a[n - 2 - i - j], {i, 0, n - 2}, {j, 0, n - 2 - i}]];
Table[a[n], {n, 0, 30}] (* Li Han, Jan 02 2021 *)

T(n,k):=if n<0 or k<0 then 0 else if nVladimir Kruchinin, Oct 03 2014 */

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

a(n)=if(n<0,0,sum(k=0,n\2,(2*n-k)!/k!/(n-2*k)!)/(n+1)!)

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

{Dx(n, F)=local(D=F); for(i=1, n, D=deriv(D)); D}
{a(n)=local(A=1); A=1+(1/x)*sum(m=1, n+1, Dx(m-1, (x^2+x^3 +x^2*O(x^n))^m/m!)); polcoeff(A, n)}  \\ Paul D. Hanna, Jun 22 2012

{Dx(n, F)=local(D=F); for(i=1, n, D=deriv(D)); D}
{a(n)=local(A=1); A=exp(sum(m=1, n+1, Dx(m-1, (x^2+x^3 +x^2*O(x^n))^m/x/m!)+x*O(x^n))); polcoeff(A, n)}  \\ Paul D. Hanna, Jun 22 2012

A001002 = lambda n: catalan_number(n)*hypergeometric([1/2-n/2, -n/2], [-2*n], -4) if n>0 else 1
[A001002(n).n(100).round() for n in range(24)] # Peter Luschny, Oct 03 2014

G.f. (offset 1) is series reversion of x - x^2 - x^3.
a(n) = (1/(n+1))*Sum_{k=ceiling(n/2)..n} binomial(n+k, k)*binomial(k, n-k). - Len Smiley
D-finite with recurrence 5*n*(n+1) * a(n) = 11*n*(2*n-1) * a(n-1) + 3*(3*n-2)*(3*n-4) * a(n-2). - Len Smiley
G.f.: (4*sin(asin((27*x+11)/16)/3)-1)/(3*x). - Paul Barry, Feb 02 2005
G.f. satisfies: A(x) = 1 + x*A(x)^2 + x^2*A(x)^3. - Paul D. Hanna, Jun 22 2012
Antidiagonal sums of triangle A104978 which has g.f. F(x,y) that satisfies: F = 1 + x*F^2 + x*y*F^3. - Paul D. Hanna, Mar 30 2005
a(n) = Sum_{k=0..floor(n/2)} C(2*n-k, n+k)*C(n+k, k)/(n+1). - Paul D. Hanna, Mar 30 2005
G.f. satisfies: x = Sum_{n>=1} 1/(1+x*A(x))^(2*n) * Product_{k=1..n} (1 - 1/(1+x*A(x))^k). - Paul D. Hanna, Apr 05 2012
G.f.: 1 + (1/x)*Sum_{n>=1} d^(n-1)/dx^(n-1) (x^2+x^3)^n/n!. - Paul D. Hanna, Jun 22 2012
G.f.: exp( Sum_{n>=1} d^(n-1)/dx^(n-1) ((x^2+x^3)^n/x)/n! ). - Paul D. Hanna, Jun 22 2012
Logarithmic derivative yields A213684. - Paul D. Hanna, Jun 22 2012
a(n) ~ 3^(3*n+3/2) / (2 * sqrt(2*Pi) * 5^(n+1/2) * n^(3/2)). - Vaclav Kotesovec, Mar 09 2014
a(n) = Catalan(n)*hypergeom([1/2-n/2, -n/2], [-2*n], -4) for n>0. - Peter Luschny, Oct 03 2014
a(n) = [x^n] 1/(1 - x - x^2)^(n+1)/(n + 1). - Ilya Gutkovskiy, Mar 29 2018
a(n) = -Sum_{i=1..n} A217596(i) * a(n-i) for n>0. - Muhammed Sefa Saydam, Jan 27 2025
a(n) = -Sum_{i=1..n+2} A217596(i) * A217596(n-i+2) for n >= 0. - Muhammed Sefa Saydam, Jul 24 2025

Revised by Emeric Deutsch and Len Smiley, Jun 05 2005

A155161 A Fibonacci convolution triangle: Riordan array (1, x/(1 - x - x^2)). Triangle T(n,k), 0 <= k <= n, read by rows.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 2, 2, 1, 0, 3, 5, 3, 1, 0, 5, 10, 9, 4, 1, 0, 8, 20, 22, 14, 5, 1, 0, 13, 38, 51, 40, 20, 6, 1, 0, 21, 71, 111, 105, 65, 27, 7, 1, 0, 34, 130, 233, 256, 190, 98, 35, 8, 1, 0, 55, 235, 474, 594, 511, 315, 140, 44, 9, 1, 0, 89, 420, 942, 1324, 1295, 924, 490, 192, 54, 10, 1

Offset: 0

Philippe Deléham, Jan 21 2009

			Triangle begins:
[0] 1;
[1] 0,  1;
[2] 0,  1,   1;
[3] 0,  2,   2,   1;
[4] 0,  3,   5,   3,   1;
[5] 0,  5,  10,   9,   4,   1;
[6] 0,  8,  20,  22,  14,   5,  1;
[7] 0, 13,  38,  51,  40,  20,  6,  1;
[8] 0, 21,  71, 111, 105,  65, 27,  7, 1;
[9] 0, 34, 130, 233, 256, 190, 98, 35, 8, 1.

Reinhard Zumkeller, Rows n = 0..120 of triangle, flattened
Paul Barry, Riordan arrays, generalized Narayana triangles, and series reversion, Linear Algebra and its Applications, 491 (2016) 343-385.

Row sums are in A215928.
Central terms: T(2*n,n) = A213684(n) for n > 0.
Cf. A000045, A037027, A122542, A059283, A321620.

a155161 n k = a155161_tabl !! n !! k
a155161_row n = a155161_tabl !! n
a155161_tabl = [1] : [0,1] : f [0] [0,1] where
   f us vs = ws : f vs ws where
     ws = zipWith (+) (us ++ [0,0]) $ zipWith (+) ([0] ++ vs) (vs ++ [0])
-- Reinhard Zumkeller, Apr 17 2013

T := (n, k) -> binomial(n-1, k-1)*hypergeom([-(n-k)/2, -(n-k-1)/2], [1-n], -4):
seq(seq(simplify(T(n, k)), k = 0..n), n = 0..11); # Peter Luschny, May 23 2021
# Uses function PMatrix from A357368.
PMatrix(10, n -> combinat:-fibonacci(n)); # Peter Luschny, Oct 07 2022

CoefficientList[#, y]& /@ CoefficientList[(1-x-x^2)/(1-x-x^2-x*y)+O[x]^12, x] // Flatten (* Jean-François Alcover, Mar 01 2019 *)
(* Generates the triangle without the leading '1' (rows are rearranged). *)
(* Function RiordanSquare defined in A321620. *)
RiordanSquare[x/(1 - x - x^2), 11] // Flatten  (* Peter Luschny, Feb 27 2021 *)

M(n,k):=pochhammer(n,k)/k!;
create_list(sum(M(k,i)*binomial(i,n-i-k),i,0,n-k),n,0,8,k,0,n); /* Emanuele Munarini, Mar 15 2011 */

T(n, k) given by [0,1,1,-1,0,0,0,...] DELTA [1,0,0,0,...] where DELTA is the operator defined in A084938.
a(n,k) = Sum_{i=0..n-k} M(k,i)*binomial(i,n-i-k), where M(n,k) = n(n+1)(n+2)...(n+k-1)/k!. - Emanuele Munarini, Mar 15 2011
Recurrence: a(n+2,k+1) = a(n+1,k+1) + a(n+1,k) + a(n,k+1). - Emanuele Munarini, Mar 15 2011
G.f.: (1-x-x^2)/(1-x-x^2-x*y). - Philippe Deléham, Feb 08 2012
Sum_{k=0..n} T(n,k)*x^k = A000007(n), A000129(n) (n > 0), A052991(n), A155179(n), A155181(n), A155195(n), A155196(n), A155197(n), A155198(n), A155199(n) for x = 0,1,2,3,4,5,6,7,8,9 respectively. - Philippe Deléham, Feb 08 2012
T(n, k) = binomial(n-1, k-1)*hypergeom([-(n-k)/2, -(n-k-1)/2], [1-n], -4). - Peter Luschny, May 23 2021

A350383 a(n) = [x^n] 1/(1 + x + x^2)^n.

Original entry on oeis.org

1, -1, 1, 2, -15, 49, -98, 48, 561, -2860, 8151, -12948, -9282, 149226, -594320, 1428952, -1448655, -5538975, 37450900, -122995950, 239589735, -37528755, -1886983020, 8939152560, -24579514050, 35197176924, 51580335366, -541312482256, 2033695030128, -4624358661240

Offset: 0

Seiichi Manyama, Dec 29 2021

Seiichi Manyama, Table of n, a(n) for n = 0..1000

Cf. A002426, A027907, A103779, A110556, A165817, A213684, A228960, A350406, A350407, A362087.

a := n -> (-1)^n*hypergeom([-n/3, 1/3 - n/3, 2/3 - n/3, n], [1/3, 2/3, 1], 1): seq(simplify(a(n)), n = 0..30); # Peter Bala, Apr 17 2023

a[n_] := Coefficient[Series[1/(1 + x + x^2)^n, {x, 0, n}], x, n]; Array[a, 30, 0] (* Amiram Eldar, Dec 29 2021 *)

a(n) = sum(k=0, n, (-1)^(n-k)*binomial(n-1+k, k)*binomial(n, 3*k));

a(n) = Sum_{k=0..n} (-1)^(n-k) * binomial(n-1+k,k) * binomial(n,3*k).
Recurrence: 3*(n-1)*n*(4*n - 7)*a(n) = -2*(n-1)*(28*n^2 - 63*n + 27)*a(n-1) - 3*(3*n - 5)*(3*n - 4)*(4*n - 3)*a(n-2). - Vaclav Kotesovec, Mar 18 2023
From Peter Bala, Apr 15 2023: (Start)
a(n) = (-1)^n*hypergeom([-n/3, 1/3 - n/3, 2/3 - n/3, n], [1/3, 2/3, 1], 1).
Conjecture: the supercongruence a(n*p^r) == a(n*p^(r-1)) (mod p^(2*r)) holds for positive integers n and r and all primes p >= 5. Cf. A228960.
More generally, let k be a positive integer, m an integer and let f(x) = g(x)/h(x), where g(x) and h(x) are both finite products of cyclotomic polynomials. Then we conjecture that the same supercongruences hold, except for a finite number of primes p depending on f(x), for the sequence {a_(k,m,f)(n): n >= 0} defined by a_(k,m,f)(n) = [x^(k*n)] f(x)^(m*n). (End)
From Peter Bala, Mar 11 2025: (Start)
G.f.: A(x) = 1 + x*d/dx(log(G(x)/x)), where G(x) = x - x^2 + x^3 - 4*x^5 + 14*x^6 - 30*x^7 + ... is the g.f. of A103779.
The following formulas hold for n >= 1:
a(n) = [x^n] T(2*n, (1 - x)/2), where T(n, x) denotes the n-th Chebyshev polynomial of the first kind.
a(n) = Sum_{k = 0..n} (-1)^(n+k) * n/(2*n-k) * binomial(2*n-k, k)*binomial(2*n-2*k, n).
a(n) = (1/2)*(-1)^n*binomial(2*n, n)*hypergeom([-n/2, (-n+1)/2], [-2*n+1], 4). Cf. A213684. (End)

A362078 Square array T(n,k), n >= 0, k >= 0, read by antidiagonals downwards, where T(n,k) = [x^n] 1/(1 - x*(1+x)^k)^n.

Original entry on oeis.org

1, 1, 1, 1, 1, 3, 1, 1, 5, 10, 1, 1, 7, 22, 35, 1, 1, 9, 37, 105, 126, 1, 1, 11, 55, 215, 511, 462, 1, 1, 13, 76, 369, 1271, 2534, 1716, 1, 1, 15, 100, 571, 2526, 7651, 12720, 6435, 1, 1, 17, 127, 825, 4401, 17577, 46614, 64449, 24310, 1, 1, 19, 157, 1135, 7026, 34412, 123810, 286599, 328900, 92378

Offset: 0

Seiichi Manyama, Apr 08 2023

			Square array begins:
    1,   1,    1,    1,    1,    1, ...
    1,   1,    1,    1,    1,    1, ...
    3,   5,    7,    9,   11,   13, ...
   10,  22,   37,   55,   76,  100, ...
   35, 105,  215,  369,  571,  825, ...
  126, 511, 1271, 2526, 4401, 7026, ...

Columns k=0..3 give A088218, A213684, A362087, A362088.
Main diagonal gives A362080.
Cf. A362079.

T(n, k) = sum(j=0, n, binomial(n+j-1, j)*binomial(k*j, n-j));

T(n,k) = Sum_{j=0..n} (-1)^j * binomial(-n,j) * binomial(k*j,n-j) = Sum_{j=0..n} binomial(n+j-1,j) * binomial(k*j,n-j).

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

Original entry on oeis.org

1, 2, 12, 77, 520, 3612, 25557, 183192, 1325808, 9666635, 70897112, 522472392, 3865669717, 28697325048, 213649228560, 1594540806612, 11926354293792, 89372808145692, 670865679851667, 5043360211505000, 37965778448487120, 286151354441445570, 2159143860124095120

Offset: 0

Seiichi Manyama, May 02 2024

nonn

Cf. A213684, A236339, A372458, A372460.

A372233 := proc(n)
    add(binomial(n+k-1,k) * binomial(3*n-k-1,n-2*k),k=0..floor(n/2));
end proc:
seq(A372233(n),n=0..50) ; # R. J. Mathar, May 02 2024

Table[SeriesCoefficient[1/((1-x)*(1-x-x^2))^n, {x, 0, n}], {n, 0, 20}] (* Vaclav Kotesovec, May 04 2024 *)

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(3*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) * (1-x-x^2) ).
D-finite with recurrence +575*n*(n-1)*(n-2)*a(n) +40*(n-1)*(n-2)*(125*n-178)*a(n-1) -16*(n-2)*(3272*n^2-5536*n+75)*a(n-2) +8*(-22112*n^3+169392*n^2-450082*n+415827)*a(n-3) +1344*(96*n^3-1328*n^2+5794*n-8139)*a(n-4) +3072*(4*n-15)*(2*n-9)*(4*n-17)*a(n-5)=0. - R. J. Mathar, May 02 2024
a(n) ~ sqrt((1/8 + cos(arccos(sqrt(37)/8)/3)/sqrt(37))/(Pi*n)) / (-2/3 + sqrt(35/18)*cos(arccos(-4537/(560*sqrt(70)))/3))^n. - Vaclav Kotesovec, May 04 2024

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

A001002 Number of dissections of a convex (n+2)-gon into triangles and quadrilaterals by nonintersecting diagonals.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Maple

Mathematica

Maxima

PARI

PARI

PARI

PARI

PARI

Sage

Formula

Extensions

A155161 A Fibonacci convolution triangle: Riordan array (1, x/(1 - x - x^2)). Triangle T(n,k), 0 <= k <= n, read by rows.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

Maxima

Formula

A350383 a(n) = [x^n] 1/(1 + x + x^2)^n.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A362078 Square array T(n,k), n >= 0, k >= 0, read by antidiagonals downwards, where T(n,k) = [x^n] 1/(1 - x*(1+x)^k)^n.

Views

Author

Keywords

Examples

Crossrefs

Programs

PARI

Formula

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

Views

Author

Keywords

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

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

Views

Author

Keywords

Crossrefs

Programs

Mathematica

PARI

Formula

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

Views

Author

Keywords

Crossrefs