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

%I #22 Nov 23 2023 16:25:30

%S 1,4,21,130,930,7560,68880,695520,7711200,93139200,1217462400,

%T 17124307200,257902444800,4140968832000,70614415872000,

%U 1274546617344000,24275666967552000,486580401635328000,10238462617743360000,225651661258383360000,5198503365971435520000

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

%H Persi Diaconis, <a href="http://www-stat.stanford.edu/~cgates/PERSI/papers/Riffle.pdf">Mathematical developments from the analysis of riffle shuffling</a>, p. 4.

%H Francis Edward Su, <a href="http://www.math.hmc.edu/funfacts/ffiles/20001.4-6.shtml">Rising Sequences in Card Shuffling</a>

%H Charles M. Grinstead and J. Laurie Snell, <a href="http://www.dartmouth.edu/~chance/teaching_aids/books_articles/probability_book/book.html">Introduction to Probability</a>, American Mathematical Society, 1997, pp.120-131.

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

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

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

%e a[3]=4 because of the 6 permutations of n=3, there are 4 ascending runs of length 2:

%e {1,3} in {1,3,2}

%e {1,3} in {2,1,3}

%e {2,3} in {2,3,1}

%e {1,2} in {3,1,2}

%e a[3]=4 because of the 6 permutations of n=3, there are 4 rising sequences of length 2:

%e {1,2} in {1,3,2}

%e {2,3} in {2,1,3}

%e {2,3} in {2,3,1}

%e {1,2} in {3,1,2}

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

%Y Column 2 of A122843.

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

%K easy,nonn

%O 2,2

%A _Harlan J. Brothers_, Jul 31 2008, Aug 24 2008

%E First example and typo in second example corrected by _Harlan J. Brothers_, Apr 29 2013