A217540 Scambler statistic on Dyck paths. Triangle T(n, k) read by rows, n >= 0, -n <= k <= n, T(n, k) is the number of Dyck paths of semilength n and k = number of returns + number of hills - number of peaks.

1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 2, 0, 1, 0, 0, 1, 3, 4, 2, 3, 0, 1, 0, 0, 1, 6, 10, 9, 8, 3, 4, 0, 1, 0, 0, 1, 10, 25, 30, 26, 17, 13, 4, 5, 0, 1, 0, 0, 1, 15, 56, 90, 90, 70, 49, 27, 19, 5, 6, 0, 1, 0, 0, 1, 21, 112, 245, 301, 266, 197, 128, 80, 39, 26, 6, 7, 0, 1

Offset

0,14

Links

Alois P. Heinz, Rows n = 0..100, flattened

Peter Luschny, The Scambler_statistic_on_Dyck_words.

Formula

T(n,-1) = A014531(n-2) = [0,0,0],1,3,10,30,90,...

T(n, 0) = A113682(n-2) = [1,0],1,1,4,9,26,70,197,...

T(n, 1) = A194588(n-1) = [0],1,0,2,2,8,17,49,128,...

Sum(k>=0,T(n,k)) = A189912(n-1) = [1],1,2,4,10,25, 66,177,..

Sum(k< 0,T(n,k)) = A217539(n) = 0,0,0,1, 4,17, 66,252,..

Sum(-n<=k<=n,T(n,k)) = A000108(n) = 1,1,2,5,14,42,132,429,..

Example

[n\k] -8,-7,-6, -5,  -4,  -3,  -2,  -1,  0,   1,  2,  3,  4, 5, 6, 7, 8
-----------------------------------------------------------------------
[ 0 ]                                    1,
[ 1 ]                               0,   0,   1,
[ 2 ]                          0,   0,   1,   0,  1,
[ 3 ]                     0,   0,   1,   1,   2,  0,  1,
[ 4 ]                0,   0,   1,   3,   4,   2,  3,  0,  1,
[ 5 ]           0,   0,   1,   6,  10,   9,   8,  3,  4,  0, 1,
[ 6 ]       0,  0,   1,  10,  25,  30,  26,  17, 13,  4,  5, 0, 1,
[ 7 ]    0, 0,  1,  15,  56,  90,  90,  70,  49, 27, 19,  5, 6, 0, 1,
[ 8 ] 0, 0, 1, 21, 112, 245, 301, 266, 197, 128, 80, 39, 26, 6, 7, 0, 1
.
T(5, -2) = 6 counting the Dyck words
[1101011000] (()()(())) [1101100100] (()(())()) [1101101000] (()(()()))
[1110010100] ((())()()) [1110100100] ((()())()) [1110101000] ((()()())) .

Maple

b:= proc(x, y, t) option remember; `if`(y<0 or y>x, 0,
      `if`(x=0, z, expand(`if`(y=0, z, 1)*(b(x-1, y+1, true)
      +b(x-1, y-1, false)*`if`(t and y<>1, 1/z, 1)))))
    end:
T:= n-> `if`(n=0, 1, (p-> seq(coeff(p, z, i), i=-n..n))
                     (b(2*n-1, 1, true))):
seq(T(n), n=0..10);  # Alois P. Heinz, Jun 10 2014

Mathematica

b[x_, y_, t_] := b[x, y, t] = If[y<0 || y>x, 0, If[x == 0, z, Expand[If[y == 0, z, 1]*(b[x-1, y+1, True]+b[x-1, y-1, False]*If[t && y != 1, 1/z, 1])]]]; T[n_] := If[n == 0, 1, Function[p, Table[Coefficient[p, z, i], {i, -n, n}]][b[2*n-1, 1, True]]]; Table[T[n], {n, 0, 10}] // Flatten (* Jean-François Alcover, Oct 24 2016, after Alois P. Heinz *)

Prog

(Sage)
def A217540(n, k):
    def characteristic(d):
        count = 1
        h = d.heights()
        for i in (1..len(d)-1):
            if d[i-1]==1 and d[i]==0: count -= 1
            if h[i]==0: count +=1
            else:
                if h[i-1]==0 and h[i+1]==0: count += 1
        return count
    if n == 0: return 1
    count = 0
    for d in DyckWords(n):
        if k == characteristic(d): count += 1
    return count
for n in (0..6): [A217540(n, k) for k in (-n..n)]

Crossrefs

Sequence in context: A144628 A286604 A366784 * A226861 A185643 A363051

Adjacent sequences: A217537 A217538 A217539 * A217541 A217542 A217543

Keyword

nonn,tabf

Author

Peter Luschny, Oct 21 2012

Status

approved