OFFSET
2,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.
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
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