[seqfan] Re: menage numbers

[William Orrick]

Dear SeqFans,

I've had more time to look at Touchard's 1953 Scripta paper and am now
strongly convinced that the value Touchard gives for phi(1,0) on page 118
is inconsistent with the rest of the paper and with his 1934 paper, i.e.
it's a mistake.  These papers are relevant to several sequences:
A000179/A102761, A000270, and A058087/094314. (For those who want to follow
the discussion and don't have a copy of the paper, which Brendan McKay
obtained for us, please let me know and I will send it to you.)

In the 1953 paper, Touchard uses the notation u_n for the menage numbers.
On pages 114-115 he works the example of enumerating permutations of 1234
discordant with both 1234 and 2143, which, importantly, are discordant with
each other. There are four such permutations: 3412, 3421, 4312, 4321. Since
2143 consists of two 2-cycles, the value of m is 2 in equation (22) and n_1
= n_2 = 2. So equation (22) gives u_4 + u_0 for the number of discordant
permutations. I think everyone agrees that u_4 = 2. The only controversy is
in the value of u_0, which must equal 2 for Touchard's formula to work.
Indeed, on page 115 Touchard writes,
 u(2,2) = u_4 + 2 = u_4 + u_0 = 4.
This, of course, is relevant to the question regarding the initial term of
A000179/A102761. The ultimate reason for choosing u_0 = 2 is because of the
connection of u_n with Chebyshev polynomials, which implies this value.
Taking this seriously allows identities on Chebyshev polynomials to be
used. Such identities lead to formulas like (22).

Moving on to A000270: on pages 115-116, Touchard generalizes the results
above to the problem of enumerating permutations discordant with two
arbitrary permutations, not necessarily discordant with each other. If the
two permutations agree in h positions, then formula (27) applies, which has
the same structure as (22), but uses Touchard's phi(h,n) in place of u_n.
(A000270 is relevant to the case h = 1.)

Consider the problem of finding permutations discordant with 12345 and
13254. These have the element 1 in common and the second has two 2-cycles,
which makes this a special case of the example treated on pages 116-118.
There are 16 such permutations:

24513, 24531, 25413, 25431,
34512, 34521, 35412, 35421,
41523, 41532, 45123, 45132,
51423, 51432, 54123, 54132

Here h = 1, s = 2, and, as in the previous example, n_1 = n_2 = 2. Equation
(27) then implies that the number of discordant permutations is phi(1,4) +
phi(1,0). This formula is the first of the three unnumbered equations
following equation (30). Unfortunately, Touchard does not give its
numerical value. If the sequence on page 118 is correct, this value is 16 +
1 = 17, which disagrees with the exhaustive enumeration. This suggests that
phi(1,0) is supposed to equal 0, not 1.

The third of the unnumbered equations following equation (30) is also
relevant. Touchard gives phi(1,8) + 4phi(1,4) + 3phi(1,0) for the number of
permutations discordant with 123456789 and 132547698. (The latter has four
2-cycles.) If phi(1,0) equals 1, we get 48771, whereas if phi(1,0) equals
0, we get 48768 = 3*2^7*(2^7 - 1). The former cannot be right since, with
four 2-cycles, the answer must be divisible by 2^4. (This follows from the
fact that the two elements of a discordant permutation that are associated
with a given 2-cycle can occur in either order.)

I can't find any mention in the 1953 paper of how phi(h,0) is meant to be
evaluated, apart from the hint that phi(0,0) = u_0 = 2 in the first example
in this post. But in the 1934 paper, Touchard writes on page 632,

 "Les equations (2) et (3) ne coincident pas lorsque n=0; pour l'exactitude
de (1), on doit definir phi(h;0) par la formule (3), d'ou phi(h;0) =
2nu(h,h)."

Equation (1) in that paper is the same as equation (27) in the 1953 paper.
Equation (3) gives phi(h,n) in terms of Chebyshev polynomials, and nu(h,h)
is the number of derangements of h items. This implies phi(0,0) = 2 and
phi(1,0) = 0.

As far as I can tell, the main reason for defining the function phi(h,n) is
for use in  equation (27). Although initial terms of sequences are often a
matter of convention, with valid arguments for different choices, I can't
see any reason in this case for choosing a value that makes equation (27)
fail.

The menage numbers are a different story. As I detailed in an earlier post,
there are at least three sensible conventions. To make equation (22) or
(27) work, however, you need u_0 = 2, u_1 = -1. Currently the version of
the menage numbers with these values is A102761, but that's causing other
problems...

The menage hit polynomials, A058087/A094314, are also involved in all this.
One can argue about whether the top row of the triangle in A058087 should
contain 1 or 2, but the next row has to be 2, -1 rather than 2, 0. The
table in Riordan's book starts with the third row, but the text preceding
the table states that the polynomial for the second row is -1 + 2t. The
version at A094314 seems to be following different conventions, and, I
think, is self-consistent as is.

Best,
Will

> Note that Lucas began at n = 4, obtaining 2, 13, 80...
>  and Comtet at n = 2, obtaining 0, 1, 2
> best
> jp
> Le 22/07/2020 à 18:04, William Orrick a écrit :
>> 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
>>>