cp's OEIS Frontend

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.

%I A000270 M3019 N1221 #107 Dec 10 2024 12:30:57
%S A000270 1,1,0,3,16,95,672,5397,48704,487917,5373920,64547175,839703696,
%T A000270 11762247419,176509466560,2825125339305,48040633506048,
%U A000270 864932233294681,16436901752820288,328791893988472843,6905593482159150480,151941269284478380119,3495011687269591273312
%N 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.
%C A000270 The old name (in the 1973 Handbook) was "Discordant permutations".
%C A000270 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
%C A000270 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
%D A000270 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A000270 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D A000270 J. Touchard, Permutations discordant with two given permutations, Scripta Math., 19 (1953), 109-119.
%H A000270 Alois P. Heinz, <a href="/A000270/b000270.txt">Table of n, a(n) for n = 0..175</a>
%H A000270 Olivier Danvy, <a href="https://arxiv.org/abs/2412.03127">Summa Summarum: Moessner's Theorem without Dynamic Programming</a>, arXiv:2412.03127 [cs.DM], 2024. See 33.
%H A000270 J. Touchard, <a href="https://gallica.bnf.fr/ark:/12148/bpt6k31506/f631.item.zoom">Sur un problème de permutations</a>, Comptes Rendus Acad. Sci. Paris, 198 (1934) 631-633.
%F A000270 G.f.: 1+(1-x)/(1+x)*Sum_{n>=0} n*n!*(x/(1+x)^2)^n. - _Vladeta Jovovic_, Jun 29 2007
%F A000270 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
%F A000270 a(n) ~ (n+1)! / exp(2). - _Vaclav Kotesovec_, Mar 15 2014
%F A000270 a(n) = A335391(1,n) for n >= 1. - _William P. Orrick_, Aug 03 2020
%e A000270 From _William P. Orrick_, Aug 07 2020: (Start)
%e A000270 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.
%e A000270 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.
%e A000270 (End)
%p A000270 a:= n-> coeftayl(1+(1-x)/(1+x)*add(k*k!*(x/(1+x)^2)^k, k=0..n), x=0, n):
%p A000270 seq(a(n), n=0..25); # _Alois P. Heinz_, Sep 24 2008
%p A000270 # second Maple program:
%p A000270 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
%t A000270 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_ *)
%Y A000270 Cf. A000179, A335391.
%K A000270 nonn,nice
%O A000270 0,4
%A A000270 _N. J. A. Sloane_
%E A000270 More terms from _Alois P. Heinz_, Sep 24 2008
%E A000270 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.