OFFSET
1,3
COMMENTS
It appears that a(n) = n*a(n-1) + 2(-1)^(n+1) and that the n-th term of any sequence of the form {A(0) =a, A(1)= b, A(n) = (n-1)(A(n-1)+A(n-2))} is A(n) = b*A000166(n) + a*A055596(n). A(n) can also be expressed as A(n) = n*A(n-1) + (2a-b)(-1)^(n+1). - Gary Detlefs, Jun 13 2009
For n>1, sum over all permutations beginning with an ascent, ending with a descent, and without double ascents on n elements and each contributes 2 to the power of the number of double descents. By symmetry, also the sum over all permutations with a descent, ending with an ascent, and no double ascents and the sum is (again) over 2 to the power of the number of double descents. - Richard Ehrenborg, Oct 08 2013
It also appears related to a Secret Santa problem: given n people getting names from an urn to give presents and putting them back in the urn if they get their own name, this seems to be the number of ways that it may fail for the last person, as he/she has no other name to get from the urn. - João Batista Souza de Oliveira, Jan 25 2016
LINKS
Alois P. Heinz, Table of n, a(n) for n = 1..200
R. Ehrenborg and J. Jung, Descent pattern avoidance, Adv. in Appl. Math., 49 (2012) 375-390.
Lapo Cioni and Luca Ferrari, Preimages under the Queuesort algorithm, arXiv preprint arXiv:2102.07628 [math.CO], 2021; Discrete Math., 344 (2021), #112561.
FORMULA
E.g.f.: (2-x-2*exp(-x))/(1-x).
a(n) = (n-1)*(a(n-1) + a(n-2)) = 2*A006347(n-1), n>2.
a(n) = n! - 2*A000166(n), n>0.
a(n) ~ n! * (1-2*exp(-1)). - Vaclav Kotesovec, Oct 07 2013
For n>2, a(n) = floor(n! * (1-2*exp(-1)) + 1/2). - Peter Bala, Oct 08 2013
a(n+1) = 2*A002467(n) - n!. - Vaclav Kotesovec, Oct 08 2013
EXAMPLE
a(4)=6 since the 3 permutations 1432, 2431, 3421 all have one double descent and hence each contributes 2 to the sum. - Richard Ehrenborg, Oct 08 2013
For the Secret Santa, a(3)=2 since person 1 will get the names of either person 2 or 3. Suppose it was person 2. Person 2 will then get either person 1 or person 3. If he/she gets person 1, the draw will fail for person 3. The other case occurs when person 1 draws person 3, person 3 draws person 1 and the draw fails for person 2. - João Batista Souza de Oliveira, Jan 25 2016
MATHEMATICA
Rest[CoefficientList[Series[(2-x-2*E^(-x))/(1-x), {x, 0, 20}], x]* Range[0, 20]!] (* Vaclav Kotesovec, Oct 07 2013 *)
PROG
(PARI) a(n)=if(n<2, n>0, n*a(n-1)-2*(-1)^n)
(PARI) a(n)=if(n<1, 0, n!*polcoeff((2-x-2*exp(-x+x*O(x^n)))/(1-x), n))
(Magma)
A055596:= func< n | Factorial(n)*(1 -2*(&+[(-1)^j/Factorial(j): j in [0..n]]) ) >;
[A055596(n): n in [1..30]]; // G. C. Greubel, Sep 06 2022
(SageMath)
def A055596(n): return factorial(n)*( 2*bool(n==0) + 1 - 2*sum((-1)^j/factorial(j) for j in (0..n)) )
[A055596(n) for n in (1..30)] # G. C. Greubel, Sep 06 2022
CROSSREFS
KEYWORD
nonn
AUTHOR
Gary Detlefs, Jul 10 2000
EXTENSIONS
More terms from James A. Sellers, Jul 11 2000
STATUS
approved