cp's OEIS Frontend

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.

%I A216121 #19 Dec 01 2018 08:58:40
%S A216121 1,1,2,5,1,16,6,2,63,31,20,5,1,294,168,150,70,30,6,2,1585,997,1072,
%T A216121 691,423,171,75,20,5,1,9692,6522,7882,6176,4744,2612,1598,656,300,100,
%U A216121 30,6,2,66275,46891,61356,54561,49013,32689,24285,13429,7812,3795,1759,651,263,75,20,5,1
%N 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.
%C A216121 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 A216121 Sum of entries in row n is (n-1)! = A000142(n-1).
%C A216121 T(n,0) = A136127(n-1).
%C A216121 Sum_{k>=1} k*T(n,k) = n!*(n-3)/24 = A061206(n-3).
%D A216121 E. Lundberg and B. Nagle, A permutation statistic arising in dynamics of internal maps. (submitted)
%H A216121 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 A216121 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 A216121 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.
%e A216121 T(4,1) = 1 because 3142 has 1 stretching pair (2,3); the other five 1-cycles in S_4 have no stretching pairs.
%e A216121 Triangle starts:
%e A216121     1;
%e A216121     1;
%e A216121     2;
%e A216121     5,   1;
%e A216121    16,   6,   2;
%e A216121    63,  31,  20,  5,  1;
%e A216121   294, 168, 150, 70, 30, 6, 2;
%e A216121   ...
%p A216121 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)));
%Y A216121 Cf. A136127, A000142, A061206, A216120.
%K A216121 nonn,tabf
%O A216121 1,3
%A A216121 _Emeric Deutsch_, Feb 26 2013
%E A216121 More terms from _Alois P. Heinz_, Apr 15 2017