A105633 -id:A105633 - cp's OEIS frontend

A243753 Number A(n,k) of Dyck paths of semilength n avoiding the consecutive step pattern given by the binary expansion of k, where 1=U=(1,1) and 0=D=(1,-1); square array A(n,k), n>=0, k>=0, read by antidiagonals.

1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 2, 1, 1, 0, 0, 0, 1, 1, 2, 1, 4, 1, 1, 0, 0, 0, 1, 1, 2, 4, 1, 9, 1, 1, 0, 0, 0, 1, 1, 2, 4, 9, 1, 21, 1, 1, 0, 0, 0, 1, 1, 1, 4, 9, 21, 1, 51, 1, 1, 0, 0, 0

Offset: 0

Alois P. Heinz, Jun 09 2014

			Square array A(n,k) begins:
  1, 1, 1, 1, 1,   1, 1,   1,   1,    1, ...
  0, 0, 0, 1, 1,   1, 1,   1,   1,    1, ...
  0, 0, 0, 1, 1,   1, 1,   2,   2,    2, ...
  0, 0, 0, 1, 1,   2, 1,   4,   4,    4, ...
  0, 0, 0, 1, 1,   4, 1,   9,   9,    9, ...
  0, 0, 0, 1, 1,   9, 1,  21,  21,   23, ...
  0, 0, 0, 1, 1,  21, 1,  51,  51,   63, ...
  0, 0, 0, 1, 1,  51, 1, 127, 127,  178, ...
  0, 0, 0, 1, 1, 127, 1, 323, 323,  514, ...
  0, 0, 0, 1, 1, 323, 1, 835, 835, 1515, ...

Alois P. Heinz, Antidiagonals n = 0..140, flattened

Columns give: 0, 1, 2: A000007, 3, 4, 6: A000012, 5: A001006(n-1) for n>0, 7, 8, 14: A001006, 9: A135307, 10: A078481 for n>0, 11, 13: A105633(n-1) for n>0, 12: A082582, 15, 16: A036765, 19, 27: A114465, 20, 24, 26: A157003, 21: A247333, 25: A187256(n-1) for n>0.
Main diagonal gives A243754 or column k=0 of A243752.
Cf. A242450, A243827, A243828, A243829, A243830, A243831, A243832, A243833, A243834, A243835, A243836.

A:= proc(n, k) option remember; local b, m, r, h;
      if k<2 then return `if`(n=0, 1, 0) fi;
      m:= iquo(k, 2, 'r'); h:= 2^ilog2(k); b:=
      proc(x, y, t) option remember; `if`(y<0 or y>x, 0, `if`(x=0, 1,
        `if`(t=m and r=1, 0, b(x-1, y+1, irem(2*t+1, h)))+
        `if`(t=m and r=0, 0, b(x-1, y-1, irem(2*t, h)))))
      end; forget(b);
      b(2*n, 0, 0)
    end:
seq(seq(A(n, d-n), n=0..d), d=0..14);

A[n_, k_] := A[n, k] = Module[{b, m, r, h}, If[k<2, Return[If[n == 0, 1, 0]]]; {m, r} = QuotientRemainder[k, 2]; h = 2^Floor[Log[2, k]]; b[x_, y_, t_] := b[x, y, t] = If[y<0 || y>x, 0, If[x == 0, 1, If[t == m && r == 1, 0, b[x-1, y+1, Mod[2*t+1, h]]] + If[t == m && r == 0, 0, b[x-1, y-1, Mod[2*t, h]]]]]; b[2*n, 0, 0]]; Table[ Table[A[n, d-n], {n, 0, d}], {d, 0, 14}] // Flatten (* Jean-François Alcover, Jan 27 2015, after Alois P. Heinz *)

A216604 G.f. satisfies: A(x) = (1 + x(1-x)A(x)) * (1 + x^2*A(x)).

Original entry on oeis.org

1, 1, 1, 2, 3, 4, 7, 12, 19, 33, 59, 102, 181, 329, 593, 1076, 1979, 3643, 6723, 12494, 23289, 43498, 81557, 153356, 288925, 545687, 1032997, 1958978, 3721819, 7083716, 13503311, 25778612, 49283755, 94345179, 180830195, 347006694, 666636809, 1282024484, 2467964693

Offset: 0

Paul D. Hanna, Sep 10 2012

nonn

The radius of convergence of the g.f. A(x) equals 1/2, with A(1/2) = 4.
More generally, if A(x) = (1 + x*(t-x)*A(x)) * (1 + x^2*A(x)), |t|>0, then
A(x) = exp( Sum_{n>=1} x^n/n * Sum_{k=0..n} binomial(n,k)^2 * x^k*(t-x)^(n-k) )
where the radius of convergence r of the g.f. A(x) satisfies
r = (1-r)^2/(t-r) = (1-t*r)/(2*(1-r)) with A(r) = 1/(r*(1-r)) = 2/(1-t*r).
Number of Motzkin excursions of length n that avoid the patterns UU, UD and DH. A Motzkin excursion is a lattice path with steps from the set {D=-1, H=0, U=1} that starts at (0,0), never goes below the x-axis, and terminates at the altitude 0. - Andrei Asinowski, Dec 20 2019

			G.f.: A(x) = 1 + x + x^2 + 2*x^3 + 3*x^4 + 4*x^5 + 7*x^6 + 12*x^7 + 19*x^8 + ...
The logarithm of the g.f. begins:
log(A(x)) = ((1-x) + x)*x + ((1-x)^2 + 2^2*x*(1-x) + x^2)*x^2/2 +
((1-x)^3 + 3^2*x*(1-x)^2 + 3^2*x^2*(1-x) + x^3)*x^3/3 +
((1-x)^4 + 4^2*x*(1-x)^3 + 6^2*x^2*(1-x)^2 + 4^2*x^3*(1-x) + x^4)*x^4/4 +
((1-x)^5 + 5^2*x*(1-x)^4 + 10^2*x^2*(1-x)^3 + 10^2*x^3*(1-x)^2 + 5^2*x^4*(1-x) + x^5)*x^5/5 + ...
Explicitly,
log(A(x)) = x + x^2/2 + 4*x^3/3 + 5*x^4/4 + 6*x^5/5 + 16*x^6/6 + 29*x^7/7 + 45*x^8/8 + 94*x^9/9 + 186*x^10/10 + ... + A217464(n)*x^n/n + ...

G. C. Greubel, Table of n, a(n) for n = 0..1000
Andrei Asinowski, Cyril Banderier, and Valerie Roitner, Generating functions for lattice paths with several forbidden patterns, preprint, 2019.

Cf. A000108, A217464, A105633, A216434, A216454, A216447, A192415, A216616, A216617.

CoefficientList[Series[((1 - x) - Sqrt[(1 - x)^2 - 4*x^3*(1 - x)])/(2*x^3 *(1 - x)), {x,0,50}], x] (* G. C. Greubel, Jan 24 2017 *)

a(n):=sum(sum(binomial(n-2*q-2,n-r-q)*binomial(q+1,r-1)*binomial(q+1,r) ,r,0,q+1)/(q+1), q,0,n); /* Vladimir Kruchinin, Jan 22 2019 */
a(n):=sum((binomial(2*m,m)*binomial(n-2*m+1,n-3*m))/(n-2*m+1),m,0,n/3);
/*Vladimir Kruchinin, Jan 27 2022 */

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

{a(n)=polcoeff(2/(1-x+sqrt((1-x)^2-4*x^3*(1-x) +x*O(x^n))),n)}
for(n=0,40,print1(a(n),", "))

a(n) = sum(k=0, n\3, binomial(n-2*k, k)*binomial(2*k, k)/(k+1)); \\ Seiichi Manyama, Jan 22 2023

G.f.: exp( Sum_{n>=1} x^n/n * Sum_{k=0..n} binomial(n,k)^2 * x^k*(1-x)^(n-k) ).
G.f.: ((1-x) - sqrt( (1-x)^2 - 4*x^3*(1-x) )) / (2*x^3*(1-x)).
a(n) ~ 2^(n+2)/(sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Sep 16 2013
a(n) = Sum_{q=0..n} 1/(q+1)*Sum_{r=0..q+1} C(n-2*q-2,n-r-q)*C(q+1,r-1)*C(q+1,r). - Vladimir Kruchinin, Jan 22 2019
a(n) = 1 + Sum_{k=0..n-3} a(k) * a(n-k-3). - Ilya Gutkovskiy, Jan 28 2021
a(n) = Sum_{m=0..n/3} C(2*m,m)*C(n-2*m+1,n-3*m)/(n-2*m+1). - Vladimir Kruchinin, Jan 27 2022

A119370 G.f. satisfies A(x) = 1 + xA(x)^2 + x^2(A(x)^2 - A(x)).

Original entry on oeis.org

1, 1, 2, 6, 19, 64, 225, 816, 3031, 11473, 44096, 171631, 675130, 2679728, 10719237, 43168826, 174885089, 712222799, 2914150406, 11973792218, 49385167369, 204386777160, 848530495383, 3532844222611, 14747626307436, 61712139464939

Offset: 0

Paul D. Hanna, May 16 2006

Equals base sequence of pendular trinomial triangle A119369; iterated convolutions of this sequence with the central terms (A119371) generates all diagonals of A119369. For example: A119372 = A119370 * A119371; A119373 = A119370^2 * A119371.

Diagonal sums of number array A133336. - Philippe Deléham, Nov 09 2009

			A(x) = 1 + x + 2*x^2 + 6*x^3 + 19*x^4 + 64*x^5 + 225*x^6 + 816*x^7 +...
x*A(x)^2 = x + 2*x^2 + 5*x^3 + 16*x^4 + 54*x^5 + 190*x^6 + 690*x^7 +...
x^2*( A(x)^2 - A(x) ) = 1*x^3 + 3*x^4 + 10*x^5 + 35*x^6 + 126*x^7 +...

G. C. Greubel, Table of n, a(n) for n = 0..1000
Stoyan Dimitrov, On permutation patterns with constrained gap sizes, arXiv:2002.12322 [math.CO], 2020.
Hannah Golab, Pattern avoidance in Cayley permutations, Master's Thesis, Northern Arizona Univ. (2024). See p. 41.

Cf. A104547, A119369, A119371, A119372, A119373, A119374, A119375, A119376.

R:=PowerSeriesRing(Rationals(), 30);
Coefficients(R!( (1+x^2 -Sqrt(1-4*x-2*x^2+x^4))/(2*x*(1+x)) )); // G. C. Greubel, Mar 17 2021

m:= 30;
S:= series( (1+x^2 -sqrt(1-4*x-2*x^2+x^4))/(2*x*(1+x)), x, m+1);
seq(coeff(S, x, j), j = 0..m); # G. C. Greubel, Mar 17 2021

CoefficientList[Series[((1+x^2)-Sqrt[(1+x^2)^2-4*x*(1+x)])/(2*x*(1+x)), {x, 0, 20}], x] (* Vaclav Kotesovec, Sep 11 2013 *)

{a(n)=polcoeff(2/((1+x^2)+sqrt((1+x^2)^2-4*x*(1+x)+x*O(x^n))),n)}

def A119370_list(prec):
    P. = PowerSeriesRing(QQ, prec)
    return P( (1+x^2 -sqrt(1-4*x-2*x^2+x^4))/(2*x*(1+x)) ).list()
A119370_list(30) # G. C. Greubel, Mar 17 2021

G.f.: A(x) = ((1+x^2) - sqrt( (1+x^2)^2 - 4*x*(1+x) ))/(2*x*(1+x)). Equals the inverse binomial transform of A104547.
Recurrence: (n+1)*a(n) = 3*(n-1)*a(n-1) + 6*(n-1)*a(n-2) + 2*(n-2)*a(n-3) - (n-5)*a(n-4) - (n-5)*a(n-5). - Vaclav Kotesovec, Sep 11 2013
a(n) ~ sqrt(-z^2-3*z+1)*(4+2*z-z^3)^(n+1)*(-z^3+z^2+z+3) / (8*sqrt(Pi) * n^(3/2)), where z = 1/(2*sqrt(3/(4+(280-24*sqrt(129))^(1/3) + 2*(35 + 3*sqrt(129))^(1/3)))) - 1/2*sqrt(8/3-1/3*(280-24*sqrt(129))^(1/3) - 2/3*(35+3*sqrt(129))^(1/3) + 8*sqrt(3/(4+(280-24*sqrt(129))^(1/3) + 2*(35 + 3*sqrt(129))^(1/3)))) = 0.225270426... is the root of the equation 1-2*z^2+z^4-4*z=0. - Vaclav Kotesovec, Sep 11 2013
G.f.: 1/G(0) where G(k) = 1 - q/(1 - (q + q^2) / G(k+1) ). - Joerg Arndt, Dec 06 2014
a(n) = Sum_{k=0..floor(n/2)} binomial(n-k-1,k) * binomial(2*n-3*k+1,n-2*k)/(2*n-3*k+1). - Seiichi Manyama, Aug 28 2023
Conjecture: A(x) = 1 + x*exp(Sum_{n >= 1} g(n, x)*x^n/n), where g(n, x) = Sum_{k = 0..n} binomial(n, k)^2*(1 + x)^k. Cf. A105633 and A167638. - Peter Bala, Sep 10 2024

A105632 Triangle, read by rows, where the g.f. A(x,y) satisfies the equation: A(x,y) = 1/(1-xy) + xA(x,y) + x^2*A(x,y)^2.

Original entry on oeis.org

1, 1, 1, 2, 1, 1, 4, 3, 1, 1, 9, 7, 4, 1, 1, 21, 19, 10, 5, 1, 1, 51, 51, 31, 13, 6, 1, 1, 127, 141, 91, 45, 16, 7, 1, 1, 323, 393, 276, 141, 61, 19, 8, 1, 1, 835, 1107, 834, 461, 201, 79, 22, 9, 1, 1, 2188, 3139, 2535, 1485, 701, 271, 99, 25, 10, 1, 1, 5798, 8953, 7711, 4803, 2381, 1001, 351, 121, 28, 11, 1, 1

Offset: 0

Paul D. Hanna, Apr 17 2005

Column 0 is A001006 (Motzkin numbers). Column 1 is A002426 (Central trinomial coefficients). Row sums form A105633 (also equal to A057580?).

T(n,k) is the number of UUDU-avoiding Dyck paths of semilength n+1 with k UDUs, where U = (1,1) is an upstep and D = (1,-1) is a downstep. For example, T(3,1) = 3 counts UDUUUDDD, UDUUDDUD, UUDDUDUD. - David Callan, Nov 25 2021

			Triangle begins:
    1;
    1,    1;
    2,    1,   1;
    4,    3,   1,   1;
    9,    7,   4,   1,   1;
   21,   19,  10,   5,   1,  1;
   51,   51,  31,  13,   6,  1,  1;
  127,  141,  91,  45,  16,  7,  1, 1;
  323,  393, 276, 141,  61, 19,  8, 1, 1;
  835, 1107, 834, 461, 201, 79, 22, 9, 1, 1; ...
Let G = (1-2*x-3*x^2), then the column g.f.s are:
k=1: 1/sqrt(G)
k=2: (G + (1)*1*x^2)/sqrt(G^3)
k=3: (G^2 + (1)*2*x^2*G + (2)*1*x^4)/sqrt(G^5)
k=4: (G^3 + (1)*3*x^2*G^2 + (2)*3*x^4*G + (5)*1*x^6)/sqrt(G^7)
k=5: (G^4 + (1)*4*x^2*G^3 + (2)*6*x^4*G^2 + (5)*4*x^6*G + (14)*1*x^8)/sqrt(G^9)
and involve Catalan numbers and binomial coefficients.
MATRIX INVERSE.
The matrix inverse starts
     1;
    -1,   1;
    -1,  -1,   1;
     0,  -2,  -1,  1;
     2,  -1,  -3, -1,  1;
     6,   2,  -2, -4, -1,  1;
    13,  10,   2, -3, -5, -1,  1;
    18,  32,  14,  2, -4, -6, -1,  1;
   -12,  76,  56, 18,  2, -5, -7, -1,  1;
  -206, 108, 162, 86, 22,  2, -6, -8, -1, 1;
- _R. J. Mathar_, Apr 08 2013

Cf. A105633 (row sums), A001006 (column 0), A002426 (column 1).

A105632 := proc(n,k)
    (1-x-sqrt((1-x)^2-4*x^2/(1-x*y)))/2/x^2 ;
    coeftayl(%,x=0,n) ;
    coeftayl(%,y=0,k) ;
end proc: # R. J. Mathar, Apr 08 2013

T[n_, k_] := SeriesCoefficient[(1 - x - Sqrt[(1 - x)^2 - 4*x^2/(1 - x*y)])/(2*x^2), {x, 0, n}] // SeriesCoefficient[#, {y, 0, k}]&;
Table[T[n, k], {n, 0, 11}, {k, 0, n}] // Flatten (* Jean-François Alcover, Jun 10 2023 *)

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

{T(n,k)=local(X=x+x*O(x^n),Y=y+y*O(y^k));polcoeff(polcoeff( 2/(1-X+sqrt((1-X)^2-4*X^2/(1-X*Y)))/(1-X*Y),n,x),k,y)}

G.f. for column k (k>0): Sum_{j=0..k-1} C(k-1, j)*A000108(j)*x^(2*j)/(1-2*x-3*x^2)^(j+1/2), where A000108(j) = binomial(2*j, j)/(j+1) is the j-th Catalan number.

G.f.: A(x, y) = (1-x - sqrt((1-x)^2 - 4*x^2/(1-x*y)))/(2*x^2).

A258973 The number of plain lambda terms presented by de Bruijn indices, see Bendkowski et al., where zeros have no weight.

Original entry on oeis.org

1, 3, 10, 40, 181, 884, 4539, 24142, 131821, 734577, 4160626, 23881695, 138610418, 812104884, 4796598619, 28529555072, 170733683579, 1027293807083, 6211002743144, 37713907549066, 229894166951757, 1406310771154682, 8630254073158599, 53117142215866687, 327800429456036588

Offset: 0

Kellen Myers, Jun 15 2015

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Maciej Bendkowski, Katarzyna Grygiel, Pierre Lescanne, and Marek Zaionc, Combinatorics of λ-terms: a natural approach, arXiv:1609.08106 [cs.LO], 2016.
Maciej Bendkowski, Katarzyna Grygiel, Pierre Lescanne, and Marek Zaionc, A Natural Counting of Lambda Terms, arXiv preprint arXiv:1506.02367 [cs.LO], 2015.
Maciej Bendkowski and Pierre Lescanne, On the enumeration of closures and environments with an application to random generation, Logical Methods in Computer Science (2019) Vol. 15, No. 4, 3:1-3:21.
K. Grygiel and P. Lescanne, A natural counting of lambda terms, Preprint 2015.

Cf. A086616, A105633, A114851, A360102.

a:= proc(n) option remember; `if`(n<4, [1, 3, 10, 40][n+1],
      ((8*n-3)*a(n-1)-(10*n-13)*a(n-2)
     +(4*n-11)*a(n-3)-(n-4)*a(n-4))/(n+1))
    end:
seq(a(n), n=0..25);  # Alois P. Heinz, Jun 30 2015
a := n -> add(hypergeom([(i+1)/2, i/2+1, i-n+1], [1, 2], -4), i=0..n-1):
seq(simplify(a(n)), n=0..25); # Peter Luschny, May 03 2018

a[n_] := a[n] = If[n<4, {1, 3, 10, 40}[[n+1]], ((8*n-3)*a[n-1] - (10*n-13)*a[n-2] + (4*n-11)*a[n-3] - (n-4)*a[n-4])/(n+1)]; Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Jul 22 2015, after Alois P. Heinz *)

a(n):=sum(sum((binomial(k+i-1,k-1)*binomial(2*k+i-2,k+i-1)*binomial(n-i-1,n-k-i))/k,k,1,n-i),i,0,n); /* Vladimir Kruchinin, May 03 2018 */

lista(nn) = {z = y + O(y^nn); Vec(((1-z)^2 - sqrt((1-z)^4-4*z*(1-z))) / (2*z*(1-z)));} \\ Michel Marcus, Jun 30 2015

G.f. G(z) satisfies z*G(z)^2 - (1-z)*G(z) + 1/(1-z) = 0 (see Bendkowski link Appendix B, p. 23). - Michel Marcus, Jun 30 2015
a(n) ~ 3^(n+1/2) * sqrt(43/(2*((43*(3397 - 261*sqrt(129)))^(1/3) + (43*(3397 + 261*sqrt(129)))^(1/3) - 86)*Pi)) / (3 - (2*6^(2/3)) / (sqrt(129)-9)^(1/3) + (6*(sqrt(129)-9))^(1/3))^n / (2*n^(3/2)). - Vaclav Kotesovec, Jul 01 2015
a(n) = 1 + a(n-1) + Sum_{i=0..n-1} a(i)*a(n-1-i). - Vladimir Kruchinin, May 03 2018
a(n) = Sum_{i=0..n} Sum_{k=1..n-i} binomial(k+i-1,k-1)*binomial(2*k+i-2,k+i-1)*binomial(n-i-1,n-k-i)/k. - Vladimir Kruchinin, May 03 2018
a(n) = Sum_{i=0..n-1} hypergeom([(i+1)/2, i/2+1, i-n+1], [1, 2], -4). - Peter Luschny, May 03 2018
From Peter Bala, Sep 02 2024: (Start)
a(n) = Sum_{k = 0..n} 1/(k + 1) * binomial(2*k, k)*binomial(n+2*k+1, 3*k+1).
Partial sums of A360102. Cf. A086616.
a(n) = (n + 1)*hypergeom([1/2, -n, (n+2)/2, (n+3)/2], [2, 2/3, 4/3], -16/27).
P-recursive: (n + 1)*a(n) = (8*n - 3)*a(n-1) - (10*n - 13)*a(n-2) + (4*n - 11)*a(n-3) - (n - 4)*a(n-4) with a(0) = 1, a(1) = 3, a(2) = 10 and a(3) = 40.
G.f. A(x) = 1/(1 - x)^2 * c(x/(1-x)^3) = (1 - x - sqrt((1 - 7*x + 3*x^2 - x^3)/(1 - x)))/(2*x), where c(x) = (1 - sqrt(1 - 4*x))/(2*x) is the g.f. of the Catalan numbers A000108. (End)

More terms from Michel Marcus, Jun 30 2015

A116424 Triangle read by rows: T(n,k) = the number of Dyck paths of semilength n with k UDUU's, 0 <= k <= floor((n-1)/2).

Original entry on oeis.org

1, 1, 2, 4, 1, 9, 5, 22, 19, 1, 57, 66, 9, 154, 221, 53, 1, 429, 729, 258, 14, 1223, 2391, 1131, 116, 1, 3550, 7829, 4652, 745, 20, 10455, 25638, 18357, 4115, 220, 1, 31160, 84033, 70404, 20598, 1790, 27, 93802, 275765, 264563, 96286, 12104, 379, 1, 284789

Offset: 0

I. Tasoulas (jtas(AT)unipi.gr), Feb 15 2006

T(n,k) also gives the number of Dyck paths of semilength n with k UUDU's.

Column k=0 gives A105633(n-1) for n > 0.

			Triangle begins:
00 :     1;
01 :     1;
02 :     2;
03 :     4,    1;
04 :     9,    5;
05 :    22,   19,    1;
06 :    57,   66,    9;
07 :   154,  221,   53,   1;
08 :   429,  729,  258,  14;
09 :  1223, 2391, 1131, 116,  1;
10 :  3550, 7829, 4652, 745, 20;
...
T(4,1) = 5 because there exist five Dyck paths of semilength 4 with one occurrence of UDUU : UDUUUDDD, UDUUDUDD, UDUUDDUD, UUDUUDDD, UDUDUUDD.

Alois P. Heinz, Rows n = 0..200, flattened
Jean-Luc Baril, Pamela E. Harris, Kimberly J. Harry, Matt McClinton, and José L. Ramírez, Enumerating runs, valleys, and peaks in Catalan words, arXiv:2404.05672 [math.CO], 2024. See p. 18.
Toufik Mansour, Statistics on Dyck Paths, Journal of Integer Sequences, Vol. 9 (2006), Article 06.1.5.
A. Sapounakis, I. Tasoulas and P. Tsikouras, Counting strings in Dyck paths, Discrete Math., 307 (2007), 2909-2924.

Cf. A105633, A243752.

b:= proc(x, y, t) option remember; `if`(y<0 or y>x, 0,
     `if`(x=0, 1, expand(b(x-1, y+1, [2, 2, 4, 2][t])*
     `if`(t=4, z, 1) +b(x-1, y-1, [1, 3, 1, 3][t]))))
    end:
T:= n-> (p-> seq(coeff(p, z, i), i=0..degree(p)))(b(2*n, 0, 1)):
seq(T(n), n=0..15);  # Alois P. Heinz, Jun 02 2014

s = Series[((1 + (t - 1) z^2) - Sqrt[(1 + (t - 1) z^2)^2 - 4*z*(1 - z + z*t)])/(2*z*(1 - z + z*t)), {z, 0, 15}] // CoefficientList[#, z]&;
CoefficientList[#, t]& /@ s // Flatten (* updated by Jean-François Alcover, Feb 14 2021 *)

T(n,k) = Sum_{i=k..floor((n-1)/2)} (-1)^(i+k) * binomial(i,k) * binomial(n-i,i) * binomial(2*n-3*i, n - 2*i -1)/(n-i), n >= 1.

G.f. G = G(t,z) satisfies G = 1 + z^2(1-t)G + z(1-z+tz)G^2.

A273897 Triangle read by rows: T(n,k) is the number of bargraphs of semiperimeter n having abscissa of first descent k (n>=2, 1<=k<=n-1).

Original entry on oeis.org

1, 1, 1, 2, 2, 1, 4, 5, 3, 1, 9, 12, 9, 4, 1, 22, 30, 25, 14, 5, 1, 57, 78, 69, 44, 20, 6, 1, 154, 210, 192, 133, 70, 27, 7, 1, 429, 582, 542, 396, 230, 104, 35, 8, 1, 1223, 1651, 1554, 1176, 731, 369, 147, 44, 9, 1, 3550, 4772, 4521, 3504, 2285, 1248, 560, 200, 54, 10, 1

Offset: 2

Emeric Deutsch, Jun 06 2016

Number of entries in row n is n-1.
Sum of entries in row n = A082582(n).
T(n,1) = A105633(n-3) (n>=3).
Sum(k*T(n,k), k>=1) = A273898(n).

			Row 4 is 2,2,1 because the 5 (=A082582(4)) bargraphs of semiperimeter 4 correspond to the compositions [1,1,1], [1,2], [2,1], [2,2], [3] and the corresponding pictures give the values 3,2,1,2,1 for the abscissae of the first descents.
Triangle starts
1;
1,1;
2,2,1;
4,5,3,1;
9,12,9,4,1;
22,30,25,14,5,1.

Alois P. Heinz, Rows n = 2..150, flattened
M. Bousquet-Mélou and A. Rechnitzer, The site-perimeter of bargraphs, Adv. in Appl. Math. 31 (2003), 86-112.
Emeric Deutsch, S Elizalde, Statistics on bargraphs viewed as cornerless Motzkin paths, arXiv preprint arXiv:1609.00088, 2016

Cf. A082582, A105633, A273898.

G := (1/2)*t*z*(1-2*t*z-z^2-sqrt(1-4*z+2*z^2+z^4))/(1-t-z+t^2*z+t*z^2): Gser := simplify(series(G, z = 0, 20)): for n from 2 to 18 do P[n] := sort(expand(coeff(Gser, z, n))) end do: for n from 2 to 18 do seq(coeff(P[n], t, j), j = 1 .. n-1) end do; # yields sequence in triangular form

nmax = 13; G = (1/2) t z (1 - 2t z - z^2 - Sqrt[1 - 4z + 2z^2 + z^4])/(1 - t - z + t^2 z + t z^2); Gser = G + O[z]^nmax;
Do[P[n] = Expand[Coefficient[Gser, z, n]], {n, 2, nmax}];
Table[CoefficientList[P[n]/t, t], {n, 2, nmax}] // Flatten (* Jean-François Alcover, Jul 24 2018, from Maple *)

G.f.: G(t,z)=(1/2)tz(1-2tz-z^2-sqrt(1-4z+2z^2+z^4))/(1-t-z+t^2z+tz^4), where z marks semiperimeter and t marks the abscissa of the first descent.

A332776 a(n) = 1 + Sum_{k=1..n-1} binomial(n-1,k) * a(k) * a(n-k-1).

Original entry on oeis.org

1, 1, 2, 5, 18, 83, 464, 3041, 22810, 192595, 1807328, 18658097, 210138882, 2563990859, 33691089824, 474327797585, 7123141539610, 113656386574099, 1920170741071280, 34242622099969217, 642792206343361602, 12669617513914228907, 261613287097165614224, 5647565141926833774977

Offset: 0

Ilya Gutkovskiy, Jun 08 2020

nonn

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

Cf. A000110, A006677, A007317, A080635, A105633, A186021.

a[n_] := a[n] = 1 + Sum[Binomial[n - 1, k] a[k] a[n - k - 1], {k, 1, n - 1}]; Table[a[n], {n, 0, 23}]
terms = 23; A[] = 0; Do[A[x] = Normal[Integrate[Exp[x] + A[x] (A[x] - 1), x] + O[x]^(terms + 1)], terms]; CoefficientList[A[x], x] Range[0, terms]!

E.g.f. A(x) satisfies: d/dx A(x) = exp(x) + A(x) * (A(x) - 1).
From Vaclav Kotesovec, Jun 09 2020: (Start)
E.g.f.: exp(x/2) * (BesselJ(2, 2*exp(x/2)) * BesselY(0,2) - BesselJ(0,2) * BesselY(2, 2*exp(x/2))) / (BesselJ(1, 2*exp(x/2)) * BesselY(0,2) - BesselJ(0,2) * BesselY(1, 2*exp(x/2))).
a(n) ~ n! / r^(n+1), where r = 1.0654335847261788612657252860730850911833168584... is the smallest real root of the equation BesselJ(1, 2*exp(r/2)) * BesselY(0,2) = BesselJ(0,2) * BesselY(1, 2*exp(r/2)). (End)

A346075 a(n) = 1 + Sum_{k=1..n-3} a(k) * a(n-k-3).

Original entry on oeis.org

1, 1, 1, 1, 2, 3, 4, 6, 10, 16, 25, 41, 69, 115, 192, 326, 558, 955, 1641, 2839, 4930, 8578, 14972, 26222, 46037, 80988, 142793, 252307, 446617, 791885, 1406394, 2501642, 4456080, 7947963, 14194221, 25379751, 45430710, 81409233, 146028788, 262192876, 471193406

Offset: 0

Ilya Gutkovskiy, Jul 04 2021

nonn

G. C. Greubel, Table of n, a(n) for n = 0..1000

Cf. A105633, A216604, A217282, A307970, A343304, A346047, A346076, A346077.

a[n_] := a[n] = 1 + Sum[a[k] a[n - k - 3], {k, 1, n - 3}]; Table[a[n], {n, 0, 40}]
nmax = 40; A[] = 0; Do[A[x] = 1/(1 - x) + x^3 A[x] (A[x] - 1) + O[x]^(nmax + 1) // Normal, nmax + 1]; CoefficientList[A[x], x]

@CachedFunction
def a(n): # a = A346075
    if (n<4): return 1
    else: return 1 + sum(a(k)*a(n-k-3) for k in range(1,n-2))
[a(n) for n in range(51)] # G. C. Greubel, Nov 27 2022

G.f. A(x) satisfies: A(x) = 1 / (1 - x) + x^3 * A(x) * (A(x) - 1).

A346076 a(n) = 1 + Sum_{k=1..n-4} a(k) * a(n-k-4).

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 3, 4, 5, 7, 11, 17, 25, 36, 54, 84, 131, 201, 307, 475, 745, 1172, 1837, 2878, 4531, 7173, 11381, 18057, 28669, 45624, 72796, 116336, 186066, 297865, 477505, 766621, 1232214, 1982292, 3191693, 5143974, 8298640, 13399691, 21652705, 35014373, 56663700

Offset: 0

Ilya Gutkovskiy, Jul 04 2021

nonn

G. C. Greubel, Table of n, a(n) for n = 0..1000

Cf. A105633, A217282, A307971, A343305, A346048, A346073, A346075, A346077.

a[n_] := a[n] = 1 + Sum[a[k] a[n - k - 4], {k, 1, n - 4}]; Table[a[n], {n, 0, 44}]
nmax = 44; A[] = 0; Do[A[x] = 1/(1 - x) + x^4 A[x] (A[x] - 1) + O[x]^(nmax + 1) // Normal, nmax + 1]; CoefficientList[A[x], x]

@CachedFunction
def a(n): # a = A346076
    if (n<5): return 1
    else: return 1 + sum(a(k)*a(n-k-4) for k in range(1,n-3))
[a(n) for n in range(51)] # G. C. Greubel, Nov 27 2022

G.f. A(x) satisfies: A(x) = 1 / (1 - x) + x^4 * A(x) * (A(x) - 1).

cp's OEIS Frontend

A243753 Number A(n,k) of Dyck paths of semilength n avoiding the consecutive step pattern given by the binary expansion of k, where 1=U=(1,1) and 0=D=(1,-1); square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A216604 G.f. satisfies: A(x) = (1 + x*(1-x)*A(x)) * (1 + x^2*A(x)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Maxima

PARI

PARI

PARI

Formula

A119370 G.f. satisfies A(x) = 1 + x*A(x)^2 + x^2*(A(x)^2 - A(x)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Sage

Formula

A105632 Triangle, read by rows, where the g.f. A(x,y) satisfies the equation: A(x,y) = 1/(1-x*y) + x*A(x,y) + x^2*A(x,y)^2.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

A258973 The number of plain lambda terms presented by de Bruijn indices, see Bendkowski et al., where zeros have no weight.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Maxima

PARI

Formula

Extensions

A116424 Triangle read by rows: T(n,k) = the number of Dyck paths of semilength n with k UDUU's, 0 <= k <= floor((n-1)/2).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A273897 Triangle read by rows: T(n,k) is the number of bargraphs of semiperimeter n having abscissa of first descent k (n>=2, 1<=k<=n-1).

A216604 G.f. satisfies: A(x) = (1 + x(1-x)A(x)) * (1 + x^2*A(x)).

A119370 G.f. satisfies A(x) = 1 + xA(x)^2 + x^2(A(x)^2 - A(x)).

A105632 Triangle, read by rows, where the g.f. A(x,y) satisfies the equation: A(x,y) = 1/(1-xy) + xA(x,y) + x^2*A(x,y)^2.