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