A092107 Triangle read by rows: T(n,k) is the number of Dyck paths of semilength n having exactly k UUU's (triple rises) where U=(1,1). Rows have 1,1,1,2,3,4,5,... entries, respectively.
1, 1, 2, 4, 1, 9, 4, 1, 21, 15, 5, 1, 51, 50, 24, 6, 1, 127, 161, 98, 35, 7, 1, 323, 504, 378, 168, 48, 8, 1, 835, 1554, 1386, 750, 264, 63, 9, 1, 2188, 4740, 4920, 3132, 1335, 390, 80, 10, 1, 5798, 14355, 17028, 12507, 6237, 2200, 550, 99, 11, 1, 15511, 43252, 57816
Offset: 0
Examples
T(5,2) = 5 because we have (U[UU)U]DUDDDD, (U[UU)U]DDUDDD, (U[UU)U]DDDUDD, (U[UU)U]DDDDUD and UD(U[UU)U]DDDD, where U=(1,1), D=(1,-1); the triple rises are shown between parentheses.
[1],[1],[2],[4, 1],[9, 4, 1],[21, 15, 5, 1],[51, 50, 24, 6, 1],[127, 161, 98, 35, 7, 1]
Triangle starts:
1;
1;
2;
4, 1;
9, 4, 1;
21, 15, 5, 1;
51, 50, 24, 6, 1;
127, 161, 98, 35, 7, 1;
323, 504, 378, 168, 48, 8, 1;
835, 1554, 1386, 750, 264, 63, 9, 1;
2188, 4740, 4920, 3132, 1335, 390, 80, 10, 1;
...
Links
- Alois P. Heinz, Rows n = 0..150, flattened
- Jean Luc Baril, Rigoberto Flórez, and José L. Ramirez, Generalized Narayana arrays, restricted Dyck paths, and related bijections, Univ. Bourgogne (France, 2025). See p. 14.
- Michael Bukata, Ryan Kulwicki, Nicholas Lewandowski, Lara Pudwell, Jacob Roth, and Teresa Wheeland, Distributions of Statistics over Pattern-Avoiding Permutations, arXiv:1812.07112 [math.CO], 2018.
- FindStat - Combinatorial Statistic Finder, The number of occurrences of the contiguous pattern [.,[.,[.,.]]].
- Lara Pudwell, On the distribution of peaks (and other statistics), 16th International Conference on Permutation Patterns, Dartmouth College, 2018.
- Toufik Mansour and Mark Shattuck, Counting occurrences of subword patterns in non-crossing partitions, Art Disc. Appl. Math. (2022).
- A. Sapounakis, I. Tasoulas and P. Tsikouras, Counting strings in Dyck paths, Discrete Math., 307 (2007), 2909-2924.
- Aristidis Sapounakis, Panagiotis Tsikouras, Ioannis Tasoulas, and Kostas Manes, Strings of Length 3 in Grand-Dyck Paths and the Chung-Feller Property, Electr. J. Combinatorics, 19 (2012), #P2.
- Yidong Sun, The statistic "number of udu's" in Dyck paths, Discrete Math., 287 (2004), 177-186.
Programs
-
Maple
b:= proc(x, y, t) option remember; `if`(y>x or y<0, 0, `if`(x=0, 1, expand(b(x-1, y-1, min(t+1,2))* `if`(t=2, z, 1) +b(x-1, y+1, 0)))) end: T:= n->(p->seq(coeff(p, z, i), i=0..degree(p)))(b(2*n, 0, 0)): seq(T(n), n=0..12); # Alois P. Heinz, Mar 11 2014 -
Mathematica
b[x_, y_, t_] := b[x, y, t] = If[y>x || y<0, 0, If[x == 0, 1, Expand[b[x-1, y-1, Min[t+1, 2]]*If[t == 2, z, 1] + b[x-1, y+1, 0]]]]; T[n_] := Function[{p}, Table[ Coefficient[p, z, i], {i, 0, Exponent[p, z]}]][b[2*n, 0, 0]]; Table[T[n], {n, 0, 12}] // Flatten (* Jean-François Alcover, Apr 29 2015, after Alois P. Heinz *)
Formula
G.f.: G(t, z) satisfies z(t+z-tz)G^2 - (1-z+tz)G + 1 = 0.
Sum_{k=0..n} T(n,k)*x^k = A001405(n), A001006(n), A000108(n), A033321(n) for x = -1, 0, 1, 2 respectively. - Philippe Deléham, Dec 10 2009
Comments