A216120 -id:A216120 - cp's OEIS frontend

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

Emeric Deutsch, Feb 26 2013

nonn

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.

			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.

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

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.

Cf. A005461, A216118, A216120.

Cf. A001113, A001620, A091725, A099285.

Concatenation([0],List([2..22],n->Factorial(n)*(n-2)*(n-3)/24)); # Muniru A Asiru, Nov 29 2018

[Factorial(n)*(n-2)*(n-3) div 24: n in [1..30]]; // Vincenzo Librandi, Nov 29 2018

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

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

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

A216121 Irregular triangle read by rows: T(n,k) is the number of permutations in C_n (= the 1-cycles in S_n) having k stretching pairs.

Original entry on oeis.org

1, 1, 2, 5, 1, 16, 6, 2, 63, 31, 20, 5, 1, 294, 168, 150, 70, 30, 6, 2, 1585, 997, 1072, 691, 423, 171, 75, 20, 5, 1, 9692, 6522, 7882, 6176, 4744, 2612, 1598, 656, 300, 100, 30, 6, 2, 66275, 46891, 61356, 54561, 49013, 32689, 24285, 13429, 7812, 3795, 1759, 651, 263, 75, 20, 5, 1

Offset: 1

Emeric Deutsch, Feb 26 2013

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.
Sum of entries in row n is (n-1)! = A000142(n-1).
T(n,0) = A136127(n-1).
Sum_{k>=1} k*T(n,k) = n!*(n-3)/24 = A061206(n-3).

			T(4,1) = 1 because 3142 has 1 stretching pair (2,3); the other five 1-cycles in S_4 have no stretching pairs.
Triangle starts:
    1;
    1;
    2;
    5,   1;
   16,   6,   2;
   63,  31,  20,  5,  1;
  294, 168, 150, 70, 30, 6, 2;
  ...

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

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.

Cf. A136127, A000142, A061206, A216120.

n := 7: with(combinat): nrcyc := proc (p) local nrfp, pc: nrfp := proc (p) local ct, j: ct := 0: for j to nops(p) do if p[j] = j then ct := ct+1 else  end if end do: ct end proc: pc := convert(p, disjcyc): nops(pc)+nrfp(p) end proc: nrcyc := proc (p) local nrfp, pc: nrfp := proc (p) local ct, j: ct := 0: for j to nops(p) do if p[j] = j then ct := ct+1 else  end if end do: ct end proc: pc := convert(p, disjcyc): nops(pc)+nrfp(p) end proc: sp := proc (p) local ct, i, j: ct := 0: for i from 2 to nops(p)-2 do for j from i+1 to nops(p)-1 do if p[i] < i and i < j and j < p[j] then ct := ct+1 else  end if end do end do: ct end proc: P[n] := permute(n): C[n] := {}: for j to factorial(n) do if nrcyc(P[n][j]) = 1 then C[n] := `union`(C[n], {P[n][j]}) else  end if end do: sort(add(t^sp(C[n][j]), j = 1 .. factorial(n-1)));

The values of T(n,k) have been found by straightforward counting (with Maple). The Maple program (improvable!) yields the generating polynomial of the specified row n. Within the program, sp(p) is the number of stretching pairs of the permutation p.

More terms from Alois P. Heinz, Apr 15 2017

cp's OEIS Frontend

A216119 Number of stretching pairs in all permutations in S_n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

Formula