|
%I #41 Dec 07 2019 02:59:10
%S 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,
%T 52,70,0,210,150,310,294,262,134,126,0,448,336,816,880,1008,816,432,
%U 252,0,1008,784,2100,2460,3208,3192,2544,1248,462,0,2100,1680,5040,6300,9300,10680,10760,8360,4104
%N 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).
%C 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.
%C T(n,0) = A001405(n) = binomial(n, floor(n/2)) = number of symmetric Dyck paths of semilength n.
%C Sum of entries in row n = A000108(n) (the Catalan numbers).
%C Apparently, T(n,2) = 2*A191522(n).
%C Sum_{k=0..n-1} k*T(n,k) = A298646(n).
%C 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!
%C 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.
%H Alois P. Heinz, <a href="/A298645/b298645.txt">Rows n = 1..141, flattened</a>
%e Triangle begins:
%e 1;
%e 2, 0;
%e 3, 0, 2;
%e 6, 0, 6, 2;
%e 10, 0, 16, 8, 8;
%e 20, 0, 40, 24, 32, 16;
%e 35, 0, 90, 60, 108, 84, 52;
%e 70, 0, 210, 150, 310, 294, 262, 134;
%e 126, 0, 448, 336, 816, 880, 1008, 816, 432;
%e 252, 0, 1008, 784, 2100, 2460, 3208, 3192, 2544, 1248;
%e ...
%e 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.
%p 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;
%p # second Maple program:
%p b:= proc(x, y, v) option remember; expand(
%p `if`(min(y, v, x-max(y, v))<0, 0, `if`(x=0, 1, (l-> add(add(
%p `if`(y=v+(j-i)/2, 1, z)*b(x-1, y+i, v+j), i=l), j=l))([-1, 1]))))
%p end:
%p g:= proc(n) option remember; add(b(n, j$2), j=0..n) end:
%p T:= (n, k)-> coeff(g(n), z, k):
%p seq(seq(T(n, k), k=0..n-1), n=1..12); # _Alois P. Heinz_, Feb 20 2018
%t 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}]]]];
%t g[n_] := g[n] = Sum[b[n, j, j], {j, 0, n}];
%t T[n_, k_] := Coefficient[g[n], z, k];
%t Table[Table[T[n, k], {k, 0, n-1}], {n, 1, 12}] // Flatten (* _Jean-François Alcover_, Dec 07 2019, after _Alois P. Heinz_ *)
%Y Cf. A000108, A001405, A191522, A298646, A298647.
%K nonn,tabl
%O 1,2
%A _Emeric Deutsch_, Feb 20 2018
|
