A000183 Number of discordant permutations of length n.
0, 0, 0, 1, 2, 20, 144, 1265, 12072, 126565, 1445100, 17875140, 238282730, 3407118041, 52034548064, 845569542593, 14570246018686, 265397214435860, 5095853023109484, 102877234050493609, 2178674876680100744, 48296053720501168037, 1118480911876659396600
Offset: 1
Examples
a(5) = 2: [ 1 2 3 4 5 ] -> [ 3 4 5 1 2 ] or [ 4 5 1 2 3 ]. 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
References
- J. Riordan, Discordant permutations, Scripta Math., 20 (1954), 14-23.
- 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).
- R. P. Stanley, Enumerative Combinatorics I, Example 4.7.17.
- 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.
Links
- Alois P. Heinz, Table of n, a(n) for n = 1..200
- J. Riordan, Discordant permutations, Scripta Math., 20 (1954), 14-23. [Annotated scanned copy]
- Anthony C. Robin, 90.72 Circular Wife Swapping, The Mathematical Gazette, Vol. 90, No. 519 (Nov., 2006), pp. 471-478.
- 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. [Annotated scanned copy]
- D. Zeilberger, Automatic Enumeration of Generalized Menage Numbers, arXiv preprint arXiv:1401.1089 [math.CO], 2014.
Programs
-
Maple
with(combinat): f:= n-> fibonacci(n-1) +fibonacci(n+1) +2: 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: seq(a(n), n=1..30); # Alois P. Heinz, Apr 19 2011
-
Mathematica
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 *) 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 *)
Formula
a(n) = Sum_{m=0..n} (-1)^m*(n-m)!*A061702(n, m), n>2.
From Vladimir Shevelev, Apr 17 2011: (Start)
Let f(n) = F(n-1) + F(n+1) + 2, where F(n) is the n-th Fibonacci number.
Then, for n>=7, we have the recursion:
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)).
This formula (in an equivalent form) is due to K. Yamamoto. (End)
a(n) ~ n!*exp(-3). - Vaclav Kotesovec, Aug 10 2013
Extensions
More terms from Vladeta Jovovic, Jun 18 2001
Comments