A217540 - OEIS

%I #23 Oct 24 2016 05:58:44

%S 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,

%T 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,

%U 6,0,1,0,0,1,21,112,245,301,266,197,128,80,39,26,6,7,0,1

%N 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.

%H Alois P. Heinz, <a href="/A217540/b217540.txt">Rows n = 0..100, flattened</a>

%H Peter Luschny, <a href="http://oeis.org/wiki/User:Peter_Luschny/OddsAndEnds#The_Scambler_statistic_on_Dyck_words">The Scambler_statistic_on_Dyck_words</a>.

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

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

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

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

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

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

%e [n\k] -8,-7,-6, -5,  -4,  -3,  -2,  -1,  0,   1,  2,  3,  4, 5, 6, 7, 8

%e -----------------------------------------------------------------------

%e [ 0 ]                                    1,

%e [ 1 ]                               0,   0,   1,

%e [ 2 ]                          0,   0,   1,   0,  1,

%e [ 3 ]                     0,   0,   1,   1,   2,  0,  1,

%e [ 4 ]                0,   0,   1,   3,   4,   2,  3,  0,  1,

%e [ 5 ]           0,   0,   1,   6,  10,   9,   8,  3,  4,  0, 1,

%e [ 6 ]       0,  0,   1,  10,  25,  30,  26,  17, 13,  4,  5, 0, 1,

%e [ 7 ]    0, 0,  1,  15,  56,  90,  90,  70,  49, 27, 19,  5, 6, 0, 1,

%e [ 8 ] 0, 0, 1, 21, 112, 245, 301, 266, 197, 128, 80, 39, 26, 6, 7, 0, 1

%e .

%e T(5, -2) = 6 counting the Dyck words

%e [1101011000] (()()(())) [1101100100] (()(())()) [1101101000] (()(()()))

%e [1110010100] ((())()()) [1110100100] ((()())()) [1110101000] ((()()())) .

%p b:= proc(x, y, t) option remember; `if`(y<0 or y>x, 0,

%p       `if`(x=0, z, expand(`if`(y=0, z, 1)*(b(x-1, y+1, true)

%p       +b(x-1, y-1, false)*`if`(t and y<>1, 1/z, 1)))))

%p     end:

%p T:= n-> `if`(n=0, 1, (p-> seq(coeff(p, z, i), i=-n..n))

%p                      (b(2*n-1, 1, true))):

%p seq(T(n), n=0..10);  # _Alois P. Heinz_, Jun 10 2014

%t 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_ *)

%o (Sage)

%o def A217540(n, k):

%o     def characteristic(d):

%o         count = 1

%o         h = d.heights()

%o         for i in (1..len(d)-1):

%o             if d[i-1]==1 and d[i]==0: count -= 1

%o             if h[i]==0: count +=1

%o             else:

%o                 if h[i-1]==0 and h[i+1]==0: count += 1

%o         return count

%o     if n == 0: return 1

%o     count = 0

%o     for d in DyckWords(n):

%o         if k == characteristic(d): count += 1

%o     return count

%o for n in (0..6): [A217540(n, k) for k in (-n..n)]

%K nonn,tabf

%O 0,14

%A _Peter Luschny_, Oct 21 2012