A102405 -id:A102405 - cp's OEIS frontend

A094507 Triangle read by rows: T(n,k) is number of Dyck paths of semilength n and having k UDUD's (here U=(1,1), D=(1,-1)).

1, 1, 1, 1, 3, 1, 1, 7, 5, 1, 1, 19, 14, 7, 1, 1, 53, 46, 22, 9, 1, 1, 153, 150, 82, 31, 11, 1, 1, 453, 495, 299, 127, 41, 13, 1, 1, 1367, 1651, 1087, 507, 181, 52, 15, 1, 1, 4191, 5539, 3967, 1991, 781, 244, 64, 17, 1, 1, 13015, 18692, 14442, 7824, 3271, 1128, 316, 77, 19

Offset: 0

Emeric Deutsch, Jun 05 2004

Column k=0 is A078481.
Column k=1 is A244236.
Row sums are the Catalan numbers (A000108).

			T(3,0) = 3 because UDUUDD, UUDDUD and UUUDDD are the only Dyck paths of semilength 3 and having no UDUD in them.
Triangle begins:
     1;
     1;
     1,    1;
     3,    1,    1;
     7,    5,    1,    1;
    19,   14,    7,    1,   1;
    53,   46,   22,    9,   1,   1;
   153,  150,   82,   31,  11,   1,  1;
   453,  495,  299,  127,  41,  13,  1,  1;
  1367, 1651, 1087,  507, 181,  52, 15,  1, 1;
  4191, 5539, 3967, 1991, 781, 244, 64, 17, 1, 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.

Cf. A078481, A000108, A102405 (the same for DUDU), A243752, A243753, A244236.

T(2n,n) gives A304361.

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, Apr 29 2015, after Alois P. Heinz *)

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

A102407 Number of Dyck paths of semilength n having no ascents of length 1 that start at an odd level.

Original entry on oeis.org

1, 1, 2, 4, 10, 26, 72, 206, 606, 1820, 5558, 17206, 53872, 170298, 542778, 1742308, 5627698, 18277698, 59652952, 195541494, 643506310, 2125255036, 7041631854, 23400092142, 77971706848, 260458050034, 872040564850, 2925902656644, 9836517749658, 33130048199466

Offset: 0

Emeric Deutsch, Jan 06 2005

nonn

Number of Łukasiewicz paths of length n having no 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: a(2)=2 because we have HH and UD, where U=(1,1), H=(1,0) and D=(1,-1). Column 0 of A102405.
From David Callan, Sep 25 2006: (Start)
a(n) is the number of Dyck n-paths containing no DUDUs. For example, a(3) = 4 counts all five Dyck 3-paths except UDUDUD.
a(n) is the number of Dyck n-paths containing no subpath of the form UUPDD where P is a nonempty Dyck path. For example, a(3) = 4 counts all five Dyck 3-paths except UUUDDD. Deutsch's involution phi on Dyck paths interchanges #DUDUs and #UUPDDs with P a nonempty Dyck path. Phi is defined recursively by phi({})={}, phi(UPDQ)=U phi(Q) D phi(P) where P,Q are Dyck paths.
a(n) is the number of ordered trees on n edges in which each leaf is either the leftmost or rightmost child of its parent. For example, a(3) counts:
  ..|....|...../\.../\
  ./ \...|....|.......|
  .......|
(End)

			a(3)=4 because among the five Dyck paths of semilength 3 only UUDUDD has an ascent of length 1 that starts at an odd level; here U=(1,1) and D=(1,-1).

Alois P. Heinz, Table of n, a(n) for n = 0..1828
Christopher Bao, Yunseo Choi, Katelyn Gan, and Owen Zhang, On a Conjecture by Baril, Cerbai, Khalil, and Vajnovszki on Two Restricted Stacks, arXiv:2308.09344 [math.CO], 2023.
Paul Barry, On Motzkin-Schröder Paths, Riordan Arrays, and Somos-4 Sequences, J. Int. Seq. (2023) Vol. 26, Art. 23.4.7.
Emeric Deutsch, An involution on Dyck paths and its consequences, Discrete Math., 204 (1999), no. 1-3, 163-166.
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. A102405, A102406.

R:=PowerSeriesRing(Rationals(), 30);
Coefficients(R!( (1+x-x^2 -Sqrt(1-2*x-5*x^2-2*x^3+x^4))/(2*x) )); // G. C. Greubel, Oct 31 2024

G:=(1+z-z^2-sqrt(1-2*z-5*z^2-2*z^3+z^4))/2/z: Gser:=series(G,z=0,31): 1,seq(coeff(Gser,z^n),n=1..29);
f:=proc(n) local i,j; add( (1/(n-j))*binomial(n-j,j)* add( binomial(n-2*j,i)*binomial(j+i, n-2*j-i+1), i=0..n-2*j), j=0..n/2 ); end; # N. J. A. Sloane, Dec 06 2007

CoefficientList[Series[(1+x-x^2 -Sqrt[1-2 x -5 x^2 -2 x^3 +x^4])/(2 x), {x, 0, 30}], x] (* Vincenzo Librandi, Mar 20 2015 *)

def A102407_list(prec):
    P. = PowerSeriesRing(ZZ, prec)
    return P( (1+x-x^2 -sqrt(1-2*x-5*x^2-2*x^3+x^4))/(2*x) ).list()
A102407_list(30) # G. C. Greubel, Oct 31 2024

G.f.: (1+z-z^2 - sqrt(1-2*z-5*z^2-2*z^3+z^4))/(2*z).
a(n) = Sum_{j=0..floor(n/2)} Sum_{i=0..n-2*j} (1/(n-j))*binomial(n-j,j) * binomial(n-2*j,i)*binomial(j+i, n-2*j-i+1) (from Sapounakis et al.). - N. J. A. Sloane, Dec 06 2007
From Gary W. Adamson, Jul 11 2011: (Start)
Let M = the following infinite square production matrix (where the main diagonal is (1,0,1,0,1,0,...)):
  1, 1, 0, 0, 0, 0, ...
  1, 0, 1, 0, 0, 0, ...
  1, 1, 1, 1, 0, 0, ...
  1, 1, 1, 0, 1, 0, ...
  1, 1, 1, 1, 1, 1, ...
  1, 1, 1, 1, 1, 0, ...
  ...
a(n) = top left term in M^n, a(n+1) = sum of top row terms in M^n. Example: top row of M^5 = (26, 19, 16, 7, 3, 1, 0, 0, 0, ...) where 26 = a(5) and 72 = a(6) = (26 + 19 + 16 + 7 + 3 + 1). (End)
(n+1)*a(n) -(2*n-1)*a(n-1) -5*(n-2)*a(n-2) -(2*n-7)*a(n-3) +(n-5)*a(n-4) = 0. - R. J. Mathar, Jan 04 2017

A102404 Triangle read by rows: T(n,k) is number of Dyck paths of semilength n having k ascents of length 1 starting at an even level.

Original entry on oeis.org

1, 0, 1, 1, 0, 1, 2, 2, 0, 1, 5, 5, 3, 0, 1, 14, 14, 9, 4, 0, 1, 39, 46, 27, 14, 5, 0, 1, 114, 143, 101, 44, 20, 6, 0, 1, 339, 466, 341, 184, 65, 27, 7, 0, 1, 1028, 1524, 1212, 664, 300, 90, 35, 8, 0, 1, 3163, 5043, 4279, 2539, 1145, 454, 119, 44, 9, 0, 1, 9852, 16812, 15206, 9564, 4665, 1819, 651, 152, 54, 10, 0, 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 even 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(4,1)=5 because we have (H)UHD, (H)U(2)DD, UHD(H), U(2)DD(H) and U(2)(H)DD, where H=(1,0), U(2)=(1,2) and D=(1,-1) and the level steps at even level are shown between parentheses. Row n contains n+1 terms. Row sums yield the Catalan numbers (A000108). Column 0 is A102406.

			T(3,1)=2 because we have (U)DUUDD and UUDD(U)D, where U=(1,1), D=(1,-1) and the ascents of length 1 starting at an even level are shown between parentheses.

Index entries for sequences related to Łukasiewicz

Cf. A000108, A102405, A102406.

m = 12; G[_] = 0;
Do[G[z_] = -((G[z]^2 z ((t-1)z - 1)^2 + 1)/((t-1)z^2 + (t-1)z - 1)) + O[z]^m, {m}];
CoefficientList[#, t]& /@ CoefficientList[G[z], z] // Flatten (* Jean-François Alcover, Nov 15 2019 *)

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

A263173 Number of Dyck paths of semilength n having exactly two (possibly overlapping) DUDU's (with U=(1,1), D=(1,-1)).

Original entry on oeis.org

1, 3, 15, 58, 231, 891, 3403, 12870, 48318, 180356, 670014, 2479302, 9143885, 33627777, 123366789, 451612846, 1650111453, 6019100025, 21922936343, 79740801036, 289690000380, 1051250045960, 3811012240380, 13802994382860, 49950211130905, 180617997397887

Offset: 4

Alois P. Heinz, Oct 11 2015

nonn

			a(4) = 1: UDUDUDUD.
a(5) = 3: UDUDUDUUDD, UUDDUDUDUD, UUDUDUDUDD.
a(6) = 15: UDUDUDUUDDUD, UDUDUDUUDUDD, UDUDUDUUUDDD, UDUDUUDDUDUD, UDUDUUDUDUDD, UDUUDDUDUDUD, UDUUDUDUDUDD, UUDDUDUDUUDD, UUDUDDUDUDUD, UUDUDUDDUDUD, UUDUDUDUDDUD, UUDUDUDUUDDD, UUUDDDUDUDUD, UUUDDUDUDUDD, UUUDUDUDUDDD.

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

Column k=2 of A102405.

a:= proc(n) option remember; `if`(n<5, `if`(n=4, 1, 0),
       ((2*n-7)*a(n-1) +(5*n-15)*a(n-2) +(2*n-5)*a(n-3)
        -(n-2)*a(n-4))/(n-4))
    end:
seq(a(n), n=4..30);

cp's OEIS Frontend

A094507 Triangle read by rows: T(n,k) is number of Dyck paths of semilength n and having k UDUD's (here U=(1,1), D=(1,-1)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A102407 Number of Dyck paths of semilength n having no ascents of length 1 that start at an odd level.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

SageMath

Formula

A102404 Triangle read by rows: T(n,k) is number of Dyck paths of semilength n having k ascents of length 1 starting at an even level.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A263173 Number of Dyck paths of semilength n having exactly two (possibly overlapping) DUDU's (with U=(1,1), D=(1,-1)).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple