A216118 Triangle read by rows: T(n,k) is the number of stretching pairs in all permutations in S_{n,k} (=set of permutations in S_n with k cycles) (n >= 3; 1 <= k <= n-2).

0, 1, 1, 10, 15, 5, 90, 165, 90, 15, 840, 1750, 1225, 350, 35, 8400, 19180, 15750, 5950, 1050, 70, 90720, 222264, 204624, 92610, 22050, 2646, 126, 1058400, 2744280, 2757720, 1421490, 411600, 67620, 5880, 210, 13305600, 36162720, 38980920, 22203720, 7408170, 1496880, 180180, 11880, 330

Offset: 3

Author

Emeric Deutsch, Feb 26 2013

Keywords

• nonn
• tabl

Comments

A stretching pair of a permutation p in S_n is a pair (i,j) (1 <= i < j <= n) satisfying p(i) < i < j < p(j). For example, for the permutation 31254 in S_5 the pair (2,4) is stretching because 1< p(2) < 2 < 4 < p(4) = 5.

Number of entries in row n (n >= 3) is n - 2.

Sum of entries in row n is A216119(n).

T(n,1) = A061206(n-3).

Examples

			T(4,1) = 1, T(4,2) = 1 because 22 permutations in S_4 have no stretching pairs, the 1-cycle 3142 has the stretching pair (2,3) and the 2-cycle 2143 has the stretching pair (2,3).
Triangle starts:
    0;
    1,    1;
   10,   15,    5;
   90,  165,   90,  15;
  840, 1750, 1225, 350, 35;
  ...
		

References

• E. Lundberg and B. Nagle, A permutation statistic arising in dynamics of internal maps. (submitted)

Links

• Muniru A Asiru, Rows n=3..100 of triangle, flattened
• E. Clark and R. Ehrenborg, Explicit expressions for the extremal excedance statistic, European J. Combinatorics, 31, 2010, 270-279.
• J. Cooper, E. Lundberg, and B. Nagle, Generalized pattern frequency in large permutations, Electron. J. Combin. 20, 2013, #P28.

Crossrefs

Cf. A216119, A061206.

Programs

GAP

List([3..12],n->List([1..n-2],k->Binomial(n,4)*Stirling1(n-2,k))); # Muniru A Asiru, Dec 13 2018

Magma

[[(-1)^(n-k)*Binomial(n,4)*StirlingFirst(n-2,k): k in [1..n-2]]: n in [3..12]]; // G. C. Greubel, Dec 13 2018

Maple

with(combinat): T := proc (n, k) options operator, arrow: binomial(n, 4)*abs(stirling1(n-2, k)) end proc: for n from 3 to 12 do seq(T(n, k), k = 1 .. n-2) end do; # yields sequence in triangular form

Mathematica

T[n_, k_] := Binomial[n, 4] * Abs[StirlingS1[n-2, k]]; Table[T[n, k], {n, 3, 12}, {k, 1, n-2}] // Flatten (* Amiram Eldar, Dec 13 2018 *)

PARI

{T(n,k) = (-1)^(n-k)*binomial(n,4)*stirling(n-2,k,1)};
for(n=3, 10, for(k=1,n-2, print1(T(n,k), ", "))) \\ G. C. Greubel, Dec 13 2018

Sage

[[binomial(n,4)*stirling_number1(n-2,k) for k in (1..n-2)] for n in (3..12)] # G. C. Greubel, Dec 13 2018

Formula

T(n,k) = binomial(n,4)*abs(Stirling1(n-2,k)).

T(n,k) = binomial(n,4)*(-1)^(n-k)*Stirling1(n-2,k).