A140717 Triangle read by rows: T(n,k) is the number of Dyck paths d of semilength n such that sum of peakheights of d - number of peaks of d = k (n >= 0, 0 <= k <= floor(n^2/4)).
1, 1, 1, 1, 1, 2, 2, 1, 3, 5, 4, 1, 1, 4, 9, 12, 10, 4, 2, 1, 5, 14, 25, 31, 26, 16, 9, 4, 1, 1, 6, 20, 44, 70, 82, 74, 54, 38, 22, 12, 4, 2, 1, 7, 27, 70, 134, 196, 227, 215, 179, 139, 99, 64, 38, 20, 9, 4, 1, 1, 8, 35, 104, 231, 400, 558, 644, 641, 576, 488, 384, 288, 200, 134, 80
Offset: 0
Examples
T(4,2) = 5 because we have UDUUDUDD (5 - 3 = 2), UDUUUDD (4 - 2 = 2), UUDDUUDD (4 - 2 = 2), UUDUDDUD (5 - 3 = 2) and UUUDDDUD (4 - 2 = 2); here U = (1,1), D = (1,-1). Triangle starts: 1; 1; 1, 1; 1, 2, 2; 1, 3, 5, 4, 1; 1, 4, 9, 12, 10, 4, 2; 1, 5, 14, 25, 31, 26, 16, 9, 4, 1;
Links
- Alois P. Heinz, Rows n = 0..50, flattened
- E. Barcucci, A. Del Lungo, E. Pergola and R. Pinzani, ECO: a methodology for the enumeration of combinatorial objects, Journal of Difference Equations and Applications, 5, 1999, 435-490.
- E. Barcucci, A. Del Lungo, E. Pergola and R. Pinzani, Some permutations with forbidden subsequences and their inversion number, Discrete Math., 234, 2001, 1-15.
- Emeric Deutsch, Dyck path enumeration, Discrete Math., 204, 1999, 167-202 (see section 5).
- G. Feinberg and K.-H. Lee, Homogeneous representations of KLR-algebras and fully commutative elements, arXiv preprint arXiv:1401.0845 [math.RT], 2014-2015.
- Niket Gowravaram and Tanya Khovanova, On the Structure of nil-Temperley-Lieb Algebras of type A, arXiv:1509.00462 [math.CO], 2015.
Programs
-
Maple
H := 1/(1+z-t*x*z-z*h[1]): for n to 13 do h[n]:=1/(1+z-x*t^(n+1)*z-z*h[n+1]) end do: G := subs({h[11]=0,x=1/t},H): Gser := simplify(series(G,z=0,12)): for n from 0 to 9 do P[n] := sort(coeff(Gser,z,n)) end do: for n from 0 to 9 do seq(coeff(P[n],t,j), j=0..floor((1/4)*n^2)) end do; # yields sequence in triangular form -
Mathematica
m = rows = 10; mt = 2 m + 1; mx = mz = m - 1; H[, , ] = 0; Do[H[t, x_, z_] = Series[1 + z (H[t, t x, z] - 1 + t x) H[t, x, z], {t, 0, mt}, {x, 0, mx}, {z, 0, mz}] // Normal, {m}]; G[t_, z_] = Series[H[t, 1/t, z], {t, 0, mt}, {z, 0, mz}] // Normal // Collect[#, z]&; CoefficientList[#, t]& /@ CoefficientList[G[t, z], z] // Take[#, m]& // Flatten (* Jean-François Alcover, Nov 25 2018 *)
Formula
G.f.: G(t,z) = H(t,1/t,z), where H(t,x,z) = 1 + zH(t,x,z)[H(t,tx,z)-1+tx] (H(t,x,z) is the trivariate g.f. of Dyck paths with respect to semilength, sum of peak-heights and number of peaks, marked by z, t and x, respectively).
Sum_{k>=0} k*T(n,k) = A008549(n-1).
Row n has 1 + floor(n^2/4) entries.
Conjecture: n-th row polynomial equals t_n for n > 0 where we start with vector v of fixed length m with elements v_i = 1, then set t = v and for i=1..m-1, for j=i+1..m apply [v_i, v_j] := [v_i + z^(j-i)*v_j, z*v_i + v_j] (here square brackets mean that instead of sequentially assigning v_i and then v_j, we reserve their values (for example, as A = v_i, B = v_j) and then assign them in any order) and t_{i+1} := v_{i+1} (after ending each cycle for j). It also looks like that if we change z^(j-i) to z^(2*(j-i)) it gives us equivalence of t_n and n-th row polynomial of A227543. - Mikhail Kurkov, Aug 30 2024
Comments