cp's OEIS Frontend

According to rook theory, John Riordan considered a(1) to be -1. - Vladimir Shevelev, Apr 02 2010

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

Sequence discovered by Touchard in 1934. - L. Edson Jeffery, Nov 13 2013

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

From Vladimir Shevelev, Jun 25 2015: (Start)

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

From Ira M. Gessel, Nov 27 2018: (Start)

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)

The number of permutations of [k+n] that differ in every position from both the identity permutation and a permutation consisting of k 1-cycles and s cycles of lengths p_1, p_2, ... p_s, with p_j >= 2 and p_1+p_2+...+p_s = n, can be expressed as Sum T(k,p_1+-p_2+-...+-p_s), where the sum is over all 2^(s-1) choices of sign and where T(k,-n) = T(k,n) (Touchard).

The first of Touchard's formulas for T(k,n) involves A034807, the number of k-matchings of C_n (A213234 or A127677 with sign included) and A047920, the k-th differences of the factorial numbers.

A slightly different formula, due to Wyman and Moser in the k=0 case, involves A213234 and A000023.

The first column is twice A000166 (twice the number of derangements of [k]); the second column is A105926 (first differences of A000166); the third column is A331007 (with offset 2); the first row is A102761 (the ménage numbers); the second row is A000270.