A000179 -id:A000179 - cp's OEIS frontend

A000185 Coefficients of ménage hit polynomials.

2, 24, 140, 1232, 11268, 115056, 1284360, 15596208, 204710454, 2888897032, 43625578836, 702025263328, 11993721979336, 216822550325472, 4135337882588880, 82986434235959712, 1747976804189353962, 38559791049947726328, 889047923669760546140

Offset: 5

N. J. A. Sloane, Simon Plouffe

nonn

J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 197.
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).

Sean A. Irvine, Table of n, a(n) for n = 5..250

A diagonal of A058087. Cf. A000179, A000425.

Conjecture: +4*(210968408*n^2 -1603518486*n +2343057493) *a(n) +(-843873632*n^3 -4039256254*n^2 +144382575631*n -553812368850) *a(n-1) +(10453330198*n^3 -175111274403*n^2 +798927275864*n -639098546595) *a(n-2) +(10059264970*n^3 -98879552663*n^2 +170576803994*n -134993524720) *a(n-3) +(470894110*n^3 -5178116941*n^2 +108179055193*n -215961878286) *a(n-4) +(1708832970*n^3 -29554327949*n^2 +137453332457*n -152801514054) *a(n-5) +3*(569610990*n^2 -3742686463*n +4740040723) *a(n-6)=0. - R. J. Mathar, Nov 02 2015
Conjecture: (241*n-1066) *(2*n-11) *(-5+n)^2 *a(n) +(-482*n^5 +10099*n^4 -79756*n^3 +285961*n^2 -426904*n +149292) *a(n-1) -(2*n-9) *(n-3) *(248*n^3 -2229*n^2 +5065*n -7134) *a(n-2) +(-14*n^5 -49*n^4 -619*n^3 +13174*n^2 -51690*n +61248) *a(n-3) -(n-3) *(n-4) *(7*n-87) *(2*n-7) *a(n-4)= 0. - R. J. Mathar, Nov 02 2015
a(n)+2*a(n+p)+a(n+2*p) is divisible by p for any prime except 3 and 5. - Mark van Hoeij, Jun 13 2019

A170904 Sequence obtained by a formal reading of Riordan's Eq. (30a), p. 206.

Original entry on oeis.org

1, 0, 0, 2, 24, 572, 21280, 1074390, 70299264, 5792903144, 587159944704, 71822748886440, 10435273503677440, 1776780701352504408, 350461958856515690496, 79284041282799128098778, 20392765404792755583221760, 5917934230798152486136427600, 1924427226324694427836833857536

Offset: 0

N. J. A. Sloane, Jan 21 2010

nonn

See the comments in A000186 for further discussion.
Neven Juric alerted me to the fact that Riordan's formula is misleading.
It is not error of Riordan, since, according to the rook theory, he considered U(1) to be -1. [Vladimir Shevelev, Apr 02 2010]
A combinatorial argument, valid for n >= 2, leads to Touchard's formula for the n-th menage number, U(n), a formula which involves the coefficients of Chebyshev polynomials of the first kind. It is combinatorially reasonable to take U(0) = 1 and U(1) = 0, leading to A335700, but taking the connection with Chebyshev polynomials seriously instead gives U(0) = 2 and U(1) = -1, leading to A102761. Riordan derives equation (30) on page 205 for the number of reduced three-line Latin rectangles (A000186) by making use of product identities on Chebyshev polynomials, and therefore requires the second definition; it also requires extending the definition of menage numbers to negative index. Riordan then obtains equation (30a) on page 206 by eliminating the negative indices and redefining U(0) to be 1 (which leads to A000179). A170904 (this sequence) is what is obtained by mistakenly using A335700 instead of A000179 in Riordan's equation (30a). - William P. Orrick, Aug 11 2020

J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, pp. 206, 209.

# A000166
unprotect(D);
D := proc(n) option remember; if n<=1 then 1-n else (n-1)*(D(n-1)+D(n-2)); fi; end;
[seq(D(n),n=0..30)];
# A335700 (equals A000179 except that A335700(1) = 0)
U := proc(n) if n<=1 then 1-n else add ((-1)^k*(2*n)*binomial(2*n-k, k)*(n-k)!/(2*n-k), k=0..n); fi; end;
[seq(U(n),n=0..30)];
# bad A000186 (A170904)
Kbad:=proc(n) local k; global D, U; add( binomial(n,k)*D(n-k)*D(k)*U(n-2*k), k=0..floor(n/2) ); end;
[seq(Kbad(n),n=0..30)];

One can enumerate 3 X n Latin rectangles by the formula A000186(2n)=a(2n) and A000186(2n+1)=a(2n+1)-A001700(n)*A000166(n)*A000166(n+1). - Vladimir Shevelev, Apr 04 2010

a(2n)=A000186(2n), a(2n+1)=A000186(2n+1)+A001700(n)*A000166(n)*A000166(n+1). [From Vladimir Shevelev, Apr 02 2010]

Edited by N. J. A. Sloane, Apr 04 2010 following a suggestion from Vladimir Shevelev

A174561 Number of 3 X n Latin rectangles whose second row contains two cycles with the same order of its elements, e.g., the cycle (x_2, x_3, ..., x_k, x_1) with x_1 < x_2 < ... < x_k.

Original entry on oeis.org

12, 120, 2020, 32410, 563948

Offset: 4

Vladimir Shevelev, Mar 22 2010

V. S. Shevelev, Reduced Latin rectangles and square matrices with equal row and column sums, Diskr. Mat.(J. of the Akademy of Sciences of Russia) 4(1992), 91-110.

Cf. A000179, A000186, A094047, A174560, A174556.

A186638 a(0)=a(1)=a(2)=0; thereafter a(n) = na(n-1) + na(n-2)/(n-2) + (-1)^(n-1)*4/(n-2).

Original entry on oeis.org

0, 0, 0, 4, 14, 78, 488, 3526, 28858, 264256, 2678632, 29787932, 360669542, 4723907966, 66555492656, 1003783052878, 16136592266226, 275459689319104, 4976428074043376, 94860000118416084, 1902729366895036542, 40062161968084543054, 883460565601444487384, 20363470614798268185558, 489687069917632739530538, 12264310955130816605856448

Offset: 0

N. J. A. Sloane, Feb 24 2011

nonn

Muir gives this recurrence without specifying the initial values.

In general, for the same recurrence a(n) = n*a(n-1) + n*a(n-2)/(n-2) + (-1)^(n-1)*4/(n-2), with a(1)=0, a(2)=0, a(3)=m, is a(n) ~ c * n!, where c = exp(-2) + (BesselI(0,2)-BesselI(1,2))*(m-1)/3. Set m=4 for this sequence and m=1 for A000179. - Vaclav Kotesovec, May 05 2015

T. Muir, A Treatise on the Theory of Determinants. Dover, NY, 1960, Sect. 132, p. 112.

Vincenzo Librandi, Table of n, a(n) for n = 0..69

A000179 satisfies essentially the same recurrence.

W:=proc(n) option remember; if n <= 2 then 0 else
n*W(n-1)+n*W(n-2)/(n-2)+(-1)^(n-1)*4/(n-2); fi; end;

Flatten[{0,0,RecurrenceTable[{a[2]==0,a[3]==4,a[n]==n*a[n-1]+n*a[n-2]/(n-2)+(-1)^(n-1)*4/(n-2)},a,{n,2,20}]}] (* Vaclav Kotesovec, May 05 2015 *)

a[0]:0$ a[1]:0$ a[2]:0$ a[n]:=n*a[n-1]+n*a[n-2]/(n-2)+4*(-1)^(n-1)/(n-2)$ makelist(a[n], n, 0, 25); /* Bruno Berselli, May 23 2011 */

Recurrence (for n>2): (n-2)*a(n) = (n^2 - 3*n + 3)*a(n-1) + (n^2 - 3*n + 3)*a(n-2) + (n-1)*a(n-3). - Vaclav Kotesovec, May 05 2015

a(n) ~ c * n!, where c = exp(-2) + BesselI(0,2) - BesselI(1,2) = 0.8242837309353508959489495107843515087389944891994982884067... . - Vaclav Kotesovec, May 05 2015

A275921 Number of 5 X n Latin rectangles.

Original entry on oeis.org

56, 9408, 11270400, 27206658048, 112681643083776, 746988383076286464, 7533492323047902093312, 111048869433803210653040640, 2315236533572491933131807916032, 66415035616070432053233927044726784, 2560483881619577552584872021599994249216

Offset: 5

N. J. A. Sloane, Aug 28 2016

nonn

N. J. A. Sloane, Table of n, a(n) for n = 5..40 [Moused from the table in Stones et al. 2016]
R. J. Stones, S. Lin, X. Liu, G. Wang, On Computing the Number of Latin Rectangles, Graphs and Combinatorics (2016) 32:1187-1202; DOI 10.1007/s00373-015-1643-1

Cf. A000179, A000186, A001623.

A332709 Triangle T(n,k) read by rows where T(n,k) is the number of ménage permutations that map 1 to k, with 3 <= k <= n.

Original entry on oeis.org

1, 1, 1, 4, 5, 4, 20, 20, 20, 20, 115, 116, 117, 116, 115, 787, 791, 791, 791, 791, 787, 6184, 6203, 6204, 6205, 6204, 6203, 6184, 54888, 55000, 55004, 55004, 55004, 55004, 55000, 54888, 542805, 543576, 543595, 543596, 543597, 543596, 543595, 543576, 542805

Offset: 3

Peter Kagey, Feb 20 2020

Rows are palindromic.
Conjecture: Rows are unimodal (i.e., increasing, then decreasing).
Conjecture: T(n,k) - T(n,k-1) = A127548(n-2k+4) for n >= 2k - 3. - Peter Kagey, Jan 22 2021

			Triangle begins:
  n\k|     3      4      5      6      7      8      9     10
  ---+--------------------------------------------------------
   3 |     1
   4 |     1,     1
   5 |     4,     5,     4
   6 |    20,    20,    20,    20
   7 |   115,   116,   117,   116,   115
   8 |   787,   791,   791,   791,   791,   787
   9 |  6184,  6203,  6204,  6205,  6204,  6203,  6184
  10 | 54888, 55000, 55004, 55004, 55004, 55004, 55000, 54888
For n=5 and k=3, the T(5,3)=4 permutations on five letters that start with a 3 are 31524, 34512, 35124, and 35212.

Peter Kagey, Table of n, a(n) for n = 3..1277 (first 50 rows)

Cf. A127548.
First column given by A258664.
Second column given by A258665.
Third column given by A258666.
Fourth column given by A258667.
Row sums given by A000179.

T[n_, k_] :=
Sum[Sum[(-1)^i*(n - i - 1)!*Binomial[2*k - j - 4, j]*
    Binomial[2*(n - k + 1) - i + j, i - j], {j, Max[k + i - n - 1, 0],
     Min[i, k - 2]}], {i, 0, n - 1}]
(* Peter Kagey, Jan 22 2021 *)

T(n,k) = Sum_{i=0..n-1} Sum_{j=max(k+i-n-1,0)..min(i,k-2)} (-1)^i*(n-i-1)! * binomial(2k-j-4,j) * binomial(2(n-k+1)-i+j,i-j).

A354152 a(n) is the number of permutations pi in S_n such that pi(i) - i != 1 (mod n) and pi(i) - i != -1 (mod n) for all i.

Original entry on oeis.org

1, 0, 1, 1, 4, 13, 82, 579, 4740, 43387, 439794, 4890741, 59216644, 775596313, 10927434466, 164806435783, 2649391469060, 45226435601207, 817056406224418, 15574618910994665, 312400218671253764, 6577618644576902053, 145051250421230224306, 3343382818203784146955

Offset: 0

Peter Kagey, May 27 2022

nonn

For n > 1, this is the number of ways of rearranging guests sitting at a circular table such that a guest may stay in the same seat, but cannot move exactly one seat to their left or right.

The recurrence comes from Doron Zeilberger's MENAGE program, available via the arXiv reference.

			For n = 5, the a(5) = 13 permutations are 12345, 12543, 14325, 14523, 15342, 32145, 34125, 34512, 35142, 42315, 42513, 45123, and 45312.
The first letter is never 2 or 5, the second letter is never 1 or 3, the third letter is never 2 or 4, the fourth letter is never 3 or 5 and the fifth letter is never 1 or 4.

Peter Kagey, Table of n, a(n) for n = 0..400
D. Zeilberger, Automatic Enumeration of Generalized Menage Numbers, arXiv preprint arXiv:1401.1089 [math.CO], 2014.

Cf. A000179, A341439, A354408.

a(n) = n*a(n-1) + 3*a(n-2) + (-2n+6)*a(n-3) - 3*a(n-4) + (n-6)*a(n-5) + a(n-6) for n > 8.
a(2k+1) = A000179(2k+1) for k > 1.
Conjecture: a(2k) = A000179(2k) + 2 for k > 1.

A354409 Maximum value in the n-th row of A354408.

Original entry on oeis.org

0, 1, 4, 13, 82, 579, 4752, 43390, 440192, 4890741, 59245120, 775596313, 10930514688, 164806652728, 2649865335040, 45226435601207, 817154768973824, 15574618910994665, 312426715251262464, 6577619798222863696, 145060238642780180480, 3343382818203784146955

Offset: 2

Peter Kagey, May 25 2022

nonn

The minimum value appears to be given by A000179.
The differences between this sequence and A000179 begin 0, 0, 2, 0, 2, 0, 14, 3, 400, 0, 28478, ...
Conjecture: a(n) = A000179(n) if and only if n is prime.

Pontus von Brömssen, Table of n, a(n) for n = 2..450

Cf. A000179, A032742, A277256, A354408.

Conjecture: a(n) = A354408(n, A032742(n)) for n != 6. - Pontus von Brömssen, May 31 2022

a(13)-a(23) from Pontus von Brömssen, May 31 2022

A002484 Number of ménage permutations.

Original entry on oeis.org

1, 2, 5, 20, 87, 616, 4843, 44128, 444621, 4936274, 59661265, 780547332, 10987097799, 165587196328, 2660378564791, 45392026278108, 819716784789209, 15620011000052754, 313219935456572497, 6593238656843759572

Offset: 3

N. J. A. Sloane

C. Berge, Principles of Combinatorics, Academic Press, NY, 1971, p. 162.
E. N. Gilbert, Knots and classes of menage permutations, Scripta Math., 22 (1956), 228-233 (1957).
J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 195.
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).

Vincenzo Librandi, Table of n, a(n) for n = 3..200
E. N. Gilbert, Knots and classes of menage permutations [Annotated scanned copy of preprint]

Cf. A000179.

with(numtheory): d := n->divisors(n): U := (m,t)->sum(2*m*binomial(2*m-k,k)*(m-k)!*(t-1)^k/(2*m-k),k=0..m): A := (n,i)->phi(n/dd[i])*(n/dd[i])^dd[i]*U(dd[i],1-dd[i]/n)/n: for n from 3 to 28 do dd := d(n): B := [seq(A(n,j),j=1..nops(dd))]: a[n] := sum(B[i],i=1..nops(B)) od: seq(a[n],n=3..28); # Emeric Deutsch, Mar 08 2004

u[m_, t_] := Sum[ 2m*Binomial[ 2m-k, k]*(m-k)!*((t-1)^k / (2m-k)), {k, 0, m}]; a[n_] := Sum[ EulerPhi[n/d] * (n/d)^d * (u[d, 1-d/n]/n), {d, Divisors[n]} ]; Table[ a[n], {n, 3, 22} ] (* Jean-François Alcover, Dec 07 2011, after Maple *)

Gilbert gives a formula (see Maple code).

a(n) ~ (n-1)! * exp(-2). - Vaclav Kotesovec, May 23 2014

More terms from Emeric Deutsch, Mar 08 2004

A058089 Coefficients of ménage hit polynomials.

Original entry on oeis.org

2, 35, 280, 2856, 30300, 349734, 4351368, 58217640, 834296862, 12759002305, 207501063952, 3577028170736, 65167077604440, 1251273416561196, 25258559758736880, 534813397441926960, 11852765770416416538, 274422835213034666655

Offset: 6

N. J. A. Sloane, Dec 02 2000

nonn

J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 197.

A diagonal of A058087. Cf. A000179, A000425.

cp's OEIS Frontend

A000185 Coefficients of ménage hit polynomials.

Views

Author

Keywords

References

Links

Crossrefs

Formula

A170904 Sequence obtained by a formal reading of Riordan's Eq. (30a), p. 206.

Views

Author

Keywords

Comments

References

Programs

Maple

Formula

Extensions

A174561 Number of 3 X n Latin rectangles whose second row contains two cycles with the same order of its elements, e.g., the cycle (x_2, x_3, ..., x_k, x_1) with x_1 < x_2 < ... < x_k.

Views

Author

Keywords

Links

Crossrefs

A186638 a(0)=a(1)=a(2)=0; thereafter a(n) = n*a(n-1) + n*a(n-2)/(n-2) + (-1)^(n-1)*4/(n-2).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Maxima

Formula

A275921 Number of 5 X n Latin rectangles.

Views

Author

Keywords

Links

Crossrefs

A332709 Triangle T(n,k) read by rows where T(n,k) is the number of ménage permutations that map 1 to k, with 3 <= k <= n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A354152 a(n) is the number of permutations pi in S_n such that pi(i) - i != 1 (mod n) and pi(i) - i != -1 (mod n) for all i.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A354409 Maximum value in the n-th row of A354408.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A002484 Number of ménage permutations.

Views

Author

Keywords

References

Links

Crossrefs

A186638 a(0)=a(1)=a(2)=0; thereafter a(n) = na(n-1) + na(n-2)/(n-2) + (-1)^(n-1)*4/(n-2).