[seqfan] Re: menage numbers

William Orrick will.orrick at gmail.com
Wed Jul 22 18:04:21 CEST 2020

Correction: the desymmetrized sequence (3) should be

1, -1, 0, 1, 2, 13, 80, 579, 4738, ...

(I left out the second 1 before.)


On Wed, Jul 22, 2020 at 11:01 AM William Orrick <will.orrick at gmail.com>

> Dear SeqFans,
> This is a spinoff of the thread on discordant permutations. (And I would
> like to apologize for my bad subject line in my latest post in that thread.)
> There are two sequences in the OEIS for the menage numbers, A000179 and
> A102761, which differ only in their initial term. Recall that the menage
> numbers multiplied by 2*n! give the number of ways of seating n female-male
> couples around a circular table so that females and males alternate and so
> that no person is seated next to their partner.
> I think it worth discussing what the initial terms should be in the main
> sequence, and what alternative sequences are worth including, either as
> separate sequences or as comments to the main sequence. The initial terms
> in both sequences have changed over the years, and a number of
> inconsistencies have arisen.
> I can see three reasonable choices:
> 1) The physically correct choice: there is one empty arrangement, no
> viable arrangements for one or two couples, one viable arrangement for
> three couples, and so on, giving
> 1, 0, 0, 1, 2, 13, 80, 579, 4738, ...
> The Examples section of A000179 contains wording very similar to what is
> written above, even though the sequence doesn't match this description
> (anymore).
> 2) The mathematically nicest choice: Touchard gives an expression for the
> menage numbers involving Chebyshev polynomials of the first kind. This
> expression results in the sequence
> 2, -1, 0, 1, 2, 13, 80, 579, 4738, ...
> He also extends the sequence to negative n using the rule a(-n) = a(n).
> This makes many recurrences extend nicely to all integers. Furthermore, the
> "non-physical" values, i.e. those for n <= 1, are actually needed in order
> for certain formulas to work, namely Touchard's formulas for the number of
> permutations discordant with two given permutations.
> Touchard isn't the only person to do this.  Riordan, on page 197 of
> "Combinatorial Analysis" writes an expression implying that a(1) = -1 and
> notes that this is a "natural value". He further writes, "the value for n =
> 0 is set by convention and it is sometimes convenient, as will appear, to
> take M_0 = U_0 = 2 rather than the usual M_0 = U_0 = 1."  Here U_0 is a(0).
> 3) A "desymmetrized" choice:
>  1, -1, 0, 2, 13, 80, 579, 4738, ...
> Riordan, as implied by the quotation, sometimes uses a(0) = 1 and
> sometimes uses a(0) = 2. One place where he uses a(0) = 1 is in his
> expression for the number of three-line Latin rectangles (A000186). What's
> going on here is that the expression is a sum with limits 0 and floor(n/2).
> The summand, however, is symmetric about n/2, so one could extend the upper
> limit to n and place a factor of 1 / 2 out in front. Then everything would
> work nicely with the "mathematically nice" convention a(0) = 2. If one
> wants to use Riordan's actual expression, with upper limit floor(n / 2),
> one needs the "desymmetrized" convention, a(0) = 1.
> ----
> So where do we stand right now? The "main sequence", A000179, at present
> is sequence (3), the desymmetrized version. It was not always this way.
> A000179 started off with offset 3, at the first non-zero value. Eventually
> the sequence was extended backwards to offset 0, settling on (1), the
> "physical" definition.
> At some point it was noticed that Riordan's expression for A000186 was
> broken (since a(1) = -1 is needed to make it work). To fix this, the
> sequence A102761 was created in 2010 at the suggestion of Vladimir Shevelev
> using (3), the desymmetrized definition. The sequence contained a comment
> that this was needed "to simplify the formula for  A000186". At the same
> time a comment was added to the main sequence, A000179, stating that "John
> Riordan considered a(1) to be -1", and a link was given to the new sequence.
> In March 2018, a(0) of A102761 was changed to 2, making the sequence agree
> with (2), the "mathematically nicest" definition. As a consequence A000186
> was again broken.
> In November 2018, a(1) of the main sequence, A000179, was changed to -1 at
> the suggestion of Donald Knuth, making it agree with (3), the desymmetrized
> version.
> So at present, A000186 does not work with A102761, even though that is its
> main reason for existence! It does now work with the original sequence,
> A000179. There are, however, dozens of other sequences that refer to
> A000179, not to mention references in the external mathematical
> literature, so changing A000179 again may break some things. A000179 also
> has many comments, formulas, and recurrences, and it is not completely
> clear to me which of these work with which definition. There are also about
> a dozen sequences referring to A102761, most of which will break if it is
> changed.
> The solution I see that requires the least work is the following.
> (1) Restore the main sequence, A000179, to the physical definition. It's
> only used the desymmetrized definition for about a year and a half, so
> probably not much depends on that definition.
> (2) Keep A102761 as is (the mathematically nice definition) since about
> ten sequences depend on its current state.
> (3) Create a new sequence for the desymmetrized definition, and modify
> A000186 to refer to it (with credit to Shevelev and Knuth).
> (4) Add prominent links in all three sequences to each of the others,
> perhaps even in the definition line, to discourage further changes.
> The main downside I see for this solution is that I would prefer the main
> sequence to be the mathematically nicest one. The main sequence is the one
> where the bulk of the comments, formulas, recurrences, and programs are
> given, and many of them need caveats such as "this definition is only valid
> for n >= ... but extends nicely to all integers if the initial terms are
> changed to...".
> Best,
> Will Orrick

More information about the SeqFan mailing list