A216119 - OEIS

%I #28 Jul 26 2022 13:08:59

%S 0,0,0,2,30,360,4200,50400,635040,8467200,119750400,1796256000,

%T 28540512000,479480601600,8499883392000,158664489984000,

%U 3112264995840000,64023737057280000,1378644471300096000,31019500604252160000,728045925946859520000,17796678189812121600000

%N Number of stretching pairs in all permutations in S_n.

%C 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.

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

%H Vincenzo Librandi, <a href="/A216119/b216119.txt">Table of n, a(n) for n = 1..450</a>

%H E. Clark and R. Ehrenborg, <a href="http://dx.doi.org/10.1016/j.ejc.2008.11.014">Explicit expressions for the extremal excedance statistic</a>, European J. Combinatorics, 31 (2010), 270-279.

%H J. Cooper, E. Lundberg, and B. Nagle, <a href="https://doi.org/10.37236/2692">Generalized pattern frequency in large permutations</a>, Electron. J. Combin., 20, (2013), Article P28.

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

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

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

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

%F From _Amiram Eldar_, May 06 2022: (Start)

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

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

%F 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

%e 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.

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

%t Join[{0}, Table[n! (n - 2) (n - 3) / 24, {n, 2, 30}]] (* _Vincenzo Librandi_, Nov 29 2018 *)

%o (Magma) [Factorial(n)*(n-2)*(n-3) div 24: n in [1..30]]; // _Vincenzo Librandi_, Nov 29 2018

%o (GAP) Concatenation([0],List([2..22],n->Factorial(n)*(n-2)*(n-3)/24)); # _Muniru A Asiru_, Nov 29 2018

%Y Cf. A005461, A216118, A216120.

%Y Cf. A001113, A001620, A091725, A099285.

%K nonn

%O 1,4

%A _Emeric Deutsch_, Feb 26 2013