A000270 For n >= 2, a(n) = b(n+1)+b(n)+b(n-1), where the b(i) are the ménage numbers A000179; a(0)=a(1)=1.

1, 1, 0, 3, 16, 95, 672, 5397, 48704, 487917, 5373920, 64547175, 839703696, 11762247419, 176509466560, 2825125339305, 48040633506048, 864932233294681, 16436901752820288, 328791893988472843, 6905593482159150480, 151941269284478380119, 3495011687269591273312

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• nice

Comments

The old name (in the 1973 Handbook) was "Discordant permutations".

For n >= 2, a(n) is the number of permutations of [n+1] discordant with both the identity permutation and a permutation consisting of one 1-cycle and one n-cycle. - William P. Orrick, Aug 03 2020

The term a(0) = 1, which comes from the table on page 118 of Touchard's 1953 Scripta Math. paper is possibly in error. Equation (3) in Touchard's 1934 Comptes Rendus article produces a(0) = 0, and the formulas following equation (30) on page 117 of his 1953 paper give incorrect results unless a(0) = 0. - William P. Orrick, Aug 07 2020

Examples

			From _William P. Orrick_, Aug 07 2020: (Start)
There are no permutations of 123 discordant with both 123 and 132, so a(2) = 0; the permutations of 1234 discordant with both 1234 and 1342 are 2413, 3421, and 4123, so a(3) = 3.
Touchard (1953), p. 117, writes a(4) + a(0) for the number of permutations discordant with 12345 and 13254. There are 16 = 4*2*2 such permutations, obtained by letting (x,y) be one of (2,3), (3,2), (4,5), (5,4), then placing x in position 1, and finally, if (x,y) is (2,3) or (3,2), placing 4, 5 (in either order) in positions 2, 3 while placing 1, y (in either order) in positions 4, 5, or, if (x,y) is (4,5) or (5,4), placing 1, y (in either order) in positions 2, 3 while placing 2, 3 (in either order) in positions 4, 5. Hence Touchard's expression gives the correct result, assuming a(0) = 0.
(End)
		

References

• N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
• J. Touchard, Permutations discordant with two given permutations, Scripta Math., 19 (1953), 109-119.

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..175
• Olivier Danvy, Summa Summarum: Moessner's Theorem without Dynamic Programming, arXiv:2412.03127 [cs.DM], 2024. See 33.
• J. Touchard, Sur un problème de permutations, Comptes Rendus Acad. Sci. Paris, 198 (1934) 631-633.

Crossrefs

Cf. A000179, A335391.

Programs

Maple

a:= n-> coeftayl(1+(1-x)/(1+x)*add(k*k!*(x/(1+x)^2)^k, k=0..n), x=0, n):
seq(a(n), n=0..25); # Alois P. Heinz, Sep 24 2008
# second Maple program:
A000270 := proc(n) if n <= 1 then 1 else n * add((-1)^(n-s)*s!*binomial(s+n-1, 2*s-1), s=1..n) fi end; seq(A000270(n), n=0..30);  # Mark van Hoeij, May 12 2013

Mathematica

max = 20; f[x_] := 1+(1-x)/(1+x)*Sum[ n*n!*(x/(1+x)^2)^n, {n, 0, max}]; CoefficientList[ Series[ f[x], {x, 0, max}], x] (* Jean-François Alcover, Dec 09 2011, after Vladeta Jovovic *)

Formula

G.f.: 1+(1-x)/(1+x)*Sum_{n>=0} n*n!*(x/(1+x)^2)^n. - Vladeta Jovovic, Jun 29 2007

D-finite with recurrence: (n-3)*a(n) = (n-3)*n*a(n-1) + (n-3)*n*a(n-2) + n*a(n-3). - Vaclav Kotesovec, Mar 15 2014

a(n) ~ (n+1)! / exp(2). - Vaclav Kotesovec, Mar 15 2014

a(n) = A335391(1,n) for n >= 1. - William P. Orrick, Aug 03 2020

Extensions

More terms from Alois P. Heinz, Sep 24 2008

Entry revised by N. J. A. Sloane, Jul 23 2020. Thanks to William P. Orrick for suggesting that this sequence needed a better definition. The initial terms a(0)=a(1)=1 have been preserved in order to agree with the sequence in Touchard's 1953 paper.