[seqfan] Re: SeqFan Digest, Vol 142, Issue 3

[William Orrick]

Dear Brendan,

Thanks for taking the time to track down and send Touchard's paper.

It seems that Touchard had a 65 page manuscript containing details of the
results he stated without proof in his 1934 Comptes Rendus paper, <
https://gallica.bnf.fr/ark:/12148/bpt6k31506/f631.item.zoom>, which he sat
on for 19 years. The Script Math. paper is a belated, and abbreviated,
publication of those results. I'm finding the Scripta Math. paper hard
to follow
without referring back to the Comptes Rendus paper.

The quantity u_n is the nth menage number, that is, the number of
permutations of {1,2,...,n} discordant with both 1,2,...,n and 2,3,...,n,1.
What is commonly called the Touchard formula is equation (17), which is
ill-defined for n = 0, but the expressions in (18) make it clear that u_0 =
2. Touchard is much more explicit about this point in the Comptes Rendus
paper.

I think I would have a hard time piecing together what phi(h,n), given in
Section 5 of the Scripta paper, is supposed to be, had I not first studied
the Comptes Rendus paper, where it is explicitly defined to be the number
of permutations discordant with two permutations whose relative permutation
has h fixed points and otherwise consists of an n-cycle. So phi(1,n), for
example, is the number of permutations discordant with 1,2,...,n,n+1 and
1,3,4,...,n+1,2.

Page 116 of the Scripta paper contains the relation of phi(1,n) to the
menage numbers that Neil has used as the new definition of A000270. What
puzzles me is that in the table on page 118, phi(1,0) is stated to equal 1.
The relation on page 116 implies that phi(1,0) = u_{-1} + u_0 + u_1 = -1 +
2 + -1 = 0. (The definition of u_n for negative n, namely u_{-n} = u_n, is
given on page 114.) In the Comptes Rendus paper, Touchard explicitly states
that phi(h,0) = 2 nu(h,h), where nu(h,h) can be seen to be D_h, the number
of derangements of h items. This again implies phi(1,0) = 0. So I suspect
that the first element of the table on page 118 is in error, unless I've
missed a change in definition somewhere.

Best,
Will


>
>
I now have Touchard's 1953 paper from Scripta Math.? In an moment
> I'll send it to Neil, Will and Frank.? Anyone else, feel free to ask.
> (I'm guessing this mailing list doesn't allow attachments, right?)
>
> A000270 appears at the top of page 118.? Five minutes is not enough
> for me to figure out what it means, but please note that it cannot be
> a count of permutations of {1,...,n} because a(8) > 8!.? I suspect that
> studying the whole paper is necessary.
>
> Cheers, Brendan.
>
> On 21/7/20 11:10 pm, Neil Sloane wrote:
> > Will :
> >
> > good suggestion, about making a(1) = 1
> >
> > i will take care 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 Tue, Jul 21, 2020 at 1:54 AM William Orrick <will.orrick at gmail.com>
> > wrote:
> >
> >> Dear Neil,
> >>
> >> I just noticed your changes to A000270. I agree with changing a(0) to 0,
> >> but you might consider keeping a(1)=1, rather than changing it to 0.
> >> There's a sequence A102761 that is the same as A000179 except for the
> first
> >> term. If you use A102761 instead of A000179 to generate A000270, and
> keep
> >> a(1)=1 in A000270, then the relation you now use to define A000270 works
> >> for all n, even negative n, with the convention a(-n) = a(n). I don't
> see a
> >> clear combinatorial meaning for a(0) and a(1), or for a(n) with n
> negative,
> >> but Touchard needs these to have the values implied by A000179 in order
> for
> >> equation (1) in his 1934 paper to work. (This is the general formula for
> >> the number of permutations discordant with two given permutations, and
> >> seems to correspond to equation (22) in Kaplansky and Riordan.)
> >>
> >> Best,
> >> Will
> >>
> >> On Tue, Jul 21, 2020 at 12:33 AM William Orrick <will.orrick at gmail.com>
> >> wrote:
> >>
> >>> Dear SeqFans:
> >>>
> >>> Thanks Neil for posting the annotated copy of Kaplansky and Riordan.
> Is
> >>> the other Kaplanasky and Riordan paper you mentioned this one:
> >>>
> >>>   The problem of the rooks and its applications. Duke Math. J. 13
> (1946)
> >>> 259-268?
> >>>
> >>> I would be interested in seeing the MathSciNet reviews you mentioned if
> >>> it's easy to send them.
> >>>
> >>> Brendan: in the original post in this thread I suggested that A000270
> is
> >>> the number of permutations of {1,2,...,n+1} discordant with both the
> >>> identity permutation and with a permutation consisting of a 1-cycle and
> >> an
> >>> n-cycle.
> >>>
> >>> I have a new proposed sequence, A335391, not yet approved that is based
> >> on
> >>> Touchard's earlier paper of 1934. I believe A000270 is the second row
> of
> >>> the square array in that sequence. Only the element in the first column
> >>> disagrees. The new sequence contains a link to a post on
> >> math.stackexchange
> >>> where some of the statements in Touchard's paper are proved. The
> relation
> >>> Neil mentioned with the menage numbers is also proved there.
> >>>
> >>> There are quite a few sequences in the OEIS with the title "discordant
> >>> permutations" or similar.  Many of these are related to permutations
> >>> discordant with three given permutations, rather than with two given
> >>> permutations as is the case here.
> >>>
> >>> Best,
> >>> Will Orrick
> >>>
>
>