[seqfan] Re: menage numbers

[Neil Sloane]

I will look into this, but it will take me a few days.  First I have to
reread the Touchard paper, which I last saw probably 50 years ago!

Brendan, thank you for getting a copy of it.


Best regards
Neil

Neil J. A. Sloane, President, OEIS Foundation.
11 South Adelaide Avenue, Highland Park, NJ 08904, USA.
Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ.
Phone: 732 828 6098; home page: http://NeilSloane.com
Email: njasloane at gmail.com



On Wed, Jul 22, 2020 at 12:04 PM William Orrick <will.orrick at gmail.com>
wrote:

> Correction: the desymmetrized sequence (3) should be
>
> 1, -1, 0, 1, 2, 13, 80, 579, 4738, ...
>
> (I left out the second 1 before.)
>
> Best,
> Will
>
> On Wed, Jul 22, 2020 at 11:01 AM William Orrick <will.orrick at gmail.com>
> wrote:
>
> > 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
> >
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>