|
|
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.
|
|
4
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,14
|
|
LINKS
|
|
|
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))):
|
|
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 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
|
|
|
KEYWORD
|
nonn,tabf
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|