Talk:Ménage problem

Umbral formula

The article contains the sentence, "A different umbral formula for M_n involving Chebyshev polynomials of first kind was given by Wyman & Moser (1958)." I'm trying to understand first what this sentence means to say and second what it ought to say. Not being well-versed in umbral methods, I don't feel qualified to pronounce on the second question, but I hope somebody else will weigh in.

Does the sentence mean to say that Touchard's formula is an umbral formula involving Chebyshev polynomials of the first kind and that Wyman and Moser's formula is a different such formula? Or is it saying that only Wyman and Moser's formula has either (both?) of these characteristics?

It seems to me that both formulas involve Chebyshev polynomials of the first kind, and that both are umbral, with some meaning of the word "umbral". Touchard writes, after giving his formula in essentially the form given in our article,

ou bien, sous forme symbolique, φ(h; n) = 2 cos(2n arc cos ½ √ν), formule dans le développement de laquelle on doit remplacer ν^μ par ν_μ = ν(h, h+μ).

Note that h = 0 is the case of Touchard's formula that is relevant to the ménage problem and that ν(0, μ) = μ!, which is how the (n−k)! factor in Touchard's formula arises in this prescription. This prescription certainly involves Chebyshev polynomials of the first kind since 2 cos(2n arc cos ½ √ν) = 2T_2n(½ √ν), and it sort of looks umbral in the replacement of the power of ν by the subscripted quantity.

Wyman and Moser's prescription is similar, but involves 2T_n(½ ν) instead of 2T_2n(½ √ν) and the subscripted quantity that replaces the power of ν is a bit more complicated in their formula. They use the phrases "umbral convention of replacing…" and "neat, mnemonic, formula", and it's not clear to me how central umbral calculus is in their thought process. Both Touchard's paper and Wyman and Moser's paper predate the modern developments in umbral calculus, but undoubtedly both sets of authors were very familiar with the classical umbral calculus. Not being an expert, I find it hard to say whether their formulas/derivations are technically umbral in either sense of the word. Any thoughts? Will Orrick (talk) 16:17, 13 June 2020 (UTC)

Ladies-first solutions

I'm thinking of revising the article to eliminate mention of ladies-first vs. non-sexist solutions. As far as I can see, Bogart and Doyle simply overlooked the straightforward way in which their visualization is compatible with Kaplansky's ladies-first proof; in the final analysis, Kaplansky's proof and Bogart & Doyle's proof are the same proof, except that Kaplansky's proof omits a few unnecessary steps. And either proof boils down to elementary combinatorics—nothing here seems worth a New York Times article or a major chunk of real estate in a Wikipedia article (see the Gleick reference). Please let me know if there are objections. Will Orrick (talk) 15:13, 21 August 2020 (UTC)

Are you talking only about the single paragraph beginning "Until the work of Bogart & Doyle (1986)" or the mathematical content surrounding it? —David Eppstein (talk) 17:08, 21 August 2020 (UTC)

I don't want to eliminate any mathematical content. The simplest change would be to cut out the paragraph you mention and change the title of that section, although it might be worthwhile making a few other adjustments at the same time. For example, Touchard's formula is actually the formula for A_n, not the formula for M_n. Touchard's 1934 paper doesn't even mention ménages, instead focussing on permutations discordant with two given permutations (and solving the general problem, not just the case relevant to the ménage problem). The relation of the ménage and discordant permutations problems would have to be moved to an earlier point in the article, but this might be good since discordant permutations were important in the pre-Lucas history of the problem and in many subsequent developments.

An alternative to deleting the Bogart and Doyle material would be to find a place to move it to, but I'm not sure where a good place for it might be. The history of the ménage problem is messy and seems to be a series of mishaps and misunderstandings. I actually find the history interesting but I'm not sure most readers will. The discordant-permutations formulation of the problem was posed by Tait, and solutions were found as far back as 1878 by Muir and Cayley, but Touchard's straightforward explicit expression wasn't found until more than half a century later, in 1934. Unfortunately, Touchard's paper was simply a concise list of results with no proofs and few explanations. Touchard produced a second manuscript of 65 pages detailing these, but never got around to publishing it. Meanwhile, in 1943 Kaplansky published a proof of Touchard's formula. His paper was very short and succinct—and elegant—but seems not to have been widely appreciated. Shortly thereafter, Kaplansky and Riordan published a more detailed derivation, but their treatment aims for slightly more and doesn't look particularly simple. Several years after that, in 1953, Touchard, realizing he'd been scooped, published his own alternative derivation with Riordan's assistance, but again, a lot of the simplicity got lost in the presentation.

Because of all this, I think it's understandable that Bogart and Doyle in 1986 felt that people had been overcomplicating the problem. Their article gets a lot of attention because it is easy to follow, but if they are correct that something was impeding understanding, it doesn't seem that their diagnosis of ailment has stood the test of time. As far as I can tell, there haven't been other "non-sexist" solutions, and their treatment doesn't seem to have become the standard. Their main contribution, according to Kirousis and Kontogeorgiou, appears to have been making it easier to appreciate Kaplansky's short proof. And their solution, which seats the "ladies" in stages, rather than all at once at the beginning, ends up being more complicated than Kaplansky's. Furthermore the number of ways of seating the women still "factors out" in their method. Will Orrick (talk) 05:38, 22 August 2020 (UTC)

Well, I think this history is interesting so that's two. But anyway, as far as I'm concerned, please go ahead with however you think would convey this more clearly. —David Eppstein (talk) 06:21, 22 August 2020 (UTC)