A298645 Triangle read by rows: T(n,k) is the number of Dyck paths of semilength n having degree of asymmetry k (n >= 1, 0 <= k <= n-1).

1, 2, 0, 3, 0, 2, 6, 0, 6, 2, 10, 0, 16, 8, 8, 20, 0, 40, 24, 32, 16, 35, 0, 90, 60, 108, 84, 52, 70, 0, 210, 150, 310, 294, 262, 134, 126, 0, 448, 336, 816, 880, 1008, 816, 432, 252, 0, 1008, 784, 2100, 2460, 3208, 3192, 2544, 1248, 462, 0, 2100, 1680, 5040, 6300, 9300, 10680, 10760, 8360, 4104

Offset: 1

Author

Emeric Deutsch, Feb 20 2018

Keywords

• nonn
• tabl

Comments

The degree of asymmetry of a Dyck path is defined in the following manner: we label the steps of a Dyck path of length 2n, from left to right, as 1, 2, ..., n-1, n, n, n-1, ..., 2, 1. The degree of asymmetry is defined as the number of pairs of identically labeled steps that are not at the same level. Example: the Dyck path uduudd has degree of asymmetry 2. Indeed, the labels are 1,2,3,3,2,1 and the steps labeled 2 are at different levels and those labeled 3 are also at different levels.

T(n,0) = A001405(n) = binomial(n, floor(n/2)) = number of symmetric Dyck paths of semilength n.

Sum of entries in row n = A000108(n) (the Catalan numbers).

Apparently, T(n,2) = 2*A191522(n).

Sum_{k=0..n-1} k*T(n,k) = A298646(n).

The Maple program needs to be improved. The initial m defines the number of rows. For m = 8 Maple 16 needs 10 secs; for m = 9 one needs 40 secs. For m>=10 one needs exponentially increasing hours!

In the Maple program: EL gives the levels of the elevated Dyck path; mg gives the levels of the merge of two Dyck paths; ME gives the levels of an elevated Dyck path merged with another Dyck path; Y[n] gives the levels of all the Catalan(n) Dyck paths of semilength n; r gives the reverse of a sequence; b gives the degree of asymmetry of a Dyck path; P(n) is the generating polynomial of the Dyck paths of semilength n with respect to the degree of asymmetry.

Examples

			Triangle begins:
    1;
    2, 0;
    3, 0,    2;
    6, 0,    6,   2;
   10, 0,   16,   8,    8;
   20, 0,   40,  24,   32,   16;
   35, 0,   90,  60,  108,   84,   52;
   70, 0,  210, 150,  310,  294,  262,  134;
  126, 0,  448, 336,  816,  880, 1008,  816,  432;
  252, 0, 1008, 784, 2100, 2460, 3208, 3192, 2544, 1248;
  ...
Row n = 3 is [3,0,2]. Indeed, showing the step levels, the Dyck paths 111111, 122221, 123321 are symmetric and each of the Dyck paths 111221, 122111 has degree of asymmetry 2.
		

Links

• Alois P. Heinz, Rows n = 1..141, flattened

Crossrefs

Cf. A000108, A001405, A191522, A298646, A298647.

Programs

Maple

m := 8: EL := proc (s) options operator, arrow: [1, seq(1+s[j], j = 1 .. nops(s)), 1] end proc: mg := proc (u, v) options operator, arrow: [seq(u[i], i = 1 .. nops(u)), seq(v[j], j = 1 .. nops(v))] end proc: ME := proc (u, v) options operator, arrow: mg(EL(u), v) end proc: Y[0] := {[]}: for n to m do Y[n] := {}: for p from 0 to n-1 do for q to nops(Y[p]) do for r to nops(Y[n-1-p]) do Y[n] := `union`(Y[n], {ME(Y[p][q], Y[n-1-p][r])}) end do end do end do end do: r := proc (s) options operator, arrow: [seq(s[nops(s)-j+1], j = 1 .. nops(s))] end proc: b := proc (s) local i, j: j := 0: for i to nops(s) do if 0 < abs((s-r(s))[i]) then j := j+1 else  end if end do: (1/2)*j end proc: P := proc (n) options operator, arrow: sort(add(t^b(Y[n][q]), q = 1 .. binomial(2*n, n)/(n+1))) end proc: T := proc (n, k) options operator, arrow: coeff(P(n), t, k) end proc: for n to m do seq(T(n, k), k = 0 .. n-1) end do;
# second Maple program:
b:= proc(x, y, v) option remember; expand(
      `if`(min(y, v, x-max(y, v))<0, 0, `if`(x=0, 1, (l-> add(add(
      `if`(y=v+(j-i)/2, 1, z)*b(x-1, y+i, v+j), i=l), j=l))([-1, 1]))))
    end:
g:= proc(n) option remember; add(b(n, j$2), j=0..n) end:
T:= (n, k)-> coeff(g(n), z, k):
seq(seq(T(n, k), k=0..n-1), n=1..12);  # Alois P. Heinz, Feb 20 2018

Mathematica

b[x_, y_, v_] := b[x, y, v] = Expand[If[Min[y, v, x - Max[y, v]] < 0, 0, If[x == 0, 1, Function[l, Sum[Sum[If[y == v + (j - i)/2, 1, z]*b[x - 1, y + i, v + j], {i, l}], {j, l}]][{-1, 1}]]]];
g[n_] := g[n] = Sum[b[n, j, j], {j, 0, n}];
T[n_, k_] := Coefficient[g[n], z, k];
Table[Table[T[n, k], {k, 0, n-1}], {n, 1, 12}] // Flatten (* Jean-François Alcover, Dec 07 2019, after Alois P. Heinz *)