A003168 -id:A003168 - cp's OEIS frontend

A003169 Number of 2-line arrays; or number of P-graphs with 2n edges.

1, 3, 14, 79, 494, 3294, 22952, 165127, 1217270, 9146746, 69799476, 539464358, 4214095612, 33218794236, 263908187100, 2110912146295, 16985386737830, 137394914285538, 1116622717709012, 9113225693455362, 74659999210200292

Offset: 1

N. J. A. Sloane

First column of triangle A100326. - Paul D. Hanna, Nov 16 2004

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Vincenzo Librandi, Table of n, a(n) for n = 1..200
M. Bicknell and V. E. Hoggatt, Jr., Sequences of matrix inverses from Pascal, Catalan and related convolution arrays, Fib. Quart., 14 (1976), 224-232.
L. Carlitz, Enumeration of two-line arrays, Fib. Quart., Vol. 11 Number 2 (1973), 113-130.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 416
R. C. Read, On the enumeration of a class of plane multigraphs, Aequat. Math. 31 (1986) no 1, 47-63.
Jun Yan, Lattice paths enumerations weighted by ascent lengths, arXiv:2501.01152 [math.CO], 2025. See p. 8.
Anssi Yli-Jyrä and Carlos Gómez-Rodríguez, Generic Axiomatization of Families of Noncrossing Graphs in Dependency Parsing, arXiv:1706.03357 [cs.CL], 2017.

Cf. A003168, A100324, A100326, A156894.

a003169 = flip a100326 0  -- Reinhard Zumkeller, Nov 21 2015

a[0]:=0:a[1]:=1:a[2]:=3:for n from 3 to 30 do a[n]:=((324*n^2-708*n+360)*a[n-1] -(371*n^2-1831*n+2250)*a[n-2]+(20*n^2-130*n+210)*a[n-3])/(16*n*(2*n-1)) od:seq(a[n],n=1..25); # Emeric Deutsch, Jan 31 2005

lim = 21; t[0, 0] = 1; t[n_, 0] := t[n, 0] = Sum[(k + 1)*t[n - 1, k], {k, 0, n - 1}]; t[n_, k_] := t[n, k] = Sum[t[j + 1, 0]*t[n - j - 1, k - 1], {j, 0, n - k}]; Table[ t[n, 0], {n, lim}] (* Jean-François Alcover, Sep 20 2011, after Paul D. Hanna's comment *)

{a(n)=if(n==0,0,if(n==1,1,if(n==2,3,( (324*n^2-708*n+360)*a(n-1) -(371*n^2-1831*n+2250)*a(n-2)+(20*n^2-130*n+210)*a(n-3))/(16*n*(2*n-1)) )))} \\ Paul D. Hanna, Nov 16 2004

{a(n)=local(A=x+x*O(x^n));if(n==1,1, for(i=1,n,A=x*(1+A)/(1-A)^2); polcoeff(A,n))}

seq(n)=Vec(serreverse(x*(1 - x)^2/(1 + x) + O(x*x^n))) \\ Andrew Howroyd, Mar 07 2023

For formula see Read reference.
D-finite with recurrence a(n) = ( (324*n^2-708*n+360)*a(n-1) - (371*n^2-1831*n+2250)*a(n-2) + (20*n^2-130*n+210)*a(n-3) )/(16*n*(2*n-1)) for n>2, with a(0)=0, a(1)=1, a(2)=3. - Paul D. Hanna, Nov 16 2004
G.f. satisfies: A(x) = x*(1+A(x))/(1-A(x))^2 where A(0)=0. G.f. satisfies: (1+A(x))/(1-A(x)) = 2*G003168(x)-1, where G003168 is the g.f. of A003168. - Paul D. Hanna, Nov 16 2004
a(n) = (1/n)*Sum_{i=0..n-1} binomial(n,i)*binomial(3*n-i-2,n-i-1). - Vladeta Jovovic, Sep 13 2006
Appears to be (1/n)*Jacobi_P(n-1,1,n-1,3). If so then a(n) = (1/(2*n-1))*Sum_{k = 0..n-1} binomial(n-1,k)*binomial(2*n+k-1,k+1) = (1/n)*Sum_{k = 0..n} binomial(n,k)*binomial(2*n-2,n+k-1)*2^k. [Added Jun 11 2023: these are correct, and can be proved using the WZ algorithm.] - Peter Bala, Aug 01 2012
a(n) ~ sqrt(33/sqrt(17)-7) * ((71+17*sqrt(17))/16)^n / (4*sqrt(2*Pi)*n^(3/2)). - Vaclav Kotesovec, Aug 09 2013
The o.g.f. A(x) = 1 + 3*x + 14*x^2 + ... taken with offset 0, satisfies 1 + x*A'(x)/A(x) = 1 + 3*x + 19*x^2 + 138*x^3 + ..., the o.g.f. for A156894. - Peter Bala, Oct 05 2015
From Peter Bala, Jun 11 2023: (Start)
a(n) = (1/n)*Sum_{k = 0..n-1} binomial(n,k+1)*binomial(2*n+k-1,k) (Carlitz, equation 3.19).
4*n*(17*n - 29)*(2*n - 1)*a(n) = (1207*n^3 - 4473*n^2 + 5258*n - 1920)*a(n-1) - 2*(2*n - 5)*(17*n - 12)*(n - 2)*a(n-2) with a(1) = 1 and a(2) = 3. (End)

More terms from Emeric Deutsch, Jan 31 2005

A049124 Revert transform of (-1 + x + x^2)/((x - 1)*(x + 1)).

Original entry on oeis.org

1, 1, 2, 6, 20, 71, 264, 1015, 4002, 16094, 65758, 272208, 1139182, 4811807, 20487096, 87832558, 378846620, 1642851797, 7158220968, 31323340342, 137595355130, 606533278416, 2682157911032, 11895267124841, 52895679368820, 235792891885786, 1053475824902774

Offset: 0

Olivier Gérard

a(n) is the number of ways to dissect a convex (n+2)-gon with non-crossing diagonals so that no 2m-gons (m > 1) appear. - Len Smiley
Number of even trees (i.e., ordered trees in which all nodes have even outdegree) with n+1 leaves. - Emeric Deutsch, Mar 06 2002
a(n) is the number of permutations on [n-1] in which the last 2 entries of each 321 pattern are adjacent in position. For example, a(5)=20 counts all permutations on [4] except 3241, 4231, 4312, 4321, the first, for instance because the 2 and 1 are not adjacent. - David Callan, Jul 20 2005
a(n) is the number of directed diagonally convex polyominoes with perimeter 2*n (this holds for every n > 1). - Svjetlan Feretic, Jul 11 2016
From Colin Defant, Sep 17 2018: (Start)
Let L(u,v) be the set of integer partitions whose Young diagrams fit inside a u by v rectangle. Given lambda in L(u,v), let E(lambda) be the number of partitions whose Young diagrams fit inside the Young diagram of lambda. Also, for 1 <= i <= v, let x_i(lambda)-1 be the number of parts of lambda of length v+1-i. Let x_{v+1}(lambda) = u+v+1-Sum_{i=1..v} x_i(lambda) so that (x_1(lambda),..., x_{v+1}(lambda)) is a composition of u+v+1 into v+1 parts. Let F(lambda) = Product_{i=1..v+1} Catalan(x_i(lambda)). We have a(n) = Sum_{k=0..n-2} Sum_{lambda in L(n-2k-2)} E(lambda) * F(lambda).
a(n) is the number of permutations of [n-1] that avoid the patterns 2341, 3241, 3412, and 3421.
a(n) is the number of permutations pi of [n-1] such that s(pi) avoids the patterns 231, 312, and 321, where s is West's stack-sorting map. (End)
a(n) is the number of permutations of length n avoiding the partially ordered pattern (POP) {4>1, 1>2} of length 4. That is, number of length n permutations having no subsequences of length 4 in which the fourth element is larger than the first element, which in turn is larger than the second element. - Sergey Kitaev, Dec 09 2020

			a(2)=2 because one diagonal may be placed 2 ways in the quadrilateral (placing none is not allowed).
Generated from Fibonacci polynomials (A011973) and odd self-convolutions of Catalan numbers (A039599):
a(0) = 1*   1 = 1.
a(1) = 1*   1 = 1.
a(2) = 1*   2 + 0*   1/3 = 2.
a(3) = 1*   5 + 1*   3/3 = 6.
a(4) = 1*  14 + 2*   9/3 +  0*  1/5 = 20.
a(5) = 1*  42 + 3*  28/3 +  1*  5/5 = 71.
a(6) = 1* 132 + 4*  90/3 +  3* 20/5 + 0* 1/7 = 264.
a(7) = 1* 429 + 5* 297/3 +  6* 75/5 + 1* 7/7 = 1015.
a(8) = 1*1430 + 6*1001/3 + 10*275/5 + 4*35/7 + 0*1/9 = 4002.
This process is equivalent to the formula:
a(n) = Sum_{k=0..floor((n-1)/2)} C(n-k-1,n-2k-1)*C(2n-2k,n-2k)/(n+1).
The odd self-convolutions of Catalan numbers begin:
A000108^1: {1, 1,  2,  5,  14,  42,  132, 329, 1430, ...}
A000108^3: {1, 3,  9, 28,  90, 297, 1001, ...}
A000108^5: {1, 5, 20, 75, 275, ...}
A000108^7: {1, 7, 35, ...}

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Paul Barry, Riordan arrays, generalized Narayana triangles, and series reversion, Linear Algebra and its Applications, 491 (2016) 343-385.
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.
Colin Defant, Stack-sorting preimages of permutation classes, arXiv:1809.03123 [math.CO], 2018.
Stoyan Dimitrov, On permutation patterns with constrained gap sizes, arXiv:2002.12322 [math.CO], 2020.
S. Feretic and D. Svrtan, Combinatorics of diagonally convex directed polyominoes, Discrete Math. 157 (1996), 147-168.
Alice L. L. Gao, Sergey Kitaev, On partially ordered patterns of length 4 and 5 in permutations, arXiv:1903.08946 [math.CO], 2019.
Alice L. L. Gao, Sergey Kitaev, On partially ordered patterns of length 4 and 5 in permutations, The Electronic Journal of Combinatorics 26(3) (2019), P3.26.
Nancy S. S. Gu, Nelson Y. Li, and Toufik Mansour, 2-Binary trees: bijections and related issues, Discr. Math., 308 (2008), 1209-1221.
Mizera, Sebastian Combinatorics and topology of Kawai-Lewellen-Tye relations J. High Energy Phys. 2017, No. 8, Paper No. 97, 54 p. (2017).
L. Smiley, Even-gon reference
L. Smiley, Variants of Schroeder Dissections, arXiv:math/9907057 [math.CO], 1999.
Index entries for reversions of series

Cf. A000108, A003168, A269228. Row sums of A319120.

Order := 20; solve(series((A-A^2-A^3)/(1-A^2),A)=x,A);

a[n_] := (2^n*(2n-1)!!* HypergeometricPFQ[{1/2-n/2, 1/2-n/2, 1-n/2, -n/2}, {1/2-n, 1-n, -n}, -4])/(n! + n*n!); Table[a[n], {n, 0, 24}] (* Jean-François Alcover, Jul 25 2011, after Paul D. Hanna *)

{a(n)=polcoeff(sum(m=0,n,sum(k=0,n, binomial(k+m-1,k)*binomial(2*k+2*m,m)*x^(2*k+m+1)/(2*k+m+1))),n)}

{a(n)=if(n==0,1,sum(k=0,(n-1)\2,binomial(n-k-1,k)*binomial(2*n-2*k,n))/(n+1))} \\ Paul D. Hanna, Dec 15 2004

G.f. satisfies: A(x) = x + A(x)^2/(1-A(x)^2); by Lagrange Inversion: A(x) = x + Sum_{n>=0} d^n/dx^n (x^2/(1-x^2))^(n+1)/(n+1)!, or: A(x) = Sum_{n>=0} Sum_{k>=n} C(k-1, k-n)*(2*k)!/(2*k-n+1)!*x^(2*k-n+1)/n!. - Paul D. Hanna, Mar 24 2004
a(n) = Sum_{k=0..floor((n-1)/2)} C(n-k-1, k)*C(2*n-2*k, n)/(n+1) for n > 0, with a(0)=1. - Paul D. Hanna, Dec 15 2004
D-finite with recurrence 5*n*(n+1)*(91*n^2 - 367*n + 348)*a(n) = 12*n*(182*n^3 - 825*n^2 + 1053*n - 328)*a(n-1) - 4*(91*n^4 - 549*n^3 + 971*n^2 - 453*n - 108)*a(n-2) + 6*(n-3)*(182*n^3 - 825*n^2 + 1092*n - 384)*a(n-3) - 4*(n-4)*(n-3)*(91*n^2 - 185*n + 72)*a(n-4). - Vaclav Kotesovec, Jul 29 2013
Lim_{n->infinity} a(n)^(1/n) = z, where z = 4.730576939379622... is the root of the equation 4 - 12*z + 4*z^2 - 24*z^3 + 5*z^4 = 0. - Vaclav Kotesovec, Jul 29 2013

More terms from Paul D. Hanna, Dec 15 2004

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

Original entry on oeis.org

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

A114496 a(n) = Sum of binomial(n,k)*binomial(2n+k,k) over all k.

Original entry on oeis.org

1, 4, 26, 190, 1462, 11584, 93536, 765314, 6323270, 52638760, 440815036, 3709445084, 31340292076, 265683004240, 2258793820988, 19251776923210, 164440378882630, 1407266585304760, 12063701803046300, 103571977632247076

Offset: 0

Eric Rowland, Dec 01 2005

Modification of A001850 inspired by the Apéry numbers A005259.
From Paul Barry, Feb 17 2009: (Start)
Central coefficient of (1 + 4x + 5x^2 + 2x^3)^n. The coefficients are the 4th row of A029635.
The third row of A029635 corresponds to the central Delannoy numbers A001850. (End)

G. C. Greubel, Table of n, a(n) for n = 0..1000
P. Barry, A Note on a Family of Generalized Pascal Matrices Defined by Riordan Arrays, Journal of Integer Sequences, 16 (2013), #13.5.4.

Cf. A114497, A114498, A003168, A156894.

Cf. A156886. - Paul Barry, Feb 17 2009

Table[Sum[Binomial[n, k]*Binomial[2n+k, k], {k, 0, n}], {n,0,25}]

a(n) = sum(k=0, n, 2^(n-k)*binomial(2*n,k)*binomial(n,k));
vector(50, n, a(n-1)) \\ Altug Alkan, Oct 05 2015

a(n) = Sum_{k=0..n} (binomial(n,k)*binomial(2n+k,k)).
Recurrence: 20*n*(2*n - 1)*a(n) = (371*n^2 - 411*n + 120)*a(n-1) -2*(81*n^2 - 299*n + 278)*a(n-2) + 4*(n-2)*(2*n-5)*a(n-3). - Vaclav Kotesovec, Oct 19 2012
a(n) ~ sqrt(1734 + 442*sqrt(17))*((71 + 17*sqrt(17))/16)^n/(68*sqrt(Pi*n)). - Vaclav Kotesovec, Oct 19 2012
From Peter Bala, Oct 05 2015: (Start)
a(n) = Sum_{i = 0..n} 2^(n-i)*binomial(2*n,i)*binomial(n,i).
4*n*(2*n - 1)*(17*n - 23)*a(n) = (1207*n^3 - 2840*n^2 + 1897*n - 360)*a(n-1) - 2*(n - 1)*(17*n - 6)*(2*n - 3)*a(n-2) with a(0) = 1 and a(1) = 4.
1 + x*exp( Sum_{n >= 1} a(n)*x^n/n ) = 1 + x + 4*x^2 + 21*x^3 + 126*x^4 + ... is the o.g.f. for A003168. (End)

A243659 Number of Sylvester classes of 3-packed words of degree n.

Original entry on oeis.org

1, 1, 5, 34, 267, 2279, 20540, 192350, 1853255, 18252079, 182924645, 1859546968, 19127944500, 198725331588, 2082256791048, 21979169545670, 233495834018591, 2494624746580655, 26786319835972799, 288915128642169250, 3128814683222599331, 34007373443388857999

Offset: 0

N. J. A. Sloane, Jun 12 2014

See Novelli-Thibon (2014) for precise definition.

Seiichi Manyama, Table of n, a(n) for n = 0..941 (terms 1..100 from Lars Blomberg)
Paul Barry, The Triple Riordan Group, arXiv:2412.05461 [math.CO], 2024. See pp. 4, 10.
J.-C. Novelli and J.-Y. Thibon, Hopf Algebras of m-permutations,(m+1)-ary trees, and m-parking functions, arXiv preprint arXiv:1403.5962 [math.CO], 2014. See Eq. (185), p. 47 and Fig. 17.

Column k=3 of A336573.
Cf. A003168, A336539.
Cf. A002293, A349331, A364747, A364765.

a := proc(n) option remember; if n = 0 then 1 elif n = 1 then 1 else (4*(37604*n^5-158474*n^4+248391*n^3-178459*n^2+58042*n-6720)*a(n-1) - 3*(n-2)*(3*n-4)*(3*n-5)*(119*n^2-85*n+14)*a(n-2) )/ (12*n*(3*n-1)*(3*n+1)*(119*n^2-323*n+218)) fi; end:
seq(a(n), n = 0..20); # Peter Bala, Sep 08 2024

b[0] = 1; b[n_] := b[n] = 1/n Sum[Sum[2^(j-2i)(-1)^(i-j) Binomial[i, 3i-j] Binomial[i+j-1, i-1], {j, 0, 3i}] b[n-i], {i, 1, n}];
a[n_] := b[n+1];
Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Jul 27 2018, after Vladimir Kruchinin *)

a(n):=if n=0 then 1 else 1/n*sum(sum(2^(j-2*i)*(-1)^(i-j)*binomial(i,3*i-j)*binomial(i+j-1,i-1),j,0,3*i)*a(n-i),i,1,n); /* Vladimir Kruchinin, Apr 07 2017 */

a(n) = if(n==0, 1, sum(i=1, n, a(n-i)*sum(j=0, 3*i, 2^(j-2*i)*(-1)^(i-j)*binomial(i,3*i-j)*binomial(i+j-1,i-1)))/n); \\ Seiichi Manyama, Jul 26 2020

a(n) = my(A=1+x*O(x^n)); for(i=0, n, A=1-x*A^3*(1-2*A)); polcoeff(A, n); \\ Seiichi Manyama, Jul 26 2020

a(n) = (-1)^n*sum(k=0, n, (-2)^k*binomial(n, k)*binomial(3*n+k+1, n)/(3*n+k+1)); \\ Seiichi Manyama, Jul 26 2020

a(n) = (-1)^n*sum(k=0, n, (-2)^(n-k)*binomial(3*n+1, k)*binomial(4*n-k, n-k))/(3*n+1); \\ Seiichi Manyama, Jul 26 2020

Novelli-Thibon give an explicit formula in Eq. (182).
a(0) = 1 and a(n) = (1/n) * Sum_{i=1..n} ( Sum_{j=0..3*i} (2^(j-2*i)*(-1)^(i-j) * binomial(i,3*i-j)*binomial(i+j-1,i-1)) *a(n-i) ) for n > 0. - Vladimir Kruchinin, Apr 09 2017
From Seiichi Manyama, Jul 26 2020: (Start)
G.f. A(x) satisfies: A(x) = 1 - x * A(x)^3 * (1 -  2 * A(x)).
a(n) = (-1)^n * Sum_{k=0..n} (-2)^k * binomial(n,k) * binomial(3*n+k+1,n)/(3*n+k+1).
a(n) = ( (-1)^n / (3*n+1) ) * Sum_{k=0..n} (-2)^(n-k) * binomial(3*n+1,k) * binomial(4*n-k,n-k). (End)
a(n) ~ sqrt(24388 + 9221*sqrt(7)) * (316 + 119*sqrt(7))^(n - 1/2) / (sqrt(7*Pi) * n^(3/2) * 2^(n + 3/2) * 3^(3*n + 3/2)). - Vaclav Kotesovec, Jul 31 2021
a(n) = (1/n) * Sum_{k=0..n-1} binomial(n,k) * binomial(4*n-k,n-1-k) for n > 0. - Seiichi Manyama, Aug 08 2023
P-recursive: 12*n*(3*n-1)*(3*n+1)*(119*n^2-323*n+218)*a(n) = 4*(37604*n^5-158474*n^4+248391*n^3-178459*n^2+58042*n-6720)*a(n-1) - (3*n-4)*(3*n-5)*(3*n-6)*(119*n^2-85*n+14)*a(n-2) with a(0) = a(1) = 1. - Peter Bala, Sep 08 2024

a(9)-a(21) from Lars Blomberg, Jul 12 2017

a(0)=1 inserted by Seiichi Manyama, Jul 26 2020

A336573 Square array T(n,k), n >= 0, k >= 0, read by antidiagonals, where T(n,k) = (-1)^n * Sum_{j=0..n} (-2)^j * binomial(n,j) * binomial(kn+j+1,n)/(kn+j+1).

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 1, 1, 3, 4, 1, 1, 4, 11, 8, 1, 1, 5, 21, 45, 16, 1, 1, 6, 34, 126, 197, 32, 1, 1, 7, 50, 267, 818, 903, 64, 1, 1, 8, 69, 484, 2279, 5594, 4279, 128, 1, 1, 9, 91, 793, 5105, 20540, 39693, 20793, 256, 1, 1, 10, 116, 1210, 9946, 56928, 192350, 289510, 103049, 512

Offset: 0

Seiichi Manyama, Jul 26 2020

T(n,k) is the number of Sylvester classes of k-packed words of degree n.

			Square array begins:
   1,   1,   1,    1,    1,    1, ...
   1,   1,   1,    1,    1,    1, ...
   2,   3,   4,    5,    6,    7, ...
   4,  11,  21,   34,   50,   69, ...
   8,  45, 126,  267,  484,  793, ...
  16, 197, 818, 2279, 5105, 9946, ...

Seiichi Manyama, Antidiagonals n = 0..139, flattened
J.-C. Novelli and J.-Y. Thibon, Hopf Algebras of m-permutations,(m+1)-ary trees, and m-parking functions, arXiv preprint arXiv:1403.5962 [math.CO], 2014. See Eq. (185), p. 47 and Fig. 17.

Columns k = 0-5 are: A011782, A001003, A003168, A243659, A243667, A243668.
Main diagonal is A336495.
Cf. A336534, A336574, A336575.

T := (n,k) -> `if`(k=0, `if`(n=0, 1, 2^(n-1)), (-1)^n*(binomial(k*n+1, n)* hypergeom([-n, k*n+1], [(k-1)*n+2], 2)) / (k*n+1)):
seq(lprint(seq(simplify(T(n, k)), k=0..9)), n=0..6); # Peter Luschny, Jul 26 2020

T[n_, k_] := (-1)^n * Sum[(-2)^j * Binomial[n, j] * Binomial[k*n+j+1, n]/(k*n+j+1), {j, 0, n}]; Table[T[k, n-k], {n, 0, 10}, {k, 0, n}] // Flatten (* Amiram Eldar, May 01 2021 *)

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

T(n, k) = my(A=1+x*O(x^n)); for(i=0, n, A=1-x*A^k*(1-2*A)); polcoeff(A, n);

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

G.f. A_k(x) of column k satisfies A_k(x) = 1 - x * A_k(x)^k * (1 - 2 * A_k(x)).
T(n,k) = ( (-1)^n / (k*n+1) ) * Sum_{j=0..n} (-2)^(n-j) * binomial(k*n+1,j) * binomial((k+1)*n-j,n-j).
T(n,k) = (-1)^n*binomial(k*n+1, n)*hypergeom([-n, k*n+1], [(k-1)*n+2], 2)/(k*n+1) for k >= 1. - Peter Luschny, Jul 26 2020
T(n,k) = (1/n) * Sum_{j=0..n-1} binomial(n,j) * binomial((k+1)*n-j,n-1-j) for n > 0. - Seiichi Manyama, Aug 08 2023

A364985 E.g.f. satisfies A(x) = 1 + xA(x)^3exp(x*A(x)^2).

Original entry on oeis.org

1, 1, 8, 123, 2884, 91445, 3664926, 177796759, 10132646840, 663644108169, 49123993335130, 4055804550134051, 369544757016476196, 36834870020525413213, 3987179241476814768854, 465777171342934543710255, 58407238852473276959363056, 7825395596421876706944643985

Offset: 0

Seiichi Manyama, Aug 15 2023

nonn

Cf. A364983, A364984, A364986.

Cf. A003168.

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

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

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

A100327 Row sums of triangle A100326, in which row n equals the inverse binomial of column n of square array A100324.

Original entry on oeis.org

1, 2, 8, 42, 252, 1636, 11188, 79386, 579020, 4314300, 32697920, 251284292, 1953579240, 15336931928, 121416356108, 968187827834, 7769449728780, 62696580696172, 508451657412496, 4141712433518956, 33872033298518728, 278014853384816184, 2289376313410678312

Offset: 0

Paul D. Hanna, Nov 17 2004

nonn

Self-convolution yields A100328, which equals column 1 of triangle A100326 (omitting leading zero).

Vincenzo Librandi, Table of n, a(n) for n = 0..200

Cf. A003168, A003169, A100326, A219538.

A100327:= func< n | n eq 0 select 1 else (2/n)*(&+[Binomial(n, k)*Binomial(2*n+k, k-1): k in [1..n]]) >;
[A100327(n): n in [0..30]]; // G. C. Greubel, Jan 30 2023

A100327 := n -> simplify(2^n*binomial(3*n,2*n)*hypergeom([-1-2*n,-n], [-3*n], 1/2)/ (n+1/2)): seq(A100327(n), n=0..22); # Peter Luschny, Jun 10 2017

Flatten[{1,Table[Sum[2*Binomial[n,k]*Binomial[2n+k,k-1]/n,{k,1,n}],{n,1,20}]}] (* Vaclav Kotesovec, Oct 17 2012 *)

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

a(n)=polcoeff((1/x)*serreverse(x*(1-x+sqrt(1-4*x +x^2*O(x^n)))/(2+x)),n)
for(n=0,25,print1(a(n),", ")) \\ Paul D. Hanna, Nov 22 2012

def A100327(n): return 2^n*binomial(3*n,2*n)*simplify(hypergeometric([-1-2*n,-n], [-3*n],1/2)/(n+1/2))
[A100327(n) for n in range(31)] # G. C. Greubel, Jan 30 2023

G.f.: (1/x)*Series_Reversion( x*(1-x + sqrt(1 - 4*x)) / (2+x) ). - Paul D. Hanna, Nov 22 2012
G.f. A(x) = (1+G(x))/(1-G(x)), also A(x)^2 = (1+G(x))*G(x)/x, where G(x) = x*(1+G(x))/(1-G(x))^2 is the g.f. of A003169.
a(n) = 2*A003168(n) for n>0 with a(0)=1.
a(n) = Sum_{k=1..n} 2*binomial(n, k)*binomial(2n+k, k-1)/n for n>0 with a(0)=1.
Recurrence: 20*n*(2*n+1)*a(n) = (371*n^2 - 395*n + 96)*a(n-1) - 6*(27*n^2 - 103*n + 96)*a(n-2) + 4*(n-3)*(2*n-5)*a(n-3). - Vaclav Kotesovec, Oct 17 2012
a(n) ~ sqrt(4046 + 1122*sqrt(17))*((71 + 17*sqrt(17))/16)^n/(136*sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Oct 17 2012
a(n) = 2^n*binomial(3*n,2*n)*hypergeometric([-1-2*n,-n], [-3*n],1/2)/(n+1/2). - Peter Luschny, Jun 10 2017

A102537 Triangle T(n,k) read by rows: (1/n) * C(2n+k,k-1) * C(n,k); n, k >= 1.

Original entry on oeis.org

1, 1, 3, 1, 8, 12, 1, 15, 55, 55, 1, 24, 156, 364, 273, 1, 35, 350, 1400, 2380, 1428, 1, 48, 680, 4080, 11628, 15504, 7752, 1, 63, 1197, 9975, 41895, 92169, 100947, 43263, 1, 80, 1960, 21560, 123970, 396704, 708400, 657800, 246675, 1, 99, 3036, 42504

Offset: 1

Ralf Stephan, Jan 14 2005

Number of dissections of a convex (2n+2)-gon by k-1 noncrossing diagonals into (2j+2)-gons, 1 <= j <= n-1.
Apparently, a signed, refined version of this array is given on page 65 of the Einziger link, related to the antipode of a Hopf algebra. - Tom Copeland, May 19 2015
The f-vectors of the simplicial noncrossing hypertree complexes of McCammond (p. 15). The reduced Euler characteristics are the signed Catalan numbers A000108. - Tom Copeland, May 19 2017
The rows seem to give (up to sign) the coefficients in the expansion of the integer-valued polynomial ((x+1)*(x+2)*...*(x+2n+1))*((x+n+2)*(x+n+3)*...*(x+2n)) / ((2n+1)!*(n)!) in the basis made of the binomial(x+i,i). - F. Chapoton, Nov 01 2022
Chapoton's observation above is correct: the precise expansion is ((x+1)*(x+2)*...*(x+2n+1))*((x+n+2)*(x+n+3)*...*(x+2n)) / ((2n+1)!*n!) = Sum_{k = 1..n} (-1)^(k+1)*T(n,n+1-k)*binomial(x+3*n+1-k, 3*n+1-k), as can be verified using the WZ algorithm. For example, n = 3 gives (x+1)*(x+2)*(x+3)*(x+4)*(x+5)*(x+6)*(x+7)*(x+5)(x+6)/(7!*3!) = 12*binomial(x+9,9) - 8*binomial(x+8,8) + binomial(x+7,7). - Peter Bala, Jun 25 2023

			Triangle begins
  1;
  1,  3;
  1,  8,   12;
  1, 15,   55,    55;
  1, 24,  156,   364,    273;
  1, 35,  350,  1400,   2380,   1428;
  1, 48,  680,  4080,  11628,  15504,   7752;
  1, 63, 1197,  9975,  41895,  92169, 100947,  43263;
  1, 80, 1960, 21560, 123970, 396704, 708400, 657800, 246675;

Michael De Vlieger, Table of n, a(n) for n = 1..11325 (rows 1 <= n <= 150).
H. Einziger, Incidence Hopf algebras: Antipodes, forest formulas, and noncrossing partitions, Dissertation (2010), George Washington University.
J. McCammond, Noncrossing Hypertrees, 2015.
Jean-Christophe Novelli and Jean-Yves Thibon, Hopf Algebras of m-permutations,(m+1)-ary trees, and m-parking functions, arXiv preprint arXiv:1403.5962 [math.CO], 2014.
Jean-Christophe Novelli and Jean-Yves Thibon, Noncommutative Symmetric Functions and Lagrange Inversion II: Noncrossing partitions and the Farahat-Higman algebra, arXiv:2106.08257 [math.CO], 2021-2022.
E. Tzanaki, Polygon dissections and some generalizations of cluster complexes, arXiv:math/0501100 [math.CO], 2005.

Left-hand columns include A005563. Right-hand columns include essentially A001764 and A013698.
Row sums are in A003168.
Cf. A000108, A120986.
Cf. A243662 for rows reversed.

[[1/n * Binomial(2*n+k,k-1) * Binomial(n,k): k in [1..n]]: n in [1.. 15]]; // Vincenzo Librandi, May 20 2015

Table[1/n*Binomial[2 n + k, k - 1] Binomial[n, k], {n, 10}, {k, n}] // Flatten (* Michael De Vlieger, May 20 2017 *)

cp's OEIS Frontend

A003169 Number of 2-line arrays; or number of P-graphs with 2n edges.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

PARI

Formula

Extensions

A049124 Revert transform of (-1 + x + x^2)/((x - 1)*(x + 1)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

Extensions

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

A114496 a(n) = Sum of binomial(n,k)*binomial(2n+k,k) over all k.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A243659 Number of Sylvester classes of 3-packed words of degree n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Maxima

PARI

PARI

PARI

PARI

Formula

Extensions

A336573 Square array T(n,k), n >= 0, k >= 0, read by antidiagonals, where T(n,k) = (-1)^n * Sum_{j=0..n} (-2)^j * binomial(n,j) * binomial(k*n+j+1,n)/(k*n+j+1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A336573 Square array T(n,k), n >= 0, k >= 0, read by antidiagonals, where T(n,k) = (-1)^n * Sum_{j=0..n} (-2)^j * binomial(n,j) * binomial(kn+j+1,n)/(kn+j+1).

A364985 E.g.f. satisfies A(x) = 1 + xA(x)^3exp(x*A(x)^2).