A055596 Expansion of e.g.f. (2 - x - 2*exp(-x))/(1-x).

1, 0, 2, 6, 32, 190, 1332, 10654, 95888, 958878, 10547660, 126571918, 1645434936, 23036089102, 345541336532, 5528661384510, 93987243536672, 1691770383660094, 32143637289541788, 642872745790835758, 13500327661607550920, 297007208555366120238

Offset: 1

Author

Gary Detlefs, Jul 10 2000

Keywords

• nonn

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

Examples

			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
		

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.

Crossrefs

Cf. A000166, A002467, A230071, A227918.

Programs

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

Mathematica

Rest[CoefficientList[Series[(2-x-2*E^(-x))/(1-x), {x, 0, 20}], x]* Range[0, 20]!] (* Vaclav Kotesovec, Oct 07 2013 *)

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))

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

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

Extensions

More terms from James Sellers, Jul 11 2000