A216119 Number of stretching pairs in all permutations in S_n.

0, 0, 0, 2, 30, 360, 4200, 50400, 635040, 8467200, 119750400, 1796256000, 28540512000, 479480601600, 8499883392000, 158664489984000, 3112264995840000, 64023737057280000, 1378644471300096000, 31019500604252160000, 728045925946859520000, 17796678189812121600000

Offset

1,4

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 p(2) = 1 < 2 < 4 < p(4) = 5.

References

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

Links

Vincenzo Librandi, Table of n, a(n) for n = 1..450

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), Article P28.

Formula

a(n) = n!*(n-2)*(n-3)/24.

a(n) = 2*A005461(n-3).

a(n) = Sum_{k>=1} A216118(k).

a(n) = Sum_{k>=1} k*A216120(n,k).

From Amiram Eldar, May 06 2022: (Start)

Sum_{n>=4} 1/a(n) = 8*(gamma - Ei(1)) + 8*e - 32/3, where gamma = A001620, Ei(1) = A091725, and e = A001113.

Sum_{n>=4} (-1)^n/a(n) = 16*(gamma - Ei(-1)) - 8/e - 28/3, where Ei(-1) = -A099285. (End)

D-finite with recurrence a(n) +(-n-10)*a(n-1) +4*(2*n+3)*a(n-2) +12*(-n+2)*a(n-3)=0. - R. J. Mathar, Jul 26 2022

Example

a(4) = 2 because 2143 has 1 stretching (namely (2,3)), 3142 has 1 stretching pair (namely (2,3)), and the other 22 permutations in S_4 have no stretching pairs.

Maple

0, seq((1/24)*factorial(n)*(n-2)*(n-3), n = 2 .. 22);

Mathematica

Join[{0}, Table[n! (n - 2) (n - 3) / 24, {n, 2, 30}]] (* Vincenzo Librandi, Nov 29 2018 *)

Prog

(Magma) [Factorial(n)*(n-2)*(n-3) div 24: n in [1..30]]; // Vincenzo Librandi, Nov 29 2018
(GAP) Concatenation([0], List([2..22], n->Factorial(n)*(n-2)*(n-3)/24)); # Muniru A Asiru, Nov 29 2018

Crossrefs

Cf. A005461, A216118, A216120.

Cf. A001113, A001620, A091725, A099285.

Sequence in context: A152277 A230610 A231597 * A083446 A230726 A091345

Adjacent sequences: A216116 A216117 A216118 * A216120 A216121 A216122

Keyword

nonn

Author

Emeric Deutsch, Feb 26 2013

Status

approved