Comments on A000179 fron Donald E. Knuth, Nov 25 2018 - Nov 27 2018
===================================================================
(minor edits from N. J. A. Sloane, Nov 29 2018)

This message is about the famous sequence introduced by Lucas
(and independently somewhat earlier by Tait, whose problem
was solved by Cayley and Muir). It's A000179 in the OEIS, currently
  1, 0, 0, 1, 2, 13, 80, 579, ...
but I shall argue below that it should be changed in one place to
  1, -1, 0, 1, 2, 13, 80, 579, ...
because those numbers are much nicer mathematically.
[That change has been made. - NJAS Nov 26 2018]

Call them u_0, u_1, ..., so that e.g. u_5 = 13. It's the number
of ways to seat five husbands at a circular table of 10 places,
allowing no adjacent couples, if five male-female m\'enages are
present and if the wives are already seated at alternate places.

One of the reasons for the change recommended above is because Riordan's
nice formula in Introduction to Combinatorial Analysis
  n! = \sum {2n\choose k} u_{n-k}
depends on that value of u_1.

I was wondering why the literature seems to have formulas
for the OGF of <u_n>, but not the EGF. Since it's a question
of permutations, the EGF is a statement about probabilities.

The nicest formula for the OGF that I know is in 
Flajolet and R. Sedgewick's Analytic Combinatorics,
page 172, although my copy of the first printing has some typos:
Let F(z) be the formal series \sum_{n\ge0} n!z^n; then
  \sum_{n\ge0} u_nz^n = ((1-z)/(1+z)) F(z/(1+z)^2).
[My copy has 2z added, giving u_1=+1; but that certainly constradicts
Touchard's famous formula on line 8. My copy also says "adapts" instead
of "adapt" on line 1.]

Dick de Bruijn gave what is probably the simplest "closed form" for u_n,
on page 10 of J. H. van Lint, Combinatorial Theory Seminar, Eindhoven University of Technology, Springer Lecture Notes in Mathematics, Vol. 382, 1974:
    u_n = \int_0^\infty e^{-y} C_n(y-2)\,dy,
where C_n is the Chebyshev polynomial 2T_n(x/2). His formula gives
u_1=-1, as desired; but it also gives u_0=2. The latter has one somewhat
nice feature, because it makes Muir's identity
    (n-2)u_n = n(n-2)u_{n-1}+nu_{n-2}-4\cdot(-1)^n
valid for all n\ne1. But that fact isn't really convincing;
I feel rather strongly that u_0=1 is the "right" starting value.

It's not difficult to show that u_n is asymptotically n!/e^2.
But I really want to know more terms of the asymptotic expansion;
what is the behavior of u_n-n!/e^2, etc.?

So I played around and came up with a nice formula that is my
main purpose in sending this message. Let
    T_n = \sum_{k=0}^n (-2)^k/k!
be the truncation of the power series for e^{-2} after the
first n+1 terms. Thus T_0=1, T_1=-1, T_2=2, T_3=-1/3, T_4=1/3,
and pretty soon T_n is very close to e^{-2}\approx.135335 because
this is a nice alternating sum with superexponential convergence.

I got lucky and discovered the following exact formula:
  u_n/n! = T_n - T_{n-2}/(n-1) + T_{n-4}/(2!(n-1)(n-2)) - \cdots
         = \sum_{k\ge0} (-1)^k T_{n-2k} / (k! (n-1)\ldots(n-k)).  (*)
(The sum stops when 2k exceeds n.) Thus u_n/n! is e^{-2} times
  1 - {1\over n-1} + {1\over 2!(n-1)(n-2)} - {1\over 3!(n-1)(n-2)(n-3)}
etc. To prove this, I noticed that the kth term of Touchard's formula
is n! times (-2)^k/k! - (-2)^{k-2}/1!/(k-2)!/(n-1)
                      + (-2)^{k-4}/2!/(k-4)!/(n-1)/(n-2)
and so on. (A surprising pattern!)

Of course my formula gives u_1 = -1.

I'm feeling happy about this, because the m\'enage problem was
discussed by my advisor Marshall Hall Jr. during the first week
of the combinatorics class I took from him in 1960. The new approach
came to me yesterday while looking at page 14 of his book.

.... Oops, after reading a bit further I discovered the amazing
paper by Wyman and Moser in Canadian J Math 10 (1958). Among
many other things, they derived "my" (*) --- in a rather complicated
way, but it's definitely there, Eq. (5.7) on page 477.
[How nice to have the Canadian Journal online now!]

Wyman and Moser also gave an extensive table, up to u_{65}.
Of course their sequence begins 1, -1, 0, 1, 2, 13, ... . Since this
table was prepared before the era of computers, I sampled
a few values [buf found no typos].

Hmm, I was scooped again. But anyway it's always good to look.