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

Author

Peter Luschny, Oct 21 2012

Keywords

• nonn
• tabf

Examples

			[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] ((()()())) .
		

Links

• Alois P. Heinz, Rows n = 0..100, flattened
• Peter Luschny, The Scambler_statistic_on_Dyck_words.

Programs

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

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

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,..