A143946 Triangle read by rows: T(n,k) is the number of permutations of [n] for which the sum of the positions of the left-to-right maxima is k (1 <= k <= n(n+1)/2).
1, 1, 0, 1, 2, 0, 2, 1, 0, 1, 6, 0, 6, 3, 2, 3, 2, 1, 0, 1, 24, 0, 24, 12, 8, 18, 8, 10, 3, 6, 3, 2, 1, 0, 1, 120, 0, 120, 60, 40, 90, 64, 50, 39, 42, 23, 28, 13, 10, 8, 6, 3, 2, 1, 0, 1, 720, 0, 720, 360, 240, 540, 384, 420, 234, 372, 198, 208, 168, 124, 98, 75, 60, 35, 34, 13, 16, 8, 6, 3
Offset: 1
Examples
T(4,6)=3 because we have 1243, 1342 and 2341 with left-to-right maxima at positions 1,2,3. Triangle starts: 1; 1, 0, 1; 2, 0, 2, 1, 0, 1; 6, 0, 6, 3, 2, 3, 2, 1, 0, 1; 24, 0, 24, 12, 8, 18, 8, 10, 3, 6, 3, 2, 1, 0, 1; ...
Links
- Alois P. Heinz, Rows n = 1..50, flattened
- I. Kortchemski, Asymptotic behavior of permutation records, arXiv: 0804.0446 [math.CO], 2008-2009.
Programs
-
Maple
P:=proc(n) options operator, arrow: sort(expand(product(t^j+j-1,j=1..n))) end proc: for n to 7 do seq(coeff(P(n),t,i),i=1..(1/2)*n*(n+1)) end do; # yields sequence in triangular form # second Maple program: b:= proc(n) option remember; `if`(n=0, 1, expand(b(n-1)*(x^n+n-1))) end: T:= n-> (p-> seq(coeff(p, x, i), i=1..degree(p)))(b(n)): seq(T(n), n=1..7); # Alois P. Heinz, Aug 05 2020 -
Mathematica
row[n_] := CoefficientList[Product[t^k + k - 1, {k, 1, n}], t] // Rest; Array[row, 7] // Flatten (* Jean-François Alcover, Nov 28 2017 *)
Formula
T(n,1) = T(n,3) = (n-1)! for n>=2.
Sum_{k=1..n*(n+1)/2} k * T(n,k) = n! * n = A001563(n).
Generating polynomial of row n is t(t^2+1)(t^3+2)...(t^n+n-1).
Sum_{k=1..n*(n+1)/2} (n*(n+1)/2-k) * T(n,k) = A001804(n). - Alois P. Heinz, Dec 19 2023
Comments