|
| |
|
|
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).
|
|
6
|
|
|
|
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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
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).
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.
|
|
|
LINKS
|
|
|
|
EXAMPLE
|
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.
|
|
|
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):
|
|
|
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];
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
