|
|
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.
(Formerly M3019 N1221)
|
|
3
|
|
|
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 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
|
|
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
|
|
|
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
|
|
EXAMPLE
|
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+(1-x)/(1+x)*add(k*k!*(x/(1+x)^2)^k, k=0..n), x=0, n):
# 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 *)
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,nice
|
|
AUTHOR
|
|
|
EXTENSIONS
|
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
|
|
|
|