A141052 Number of runs or rising sequences of length 2 among all permutations of n.

1, 4, 21, 130, 930, 7560, 68880, 695520, 7711200, 93139200, 1217462400, 17124307200, 257902444800, 4140968832000, 70614415872000, 1274546617344000, 24275666967552000, 486580401635328000, 10238462617743360000, 225651661258383360000, 5198503365971435520000

Offset

2,2

Links

Table of n, a(n) for n=2..22.

Persi Diaconis, Mathematical developments from the analysis of riffle shuffling, p. 4.

Francis Edward Su, Rising Sequences in Card Shuffling

Charles M. Grinstead and J. Laurie Snell, Introduction to Probability, American Mathematical Society, 1997, pp.120-131.

Formula

a(n) = n!*(5n+1)/4! + floor(2/n)*(1/12), n>=2.

Recurrence: a(n) = (n+1)*a(n-1)+(n-1)!/6, n>=2, with a(2)=1 and a(3)=4.

E.g.f.: x^2*(x-2)*(x-6)/(24*(x-1)^2).

Example

a[3]=4 because of the 6 permutations of n=3, there are 4 ascending runs of length 2:
{1,3} in {1,3,2}
{1,3} in {2,1,3}
{2,3} in {2,3,1}
{1,2} in {3,1,2}
a[3]=4 because of the 6 permutations of n=3, there are 4 rising sequences of length 2:
{1,2} in {1,3,2}
{2,3} in {2,1,3}
{2,3} in {2,3,1}
{1,2} in {3,1,2}

Mathematica

Table[n!(5n + 1)/4! + Floor[2/n](1/12), {n, 2, 10}]

Crossrefs

Column 2 of A122843.

Cf. A008292, A097900, A001286, A001048, A000142, A028387, A001710.

Sequence in context: A232956 A234268 A111177 * A058308 A078591 A090366

Adjacent sequences: A141049 A141050 A141051 * A141053 A141054 A141055

Keyword

easy,nonn

Author

Harlan J. Brothers, Jul 31 2008, Aug 24 2008

Extensions

First example and typo in second example corrected by Harlan J. Brothers, Apr 29 2013

Status

approved