A216119 -id:A216119 - cp's OEIS frontend

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

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 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).

			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;
  ...

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

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.

Cf. A216119, A061206.

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

[[(-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

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

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 *)

{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

[[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

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

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

A216120 Irregular triangle read by rows: T(n,k) is the number of permutations in S_n having k stretching pairs.

Original entry on oeis.org

1, 2, 6, 22, 2, 94, 22, 4, 462, 172, 72, 12, 2, 2582, 1244, 824, 276, 94, 16, 4, 16214, 9126, 8016, 3996, 1990, 660, 248, 56, 12, 2, 113166, 70482, 74220, 48012, 30898, 14372, 7520, 2720, 1068, 318, 84, 16, 4, 869662, 581264, 690744, 534000, 414532, 239704, 156440, 75668, 39256, 16952, 7032, 2384, 868, 224, 56, 12, 2

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! = A000142(n).
Sum(k*T(n,k), k>=1) = A216119(n).

			T(4,1) = 2 because 2143 has 1 stretching pair (2,3) and 3142 has 1 stretching pair (2,3); the other 22 permutations in S_4 have no stretching pairs.
Triangle starts:
1;
2;
6;
22,      2;
94,     22,   4;
462,   172,  72,  12,  2;
2582, 1244, 824, 276, 94, 16, 4;

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

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. A000142, A216119, A216121.

n := 7: with(combinat): 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 := permute(n): f[n] := sort(add(t^sp(P[j]), j = 1 .. factorial(n)));

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

cp's OEIS Frontend

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).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

Sage

Formula