login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A216120 Irregular triangle read by rows: T(n,k) is the number of permutations in S_n having k stretching pairs. 2
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

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! = A000142(n).

Sum(k*T(n,k), k>=1) = A216119(n).

REFERENCES

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

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

MAPLE

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

CROSSREFS

Cf. A000142, A216119, A216121.

Sequence in context: A156155 A263486 A182544 * A216964 A187250 A129534

Adjacent sequences:  A216117 A216118 A216119 * A216121 A216122 A216123

KEYWORD

nonn,tabf

AUTHOR

Emeric Deutsch, Feb 26 2013

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 15 13:54 EST 2019. Contains 329149 sequences. (Running on oeis4.)