First Written: Jan. 5, 2014.
This version: Feb. 3, 2014.
In fond memory of Alain Lascoux (1944-2013), one of the most CREATIVE and ORIGINAL and INTERESTING
mathematicians that I have ever known
The two other talks were indoors. At the second talk I mentioned and briefly sketched, the
Brydges-Spencer Lace Expansion, that lead, way back in the early-1990s, to the seminal work of
Takashi Hara and Gordon Slade about the asymptotic behavior of the enumerating
sequence of self-avoiding walks in dimensions five and up.
The last talk, that formed the basis of the present
article, was about counting restricted permutations via rook polynomials, and how computers can be taught to generate,
in a few seconds, deep theorems, that took such great minds like Arthur Cayley, F.R.S., Sir Thomas Muir, Monsieur le colonel
Charles Moreau (a decorated soldier, brilliant amateur mathematician, but not quite as good chess player),
notable politician Charles-Ange Laisant, the great Major Percy MacMahon, Jacques Touchard,
John Riordan (the master of ars combinatorica), the great algebraist Irving Kaplansky,
the great enumerator Earl Glenn Whitehad, and numerous others (including algebaric
combinatorics guru Richard Stanley, that covered rook polynomials in his classic EC1, but
regretfully did not even mention John Riordan, his analog a generation earlier).
The venue was especially auspicious, as Bertinoro is the birthplace of one
of the greatest medieval rabbis,
Obadiah Bertinura, the great commentator of the Mishna.
My good friend Omar Foda, who participated in the conference, found
his house
and kindly took a
picture
of me standing in front Obadiah's house, and
another picture
of my wife Jane and I standing in front of it
-
To see the generating functions for rook polynomials for k-discorcant
permutations for k from 1 to 4, reproducing in 12 seconds, the
labor of Euler (k=1), Lucas (and Laisant, Moreau, Touchard, Kaplasnky and many other smart people) (k=2),
Riordan (k=3, plus we got a brand-new recurrence for the enumerating sequence itself),
and Whitehead(k=4). It also gives you the first 40 terms, and the 300-th term of the enumerating sequences.
the input file
yields the
output file.
-
It is amazing that a human (Earl Glen Whitehead) could do, by hand, the case k=4, but
I am willing to bet that even he would give up for k=5, and k=6. If you want
the generating functions for rook polynomials for k-discordant permutations for k from 1 to 6,
(and the first 40 terms, and the 300-th term of the enumerating sequences)
the input file
yields the
output file.
-
To see a webbook that gives you the generating functions for rook polynomials for enumerating
permutations π of {0,1,..,n-1} such that π[i]-i mod n is never in the set S,
for all subsets S of {0,1,2,3,4} including 0, and in many cases, nice recurrences
for the enumerating sequences themselves, and the first 40 terms, and the 400-th term
the input file
yields the
output file.
-
To see a webbook that gives you the generating functions for rook polynomials for enumerating
permutations π of {1,..,n} such that π[i]-i is never in the set S,
for all subsets S of {-2,-1,0,1,2} with at least two elementes,
and in many cases, nice recurrences for the enumerating sequence itself,
the input file
yields the
output file.
-
To see the first 30 terms, linear recurrences, asymptotics, and the 1000-th term
of the sequences "number of (usual) permutations π of {1,...n}" where
πi -i is never in {0} (the good-old derangements) and,
when πi -i is never in {0,1} (the straight Menages problem)
[Using the "clever" approach inpspired by Kaplansky's solution]
the input file
yields the
output file.
Here we find A000166 (the famous derangements number)
and A000271, the straight Ménage numbers.
-
To see the first 30 terms, linear recurrences, asymptotics, and the 1000-th term
of the sequences "number of (usual) permutations π of {1,...n}" where
πi -i is never in {0} (the good-old derangements) and,
when πi -i is never in {0,1} (the straight Menages problem)
[Using the "clever" approach inpspired by Kaplansky's solution] (so far it is the same as above),
as well as for the enunerating sequence of permutations π for which πi -i is never in {0,2}
and the enumerating sequence of permutations where πi -i is never in {0,1,2}
(that took the great John Riordan many a long months (by hand!))
the input file
yields the
output file.
[Note that the sequence for S={0,2} is not yet (Dec. 26, 2013) in the OEIS.
The sequence for S={0,1,2} is A0001887, considered
by John Riordan in 1963. Note that Shalosh redid in less than three seconds
what took Riordan probably a couple of months, and it did much more, and found
a seventh-order linear recurrence equation with polynomial coefficients
(at worst quadratic) satisfied by the sequence, as well as asymptotics to order 10.]
-
To see the more extensive date for all sequences enumerating permutations
π for which πi-i is NEVER in a given, prescribed set
S, for ALL subsets of {0,1,2,3} containing 0,
[still using the "clever" approach inspired by Kaplansky's solution]
the input file
yields the
output file.
[Note that for the sets {0,1,3}, {0,2,3}, and {0,1,2,3} there is no linear recurrence of "complexity" ≤ 20,
so it only returned the first 30 terms of the enumerating sequece. One can increase the
the third argument of pocedure Sefer to get them, if one wishes. Many of these sequences are not yet (Dec. 26, 2013) in OEIS]
-
To see the first 30 terms, a recurrence, asymptotics, and the 1000-th term for
ALL sequences
π for which πi-i is NEVER in a given, prescribed set
S, for ALL 31 non-empty subsets of {-2,-1,0,1,2}
[Using the "empircal-yet-rigorous" Zeilberger-style approach]
the input file
yields the
output file.
[Note, some of the theorems are trivially equivalent to each other, of course, but who cares?
Many of these sequences are not yet (Dec. 26, 2013) in OEIS.]
-
Suppose there are n diners sitting around a ROUND table. After the main course is over, they
all go for a little walk in the woods, and then return for dessert.
In how many ways can they be reseated in such a way that the "distance" (by number of chairs),
counted clockwise, between the location of each diner during the main course and during
the dessert is NEVER in a prescribed set S. Let's call this set aS(n).
[Note that when S={0} it is derangements, and S={0,1} it is ,
A0000179, the classical problème des ménages]
If you want to see interesting information about these sequences for
ALL 7 non-empty subsets, S, of {0,1,2,3} containing 0, the
the input file
yields the
output file.
[It also uses the "empircal-yet-rigorous" Zeilberger-style approach]
For S={0,1,2,3} is is A004307
For S={0,2,3} it is not yet (Dec. 26, 2013) in OEIS.
For S={0,1,3} it is not yet (Dec. 26, 2013) in OEIS.
For S={0,1,2} (alias S={-1,0,1}) it is A000183 that goes back to John Riordan (1954),
but the recurrence seems to be new.
For S={0,3} it is not yet (Dec. 26, 2013) in OEIS. (Note the complicated recurrence)
For S={0,2} (alias S={-1,1}) it is not yet (Dec. 26, 2013) in OEIS!
This is the numbers of ways of reseating n people around a round table where
it is OK to go back to the original chair, but you can't seat in an adjacent chair.
Note the elegant recurrence
a(n) = na(n-1)+3a(n-2)+(-2n+6)*a(n-3)-3a(n-4)+(n-6)a(n-5)+a(n-6) .
In the old days, it would have been worthy of a whole paper!
-
To see, yet another time, the good old derangement numbers, i.e. the
number of ways of reseating n diners in a round table, where no one can go back
to the original chair (of course, it is the same whether the table is
circular or straight).
the input file
yields the
output file.
-
To see, yet another time, the good old Ménage numbers,
A0000179,
i.e. the number of ways of reseating n diners in a round table, where no one can go back
to the original chair, and the chair next to it (going clockwise),
the input file
yields the
output file.
-
To see, yet another time,
information about the sequence enumerating the number of ways of reseating n diners in a round table, where each diner
must avoid the original chair and the two chairs next to it,
i.e. sequence A000183 that goes back to John Riordan (1954),
the input file
yields the
output file.
[Note the complicated (new!) 8-th order linear recurrence with quartic coefficients, and the implied asymptotics.]
-
To see information about the sequence enumerating the number of ways of reseating n diners in a round table, where each diner
must move at least four chairs clockwise (i.e. S={0,1,2,3}), a sequence considered by
"Earl Glen Whitehead, Jr., Four-discordant permutations, J. Austral. Math. Soc. Ser. A 28 (1979), no. 3, 369-377."
i.e. sequence A004307 ,
the input file
yields the
output file.
[Note the complicated (new!) 21-th order linear recurrence with degree-eight coefficients!]
-
To see information about the sequence enumerating the number of ways of reseating n diners in a round table, where each diner
must move at least five chairs clockwise (i.e. S={0,1,2,3,4}), i.e. sequence
A189389,
the input file
yields the
output file.
[Shalosh refused to find a recurrence, to save bytes]
-
To see information about the sequence enumerating the number of ways of reseating n diners in a round table, where each diner
must move at least six chairs clockwise (i.e. S={0,1,2,3,4,5}), i.e. sequence
A184965,
the input file
yields the
output file.
[Shalosh refused to find a recurrence, to save bytes]