|
| |
|
|
A000183
|
|
Number of discordant permutations of length n.
(Formerly M2121 N0838)
|
|
13
|
|
|
|
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.
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
|
|
|
|
FORMULA
|
a(n) = Sum_{m=0..n} (-1)^m*(n-m)!*A061702(n, m), n>2.
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. - 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:
|
|
|
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
|
|
|
|
KEYWORD
|
nonn,nice,easy
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
