A078481 -id:A078481 - 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 *)

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)).

Original entry on oeis.org

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.

A384685 Triangle read by rows: T(n,k) is the number of rooted ordered trees with node weights summing to n, where the root has weight 0, all internal nodes have weight 1, and leaf nodes have weights in {1,...,k}.

Original entry on oeis.org

1, 0, 1, 0, 2, 3, 0, 5, 8, 9, 0, 14, 25, 28, 29, 0, 42, 83, 95, 98, 99, 0, 132, 289, 337, 349, 352, 353, 0, 429, 1041, 1236, 1285, 1297, 1300, 1301, 0, 1430, 3847, 4652, 4854, 4903, 4915, 4918, 4919, 0, 4862, 14504, 17865, 18709, 18912, 18961, 18973, 18976, 18977

Offset: 0

John Tyler Rascoe, Jun 06 2025

			Triangle begins:
    k=0     1     2     3     4     5     6     7      8
 n=0 [1]
 n=1 [0,    1]
 n=2 [0,    2,    3]
 n=3 [0,    5,    8,    9]
 n=4 [0,   14,   25,   28,   29]
 n=5 [0,   42,   83,   95,   98,   99]
 n=6 [0,  132,  289,  337,  349,  352,  353]
 n=7 [0,  429, 1041, 1236, 1285, 1297, 1300, 1301]
 n=8 [0, 1430, 3847, 4652, 4854, 4903, 4915, 4918, 4919]
...
T(2,2) = 3 counts:
  o    o      o
  |    |     / \
 (2)  (1)  (1) (1)
       |
      (1)

Cf. (column k=1) A000108, A078481, A078482, A088218, (column k=2) A143330, A380761, A384613.

b(k) = {(x^2-x^(k+1))/(1-x)}
P(N,k) = {my(x='x+O('x^N)); Vec((1-b(k)-sqrt((b(k)-1)^2-4*x))/(2*x))}
T(max_row) = { my( N = max_row+1, v = vector(N, i, if(i==1,1,0))~); for(k=1,N, v=matconcat([v,P(N+1,k)~])); vector(N,n, vector(n,k,v[n,k]))}

G.f. of column k is (1 - b(k,x) - sqrt((b(k,x) - 1)^2 - 4*x))/(2*x) where b(k,x) = (x^2 - x^(k + 1))/(1 - x).

T(n,k) = T(n,n) for k > n.

A120060 Triangle read by rows: T(n,k) is the number of Dyck n-paths (A000108) whose longest sawtooth has size k.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 3, 1, 1, 0, 7, 5, 1, 1, 0, 19, 16, 5, 1, 1, 0, 53, 54, 18, 5, 1, 1, 0, 153, 187, 64, 18, 5, 1, 1, 0, 453, 653, 233, 66, 18, 5, 1, 1, 0, 1367, 2302, 859, 243, 66, 18, 5, 1, 1, 0, 4191, 8174, 3189, 906, 245, 66, 18, 5, 1, 1

Offset: 0

David Callan, Jun 06 2006

A sawtooth in a Dyck path is a subpath of the form (UD)^k with k>=1 (U=upstep, D=downstep). The longest sawtooth in the Dyck path UududUududDUDD has size 2; there are two of them, indicated by lowercase letters.

			Table begins
\ k..0....1....2....3....4....5....6....7
n
0 |..1
1 |..0....1
2 |..0....1....1
3 |..0....3....1....1
4 |..0....7....5....1....1
5 |..0...19...16....5....1....1
6 |..0...53...54...18....5....1....1
7 |..0..153..187...64...18....5....1....1
a(3,1)=3 because the Dyck 3-paths whose longest sawtooth has size 1 are
UUUDDD, UUDDUD, UDUUDD.

Cf. A120059. Column k=1 is A078481. Row sums are the Catalan numbers A000108.

Clear[a,b,c] (* a[n,k] is the number of Dyck n-paths whose longest sawtooth has size <=k, b[n,k] is the number of Dyck n-paths that start UU whose longest sawtooth has size <=k, c[n,k] is the number of Dyck n-paths that start UD whose longest sawtooth has size <=k *) catalanNumber[n_] := 1/(n+1)Binomial[2n,n] a[0,k_]/;k>=0 := 1; a[1,k_]/;k>=1 := 1; a[n_,0]/;n>=1 := 0; a[n_,k_]/;k<0 := 0; b[1,k_]/;k>=0 := 0; c[1,k_]/;k>=1 := 1; b[n_,k_] := a[n,k] - c[n,k] c[n_,k_]/;1<=k<=n-1 := c[n,k] = Sum[b[n-j,k],{j,k}] c[n_,k_]/;k>=n>=1 := catalanNumber[n-1]; a[n_,k_]/;k>=n>=0 := catalanNumber[n]; a[n_,k_]/;k==n-1 := catalanNumber[n]-1; a[n_,k_]/;1<=k<=n-2 && n>=3 := a[n,k] = Sum[b[n-j,k],{j,k}] + Sum[a[j-1,k]a[n-j,k],{j,2,n}] Table[a[n,k]-a[n,k-1],{n,0,8},{k,0,n}]

Generating function for column k>=1 is F[k]-F[k-1] where F[k]:=(Sum[x^j,{j,0,k+1}]-Sqrt[Sum[x^j,{j,0,k+1}]^2] - 4x Sum[x^j,{j,0,k}]^2)/ (2x Sum[x^j,{j,0,k}]).

A218538 Triangle read by rows: T(n,k) is the number of permutations of{1,2,...,n} avoiding [x,x+1] having genus k (see first comment for definition of genus).

Original entry on oeis.org

1, 1, 0, 3, 0, 0, 7, 4, 0, 0, 19, 29, 5, 0, 0, 53, 180, 76, 0, 0, 0, 153, 1004, 901, 61, 0, 0, 0, 453, 5035, 8884, 2315, 0, 0, 0, 0, 1367, 23653, 74177, 46285, 2847, 0, 0, 0, 0, 4191, 106414, 546626, 667640, 143586, 0, 0, 0, 0, 0, 13015, 463740, 3658723, 7777935, 3896494, 209624, 0

Offset: 1

Joerg Arndt, Nov 01 2012

The genus g(p) of a permutation p of {1,2,...,n} is defined by g(p)=(1/2)[n+1-z(p)-z(cp')], where p' is the inverse permutation of p, c = 234...n1 = (1,2,...,n), and z(q) is the number of cycles of the permutation q.
Row sums are A000255 (permutations with no substring [x,x+1]).
First column is A078481.

			Triangle starts:
[ 1]  1,
[ 2]  1, 0,
[ 3]  3, 0, 0,
[ 4]  7, 4, 0, 0,
[ 5]  19, 29, 5, 0, 0,
[ 6]  53, 180, 76, 0, 0, 0,
[ 7]  153, 1004, 901, 61, 0, 0, 0,
[ 8]  453, 5035, 8884, 2315, 0, 0, 0, 0,
[ 9]  1367, 23653, 74177, 46285, 2847, 0, 0, 0, 0,
[10]  4191, 106414, 546626, 667640, 143586, 0, 0, 0, 0, 0,
[11]  13015, 463740, 3658723, 7777935, 3896494, 209624, 0, 0, 0, 0, 0,
[12]  40857, 1972339, 22712736, 77535694, 74678363, 13959422, 0, 0, ...,
[13]  129441, 8228981, 132804891, 685673340, 1131199122, 485204757, 23767241, 0, ...,
...

Cf. A177267 (genus of all permutations).

Cf. A178514 (genus of derangements), A178515 (genus of involutions), A178516 (genus of up-down permutations), A178517 (genus of non-derangement permutations), A178518 (permutations of [n] having genus 0 and p(1)=k), A185209 (genus of connected permutations).

A177896 A binomial conjugate of the Narayana numbers.

Original entry on oeis.org

1, 1, 1, 2, 3, 1, 4, 9, 6, 1, 9, 26, 26, 10, 1, 21, 75, 100, 60, 15, 1, 51, 216, 360, 295, 120, 21, 1, 127, 623, 1246, 1295, 735, 217, 28, 1, 323, 1800, 4200, 5292, 3864, 1624, 364, 36, 1, 835, 5211, 13896, 20580, 18396, 10080, 3276, 576, 45, 1, 2188, 15115, 45345, 77190, 81690, 55314, 23730, 6150, 870, 55, 1

Offset: 0

Paul Barry, Dec 15 2010

Equals P^{-1}*N*P where P is A007318 and N is A001263.
First column is Motzkin numbers A001006. Row sums are A071356.
Diagonal sums are A078481.

			Triangle begins
1,
1, 1,
2, 3, 1,
4, 9, 6, 1,
9, 26, 26, 10, 1,
21, 75, 100, 60, 15, 1,
51, 216, 360, 295, 120, 21, 1,
127, 623, 1246, 1295, 735, 217, 28, 1,
323, 1800, 4200, 5292, 3864, 1624, 364, 36, 1

G.f.: ( 1-x(1+y)-sqrt(1-2x(1+y)+x^2(1+y)(y-3)) )/(2x^2(1+y));

G.f.: 1/(1-x-xy-x^2(1+y)/(1-x-xy-x^2(1+y)/(1-... (continued fraction).

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

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

A384685 Triangle read by rows: T(n,k) is the number of rooted ordered trees with node weights summing to n, where the root has weight 0, all internal nodes have weight 1, and leaf nodes have weights in {1,...,k}.

Views

Author

Keywords

Examples

Crossrefs

Programs

PARI

Formula

A120060 Triangle read by rows: T(n,k) is the number of Dyck n-paths (A000108) whose longest sawtooth has size k.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A218538 Triangle read by rows: T(n,k) is the number of permutations of{1,2,...,n} avoiding [x,x+1] having genus k (see first comment for definition of genus).

Views

Author

Keywords

Comments

Examples

Crossrefs

A177896 A binomial conjugate of the Narayana numbers.

Views

Author

Keywords

Comments

Examples

Formula