login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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). 5
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, by 1,2,..., n-1, n, n, n-1, ..., 2,1. The degree of asymmetry is defined to be 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 123321 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 has 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 an other 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

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

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

seq(seq(T(n, k), k=0..n-1), n=1..12);  # Alois P. Heinz, Feb 20 2018

CROSSREFS

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

Sequence in context: A303711 A154109 A011374 * A243319 A189230 A243982

Adjacent sequences:  A298642 A298643 A298644 * A298646 A298647 A298648

KEYWORD

nonn,tabl

AUTHOR

Emeric Deutsch, Feb 20 2018

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 21 06:55 EDT 2019. Contains 325192 sequences. (Running on oeis4.)