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
Examples
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}
Links
- 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.
Programs
-
Mathematica
Table[n!(5n + 1)/4! + Floor[2/n](1/12), {n, 2, 10}]
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).
Extensions
First example and typo in second example corrected by Harlan J. Brothers, Apr 29 2013