|
| |
|
|
A000183
|
|
Number of discordant permutations of length n.
(Formerly M2121 N0838)
|
|
7
| |
|
|
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; 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
|
|
|
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)
|
|
|
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. [From 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}] (* From Jean-François Alcover, Oct 24 2011 *)
|
|
|
CROSSREFS
| Cf. A061702, A061703, A000338, A000561-A000565, A000045.
Diagonal of A008305.
Sequence in context: A003490 A003481 A081006 * A198052 A203216 A198647
Adjacent sequences: A000180 A000181 A000182 * A000184 A000185 A000186
|
|
|
KEYWORD
| nonn,nice,easy
|
|
|
AUTHOR
| N. J. A. Sloane (njas(AT)research.att.com).
|
|
|
EXTENSIONS
| More terms from Vladeta Jovovic (vladeta(AT)eunet.rs), Jun 18 2001
|
| |
|
|
