login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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

%I M3019 N1221 #99 Feb 24 2021 08:44:56

%S 1,1,0,3,16,95,672,5397,48704,487917,5373920,64547175,839703696,

%T 11762247419,176509466560,2825125339305,48040633506048,

%U 864932233294681,16436901752820288,328791893988472843,6905593482159150480,151941269284478380119,3495011687269591273312

%N 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 The old name (in the 1973 Handbook) was "Discordant permutations".

%C 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 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 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%D J. Touchard, Permutations discordant with two given permutations, Scripta Math., 19 (1953), 109-119.

%H Alois P. Heinz, <a href="/A000270/b000270.txt">Table of n, a(n) for n = 0..175</a>

%H 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 G.f.: 1+(1-x)/(1+x)*Sum_{n>=0} n*n!*(x/(1+x)^2)^n. - _Vladeta Jovovic_, Jun 29 2007

%F 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 a(n) ~ (n+1)! / exp(2). - _Vaclav Kotesovec_, Mar 15 2014

%F a(n) = A335391(1,n) for n >= 1. - _William P. Orrick_, Aug 03 2020

%e From _William P. Orrick_, Aug 07 2020: (Start)

%e 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 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 (End)

%p a:= n-> coeftayl(1+(1-x)/(1+x)*add(k*k!*(x/(1+x)^2)^k, k=0..n), x=0, n):

%p seq(a(n), n=0..25); # _Alois P. Heinz_, Sep 24 2008

%p # second Maple program:

%p 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 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 Cf. A000179, A335391.

%K nonn,nice

%O 0,4

%A _N. J. A. Sloane_

%E More terms from _Alois P. Heinz_, Sep 24 2008

%E 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.

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 12:26 EDT 2024. Contains 371254 sequences. (Running on oeis4.)