login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000183 Number of discordant permutations of length n.
(Formerly M2121 N0838)
10
0, 0, 0, 1, 2, 20, 144, 1265, 12072, 126565, 1445100, 17875140, 238282730, 3407118041, 52034548064, 845569542593, 14570246018686, 265397214435860, 5095853023109484, 102877234050493609, 2178674876680100744, 48296053720501168037, 1118480911876659396600 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,5

COMMENTS

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

REFERENCES

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

Anthony C. Robin, Circular Wife Swapping, The Mathematical Gazette, November 2006.

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]

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, 2014

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

EXAMPLE

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

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 *)

CROSSREFS

Cf. A061702, A061703, A000338, A000561-A000565, A000045.

Diagonal of A008305.

Sequence in context: A003490 A081006 A003481 * A198052 A203216 A198647

Adjacent sequences:  A000180 A000181 A000182 * A000184 A000185 A000186

KEYWORD

nonn,nice,easy

AUTHOR

N. J. A. Sloane

EXTENSIONS

More terms from Vladeta Jovovic, Jun 18 2001

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy .

Last modified March 27 13:47 EDT 2017. Contains 284176 sequences.