A061702 -id:A061702 - cp's OEIS frontend

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

N. J. A. Sloane

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

			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

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.

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.

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

Diagonal of A008305.

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

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

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

More terms from Vladeta Jovovic, Jun 18 2001

A061703 G.f.: 2x(2-2x-3x^2+2x^3)/((1-3x-x^2+x^3)*(1-x)).

Original entry on oeis.org

0, 4, 12, 34, 108, 344, 1104, 3546, 11396, 36628, 117732, 378426, 1216380, 3909832, 12567448, 40395794, 129844996, 417363332, 1341539196, 4312135922, 13860583628, 44552347608, 143205490528, 460308235562, 1479577849604

Offset: 0

Vladeta Jovovic, Jun 18 2001

R. P. Stanley, Enumerative Combinatorics I, Example 4.7.17.

Index entries for linear recurrences with constant coefficients, signature (4,-2,-2,1)

Row sums of A061702, A000183.

A302232 Triangle T(n,k) of the numbers of k-matchings in the n-Moebius ladder (0 <= k <= n, n > 2).

Original entry on oeis.org

1, 9, 18, 6, 1, 12, 42, 44, 7, 1, 15, 75, 145, 95, 13, 1, 18, 117, 336, 420, 192, 18, 1, 21, 168, 644, 1225, 1085, 371, 31, 1, 24, 228, 1096, 2834, 3880, 2588, 696, 47, 1, 27, 297, 1719, 5652, 10656, 11097, 5823, 1278, 78, 1, 30, 375, 2540, 10165, 24626, 35645, 29380, 12535, 2310, 123

Offset: 3

Eric W. Weisstein, Apr 03 2018

Initial terms in each row match those in A061702.

			As polynomials sum(k=0..n) x^k*T(n, k):
1 + 9*x + 18*x^2 + 6*x^3,
1 + 12*x + 42*x^2 + 44*x^3 + 7*x^4,
1 + 15*x + 75*x^2 + 145*x^3 + 95*x^4 + 13*x^5,
1 + 18*x + 117*x^2 + 336*x^3 + 420*x^4 + 192*x^5 + 18*x^6,
...

Eric Weisstein's World of Mathematics, Matching-Generating Polynomial
Eric Weisstein's World of Mathematics, Moebius Ladder

Row sums are A020877.

Cf. A061702.

CoefficientList[LinearRecurrence[{1 + x, 2 x (1 + x), -(-1 + x) x^2, -x^4}, {1 + 3 x, 1 + 6 x + 3 x^2, 1 + 9 x + 18 x^2 + 6 x^3, 1 + 12 x + 42 x^2 + 44 x^3 + 7 x^4}, {3, 10}], x] // Flatten
CoefficientList[CoefficientList[Series[-((-1 - 9 x - 18 x^2 - 6 x^3 - 2 x z - 15 x^2 z - 20 x^3 z - x^4 z - x^2 z^2 - 5 x^3 z^2 + 4 x^4 z^2 + 6 x^5 z^2 + x^4 z^3 + 6 x^5 z^3 + 3 x^6 z^3)/((1 + x z) (1 - z - 2 x z - x z^2 + x^3 z^3))), {z, 0, 10}], z], x] // Flatten

G.f.: -((z^2*(-1 - 9*x - 18*x^2 - 6*x^3 - 2*x*z - 15*x^2*z - 20*x^3*z - x^4*z - x^2*z^2 - 5*x^3*z^2 + 4*x^4*z^2 + 6*x^5*z^2 + x^4*z^3 + 6*x^5*z^3 + 3*x^6*z^3))/((1 + x*z)*(1 - z - 2*x*z - x*z^2 + x^3*z^3))).

Writing t(n, x) = sum(k=0..n) x^k*T(n, k), t(n, x) == (1 + x)*t(n-1, x) + 2*x*(1 + x)*t(n-2, x) -(-1 + x)*x^2*t(n-3, x) -x^4*t(n-4, x).

A094315 Triangle read by rows giving number of circular permutations of n letters such that all letters are displaced by no more than k places from their original position.

Original entry on oeis.org

1, 0, 1, 0, 0, 2, 0, 0, 0, 6, 1, 0, 6, 8, 9, 2, 15, 20, 40, 30, 13, 20, 72, 180, 176, 180, 72, 20, 144, 609, 1106, 1421, 980, 595, 154, 31, 1265, 4960, 9292, 10352, 8326, 4096, 1676, 304, 49

Offset: 0

N. J. A. Sloane, based on a suggestion from Anthony C Robin, Jun 02 2004

The n-th row sums to n!.

			1;
0, 1;
0, 0, 2;
0, 0, 0, 6;
1, 0, 6, 8, 9;
2, 15, 20, 40, 30, 13;
20, 72, 180, 176, 180, 72, 20;
144, 609, 1106, 1421, 980, 595, 154, 31;

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

Anthony C. Robin, 90.72 Circular Wife Swapping, The Mathematical Gazette, Vol. 90, No. 519 (Nov., 2006), pp. 471-478.
J. Riordan, Discordant permutations, Scripta Math., 20 (1954), 14-23. [Annotated scanned copy] (See Table 2)

Diagonals give A000183 (which has further references), A000476, A000388, A000380, A000440, etc.

cp's OEIS Frontend

A000183 Number of discordant permutations of length n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A061703 G.f.: 2*x*(2-2*x-3*x^2+2*x^3)/((1-3*x-x^2+x^3)*(1-x)).

Views

Author

Keywords

References

Links

Crossrefs

A302232 Triangle T(n,k) of the numbers of k-matchings in the n-Moebius ladder (0 <= k <= n, n > 2).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A094315 Triangle read by rows giving number of circular permutations of n letters such that all letters are displaced by no more than k places from their original position.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

A061703 G.f.: 2x(2-2x-3x^2+2x^3)/((1-3x-x^2+x^3)*(1-x)).