A094507 -id:A094507 - cp's OEIS frontend

A243752 Number T(n,k) of Dyck paths of semilength n having exactly k (possibly overlapping) occurrences of the consecutive step pattern given by the binary expansion of n, where 1=U=(1,1) and 0=D=(1,-1); triangle T(n,k), n>=0, read by rows.

1, 0, 1, 0, 1, 1, 1, 3, 1, 1, 11, 2, 9, 16, 12, 4, 1, 1, 57, 69, 5, 127, 161, 98, 35, 7, 1, 323, 927, 180, 1515, 1997, 1056, 280, 14, 4191, 5539, 3967, 1991, 781, 244, 64, 17, 1, 1, 10455, 25638, 18357, 4115, 220, 1, 20705, 68850, 77685, 34840, 5685, 246, 1

Offset: 0

Alois P. Heinz, Jun 09 2014

			Triangle T(n,k) begins:
: n\k :    0     1     2     3    4    5  ...
+-----+----------------------------------------------------------
:  0  :    1;                                 [row  0 of A131427]
:  1  :    0,    1;                           [row  1 of A131427]
:  2  :    0,    1,    1;                     [row  2 of A090181]
:  3  :    1,    3,    1;                     [row  3 of A001263]
:  4  :    1,   11,    2;                     [row  4 of A091156]
:  5  :    9,   16,   12,    4,   1;          [row  5 of A091869]
:  6  :    1,   57,   69,    5;               [row  6 of A091156]
:  7  :  127,  161,   98,   35,   7,   1;     [row  7 of A092107]
:  8  :  323,  927,  180;                     [row  8 of A091958]
:  9  : 1515, 1997, 1056,  280,  14;          [row  9 of A135306]
: 10  : 4191, 5539, 3967, 1991, 781, 244, ... [row 10 of A094507]

Alois P. Heinz, Rows n = 0..270, flattened

Columns k=0-10 give: A243754, A243770, A243771, A243772, A243773, A243774, A243775, A243776, A243777, A243778, A243779, or main diagonals of A243753, A243827, A243828, A243829, A243830, A243831, A243832, A243833, A243834, A243835, A243836.
Row sums give A000108.
Cf. A098978, A114463, A114848, A116424, A135305, A242450, A243366, A243838.

A078481 Expansion of (1 - x - x^2 - sqrt(1 - 2x - 5x^2 - 2x^3 + x^4)) / (2x + 2*x^2).

Original entry on oeis.org

0, 1, 1, 3, 7, 19, 53, 153, 453, 1367, 4191, 13015, 40857, 129441, 413337, 1328971, 4298727, 13978971, 45673981, 149867513, 493638797, 1631616239, 5410015615, 17990076527, 59981630321, 200476419713, 671564145137, 2254338511507, 7582179238151, 25547868961315

Offset: 0

N. J. A. Sloane, Jan 04 2003

nonn

Number of irreducible stack sortable permutations of degree n.
Also number of Dyck paths of semilength n with no UDUD. Example: a(3)=3 because the only Dyck paths of semilength 3 with no UDUD in them are: UDUUDD, UUDDUD and UUUDDD (the nonqualifying ones being UUDUDD and UDUDUD). - Emeric Deutsch, Jan 27 2003
From Paul Barry, Jan 29 2009: (Start)
The sequence 1,1,1,3,7,19,... has general term sum{k=0..n, C(n+k,2k)*(-1)^(n-k)*A006318(k)} and g.f. given by
1/(1+x-2x/(1+x-x/(1+x-2x/(1+x-x/(1+x-2x/(1+x-x/(1-..... (continued fraction). (End)

			x + x^2 + 3*x^3 + 7*x^4 + 19*x^5 + 53*x^6 + 153*x^7 + 453*x^8 + 1367*x^9 + ...

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Andrei Asinowski, Axel Bacher, Cyril Banderier, and Bernhard Gittenberger, Analytic Combinatorics of Lattice Paths with Forbidden Patterns: Enumerative Aspects, in International Conference on Language and Automata Theory and Applications, S. Klein, C. Martín-Vide, D. Shapira (eds), Springer, Cham, pp 195-206, 2018.
Andrei Asinowski, Axel Bacher, Cyril Banderier, and Bernhard Gittenberger, Analytic combinatorics of lattice paths with forbidden patterns, the vectorial kernel method, and generating functions for pushdown automata, Laboratoire d'Informatique de Paris Nord (LIPN 2019).
M. D. Atkinson and T. Stitt, Restricted permutations and the wreath product, Preprint, 2002.
M. D. Atkinson and T. Stitt, Restricted permutations and the wreath product, Discrete Math., 259 (2002), 19-36.
J.-L. Baril, Avoiding patterns in irreducible permutations, Discrete Mathematics and Theoretical Computer Science, Vol 17, No 3 (2016). See Table 4.
Paul Barry, On Motzkin-Schröder Paths, Riordan Arrays, and Somos-4 Sequences, J. Int. Seq. (2023) Vol. 26, Art. 23.4.7.
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.
Murray Tannock, Equivalence classes of mesh patterns with a dominating pattern, MSc Thesis, Reykjavik Univ., May 2016.

Cf. A006318, A094507.

CoefficientList[Series[(1 - x - x^2 - (1 - 2*x - 5*x^2 - 2*x^3 + x^4)^(1/2)) / (2*x + 2*x^2), {x, 0, 20}], x] (* Vaclav Kotesovec, Jan 27 2015 *)
CoefficientList[Series[(1 - x - x^2 - Sqrt[1 - 2 x - 5 x^2 - 2 x^3 + x^4]) / (2 x + 2 x^2), {x, 0, 33}], x] (* Vincenzo Librandi, May 27 2016 *)

a(n):=if n=0 then 0 else sum(((sum(binomial(k+1,n-k-i)*binomial(k+i,k),i,0,n-k))*binomial(n-k-2,k))/(k+1),k,0,n); /* Vladimir Kruchinin, Nov 22 2014 */

{a(n) = if( n<1, 0, polcoeff( -1 + 2*(1 + x) / (1 + x + x^2 + sqrt((1 - x + x^2)^2 - 8*x^2 + x*O(x^n))), n))} /* Michael Somos, Sep 08 2005 */

G.f.: (1 - x - x^2 - (1 - 2*x - 5*x^2 - 2*x^3 + x^4)^(1/2)) / (2*x + 2*x^2) = -1 + 2*(1 + x) / (1 + x + x^2 + sqrt((1 - x + x^2)^2 - 8*x^2)).
G.f. A(x) satisfies A(x) = x + (x + x^2) * (A(x) + A(x)^2). - Michael Somos, Sep 08 2005
Given g.f. A(x), then series reversion of B(x) = x + x*A(x) is -B(-x). - Michael Somos, Sep 08 2005
Given g.f. A(x), then B(x) = x + x*A(x) satisfies 0 = f(x, B(x)) where f(u, v) = u^2*(v + v^2) + u*(1 + v + v^2) - v. - Michael Somos, Sep 08 2005
Given g.f. A(x), then B(x) = x + x*A(x) satisfies B(x) = x + C(x*B(x)) where C(x) is g.f. of A006318 with offset 1. - Michael Somos, Sep 08 2005
D-finite with recurrence: (n+1)*a(n) +(-n+2)*a(n-1) +(-7*n+11)*a(n-2) +(-7*n+17)*a(n-3) +(-n+2)*a(n-4) +(n-5)*a(n-5)=0. - R. J. Mathar, Nov 26 2012
a(n) = sum(k=0..n, ((sum(i=0..n-k, binomial(k+1,n-k-i)*binomial(k+i,k)))*binomial(n-k-2,k))/(k+1)), n>0, a(0)=0. - Vladimir Kruchinin, Nov 22 2014.
a(n) ~ sqrt(2 - 1/sqrt(2) + sqrt(7*(4*sqrt(2)-5)/2)) * ((1 + 2*sqrt(2) + sqrt(5 + 4*sqrt(2)))/2)^n / (2 * n^(3/2) * sqrt(Pi)). - Vaclav Kotesovec, Jan 27 2015

Replaced definition with g.f. given by Atkinson and Still (2002). - N. J. A. Sloane, May 24 2016

A102405 Triangle read by rows: T(n,k) is number of Dyck paths of semilength n having k ascents of length 1 that start at an odd level.

Original entry on oeis.org

1, 1, 2, 4, 1, 10, 3, 1, 26, 12, 3, 1, 72, 41, 15, 3, 1, 206, 143, 58, 18, 3, 1, 606, 492, 231, 76, 21, 3, 1, 1820, 1693, 891, 335, 95, 24, 3, 1, 5558, 5823, 3403, 1411, 455, 115, 27, 3, 1, 17206, 20040, 12870, 5848, 2061, 591, 136, 30, 3, 1, 53872, 69033, 48318, 23858, 9143, 2850, 743, 158, 33, 3, 1

Offset: 0

Emeric Deutsch, Jan 06 2005

T(n,k) is number of Łukasiewicz paths of length n having k level steps at an odd level. A Łukasiewicz path of length n is a path in the first quadrant from (0,0) to (n,0) using rise steps (1,k) for any positive integer k, level steps (1,0) and fall steps (1,-1) (see R. P. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge Univ. Press, Cambridge, 1999, p. 223, Exercise 6.19w; the integers are the slopes of the steps). Example: T(3,1)=1 because we have only UHD with exactly one level step at an odd level; here U=(1,1), H=(1,0) and D=(1,-1). Row n has n-1 terms (n>=2). Row sums are the Catalan numbers (A000108). Column 0 yields A102407.

T(n,k) is the number of Dyck paths of semilength n with k DUDU's. - I. Tasoulas (jtas(AT)unipi.gr), Feb 19 2006

			T(4,1) = 3 because we have UDUUD(U)DD, UUD(U)DDUD and UUUDD(U)DD, where U=(1,1), D=(1,-1) and the ascents of length 1 that start at an odd level are shown between parentheses.
Triangle starts:
00 :    1;
01 :    1;
02 :    2;
03 :    4,    1;
04 :   10,    3,    1;
05 :   26,   12,    3,    1;
06 :   72,   41,   15,    3,   1;
07 :  206,  143,   58,   18,   3,   1;
08 :  606,  492,  231,   76,  21,   3,  1;
09 : 1820, 1693,  891,  335,  95,  24,  3, 1;
10 : 5558, 5823, 3403, 1411, 455, 115, 27, 3, 1;

Alois P. Heinz, Rows n = 0..150, flattened
A. Sapounakis, I. Tasoulas and P. Tsikouras, Counting strings in Dyck paths, Discrete Math., 307 (2007), 2909-2924.
Index entries for sequences related to Łukasiewicz

Cf. A000108, A094507 (the same for UDUD), A102404, A102407, A263173.

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])
      +b(x-1, y+1, [1, 3, 1, 3][t])*`if`(t=4, z, 1))))
    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

b[x_, y_, t_] := b[x, y, t] = If[y<0 || y>x, 0, If[x == 0, 1, Expand[b[x-1, y-1, {2, 2, 4, 2}[[t]]] + b[x-1, y+1, {1, 3, 1, 3}[[t]]]*If[t == 4, z, 1]]]]; T[n_] := Function[{p}, Table[Coefficient[p, z, i], {i, 0, Exponent[p, z]}]][b[2*n, 0, 1]]; Table[T[n], {n, 0, 15}] // Flatten (* Jean-François Alcover, May 20 2015, after Alois P. Heinz *)

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

A244236 Number of Dyck paths of semilength n having exactly one occurrence of the consecutive pattern UDUD.

Original entry on oeis.org

0, 0, 1, 1, 5, 14, 46, 150, 495, 1651, 5539, 18692, 63356, 215556, 735717, 2517941, 8637881, 29693938, 102263818, 352762106, 1218634659, 4215351719, 14598518663, 50611799048, 175639493624, 610076726280, 2120837219465, 7378415912617, 25687819032237

Offset: 0

Alois P. Heinz, Jun 23 2014

nonn

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

Column k=1 of A094507 and column k=10 of A243827.

a:= proc(n) option remember; `if`(n<5, [0$2, 1$2, 5][n+1],
     ((n-2)*(2*n-7)^2*a(n-1) +(28*n^3-212*n^2+501*n-361)*a(n-2)
      +(28*n^3-208*n^2+481*n-344)*a(n-3) +(n-3)*(2*n-3)^2*a(n-4)
      -(n-4)*(2*n-3)*(2*n-5)*a(n-5)) / ((n-1)*(2*n-5)*(2*n-7)))
    end:
seq(a(n), n=0..30);

b[x_, y_, t_] := b[x, y, t] = If[y < 0 || y > x, 0, If[x == 0, 1, Expand[ b[x - 1, y + 1, {2, 2, 4, 2}[[t]]] + b[x - 1, y - 1, {1, 3, 1, 3}[[t]]]* If[t == 4, z, 1]]]];
a[n_] := Coefficient[b[2 n, 0, 1], z, 1];
a /@ Range[0, 30] (* Jean-François Alcover, Dec 21 2020, after Alois P. Heinz in A094507 *)

a(n) ~ c * (1/2+sqrt(2)+sqrt(5+4*sqrt(2))/2)^n / sqrt(n), where c = 0.0543819313385500572292392822783525275532509057751364636784836521... . - Vaclav Kotesovec, Jul 16 2014

A304361 Number of Dyck paths of semilength 2n having exactly n (possibly overlapping) occurrences of the consecutive pattern UDUD, where U=(1,1) and D=(1,-1).

Original entry on oeis.org

1, 1, 1, 9, 41, 244, 1555, 10037, 68599, 476981, 3399518, 24652718, 181411439, 1352123760, 10185964435, 77458698781, 593871350009, 4586247704944, 35646681303447, 278665636846853, 2189789189667782, 17288684906561300, 137081212514315262, 1091163063187762414

Offset: 0

Alois P. Heinz, May 11 2018

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..1072
Vaclav Kotesovec, Recurrence (of order 6)
Wikipedia, Counting lattice paths

Cf. A094507, A333156.

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])
        +b(x-1, y-1, [1, 3, 1, 3][t])*`if`(t=4, z, 1))))
    end:
a:= n-> coeff(b(4*n, 0, 1), z, n):
seq(a(n), n=0..35);

b[x_, y_, t_] := b[x, y, t] = If[y < 0 || y > x, 0, If[x == 0, 1, Expand[ b[x - 1, y + 1, {2, 2, 4, 2}[[t]]] + b[x - 1, y - 1, {1, 3, 1, 3}[[t]]]*If[t == 4, z, 1]]]];
a[n_] := Coefficient[b[4*n, 0, 1], z, n];
Table[a[n], {n, 0, 35}] (* Jean-François Alcover, Jun 02 2018, from Maple *)

a(n) = A094507(2n,n).

a(n) ~ c * d^n / n^2, where d = 8.678461743575504549836851346229164298625429506253061911480810294... is the real root of equation 28*d^5 - 72*d^4 - 1119*d^3 - 3136*d^2 - 272*d - 16 = 0 and c = 0.15899091419445210968174633623072264522489566046427010886172717963... - Vaclav Kotesovec, Mar 25 2020

cp's OEIS Frontend

A243752 Number T(n,k) of Dyck paths of semilength n having exactly k (possibly overlapping) occurrences of the consecutive step pattern given by the binary expansion of n, where 1=U=(1,1) and 0=D=(1,-1); triangle T(n,k), n>=0, read by rows.

Views

Author

Keywords

Examples

Links

Crossrefs

A078481 Expansion of (1 - x - x^2 - sqrt(1 - 2*x - 5*x^2 - 2*x^3 + x^4)) / (2*x + 2*x^2).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Maxima

PARI

Formula

Extensions

A102405 Triangle read by rows: T(n,k) is number of Dyck paths of semilength n having k ascents of length 1 that start at an odd level.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A244236 Number of Dyck paths of semilength n having exactly one occurrence of the consecutive pattern UDUD.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A304361 Number of Dyck paths of semilength 2n having exactly n (possibly overlapping) occurrences of the consecutive pattern UDUD, where U=(1,1) and D=(1,-1).

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A078481 Expansion of (1 - x - x^2 - sqrt(1 - 2x - 5x^2 - 2x^3 + x^4)) / (2x + 2*x^2).