cp's OEIS Frontend

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

%I A216120 #18 Nov 29 2018 10:35:47
%S A216120 1,2,6,22,2,94,22,4,462,172,72,12,2,2582,1244,824,276,94,16,4,16214,
%T A216120 9126,8016,3996,1990,660,248,56,12,2,113166,70482,74220,48012,30898,
%U A216120 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
%N A216120 Irregular triangle read by rows: T(n,k) is the number of permutations in S_n having k stretching pairs.
%C A216120 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.
%C A216120 Sum of entries in row n is n! = A000142(n).
%C A216120 Sum(k*T(n,k), k>=1) = A216119(n).
%D A216120 E. Lundberg and B. Nagle, A permutation statistic arising in dynamics of internal maps. (submitted, 2013)
%H A216120 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 A216120 J. Cooper, E. Lundberg, and B. Nagle, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v20i1p28">Generalized pattern frequency in large permutations</a>, Electron. J. Combin. 20, 2013, #P28.
%F A216120 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.
%e A216120 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.
%e A216120 Triangle starts:
%e A216120 1;
%e A216120 2;
%e A216120 6;
%e A216120 22,      2;
%e A216120 94,     22,   4;
%e A216120 462,   172,  72,  12,  2;
%e A216120 2582, 1244, 824, 276, 94, 16, 4;
%p A216120 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)));
%Y A216120 Cf. A000142, A216119, A216121.
%K A216120 nonn,tabf
%O A216120 1,2
%A A216120 _Emeric Deutsch_, Feb 26 2013