Séminaire Lotharingien de Combinatoire 71 (2014), Article B71a

Automatic Enumeration of Generalized Ménage Numbers

Doron ZEILBERGER^{1}

In fond memory of Alain Lascoux (1944–2013), one of the most CREATIVE and ORIGINAL and INTERESTING mathematicians that I have ever known

One of Alain Lascoux’s Favorite Identities: 0 = 1 + (−1)

Alain Lascoux once said that “adding and subtracting one” is one of the most useful tricks in mathematics, and he was right!

Suppose that you have a large set of guys, that is easy to count, and there is a smaller set of good guys that is hard to count. In other words, the sum

A := ∑_{g∈AllGuys} 1 ,

is easy, but

G := ∑_{g∈GoodGuys} 1 ,

is hard.

Another deep identity in mathematics is, ( for i a non-negative integer)

0^{i} = 0 if i > 0, 0^{0} = 1.

1 Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen Rd., Piscataway, NJ 08854-8019, USA. zeilberg at math dot rutgers dot edu ,

http://www.math.rutgers.edu/~zeilberg/ .

First version: Jan. 5, 2014. This version: Feb. 3, 2014 [Many thanks are due to the two editors, Christian Krattenthaler and Volker Strehl, for many insightful comments, and numerous corrections, that greatly improved this article.]

Accompanied by Maple package MENAGES downloadable from

http://www.math.rutgers.edu/~zeilberg/tokhniot/MENAGES .

[Disclaimer: this package outputs theorems with proofs that are either already rigorous, or could be easily made so, if desired. No attempt is made to distinguish between these two cases, since the author does not believe this distinction to be important. However, those who do care about this distinction are more than welcome to rigorize themselves the proofs that they believe are in need of such a rigorization.]

Supported in part by the NSF.

If some guy, let’s call him Mr. g, is not a good guy, it means that he is a bad guy, which means that his set of sins, Sins(g), is non-empty, so we have

G = ∑_{g∈AllGuys} 0^{|Sins(g)|} ,

(the number of elements of a set S is denoted by |S|). Now we use Lascoux’s favorite identity 0 = 1 + (−1) and get

G = ∑_{g∈AllGuys}(1 + (−1))^{|Sins(g)|} .

We need yet another deep identity. For any set S, we have: ^{2}

(1 + (−1))^{|S|} = ∑_{T ⊂S}(−1)^{|T |} .

Going back to the formula for G, we have

G = ∑_{g∈AllGuys} 0^{|Sins(g)|} = ∑_{g∈AllGuys}(1 − 1)^{|Sins(g)|} = ∑_{g∈AllGuys} ∑_{T ⊂Sins(g)}(−1)^{|T |} .

By Discrete Fubini (aka changing the order of summation), we have

G = ∑_{T ⊂AllSins}(−1)^{|T |} ( ∑_{{g:Sins(g)⊃T }} 1) .

Abbreviating, for any set of sins T,

A_{T} := ∑_{{g:Sins(g)⊃T }} 1 = |{g ∈ AllGuys ; T ⊂ Sins(g)}| ,

the number of guys that are guilty of all the sins in T (but very possibly of other ones as well!), we have a form of the famous Inclusion-Exclusion Principle:

G = ∑_{T ⊂AllSins}(−1)^{|T |}A_{T} .  (P IE)

(1 + (−1))^{|S|} = ∏_{s∈S}(1 + (−1)) = ∑_{T ⊂S} ∏_{s∈S} 1^{χ(s∉T)}(−1)^{χ(s∈T)}

= ∑_{T ⊂S} ∏_{s∈S}(−1)^{χ(s∈T)} = ∑_{T ⊂S} ∏_{t∈T}(−1) = ∑_{T ⊂S}(−1)^{|T |} .

2 Let χ(statement) equal 1 or 0 according to whether the statement is true or false. We have ??

From the Mouth of our Patron Saint: Gian-Carlo Rota

The patron saint of enumerative combinatorics, Gian-Carlo Rota (1932–1999), started his seminal article [Ro] as follows:

“One of the most useful principles of enumeration in discrete probability and combinatorial theory is the celebrated principle of inclusion-exclusion. When skillfully applied, this principle has yielded the solution of many a combinatorial problem … ” .

He then goes on to say:

“One frequently notices, however, a wide gap between the bare statement of the principle and the skill required in recognizing that it applies to a particular problem … ”

And indeed, it required lots of human ingenuity to apply it to many separate problems, and one of the most impressive applications was to the enumeration of permutations with restricted positions, with its accompanying beautiful theory of rook polynomials, described at length in the classic [Ri1] of yet-another-guru, John Riordan, and from a more ‘advanced’ viewpoint in the later classic [St], by still-another-guru, Richard Stanley, who used the transfer-matrix method (but he should have mentioned the earlier classic [Ri1]!).

Back to Inclusion-Exclusion

In many applications, including the ones discussed in this article, to the counting of discordant permutations, and more generally, permutations with restricted positions, it so happens that, in Eq. (P IE), for many T ’s, A_{T} = 0, since the sins in T are incompatible, but for those T for which A_{T} ≠ 0, A_{T} only depends on the number of elements of T, |T |, so we have, in these cases

A_{T} = 0 or A_{T} = f(|T |) ,

for some discrete function f(k).

So things boil down to the weighted counting of compatible sets of sins, T, i.e., sets of sins for which A_{T} ≠ 0, according to the weight (−1)^{k}f(k), where k := |T |.

Enumerating Permutations with Restricted Positions NUMERICALLY

Fix a positive integer n, say n = 5. For each integer i, 1 ≤ i ≤ n, let there be a subset A_{i} of {1, …, n}. For example,

A_{1} = {1, 4, 5}, A_{2} = {3, 4}, A_{3} = {1, 3, 4}, A_{4} = {2, 3, 5}, A_{5} = {1, 4, 5}.

We want to count the number of n-permutations π such that

π(i) ∉ A_{i}, i = 1 … n.

Before reviewing how to do it via the Principle of Inclusion-Exclusion (Eq. (P IE)), and Riordan’s lovely rook polynomials, let us recall the straightforward, “positive” approach, via permanents.

The Positive (Naive) Approach

Let Us define the complement sets

B_{i} := {1, …, n}\A_{i} ,

so in the above example

B_{1} = {2, 3}, B_{2} = {1, 2, 5}, B_{3} = {2, 5}, B_{4} = {1, 4}, B_{5} = {2, 3}.

So our problem is to count the n-permutations such that

π(i) ∈ B_{i}, 1 ≤ i ≤ n.

Now form the 0 − 1 matrix P = P_{i,j} whose i-th row has 1’s in the columns belonging to B_{i}, so in this example:

P = ( \begin{matrix}0 & 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 & 0 \end{matrix} ) .

The desired number is simply the permanent of P, per P, in this example

per P = per ( \begin{matrix}0 & 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 & 0 \end{matrix} )

= 1 · per ( \begin{matrix}1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \end{matrix} ) + 1 · per ( \begin{matrix}1 & 1 & 0 & 1 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \end{matrix} ) = 1 + 1 = 2 .

And indeed, there are two permutations that satisfy the conditions, namely:

{21543, 31542} .

Thanks to Leslie Gabriel Valiant [V], we know that for larger n, and random (not too small) B_{i}, this method is (probably) hopeless.

A crash course on Rook Polynomials

Fix, for now, a specific (numeric), positive integer n, and suppose that we are given any (arbitrary) n subsets A_{i}, 1 ≤ i ≤ n, as above, and ask for the number of permutations of length n, π, such that

π(i) ∉ A_{i} .

So the set of all guys, AllGuys, is S_{n}, and there are

∑_{i=1}^{n} |A_{i}| ,

possible sins that such a permutation can commit, and we want to count the good guys, those that have no sins.

There is a natural way of representing permutations in terms of ways of placing n non-attacking rooks on an n × n chessboard. For any permutation π, let the (sole, of course) rook in the i-th row, be placed in the π(i)-th column. The condition that π is a permutation guarantees that there is exactly one rook in every column.

Now, given the sets A_{i} above, cross out, in each row i, the entries of the columns corresponding to the members of A_{i}, (in other words, you put an X at P_{ij} for j ∈ A_{i}) getting a board, a certain subset of the n×n chessboard, where it is forbidden to place rooks. For example if, as above

A_{1} = {1, 4, 5}, A_{2} = {3, 4}, A_{3} = {1, 3, 4}, A_{4} = {2, 3, 5}, A_{5} = {1, 4, 5},

then we have the cross-out board

( \begin{matrix}X & & & X & X \\ & & X & X \\ X & & X & X \\ & X & X & & X \\ X & & & X & X \end{matrix} ) .

Now it is time to look at the possible ‘sets of sins’, T, and the corresponding cardinality of A_{T}.

Let Us look at the possible subsets of sins a permutation may be guilty of. If the set T, of chosen Xs, has two or more members in the same row, or two or more members in the same column, then no permutation can be so sinful, (or else it would not even be a permutation!). On the other hand, if the set, T, of chosen Xs has the property that no two of its members are ever on the same row, or on the same column, and T has k members, then the cardinality of A_{T} is (n − k)!, since we already know, for sure, where k rooks are, and the number of ways of placing the n − k remaining rooks is (n − k)!.

This may be viewed as a brand-new combinatorial problem, that of weight-enumerat-ing the set of placements of any number of rooks (from 0 to n) on the squares marked by X (the board), in such a way that they are non-attacking, weighted by t^{k}, where k is the number of rooks participating. In the above example, we have

R(t) = 1 + 14 t + 63 t^{2} + 105 t^{3} + 56 t^{4} + 6 t^{5} ,

meaning that there is exactly 1 ways (of course) of placing 0 rooks, 14 ways (of course) of placing 1 rook, 63 ways of placing 2 non-attacking rooks, …, and 6 ways of placing 5 non-attacking rooks.

This is called the rook polynomial of the board, R_{B}(t).

We now do the ‘umbral’ substitution t^{i} → (−1)^{i}(n − i)!, or equivalently, evaluate the integral

∫_{0}^{∞} e^{−t}t^{n}R(−\frac{1}{t}) dt ,

and get, in this example, with n = 5, that it equals 2, confirming the previous ‘positive’ approach using permanents.

How to compute Rook Polynomials for a specific (arbitrary) board?

By recursion of course! It is more convenient to represent a board by a 0-1 matrix, where 1 denotes X and 0 denotes a blank square. So you get the complementary matrix to the one above when we did it via permanents. In the above example, we have the cross-out board

B = ( \begin{matrix}1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 1 & 0 \\ 0 & 1 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 & 1 \end{matrix} ) .

If you input such a 0-1 matrix, B, let us look at the top row. If it is not the all-0 row, i.e., there is at least one 1, let j be the smallest column with that 1. Then we have the dilemma ‘to place or not to place’ a rook there. If we decide not to place a rook there, we replace the 1 by 0, getting another n × n matrix with one fewer 1, let us call it B_{1}. In this example, we have the cross-out board

B_{1} = ( \begin{matrix}0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 1 & 0 \\ 0 & 1 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 & 1 \end{matrix} ) .

On the other hand, if we decide to place a rook there, then we must delete the first row, and the j-th column, since no more rooks are allowed there, getting a smaller, (n − 1) × (n − 1) matrix B_{2}. In this example, we have

B_{2} = ( \begin{matrix}0 & 1 & 1 & 0 \\ 0 & 1 & 1 & 0 \\ 1 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 \end{matrix} ) .

Since R_{B}(t) is the weight-enumerator, according to the weight t^{#rooks}, we have the recursion

R_{B}(t) = R_{B_{1}}(t) + tR_{B_{2}}(t) ,

where both B_{1} and B_{2} are ‘smaller’ in some sense.

What if the first row only has 0’s? Then we do the analogous thing to the first column. What if the first row and the first column have all zeros?, then we delete both the first row and the first column, getting an (n − 1) × (n − 1) matrix, B′, and of course R_{B}(t) = R_{B′}(t).

But we are mathematicians, NOT accountants, we want GENERAL, Explicit, Symbolic Formulas, Valid for Every n

So we need more structure, and consider ‘infinite families’ of boards.

The grand-daddy of this type of problems is the good-old Problème de rencontres, raised way back in 1713 by Pierre Rémond de Montmort, and solved by Euler, see the many references in [Sl1].

Here the board is the identity matrix I_{n}, and we have the trivial recurrence

R_{n}(t) = (t + 1)R_{n−1}(t), R_{0}(t) = 1,

leading to the ‘explicit’ expression

R_{n}(t) = (t + 1)^{n} ,

and hence the number of derangements is

D_{n} = ∫_{0}^{∞} t^{n} (1 − \frac{1}{t})^{n} e^{−t} = ∫_{0}^{∞}(t − 1)^{n}e^{−t} ,

that implies (inter alia via the not-as-famous-as-it-should-be Almkvist–Zeilberger algorithm [AZ]), the inhomogeneous first-order linear recurrence with polynomial coefficients

D_{n} − nD_{n−1} = (−1)^{n} ,

as well as the homogeneous linear recurrence with polynomial coefficients

D_{n} − (n − 1)D_{n−1} − (n − 1)D_{n−2} = 0 .

Both of these recurrences go back, at least, to Euler.

The Problème des Ménages of Edouard Lucas

A bit more challenging are the boards

M_{1} = ( \begin{matrix}X & X \\ & X & X \\ … \\ … \\ & & & X & X \\ & & & & X \end{matrix} ) ,

for a straight table, and

M_{2} = ( \begin{matrix}X & X \\ & X & X \\ … \\ … \\ & & & X & X \\ X & & & & X \end{matrix} ) ,

for a ‘round table’ (see below). These come up in the solution of the celebrated Problème des Ménages concocted by one of the most amusing (and deep!) mathematicians of all time, the inimitable Edouard Lucas. In his own mots ([Lu], p. 215, also quoted by Major Percy Alexander MacMahon [M], p. 253):

“ Problème des ménages. – Des femmes, en nombre n, sont rangées autour d’une table, dans un ordre déterminé ; on demande quel est le nombre des manières de placer leur maris respectifs, de telle sorte qu’un homme soit placé entre deux femmes, sans se trouver à côté de la sienne” .

In other words, in how many ways can n married couples, sitted around a round table, have a fun and interesting dinner, where each wife can flirt with both men next to her, and not sit next to her boring husband, who, being French, probably cheats on her, and conversely, every husband has opportunities to seduce two other married women.

This problem was independently posed, in a more ‘serious’ context, by Peter Guthrie Tait, the close collaborator of Lord Kelvin, that somehow came up in his study of knots.

The two sequences that come up (for a straight and round table respectively) are [Sl2] and [Sl3], see the many references given there. The most satisfactory answer was given by monsieur le colonel Charles Paul Narcisse Moreau, a decorated soldier, superb amateur mathematician, but not-quite-as-good chess player, and noted politician and mathematician/engineer Charles Ange Laisant, who derived the recurrence (for the round table):

A_{n} = nA_{n−1} + 2A_{n−2} − (n − 4)A_{n−3} − A_{n−4} .

This answer, that only requires O(N) arithmetical operations to compute the first N terms, is much better (at least in the sense of my master, Herb Wilf) than the later ‘answer’ by Jacques Touchard,

A_{n} = ∑_{k=0}^{n}(−1)^{k} \frac{2n}{2n − k} \binom{2n − k}{k}(n − k)! ,

that requires O(N^{2}) arithmetical operations, notwithstanding Gian-Carlo Rota’s pronouncement ([Ro], p. 340) that Touchard’s ‘explicit’ formula is superior to the recurrences. In fact, using the Zeilberger algorithm [Z1], one can use Touchard’s ‘explicit’ binomial coefficients sum to give yet-another-proof of the colonel’s and the politician’s recurrence.

But why stop here? The great (and fearless!) John Riordan [Ri2], did the next-in-line, the board

( \begin{matrix}X & X & X \\ & X & X & X \\ … \\ … \\ & & & & X & X & X \\ X & & & & & X & X \\ X & X & & & & & X \end{matrix} ) ,

(and the analogous board for a straight table), that lead to sequences [Sl4] and [Sl5], but was unable to find linear recurrences for the sequences themselves, only the generating functions of the sequences of the rook polynomials, from which one can easily get many terms.

Moving right along, the great enumerator, Earl Glen Whitehead [W] treated (by hand!) the case of four-discordant permutations, i.e., the board

( \begin{matrix}X & X & X & X \\ & X & X & X & X \\ … \\ … \\ & & & & & X & X & X & X \\ X & & & & & & X & X & X \\ X & X & & & & & & X & X \\ X & X & X & & & & & & X \end{matrix} ) ,

that yielded sequence [Sl6], once again without finding a recurrence for the sequence itself, but an explicit rational generating function of the sequence of rook polynomials, and hence as many terms of the enumerating sequence as desired.

[See http://www.math.rutgers.edu/~zeilberg/tokhniot/oMENAGESegw1f for a re-

currence of order 40 and with coefficients that are of degree 2 in n, for the enumerating sequence.]

How did these amazing humans do it?

They used, either explicitly, or implicitly, the transfer-matrix method, described in [St], or, other human ingenious, but ad hoc, ways, that every time one had to start from scratch, and get a Rube Goldberg monster.

The General problem

Since we are not interested in retail mathematics, only in wholesale, we want an algorithm, fully implemented, that can answer it in general.

Input: Any finite set S of integers (where both negative and positive integers are allowed, as well as 0, of course).

Output: An efficient way to generate the first 1000 (or whatever) terms of the sequences

(i) a_{S}(n): the number of n-permutations π such that π(i) − i ∉ S

(ii) b_{S}(n): the number of ‘circular’ n-permutations π such that π(i) − i ∉ S, where 1 comes after n. For this case, one can assume without loss of generality that all the members of S are non-negative, and the smallest member is 0 (since we are sitting around a circular table, you can always move them around).

The best would be a linear recurrence for the enumerating sequence, but failing this (if it is too complicated), an explicit generating function for the sequence of rook polynomials, from which one can get as many terms as one desires.

The Hard Way: Teaching Human Ingenuity to the Computer

Given such a finite set S we have to find a scheme for the rook polynomials of the n × n board B(n), implied by S. We can call it a ‘symbolic board’.

Now using the generic recurrence for specific (numeric) matrices, given above, one can apply it to the symbolic board B(n), thereby getting other ‘symbolic boards’, B′(n), B′′(n), that in turn, after you apply the recurrence to them give rise to yet more boards B′′′(n), B′′′′(n), etc.

It it is easy to see that if one continues this process, sooner or later, we do not encounter any new symbolic boards, only previously encountered boards, with n replaced by n − 1. This would enable the computer to set up a system of linear equations with symbolic coefficients, for the generating functions (with respect to x) of R_{n}(t),R′_{n}(t), R′′_{n}(t), etc., let us call them F (x, t), F′(x, t), F′′(x, t), etc. (see, p. 196 of [Ri1] for a very simple human example, done by hand).

It follows from Cramer’s rule that the solutions to this system of linear equations are rational functions of (x, t). In particular, our original object of desire, F (x, t)

F (x, t) = ∑_{n=0}^{∞} R_{n}(t)x^{n} ,

is such a nice rational function of both x and t. Hence

R_{n}(t) = \frac{1}{2πi} ∫_{|x|=1} \frac{F (x, t)}{x^{n+1}} dx ,

and hence, the sequence itself:

A_{n} = ∫_{0}^{∞} t^{n}R_{n}(−\frac{1}{t})e^{−t} dt ,

is given by the double-integral

A_{n} = \frac{1}{2πi} ∫_{0}^{∞} t^{n} e^{−t} ∫_{|x|=1} \frac{F (x, −\frac{1}{t})}{x^{n+1}} dx dt ,

from which one can (at least in principle, but often also in practice) obtain a rigorously-derived linear recurrence equation with polynomial coefficients, using the multi-Almkvist–Zeilberger algorithm due to Moa Apagodu and Doron Zeilberger [ApZ].

Once a computer has been ‘taught’ how to do ‘research’, i.e., derive the scheme for the rook polynomials (by introducing dynamically many other auxiliary ‘boards’, but finitely many of them), and then using the built-in (in Maple) procedure solve that can handle symbolic systems of linear equations, it can do it, at least in principle, for any finite set S of integers, and thereby reproduce, in a few seconds, countless hours of human labor (by very smart people, some of whom were mentioned above), and then go on to generate new knowledge way beyond the scope of mere humans.

But, there is one problem. At this time of writing, one still needs a human to do the teaching! In other words, design an algorithm, and implement it, that does the above for any set S. And, do not expect too much! As the sets S get bigger, even computers would refuse to do it! Computers are only a few orders of magnitude better than humans. Programming the computer to do such research requires at least as much ingenuity, (and hard work!) as doing special cases by hand. But, if you are like me and are lazy, and do not feel like wasting weeks writing a long computer program, you can use the Zeilberger Gordian knot. Replace ingenuity by meta-ingenuity.

The ‘Gordian Knot’ Way: Long Live the Empirical (yet rigorous) approach!

Since we know, a priori, by general ‘hand-waving’ (that can be easily made rigorous), that there exists a scheme, or in the language of Richard Stanley [St], there exists a transfer matrix, we know a priori, that the sequence of rook polynomials for S, R_{n}(t), satisfies some linear recurrence equation with constant coefficients, i.e., belongs to the C-finite ansatz [Z2,KP]. This means that the (ordinary) generating function with respect to x is a rational function of x and t. Hence we can use the straightforward specific procedure, mentioned above, for finding R_{B}(t) for any board, to crank out the first few terms of the sequence of rook polynomials for the n × n boards implied by S, and then guess the recurrence, that we know exists! Then the computer can either find the implied rational generating function, and use the multi-Almkvist– Zeilberger algorithm, but a much better way, once the linear recurrence equation for the sequence of rook polynomials is known, is to crank out many more terms, and then use them (by the umbral operator t^{i} → (−1)^{i}(n − i)!) to crank out sufficiently many terms of the sequence a_{S}(n) (or b_{S}(n)), and guess a linear recurrence equation with polynomial coefficients (i.e., use the holonomic ansatz), that once again can be justified fully rigorously (if desired), since we know that it exists, and one can easily find a priori upper bounds for the order and degree.

The Maple package MENAGES

All this (and much more!) is implemented in the Maple package MENAGES available directly from

Automatic Enumeration of Generalized Ménage Numbers 13

http://www.math.rutgers.edu/~zeilberg/tokhniot/MENAGES ,

or by clicking on the indicated link in the front of the present article

http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/menages.html ,

that contains lots of input and output files. To access the on-line help just type ezra(); . I will only mention a few of the available procedures.

• RP(M,t);: inputs a square 0-1 matrix, M, and a variable t, and outputs the rook polynomial of M, where the 1’s denote the X’s and the 0’s the other squares of the n × n.

• RookPrec(S,t);: inputs a set of integers S and a variable t and outputs the linear recurrence equation with constant coefficients satisfied by the rook polynomials of the board implied by the problem of counting n-permutations π such that π(i) − i ∉ S.

For example, ‘RookPrec({0, 1},t);’ outputs [[1+t,1+3t+t**2],[1+2t,-t**2]],

which is the package’s way of telling you that the sequence of rook polynomials, R_{n}(t) for an n × n board, satisfies the recurrence

R_{n}(t) = (1 + 2t)R_{n−1}(t) − t^{2}R_{n−2}(t) ,

subject to the initial conditions R_{1}(t) = 1 + t, R_{2}(t) = 1 + 3t + t^{2}.

• RookPcrec(S,t);: is the analogous procedure for circular permutations (diners around a round table)

• Seq(S,N);: inputs a set of integers S and outputs the first N terms of the sequence enumerating n-permutations such that π(i) − i ∉ S, starting at n = 1. For example,

Seq({0, 1},21);
yields [Sl2] (i.e., http://oeis.org/A000271).

• SeqC(S,N);: inputs a set of integers S and outputs the first N terms of the sequence enumerating n-circular permutations such that π(i)−i ∉ S (where 1 follows n) starting at n = 1. For example,

SeqC({0, 1},21);

yields [Sl3] (i.e., http://oeis.org/A000179), and all these terms, except the last one, are already in Lucas’ classic [Lu] (p. 495).

• InfoE(S,n,N,MaxC,K,L1,L2);: inputs a set of integers S, symbols n and N (where N is the shift operator in n) and outputs a list consisting of

(i) A list of L1 terms whose n-th term is the number of permutations π of {1, ..., n} such that π(i) − i ∉ S, let us call it a(n);

(ii) a linear recurrence operator of complexity ORDER+DEGREE ≤ MaxC, of minimal order, ORDER, annihilating the sequence, or FAIL, if none exists;

(iii) a(L2) (if the second component is not FAIL), otherwise FAIL;

(iv) The asymptotic expression for a(n)/n! (or FAIL), to order K.

• InfoEC(S,n,N,MaxC,K,L1,L2);: ditto for circular permutations, except that, without loss of generality, the set S can consist of non-negative integers and its smallest element is 0.

InfoEV, InfoECV are verbose versions, and procedures SeferE and SeferEC output webbooks. See the on-line help.

Other procedures that output articles are Mamar, MamarC, and MamarDiscordant. Try them out!

The Maple package BALTIC

The complementary, easier (at least conceptually), problem of finding generating functions for the enumeration of permutations π, where π(i) − i ∈ S for a prescribed set of integers S, is treated in the small Maple package BALTIC, reproducing empiricallyyet-rigorously results of Lehmer [Le], Baltić [B], and Stanley [St] (pp. 252–253). In particular,

GFbaltic({-2,-1,1,2},t,20);

finds in 0.024 seconds, that the generating function for the enumerating sequence for permutations π with π(i) − i = ±1 or ±2 is

\frac{1 − t}{1 − t − t^{2} − t^{3} − t^{4} + t^{5}}

(given at the bottom of page 252 of [St]), that took Richard Stanley, using admittedly elegant human reasoning, quite a bit longer, and

GFbaltic({-2,-1,0,1,2},t,20); yields

\frac{1 − t}{1 − 2 t − 2 t^{3} + t^{5}} ,

given at the top of p. 253 of [St]. For far deeper generating functions see:

http://www.math.rutgers.edu/~zeilberg/tokhniot/oBALTIC2b .

Conclusion: It is Time to Stop to Think and Start to Meta-Think

Three of the greatest combinatorics gurus of the 20th century, John Riordan, Gian-Carlo Rota, and Richard Stanley ([Ri1,Ro,St]) taught us how to apply the transfermatrix method, and the principle of Inclusion-Exclusion, by using insight and ingenuity, to solve combinatorial problems. Alas, for each separate problem, one needs both inspiration and perspiration, wasting lots of very-smart-people’s precious time. In this paper we did a bit of meta-thinking, and realized, by ‘hand-waving’ (but fully rigorously!), that because each of these problems may be used by combining the principle of inclusion and exclusion (via rook polynomials) and the transfer-matrix method, it follows a priori, that the sequence of rook polynomials, for any ‘forbidden’ set S, belongs to the C-finite ansatz, i.e., satisfies some linear recurrence equation with constant coefficients. Having realized that, we can ask our beloved silicon collaborators to crank out the first few terms, and using straightforward guessing, guess the recurrence, that immediately becomes proved because of general principles. Then it follows from ‘general holonomic nonsense’ that the enumerating sequences themselves are holonomic (aka P -recursive), and once again, a recurrence can be guessed, that a posteriori is fully rigorous (not that I care!).

The moral is: an ounce of meta-thinking (plus help from our computers) is worth a pound of (human) thinking!

Appendix: Some Recommended Webbooks by Shalosh B. Ekhad generated by MENAGES

• To see the generating functions for rook polynomials for r-discordant permutations for r from 1 to 4, reproducing in 12 seconds, the labor of Euler (r = 1), Lucas (and Laisant, Moreau, Touchard, Kaplansky and many other smart people) (r = 2), Riordan [Ri2] (r = 3 plus we got a brand-new recurrence for the enumerating sequence itself!), and Whitehead [W] (r = 4), look at:

http://www.math.rutgers.edu/~zeilberg/tokhniot/oMENAGES7 .

• To see the generating functions for rook polynomials for r-discordant permutations for r = 5, 6 (in addition to the above 1 ≤ r ≤ 4), look at:

http://www.math.rutgers.edu/~zeilberg/tokhniot/oMENAGES7a .

• 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} that include 0, and in many cases, nice recurrences for the enumerating sequences themselves, look at:

http://www.math.rutgers.edu/~zeilberg/tokhniot/oMENAGES8 .

• 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} of cardinality at least 2 (some of the theorems are trivially equivalent, by symmetry, but who cares?), look at:

http://www.math.rutgers.edu/~zeilberg/tokhniot/oMENAGES9 .

References

[AlZ] Gert Almkvist and Doron Zeilberger, The method of differentiating under the integral sign, J. Symbolic Comput. 10 (1990), 571–591.

http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimPDF/duis.pdf .

[ApZ] Moa Apagodu and Doron Zeilberger, Multi-variable Zeilberger and Almkvist– Zeilberger algorithms and the sharpening of Wilf–Zeilberger theory, Adv. Appl. Math. 37 (2006), (special issue in honor of Amitai Regev), 139–152.

http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/multiZ.html .

[B] Vladimir Baltić, On the number of certain types of strongly restricted permutations, Appl. Anal. Discrete Math. 4 (2010), 119–135.

http://pefmath.etf.rs/vol4num1/AADM-Vol4-No1-119-135.pdf .

[KP] Manuel Kauers and Peter Paule, “The Concrete Tetrahedron”, Springer–Verlag, 2011.

[Le] Derrick Henry Lehmer, Permutations with strongly restricted displacements, in “Combinatorial theory and its applications, II (Proc. Colloq., Balatonfured, 1969)”, 755–770. North–Holland, Amsterdam, 1970.

[Lu] Edouard Lucas, “Théorie Des Nombres”, Gauthier-Villars et Fils, Paris, 1891.

[M] Major Percy Alexander MacMahon, F.R.S., D.Sc., LL.D., “Combinatory Analysis”, vol. I, Cambridge University Press, 1917. Reprinted (together with vol, II), by Chelsea, 1984.

[Ri1] John Riordan, “Introduction to Combinatorial Analysis”, John Wiley, 1958. Reprinted by Dover, 2002.

[Ri2] John Riordan, The enumeration of permutations with three-ply staircase restrictions, unpublished memorandum, Bell Telephone Laboratories, Murray Hill, NJ, Oct.

1963. Available (thanks to Neil Sloane!) from

http://oeis.org/A001883/a001883 21.pdf .

[Ro] Gian-Carlo Rota, On the foundation of combinatorial theory I. Theory of Möbius functions, Z. Wahrscheinlichkeitstheorie 2 (1964), 340–368, reprinted in “Classic Papers in Combinatorics”, I. M. Gessel and G.-Rota, eds., Birkhäuser, 1987.

[Sl1] Neil Sloane, “The On-Line Encyclopedia of Integer Sequences (OEIS)”, Sequence

http://oeis.org/A000166 .

[Sl2] Neil Sloane, “The On-Line Encyclopedia of Integer Sequences (OEIS)”, Sequence

http://oeis.org/A000271 .

[Sl3] Neil Sloane, “The On-Line Encyclopedia of Integer Sequences (OEIS)”, Sequence

http://oeis.org/A000179 .

[Sl4] Neil Sloane, “The On-Line Encyclopedia of Integer Sequences (OEIS)”, Sequence

http://oeis.org/A000183 .

[Sl5] Neil Sloane, “The On-Line Encyclopedia of Integer Sequences (OEIS)”, Sequence

http://oeis.org/A001887 .

[Sl6] Neil Sloane, “The On-Line Encyclopedia of Integer Sequences (OEIS)”, Sequence

http://oeis.org/A004307 .

[St] Richard Peter Stanley, “Enumerative Combinatorics, volume I” (first edition), Wadsworth & Brooks/Cole, 1986. Reprinted by Cambridge University Press, 1998.

[V] Leslie Gabriel Valiant, The complexity of computing the permanent, Theoret. Computer Sci. 8 (1979), 189–201.

[W] Earl Glen Whitehead, Jr., Four-discordant permutations, J. Austral. Math. Soc. Ser. A 28 (1979), 369–377.

[Z1] Doron Zeilberger, The method of creative telescoping, J. Symbolic Comput. 11(1991), 195–204.

http://www.math.rutgers.edu/~zeilberg/mamarimY/CreativeTelescoping.pdf .

[Z2] Doron Zeilberger, The C-finite ansatz, Ramanujan J. 31 (2013), 23–32.

http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/cfinite.html .