login
Number of discordant permutations of length n.
(Formerly M2121 N0838)
13

%I M2121 N0838 #61 Oct 20 2017 14:33:52

%S 0,0,0,1,2,20,144,1265,12072,126565,1445100,17875140,238282730,

%T 3407118041,52034548064,845569542593,14570246018686,265397214435860,

%U 5095853023109484,102877234050493609,2178674876680100744,48296053720501168037,1118480911876659396600

%N Number of discordant permutations of length n.

%C Ways to reseat n diners at circular table, none in or next to original chair.

%D J. Riordan, Discordant permutations, Scripta Math., 20 (1954), 14-23.

%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 R. P. Stanley, Enumerative Combinatorics I, Example 4.7.17.

%D K. Yamamoto, Structure polynomial of Latin rectangles and its application to a combinatorial problem, Memoirs of the Faculty of Science, Kyusyu University, Series A, 10 (1956), 1-13.

%H Alois P. Heinz, <a href="/A000183/b000183.txt">Table of n, a(n) for n = 1..200</a>

%H J. Riordan, <a href="/A000211/a000211.pdf">Discordant permutations</a>, Scripta Math., 20 (1954), 14-23. [Annotated scanned copy]

%H Anthony C. Robin, <a href="http://www.jstor.org/stable/40378205">90.72 Circular Wife Swapping</a>, The Mathematical Gazette, Vol. 90, No. 519 (Nov., 2006), pp. 471-478.

%H K. Yamamoto, <a href="/A000183/a000183.pdf">Structure polynomial of Latin rectangles and its application to a combinatorial problem</a>, Memoirs of the Faculty of Science, Kyusyu University, Series A, 10 (1956), 1-13. [Annotated scanned copy]

%H D. Zeilberger, <a href="http://arxiv.org/abs/1401.1089">Automatic Enumeration of Generalized Menage Numbers</a>, arXiv preprint arXiv:1401.1089 [math.CO], 2014.

%F a(n) = Sum_{m=0..n} (-1)^m*(n-m)!*A061702(n, m), n>2.

%F From _Vladimir Shevelev_, Apr 17 2011: (Start)

%F Let f(n) = F(n-1) + F(n+1) + 2, where F(n) is the n-th Fibonacci number.

%F Then, for n>=7, we have the recursion:

%F a(n) = (-1)^n*(4*n+f(n)) + (n/(n-1))*((n+1)*a(n-1) + 2*(-1)^n*f(n-1)) - ((2*n)/(n-2))*((n-3)*a(n-2) + (-1)^n*f(n-2)) + (n/(n-3))*((n-5)*a(n-3) + 2*(-1)^(n-1)*f(n-3)) + (n/(n-4))*(a(n-4) + (-1)^(n-1)*f(n-4)).

%F This formula (in an equivalent form) is due to K. Yamamoto. (End)

%F a(n) ~ n!*exp(-3). - _Vaclav Kotesovec_, Aug 10 2013

%e a(5) = 2: [ 1 2 3 4 5 ] -> [ 3 4 5 1 2 ] or [ 4 5 1 2 3 ].

%e Let n=7. Then, using the previous values of a(n), we have a(7) = -(4*7+31) + (7/6)*(8*20-2*20) - (14/5)*(4*2-13) + (7/4)*(2*1+2*9) + (7/3)*6 = -59+140+14+35+14 = 144. - _Vladimir Shevelev_, Apr 17 2011

%p with(combinat): f:= n-> fibonacci(n-1) +fibonacci(n+1) +2:

%p a:= proc(n) option remember; `if` (n<7, [0$3, 1, 2, 20][n], (-1)^n*(4*n+f(n)) +(n/(n-1))*((n+1)*a(n-1) +2*(-1)^n*f(n-1)) -((2*n)/(n-2))*((n-3)*a(n-2) +(-1)^n*f(n-2)) +(n/(n-3))*((n-5)*a(n-3) +2*(-1)^(n-1)*f(n-3)) +(n/(n-4))*(a(n-4) +(-1)^(n-1)*f(n-4))) end:

%p seq(a(n), n=1..30); # _Alois P. Heinz_, Apr 19 2011

%t max = 22; f[x_, y_] := y*(1 + 3*x - 4*x^2*y - 3*x^2*y^2 - 3*x^3*y^2 + 4*x^4*y^3)/((1 - y - 2*x*y - x*y^2 + x^3*y^3)*(1 - x*y)); se = Series[f[x, y], {x, 0, max}, {y, 0, max}];coes = CoefficientList[se, {x, y}] ;t[n_, k_] := coes[[k, n]]; a[n_] := Sum[ (-1)^(k+1)*(n-k+1)!*t[n+1, k], {k, 1, n+1}]; a[1] = a[2] = a[3] = 0; Table[a[n], {n, 1, max}] (* _Jean-François Alcover_, Oct 24 2011 *)

%t Flatten[{0,0,RecurrenceTable[{(382-1142 n+712 n^2-185 n^3+22 n^4-n^5) a[-7+n]+(-3776+11024 n-7689 n^2+2397 n^3-384 n^4+31 n^5-n^6) a[-6+n]+(7394-18064 n+12353 n^2-3937 n^3+661 n^4-57 n^5+2 n^6) a[-5+n]+(1452-10548 n+8254 n^2-2655 n^3+423 n^4-33 n^5+n^6) a[-4+n]+(-11046+26716 n-18588 n^2+6013 n^3-1015 n^4+87 n^5-3 n^6) a[-3+n]+(632+5546 n-3888 n^2+1007 n^3-116 n^4+5 n^5) a[-2+n]+(3966-4666 n+3655 n^2-1445 n^3+284 n^4-27 n^5+n^6) a[-1+n]+(2444-3214 n+1409 n^2-283 n^3+27 n^4-n^5) a[n]==0,a[8]==1265,a[9]==12072,a[3]==0,a[4]==1,a[5]==2,a[6]==20,a[7]==144},a,{n,3,20}]}] (* _Vaclav Kotesovec_, Aug 10 2013 *)

%Y Cf. A061702, A061703, A000338, A000561-A000565, A000045, A264801.

%Y Diagonal of A008305.

%K nonn,nice,easy

%O 1,5

%A _N. J. A. Sloane_

%E More terms from _Vladeta Jovovic_, Jun 18 2001