[seqfan] menage numbers

[William Orrick]

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