|
|
A000179
|
|
Ménage numbers: a(0) = 1, a(1) = -1, and for n >= 2, a(n) = number of permutations s of [0, ..., n-1] such that s(i) != i and s(i) != i+1 (mod n) for all i.
(Formerly M2062 N0815)
|
|
62
|
|
|
1, -1, 0, 1, 2, 13, 80, 579, 4738, 43387, 439792, 4890741, 59216642, 775596313, 10927434464, 164806435783, 2649391469058, 45226435601207, 817056406224416, 15574618910994665, 312400218671253762, 6577618644576902053, 145051250421230224304, 3343382818203784146955, 80399425364623070680706, 2013619745874493923699123
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,5
|
|
COMMENTS
|
This is also the value that the formulas of Touchard and of Wyman and Moser give and is compatible with many recurrences. - William P. Orrick, Aug 31 2020
Or, for n >= 3, the number of 3 X n Latin rectangles the second row of which is full cycle with a fixed order of its elements, e.g., the cycle (x_2,x_3,...,x_n,x_1) with x_1 < x_2 < ... < x_n. - Vladimir Shevelev, Mar 22 2010
Muir (p. 112) gives essentially this recurrence (although without specifying any initial conditions). Compare A186638. - N. J. A. Sloane, Feb 24 2011
Although these are also known as Touchard numbers, the problem was formulated by Lucas in 1891, who gave the recurrence formula shown below. See Cerasoli et al., 1988. - Stanislav Sykora, Mar 14 2014
An equivalent problem was formulated by Tait; solutions to Tait's problem were given by Muir (1878) and Cayley (1878). - William P. Orrick, Aug 31 2020
According to the ménage problem, 2*n!*a(n) is the number of ways of seating n married couples at 2*n chairs around a circular table, men and women in alternate positions, so that no husband is next to his wife.
It is known [Riordan, ch. 7] that a(n) is the number of arrangements of n non-attacking rooks on the positions of the 1's in an n X n (0,1)-matrix A_n with 0's in positions (i,i), i = 1,...,n, (i,i+1), i = 1,...,n-1, and (n,1). This statement could be written as a(n) = per(A_n). For example, A_5 has the form
001*11
1*0011
11001* (1)
11*100
0111*0,
where 5 non-attacking rooks are denoted by {1*}.
We can indicate a one-to-one correspondence between arrangements of n non-attacking rooks on the 1's of a matrix A_n and arrangements of n married couples around a circular table by the rules of the ménage problem, after the ladies w_1, w_2, ..., w_n have taken the chairs numbered
2*n, 2, 4, ..., 2*n-2 (2)
respectively. Suppose we consider an arrangement of rooks: (1,j_1), (2,j_2), ..., (n,j_n). Then the men m_1, m_2, ..., m_n took chairs with numbers
2*j_i - 3 (mod 2*n), (3)
where the residues are chosen from the interval[1,2*n]. Indeed {j_i} is a permutation of 1,...,n. So {2*j_i-3}(mod 2*n) is a permutation of odd positive integers <= 2*n-1. Besides, the distance between m_i and w_i cannot be 1. Indeed, the equality |2*(j_i-i)-1| = 1 (mod 2*n) is possible if and only if either j_i=i or j_i=i+1 (mod n) that correspond to positions of 0's in matrix A_n.
For example, in the case of positions of {1*} in(1) we have j_1=3, j_2=1, j_3=5, j_4=2, j_5=4. So, by(2) and (3) the chairs 1,2,...,10 are taken by m_4, w_2, m_1, w_3, m_5, w_4, m_3, w_5, m_2, w_1, respectively. (End)
The first 20 terms of this sequence were calculated in 1891 by E. Lucas (see [Lucas, p. 495]). - Peter J. C. Moses, Jun 26 2015
If we invert the formula
Sum_{ n>=0 } u_n z^n = ((1-z)/(1+z)) F(z/(1+z)^2)
that Don Knuth mentions (see link) (i.e., set x=z/(1+z)^2 and solve for z in terms of x), we get a formula for F(z) = Sum_{n >= 0} n! z^n as a sum with all positive coefficients of (almost) powers of the Catalan number generating function.
The exact formula is (5) of the Yiting Li article.
This article also gives a combinatorial proof of this formula (though it is not as simple as one might want). (End)
|
|
REFERENCES
|
W. W. R. Ball and H. S. M. Coxeter, Mathematical Recreations and Essays, 13th Ed. Dover, p. 50.
M. Cerasoli, F. Eugeni and M. Protasi, Elementi di Matematica Discreta, Nicola Zanichelli Editore, Bologna 1988, Chapter 3, p. 78.
L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 185, mu(n).
Kaplansky, Irving and Riordan, John, The probleme des menages, Scripta Math. 12, (1946). 113-124. See u_n.
E. Lucas, Théorie des nombres, Paris, 1891, pp. 491-495.
P. A. MacMahon, Combinatory Analysis. Cambridge Univ. Press, London and New York, Vol. 1, 1915 and Vol. 2, 1916; see vol. 1, p 256.
T. Muir, A Treatise on the Theory of Determinants. Dover, NY, 1960, Sect. 132, p. 112. - N. J. A. Sloane, Feb 24 2011
J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 197.
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. - Vladimir Shevelev, Mar 22 2010
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).
H. M. Taylor, A problem on arrangements, Mess. Math., 32 (1902), 60ff.
J. Touchard, Permutations discordant with two given permutations, Scripta Math., 19 (1953), 108-119.
J. H. van Lint, Combinatorial Theory Seminar, Eindhoven University of Technology, Springer Lecture Notes in Mathematics, Vol. 382, 1974. See page 10.
|
|
LINKS
|
M. A. Alekseyev, Weighted de Bruijn Graphs for the Menage Problem and Its Generalizations. Lecture Notes in Computer Science 9843 (2016), 151-162. doi:10.1007/978-3-319-44543-4_12 arXiv:1510.07926, [math.CO], 2015-2016.
|
|
FORMULA
|
a(n) = ((n^2-2*n)*a(n-1) + n*a(n-2) - 4*(-1)^n)/(n-2) for n >= 3.
a(n) = A059375(n)/(2*n!) for n >= 2.
a(n) = Sum_{k=0..n} (-1)^k*(2*n)*binomial(2*n-k, k)*(n-k)!/(2*n-k) for n >= 1. - Touchard (1934)
G.f.: ((1-x)/(1+x))*Sum_{n>=0} n!*(x/(1+x)^2)^n. - Vladeta Jovovic, Jun 26 2007
a(2^k+2) == 0 (mod 2^k); for k >= 2, a(2^k) == 2(mod 2^k). - Vladimir Shevelev, Jan 14 2011
a(n) = round( 2*n*exp(-2)*BesselK(n,2) ) for n > 1. - Mark van Hoeij, Oct 25 2011
0 = a(n)*(-a(n+2) +a(n+4)) +a(n+1)*(+a(n+1) +a(n+2) -3*a(n+3) -5*a(n+4) +a(n+5)) +a(n+2)*(+2*a(n+2) +3*a(n+3) -3*a(n+4)) +a(n+3)*(+2*a(n+3) +a(n+4) -a(n+5)) +a(n+4)*(+a(n+4)), for all n>1. If a(-2..1) = (0, -1, 2, -1) then also true for those values of n. - Michael Somos, Apr 29 2018
D-finite with recurrence: 0 = a(n) +n*a(n+1) -2*a(n+2) +(-n-4)*a(n+3) +a(n+4), for all n in Z where a(n) = a(-n) for all n in Z and a(0) = 2, a(1) = -1. - Michael Somos, May 02 2018
a(n) = Sum_{k=0..n} A213234(n,k) * A000023(n-2*k) = Sum_{k=0..n} (-1)^k * n/(n-k) * binomial(n-k, k) * (n-2*k)! Sum_{j=0..n-2*k} (-2)^j/j! for n >= 1. [Wyman and Moser (1958)]. - William P. Orrick, Jun 25 2020
a(k+4*p) - 2*a(k+2*p) + a(k) is divisible by p, for any k > 0 and any prime p. - Mark van Hoeij, Jan 11 2022
|
|
EXAMPLE
|
a(2) = 0; nothing works. a(3) = 1; (201) works. a(4) = 2; (2301), (3012) work. a(5) = 13; (20413), (23401), (24013), (24103), (30412), (30421), (34012), (34021), (34102), (40123), (43012), (43021), (43102) work.
|
|
MAPLE
|
A000179:= n ->add ((-1)^k*(2*n)*binomial(2*n-k, k)*(n-k)!/(2*n-k), k=0..n); # for n >= 1
U:= proc(n) local k; add( (2*n/(2*n-k))*binomial(2*n-k, k)*(n-k)!*(x-1)^k, k=0..n); end; W := proc(r, s) coeff( U(r), x, s ); end; A000179 := n->W(n, 0); # valid for n >= 1
|
|
MATHEMATICA
|
a[n_] := 2*n*Sum[(-1)^k*Binomial[2*n - k, k]*(n - k)!/(2*n - k), {k, 0, n}]; a[0] = 1; Table[a[n], {n, 0, 21}] (* Jean-François Alcover, Dec 05 2012, from 2nd formula *)
|
|
PROG
|
(PARI) \\ 3 programs adapted to a(1) = -1 by Hugo Pfoertner, Aug 31 2020
(PARI) {a(n) = my(A); if( n, A = vector(n, i, i-2); for(k=4, n, A[k] = (k * (k - 2) * A[k-1] + k * A[k-2] - 4 * (-1)^k) / (k-2)); A[n], 1)}; /* Michael Somos, Jan 22 2008 */
(PARI) {a(n) = my(A); if( n, A = vector(n, i, i-2); for(k=5, n, A[k] = k * A[k-1] + 2 * A[k-2] + (4-k) * A[k-3] - A[k-4]); A[n], 1)} /* Michael Somos, May 02 2018 */
(Haskell)
import Data.List (zipWith5)
a000179 n = a000179_list !! n
a000179_list = 1 : -1 : 0 : 1 : zipWith5
(\v w x y z -> (x * y + (v + 2) * z - w) `div` v) [2..] (cycle [4, -4])
(drop 4 a067998_list) (drop 3 a000179_list) (drop 2 a000179_list)
(Python)
from math import comb, factorial
def A000179(n): return 1 if n == 0 else sum((-2*n if k & 1 else 2*n)*comb(m:=2*n-k, k)*factorial(n-k)//m for k in range(n+1)) # Chai Wah Wu, May 27 2022
|
|
CROSSREFS
|
Cf. A000904, A059375, A102761, A000186, A094047, A067998, A033999, A258664, A258665, A258666, A258667, A258673, A259212, A213234, A000023.
|
|
KEYWORD
|
sign,nice,easy
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|