

A000270


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


2



1, 1, 0, 3, 16, 95, 672, 5397, 48704, 487917, 5373920, 64547175, 839703696, 11762247419, 176509466560, 2825125339305, 48040633506048, 864932233294681, 16436901752820288, 328791893988472843, 6905593482159150480, 151941269284478380119, 3495011687269591273312
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,4


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 1cycle and one ncycle.  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


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), 109119.


LINKS

Alois P. Heinz, Table of n, a(n) for n = 0..175
J. Touchard, Sur un problème de permutations, Comptes Rendus Acad. Sci. Paris, 198 (1934) 631633.


FORMULA

G.f.: 1+(1x)/(1+x)*Sum_{n>=0} n*n!*(x/(1+x)^2)^n.  Vladeta Jovovic, Jun 29 2007
Dfinite with recurrence: (n3)*a(n) = (n3)*n*a(n1) + (n3)*n*a(n2) + n*a(n3).  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


EXAMPLE

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)


MAPLE

a:= n> coeftayl(1+(1x)/(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)^(ns)*s!*binomial(s+n1, 2*s1), s=1..n) fi end; seq(A000270(n), n=0..30); # Mark van Hoeij, May 12 2013


MATHEMATICA

max = 20; f[x_] := 1+(1x)/(1+x)*Sum[ n*n!*(x/(1+x)^2)^n, {n, 0, max}]; CoefficientList[ Series[ f[x], {x, 0, max}], x] (* JeanFrançois Alcover, Dec 09 2011, after Vladeta Jovovic *)
A000270 := proc(n) if n = 0 then 1 else n * add((1)^(ns)*s!*binomial(s+n1, 2*s1), s=1..n) fi end; seq(A000270(n), n=0..30); (* JeanFrançois Alcover, May 13 2013, after Mark van Hoeij *)


CROSSREFS

Cf. A000179, A335391.
Sequence in context: A114174 A181067 A006347 * A157051 A000271 A157016
Adjacent sequences: A000267 A000268 A000269 * A000271 A000272 A000273


KEYWORD

nonn,nice


AUTHOR

N. J. A. Sloane


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.


STATUS

approved



