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 , 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.