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.

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,3

Comments

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

References

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

Links

Table of n, a(n) for n=1..60.

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.

Formula

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.

Example

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

Maple

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

Crossrefs

Cf. A136127, A000142, A061206, A216120.

Sequence in context: A185140 A111797 A122104 * A104546 A121632 A186361

Adjacent sequences: A216118 A216119 A216120 * A216122 A216123 A216124

Keyword

nonn,tabf

Author

Emeric Deutsch, Feb 26 2013

Extensions

More terms from Alois P. Heinz, Apr 15 2017

Status

approved