Séminaire Lotharingien de Combinatoire 50 (2003), Article B50a

The Lotharingian impact on Combinatorial Mathematics: myth or reality?

Dominique Foata ^{1} (Strasbourg)

It is very fortunate that two, and sometimes three, sessions of the Séminaire Lotharingien have been held every year since its beginning in 1980. Otherwise, several of us, at least the confirmed optimists, would have witnessed the jubilee in Paradise! Anyway, this is a great privilege to have all of you here, at the Domaine Saint-Jacques, a place regarded as a valeur sûre by the younger generation.

In fact, the Seminar had long been in limbo, all through the seventies, when regular meetings on Combinatorics were organized at the Mathematisches Forschungsinstitut, Oberwolfach under the direction of Konrad Jacobs, a distinguished probabilist, but also a great promoter of the combinatorial methods in Mathematics. Suddenly, the Oberwolfach Institute had become too small to shelter all the European mathematicians interested in Combinatorics. It became urgent to create a new structure, where everybody could come, bring his contribution and be exposed to the current ideas of that field.

As had been told on several occasions, the Lotharingian Seminar had a true spontaneous birth at Strasbourg in 1980, at a time when Adalbert (a true Lotharingian Christian name!) Kerber kept shuttling between Aachen (the seat of Charlemagne’s kingdom) and Bayreuth. Volker Strehl, already based in Erlangen, responded to the idea with a great enthusiasm and accepted to be the third pillar of the whole edifice. As a matter of fact, he immediately made the suitable arrangements for the second session that took place in Burg Feuerstein, near Bamberg, the same year, in the Fall 1980.

1 The papers which are electronically published on the Séminaire Lotharingien site:

http://www.mat.univie.ac.at/∼slc/ are referred to as [SLC Bxx] and not further mentioned in the list of references at the end of the paper.

DOMINIQUE FOATA

Since then, the three mother Universities, Bayreuth, Erlangen and Strasbourg have scheduled two or three meetings per year, occasionally assisted by other Institutions, such as Wien, Bologna, Cagliari, Leoben, Potenza, Lyon. In 2000 a new trio took charge: Wien-Erlangen-Marne-la-Vallée, that soon became Lyon-Erlangen-Marne-la-Vallée, as Christian Krattenthaler has moved from Austria to France. As everybody knows, together with Volker Strehl and Jean-Yves Thibon, Christian rules over the Séminaire with wisdom, science and efficiency.

Here is the full list of the sessions with their locations and their organizing instances:

1980: 01 Strasbourg (Strasbourg), 02 Burg Feuerstein (Erlangen), 1981: 03 Le Kleebach (Strasbourg), 04 Bayreuth (Bayreuth),

05 Sainte-Croix-aux-Mines (Strasbourg), 1982: 06 Burg Feuerstein (Erlangen), 1983: 07 Donndorf (Bayreuth), 08 Sainte-Croix-aux Mines (Strasbourg),

09 Hollabrunn (Wien), 1984: 10 Burg Feuerstein (Erlangen),

11 Wasserschloss Mitwitz (Bayreuth), 1985: 12 Le Kleebach (Strasbourg), 13 Terme di Castel San Pietro

(Bologna), 1986: 14 Burg Feuerstein (Erlangen), 15 Schloss Schney (Bayreuth), 1987: 16 Liebfrauenberg (Strasbourg), 17 Eremo San Paolo (Strasbourg),

18 Obsteig (Wien), 1988: 19 Schloss Schwanberg (Erlangen), 20 Alghero (Cagliari), 1989: 21 Schloss Thurnau (Bayreuth), 22 Hesselberg (Erlangen), 1990: 23 Rouge-Gazon (Strasbourg), 24 Liebfrauenberg (Strasbourg),

25 Salzburg (Leoben), 1991: 26 Schloss Thurnau (Bayreuth), 27 Hesselberg (Erlangen), 1992: 28 Domaine Saint-Jacques (Strasbourg),

29 Schloss Thurnau (Bayreuth), 1993: 30 Hesselberg (Erlangen), 31 Domaine Saint-Jacques (Strasbourg), 1994: 32 Domaine Saint-Jacques (Strasbourg), 33 Freiberg (Bayreuth), 1995: 34 Domaine Saint-Jacques (Strasbourg), 35 Hesselberg (Erlangen), 1996: 36 Schloss Thurnau (Bayreuth), 37 Strasbourg (Strasbourg),

38 Bellagio (Strasbourg), 1997: 37 Schloss Thurnau (Bayreuth), 40 Bellagio (Strasbourg), 1998: 41 Domaine Saint-Jacques (Marne-la-Vallée),

42 Maratea (Potenza), 1999: 43 Kloster Schoental (Erlangen). 2000: 44 Domaine Saint-Jacques (Strasbourg),

THE LOTHARINGIAN IMPACT

45 Bellagio (Marne-la-Vallée), 2001: 46 Lyon (Lyon), 47 Bertinoro (Bologna), 2002: 48 Domaine Saint-Jacques (Marne-la-Vallée),

49 Haus Schönenberg, Ellwangen (Erlangen), 2003: 50 Domaine Saint-Jacques (Marne-la-Vallée ).

The next meeting is already scheduled to take place in Bertinoro.

Back in 1980 our intention was to have a joint seminar for the three mother Universities, where each group could discuss its recent works. Soon however, it appeared useful to ask one of us, or a distinguished visitor, to prepare and read a survey paper in Combinatorics, or more often in a related area.

We then had so-called main speakers. They have certainly enlarged our vision of Combinatorics and enriched the connections between several branches of Mathematics. Most of those survey papers have been published in our proceedings, in paper form in the beginning, then in electronic form after 1994. I will not speak about the change of policy of our Séminaire when we decided to move from traditional to electronic publishing, but will focus my attention to the main mathematical themes that were discussed along those years, after mentioning a few basic facts and figures.

1. Some statistics

50 sessions, so far, as we celebrate the jubilee.

27 locations used for the Séminaire, the Domaine Saint-Jacques (8 times), Thurnau (5 times), Burg Feuerstein and Hesselberg (each 4 times), Bellagio (3 times), Strasbourg, Kleebach, Sainte-Croix-aux-Mines, Liebfrauenberg (each twice), the other places once.

23 years of existence, so far, from 1980 to 2003.

29 printed seminar proceedings: a joint issue 1-3, all issues from no. 5 to no. 31, plus no. 34, published in the series Publications de l’Institut de Recherche Mathématique Avancée, Strasbourg.

323 papers, electronically deposited on the Séminaire Lotharin-

gien site: http://www.mat.univie.ac.at/∼slc/.

332 registered Lotharingians listed on the site, mostly mathematicians who have attended the Séminaire at least once. Almost one paper per Lotharingian!

2. The impact?

If we examine the classification of Mathematical Reviews to-day, we notice that 05 Combinatorics is subdivided into five subclasses:

05A (1973 -Current ) Enumerative combinatorics

05B (1973 -Current ) Designs and configurations

05C (1973 -Current ) Graph theory 05D (1991 -Current ) Extremal combinatorics 05E (1991 -Current ) Algebraic combinatorics

We have to admit that few papers on Designs, Graphs and Extremal Problems have been read in the sessions of the Séminaire, with the exception of Matroid Theory (essentially by the Bielefeld school), waiting for the enumerative aspects of that theory by Bodo Lass, the study of polyominoes by the Bordeaux school, Ramsey Theory by the late Walter Deuber, a fascinating introduction to the four-colour problem [Co87] with many illuminating figures by Daniel I. A. Cohen, a paper that would deserve an electronic version.

As for 05A Enumerative and 05E Algebraic Combinatorics, they have been most present in our Séminaire. Mathematical Reviews provides the further descriptions:

05A05 (1973-now) Combinatorial choice problems

(subsets, representatives, permutations)

05A10 (1973-now) Factorials, binomial coefficients,

combinatorial functions

05A15 (1973-now) Exact enumeration problems, generating functions 05A16 (1991-now) Asymptotic enumeration 05A17 (1973-now) Partitions of integers 05A18 (1991-now) Partitions of sets 05A19 (1973-now) Combinatorial identities 05A20 (1973-now) Combinatorial inequalities 05A30 (1985-now) q-calculus and related topics 05A40 (1985-now) Umbral calculus

05E05 (1991-now) Symmetric functions 05E10 (1991-now) Tableaux, representations of the symmetric group 05E15 (1991-now) Combinatorial problems concerning

the classical groups

05E20 (1991-now) Group actions on designs, geometries and codes 05E25 (1991-now) Group actions on posets and homology

groups of posets

05E30 (1991-now) Association schemes, strongly regular graphs 05E35 (1991-now) Orthogonal polynomials

Some items of 05A Enumerative Combinatorics seem to be old-fash-ioned and there is some disparity of topics within 05E Algebraic Combinatorics. Anyway, let us take them as such and examine how they have been illustrated along our sessions. Of course, my description will be awfully sketchy and partial, but there was no way “to cram within this short address the vasty fields” of Lotharingian Combinatorics, to paraphrase King Henry the Fifth’s Chorus.

As I cannot make an exhaustive excursion to all the topics, I will shortly mention some topics that were regularly discussed. Again, I should like to apologize myself for being so brief on so many fascinating and fast-growing subjects. Let me mention:

The theory of permanents and its challenging conjectures, thanks to the expertise of Arnold Kräuter (see his three papers [SLC B09b, B11b, B16b]), Norbert Seifter and Peter Gerl and the more recent paper by Guoniu Han and Christian Krattenthaler on the Scott-type permanents [SLC B43g].

The theory of Codes and Languages, presented by our colleagues Berstel, König and Perrin, in particular; automata studies by Werner Kuich [Ku88], Véronique Bruyère [SLC B35b], Jean-Pierre Allouche [SLC B30c] in relation with arithmetical problems.

Pólya theory and its impact on Chemical Engineering by Adalbert Kerber.

Maps and hypermaps by Robert Cori, Didier Arquès.

Plane tiling by Andreas Dress and his school, especially hexagon tiling by Ilse Fischer [SLC B45f] and the Viennese school.

The theory of Witt vectors by Henri Gaudier [SLC B18c, B21f] and Andreas Dress [SLC B28c].

Algorithmic Complexity by Peter Bürgisser and Michael Clausen [SLC B36a, B36b].

Umbral Calculus by Marilena Barnabei and her Bolognese co-workers; also by Luigi Cerlienco and his Sardinian co-workers.

Tree Enumeration by Peter Kirschenhofer [Ki90]. The paper exists in a pre-TEX form. Peter should be convinced to offer us a definitive electronic version.

Next, let me present a few Lotharingian gems I should like to extract from our Treasure.

3. Enumerative Combinatorics

In 1988 Volker Strehl [St88] brought our attention to the following identity due to P. Brock [Br60]: for A, B ≥ 0 let

H(A, B) = ∑_{i=0}^{A} ∑_{j=0}^{B} \binom{i + j}{j}\binom{A − i + j}{j}\binom{B + i − j}{B − j}\binom{A − i + B − j}{B − j}.

Then H(A, B) − H(A − 1, B) − H(A, B − 1) = \binom{A + B}{A}^{2}.

Such identities are no mystery to-day, as they can be proved by means of computer algebra methods (Zeilberger, Paule, Krattenthaler), but what Volker taught us in 1988 was an implementation of the identity into various combinatorial contexts, in particular in his powerful periodical, local-injective endofunction geometry (the PLI-endofunctions), in which the identity reflected a banal counting.

With his kind permission the graph of such a PLI-endofunction is reproduced in Fig. 1. First, an ordered partition (S_{1}, S_{2}, …, S_{p}) (here p = 3) of a finite set S is given; then, for each i = 1, 2, …, p the restriction of the endofunction to S_{i} is an injection of S_{i} into S_{i} ∪S_{i+1} (by convention S_{p+1} := S_{1}). Thus, the name of local-injective and periodical is very appropriate. Next, such an endofunction can be given a weight that takes the cycles within each block S_{i} into account and also the cardinalities of the S_{i}’s. For instance, the PLI-endofunction in Fig. 1 is given the weight

(1 + α_{2})^{2}(1 + α_{3})x_{1}^{8}x_{2}^{11}x_{3}^{10},

as there are two cycles in S_{2} and one cycle in S_{3} and since S_{1}, S_{2} and S_{3} are of cardinalities 8, 11, 10, respectively.

Fig. 1

The problem left to the reader is to use the above algebra of the PLIendofunctions with their weights and derive the Brock identity. The paper by Volker Strehl (hopefully in electronic form some day) will certainly rescue the unsuccessful reader in case of difficulty.

Let me digress on the paper by Dumont [SLC B05b] that updates an old paper by Seidel [Se77] on the finite-difference calculus of classical numbers, because simple facts in mathematics are recurrent and deserve to be remembered. Let (a(0, n)) (n ≥ 0) be a given sequence, called the initial sequence, of elements from a ring Ω and define the matrix (a(i, j)) (i, j ≥ 0) by:

a(i, j) = a(i − 1, j) + a(i − 1, j + 1)  (i ≥ 1, j ≥ 0).

The leftmost column (a(n, 0)) (n ≥ 0) of the above matrix is called the final sequence. It is easy to derive the generating function for the latter sequence from the generating function for the initial one. There are several unexpected correspondences between those two sequences. For instance, let E_{n} (n ≥ 0) be the numbers defined by the generating function

tan u + sec u = ∑_{n≥0} \frac{u^{n}}{n!} E_{n} = 1 + \frac{u}{1!}1 + \frac{u^{2}}{2!} 1 + \frac{u^{3}}{3!} 2 + \frac{u^{4}}{3!} 5 + \frac{u^{5}}{5!} 16 + ⋯

so that the coefficients E_{2n−1} are the secant numbers and E_{2n} the tangent numbers. If we take a(0, 0) = 1, a(0, 2n) = 0 (n ≥ 0) and a(0, 2n − 1) = (−1)^{n}E_{2n−1} (the signed tangent number), then the final sequence reads: a(2n, 0) = (−1)^{n}E_{2n} (the signed secant number) and a(2n − 1, 0) = 0.

4. q-calculus and related topics

The algebra of q-series goes back to Heine (1850) and has long been nurtured by the specialists of Partition Theory, such as our friend George Andrews. It entered the field of Enumerative Combinatorics in the early seventies with the works of Carlitz, Gessel in his Ph.D. thesis [Ge77], although many calculations were anticipated by MacMahon himself [MacM15] in his monumental treatise.

The first issue of the Séminaire ever published came with the fifth Session that took place in the School of Music in Sainte-Croix-aux-Mines in 1981. It contains a superb contribution of J. Cigler [SLC B05a] to the study of q-Calculus, which is modestly called “Elementary q-Identities”. His operator approach is very convincing and deals with the algebra of q-Hermite and q-Laguerre polynomials that enables him to derive a simple proof of the Mehler formula for the q-Hermite polynomials.

Let me mention that identity by recalling, as was done by Jacques Désarménien [SLC B06b], that several versions of those polynomials exist but can be transformed into one another by a suitable change of variables. We had to wait for 2002 to have a true combinatorial proof of that famous identity, a proof due to Hung Quang Ngo [SLC B48b], a student of Dennis Stanton.

In the sequel we make use of the usual notations:

\begin{aligned}(a; q)_{n} & = \{ \begin{matrix}1, & if n = 0; \\ (1 − a)(1 − aq) … (1 − aq^{n−1}), & ifi n ≥ 1; \end{matrix} \\ (a; q)_{∞} & = lim_{n}(a; q)_{n} = ∏_{n≥0}(1 − aq^{n}). \end{aligned}

One of the versions of the q-Hermite polynomials H_{n}(x|q) can be defined by their generating function

∑_{n≥0} H_{n}(x|q)\frac{u^{n}}{(q; q)_{n}} = ∏_{k≥0} \frac{1}{(1 − 2xuq^{k} + u^{2}q^{2k})}.

Then Hung Quang Ngo was able to derive the identity

∑_{n≥0} H_{n}(x|q)H_{n}(y|q)\frac{u^{n}}{(q; q)_{n}}

= ∏_{k≥0} \frac{(u^{2}; q)_{∞}}{(1 − 4uq^{k}xy + 2u^{2}q^{2k}(−1 + 2x^{2} + 2y^{2}) − 4u^{3}q^{3k}xy + u^{4}q^{4k})},

using a very clever combinatorial set-up of bicolored (q, n)-involutionary graphs.

Let me go back again to that first issue and mention the paper by Daniel Barsky [SLC B05b] on the p-adic analysis of the sequences of classical numbers. It is a pity that the p-adic approach has not been used more extensively in combinatorial studies, as it was a powerful tool in providing a short proof [Ba81] of the Gandhi conjecture [Ga70] for the Genocchi numbers.

The paper by Josef Hofbauer on Lagrange-Inversion has been electronically reproduced [SLC B06a]. It contains the various q-versions of the Lagrange inversion identity, mentions the multilinear extension (due to Good, but already known to Jacobi, as Hofbauer found out) and shows how the MacMahon Master Theorem is a plain consequence of that multilinear extension. This raises the question of imagining a true q-multilinear version of the Lagrange identity (perhaps it is not even an identity), that would be a handy tool in the algebra of q-series. Notice that a very convincing combinatorial proof of the multivariable Lagrange inversion formula is due to Gessel [Ge87] and a β-extension was derived by Zeng [SLC B20b].

As Pierre Cartier puts it [SLC B23a] there are “new adventures in the country of q-calculus” in Statistical Mechanics and the Yang-Baxter equation.

5. Partitions of integers

Back in the seventies the classical theory of partitions had not yet exploded. It was most challenging to wait for the latest contribution of George Andrews to make sure that Partition Theory had not become a foreign subject to most of us. Regretfully we only have two contributions of his in our proceedings [SLC B25f, B42i], the second one jointly written with Peter Paule on the rebirth of MacMahon’s partition analysis. In Maratea George Andrews and Peter Paule [SLC B42i] read their fourth paper on the subject (“MacMahon’s Partition Analysis IV: Hypergeometric Multisums”). Other papers on partitions appear in vol. 42, the Andrews Festschrift, that contains a formidable paper by Bruce Berndt and Ken Ono on the tau-function and the work of Ramanujan. Thanks to Peter Paule [SLC B18f] the Bailey chain tool for proving q-identities has become a classic.

6. Symmetric Functions

This is a topic that has been extensively studied, especially under the leadership of Alain Lascoux, a strong symmetric function believer. When the proceedings of the eighth session were published (Publ. IRMA, 1984 229/S-08), he had already written, jointly with the late Marco Schützenberger, his first memoir on the subject [La84]. Only the first chapter of that memoir was printed in the proceedings. The good news is that an updated version of the memoir has just appeared in print [La03].

Let me mention the paper by Ira Gessel [SLC B17a] that extends the notion of D-finiteness to the class of symmetric functions and makes a clever use of that notion to derive the P -recursiveness of several combinatorial sequences.^{2}

In 1988 we were privileged to be invited by the Sardinian School to have the Séminaire at Alghero. We could have Ian G. Macdonald as a main speaker, who, for the first time, read his seminal paper on “A new class of symmetric functions” [SLC B20a]. For each positive integer r let p_{r} denote the power-sum ∑ x_{i}^{r} and for each partition λ = (λ_{1}, λ_{2}, …) let p_{λ} := p_{λ_{1}}p_{λ_{2}} … and denote by ℓ(λ) the number of parts of λ; furthermore, if the multiplicative form of λ reads λ = 1^{m_{1}}2^{m_{2}} …, let z_{λ} := ∏_{r≥1}(r^{m_{r}} · m_{r}!). Finally, define

z_{λ}(q, t) := z_{λ} ∏_{i=1}^{ℓ(λ)} \frac{1 − q^{λ_{i}}}{1 − t^{λ_{i}}} .

2 I owe this informative comment to Christian Krattenthaler, who added that Gessel’s approach has been taken up again by Chyzak, Mishna and Salvy in a recent work (math.CO/0310132).

In the algebra of symmetric functions Macdonald introduced the scalar product ⟨ , ⟩_{(q,t)} defined by

⟨p_{λ}, p_{μ}⟩_{(q,t)} = δ_{λμ}z_{λ}(q, t)

and proved that there is a unique class of symmetric functions P_{λ} = P_{λ}(q, t) with coefficients in the field of rational functions in q and t, which are orthogonal with respect to the above scalar product. Moreover, those polynomials specialize to all known classical bases of the symmetric functions: the monomial, homogeneous, elementary, Schur, Hall-Littlewood, Jack functions.

Several conjectures concerning those polynomials were stated at that time. The paper has been the source of numerous significant works. In particular, Jennifer Morse [SLC B41a] was able to give an explicit expansion of P_{λ} in the case of two variables. It is worth mentioning that the Lotharingian memoir itself was later reproduced, with minor changes, as the sixth chapter in the second edition of Macdonald’s book [Mac95].

The first meeting at Domaine Saint-Jacques took place in Spring 1992. It was the twenty-eighth session. Macdonald [SLC B28a] brought a further contribution to the subject by unifying various recent extensions and analogues of Schur functions, especially the ribbon Schur functions introduced by Lascoux and Pragacz [La88].

A fruitful application of the Schur function algebra was made by Jacques Désarménien [SLC B15a] who reproved the classical Gordon and Macdonald identities and also derived two new identities, regarded as qanalogs of two formulas obtained by Desainte-Catherine and Viennot on partitions. Those two q-identities read:

∑_{λ⊂(2m)^{n}} S_{λ}(q^{n}, q^{n−1}, …, q) = ∏_{1≤i≤j≤n} \frac{q^{2m+i+j} − 1}{q^{i+j} − 1};

∑_{λ⊂(2m)^{n}} S_{λ}(q^{2n−1}, q^{2n−3}, …, q)= ∏_{1≤i≤n} \frac{q^{2m+2i} − 1}{q^{2i} − 1} ∏_{1≤i<j≤n} \frac{q^{2(2m+i+j)} − 1}{q^{2(i+j)} − 1};

where the sum is over all partitions λ having only even parts.

7. Orthogonal polynomials

Let (p_{n}(x)) be a sequence of orthogonal polynomials with respect to a functional L. For several classical polynomials (Hermite, Laguerre, Krawtchouk, Meixner, …) the evaluation of the functional L(∏_{i=1}^{m} p_{n_{i}}(x)) was to be made and the major problem was to characterize the positivity domain of that functional.

The combinatorial approach consists of reinterpreting the functional as a generating function for combinatorial structures, such as muticolored derangements, by some univariable or multivariable statistics. If a closed formula can be derived for the functional, the positivity property becomes a simple by-product or a bonus! That approach has been successfully used by Jiang Zeng in several contributions; see [Zen88] in particular.

8. Tableaux, representations of the symmetric group

Let me mention the Robinson-Schensted analog for oscillating tableaux derived by Marie-Pierre Delest and her followers [SLC B20b], the geometric version of the Kerov-Kirillov-Reshetikhin construction by Guoniu Han [SLC 31a] and a study of tableaux of dominoes by Christophe Carré and Bernard Leclerc [SLC B31c]. The celebrated jeu de taquin was restructured by Marc van Leeuwen [SLC B41b] to walk over the Crystal paths of Littelmann.

In Representation Theory proper Adalbert Kerber and his school have constantly be present, and also the Marne-la-Vallée phalanstère [SLC B32c] and Christine Bessenrodt [B33a].

9. Computer-assisted proofs of identities

In 1993 we invited Doron Zeilberger to give three talks on his fantastic method of proving hypergeometric identities with the help of a computer. We were sure that his lectures would be fascinating and probably most entertaining (they were!), but were afraid of learning more on the scientific achievements of his chairman compared with the talent and production of his personal computer than about hypergeometric identity proving. To our great surprise his lectures were masterly done and the text he gave us [SLC B24b] remains an excellent introduction to the subject, even to-day. An updated version of the paper was further published [Ze95].

In the same vein Volker Strehl [B29b] studied the conjugacy of sequences satisfying linear recurrences by having a closer look at the identity

∑_{k=0}^{n} \binom{n}{k}^{2}\binom{n + k}{k}^{2} = ∑_{k=0}^{n} \binom{n}{k}\binom{n + k}{k} ∑_{j=0}^{k} \binom{k}{j}^{3},

an identity that involves the famous Apéry numbers ∑_{k} \binom{n}{k}^{2}\binom{n+k}{k}^{2}. Volker showed us how the interplay between computer algebra softwares and some human cleverness (!) can lead to a new approach of diophantine approximation.

Pierre Cartier’s Mathemagics [SLC B44d] convinced us that he remained a strong supporter of a sound use of experimental mathematics.

We had expected a memoir on the polylogarithms and their connections with the shuffle algebras, as was developed by the Lille school, but it would have been of double use with the two papers on the subject read by Minh [SLC B43e, B44i].

We are finally proud of saying that the first announcements of the implementations of Christian Krattenthaler’s HYP and HYPQ packages [SLC B30a] were first made in a session of our Séminaire (the thirtieth).

10. Determinant Calculus

Let me quote George Andrews in his review [MR2002i:05013] of Christian Krattenthaler’s 67-page paper “Advanced Determinant Calculus” published in [SLC B 42q]: “This is a valuable, useful and unique survey carefully prepared by the only person who could successfully pull it all together.” Yes indeed, many evaluations in Combinatorics first to lead to a determinant that remains to be calculated, but how? We feel privileged to have that unique oiseau rare among us. See also his paper on q-analogues of Determinant Identities arising in Plane Partitions [SLC 36e] and [SLC 47g].

11. Other excursions

The Séminaire had welcomed the incursion into Probability Theory with the contribution of Roland Speicher [SLC B39c] (“Free probabililty theory and non-crossing partitions”). I will not explain the first part of the title, but rather recall what the second part refers to. Here, partition means set-partition, and more precisely a set of disjoint non-empty blocks whose union is the interval [n] = {1, 2, …, n}. If there exist four integers 1 ≤ i < k < j < l ≤ n such that i and j belong to the same block and k and l belong to another block of a partition π, we say that π is a crossing partition. Otherwise, π is said to be non-crossing. Those noncrossing partitions of [n] form a lattice, that is quite similar to the lattice of all partitions of [n]. It is remarkable that the notion first introduced and studied by Kreweras [Kr72] was exactly the object needed by the probabilists to express the relations between the moments of a random variable and the so-called free cumulants.

12. Statistical Study of Coxeter Groups

The purpose is to see how various statistics defined on the symmetric group, such as the descent number, the length, the major index… can be naturally (?) extended to certain Coxeter groups and how reasonable (?) analytic expressions can be derived for the generating series for those statistics. Back in the seventies the difficulty was to imagine the appropriate normalization for the series involved. For instance, the coefficients C_{n} in the following identity

∑_{n} \frac{u^{n}}{(s; p)_{n+1} (t, q)_{n+1}} C_{n} = ∑_{k,l} s^{k}t^{l} \frac{(−zu; p, q)_{k+1,l+1}}{(u; p, q)_{k+1,l+1}}

can be interpreted as a generating polynomial for permutations by some multivariable statistic. Observe the normalization of the series. On the right-hand side (u; p, q)_{k+1,l+1} stands for the product ∏(1 − up^{i}q^{j}) (0 ≤ i ≤ k; 0 ≤ j ≤ l). Such a normalization for this kind of problem goes back to Gessel in his Ph.D. thesis and was essential for expressing further permutation statistic identities.

Recently, the Israeli school with Ron Adin, Francesco Brenti, Yuval Roichman [Ad03] used a further normalization

[t; q]_{n} := \{ \begin{matrix}1 − t, & if n = 0; \\ (1 − t)(1 − tq_{1})(1 − tq_{1}q_{2}) ⋯ (1 − tq_{1} ⋯ q_{n}), & if n ≥ 1, \end{matrix}

so that we can derive:

∑_{n} \frac{u^{n}}{[s; p]_{n+1} [t; q]_{n+1}} C_{n}(z, s, t, p, q) = ϕ_{p}ϕ_{q} ∑_{k,l} s^{k}t^{l} ∏_{{1≤i≤k+1 \atop 1≤j≤l+1}} \frac{(1 + zux_{i}y_{j})}{(1 − ux_{i}y_{j})}.

In that formula ϕ_{p}, ϕ_{q} are linear homomorphisms, but not ring homomorphisms. Further work is to be done to derive an extension of the next to the last identity with the elimination of ϕ_{p} and ϕ_{q}.

Several transformations on the symmetric group have been constructed and were used to prove that certain classical statistics, such as the major index and the inversion number, were equidistributed. Analogs of those transformations should be constructed, for other Coxeter groups, at least for the signed permutations, that would help prove further equidistribution properties.

13. Conclusion

Nobody would object that Lotharingia as a whole—that is, the very many participants in our Séminaire—has had a real impact on Combinatorics. Our Séminaire was created at the time of the explosion of that discipline, thus opening it up to a challenging exchange from the very beginning. Moreover, the door has been kept open to other fields that welcome combinatorial methods. A new generation of mathematicians is now in command of both the organization of the seminars themselves and of the electronic journal. They keep a watchful eye on the frontiers: Classical and Commutative Algebra, Computer Algebra, Special Functions, Theoretical Computer Science, Algorithms, Probability, … There is no doubt that our Séminaire is more vivid than ever.

REFERENCES

[Ad03] Ron M. Adin, Francesco Brenti, Yuval Roichman, Descent Representations and Multivariate Statistics, preprint, 47 pages.

[Ba81] Daniel Barsky, Congruences pour les nombres de Genocchi de deuxième espèce, Groupe d’étude d’analyse ultramétrique (Y. Amice, G. Christol, P. Robba), 8^{ième} année, 1980/81, n^{o} 34, 13 p. Secrétariat de math., Univ. Paris 7.

[Br60] P. Brock, On a binomial identity arising from a sorting problem, problem 60-2, SIAM Review, vol. 2, 1960, p. 40.

[Co87] Daniel I. A. Cohen and V. S. Miller, On the four color problem, Publ. IRMA Strasbourg, vol. 341/S-16, 1987, p. 5-62.

[Ga70] Gandhi (J.M.), A conjectured representation of Genocchi numbers, Amer. Math. Monthly, vol. 77, 1970, p. 505–506.

[Ge77] Ira Gessel, Generating functions and enumeration of sequences, Ph. D. thesis, Dept. Math., M.I.T., Cambridge, Mass., 111 p., 1977.

[Ge87] Ira Gessel, A combinatorial proof of the multivariable Lagrange inversion formula, J. Combin. Theory Ser. A, vol. 45, 1987, p. 178-195.

[Ki90] Peter Kirschenhofer, Enumeration of trees, Publ. IRMA Strasbourg, vol. 462/S-25, 1990, p. 19-61.

[Kr72] Germain Kreweras, Sur les partitions non-croisées d’un cycle, Discrete Math., vol. 1, 1972, p. 333-350.

[Ku88] Werner Kuich, Semirings, automata and combinatorial applications, Publ. IRMA Strasbourg, vol. 358/S-18, 1988, p. 5-51.

[La03] Alain Lascoux, Symmetric Functions and Combinatorial Operators on Polynomials. Providence, R.I., Amer. Math. Soc., CBMS, vol. 99 2003.

[La88] Alain Lascoux and Piotr Pragacz, Ribbon Schur functions, Europ. J. Combinatorics, vol. 9, 1988, p. 561-574.

[La84] Alain Lascoux and M.-P. Schützenberger, Formulaire raisonné des fonctions symétriques. L.I.T.P., U.E.R. Math., Univ. Paris VII, 138 p., 1984.

[Mac95] Ian G. Macdonald, Symmetric Functions and Hall polynomials.

Second Edition. Oxford, Clarendon Press, 1995.

[MacM15] Percy Alexander MacMahon, Combinatory Analysis, vol. 1 and 2.

Cambridge, Cambridge Univ. Press, 1915, (Reprinted by Chelsea, New York, 1955).

[Se77] L. Seidel, Über eine einfache Entstehungsweise der Bernoullischen Zahlen und einiger verwandten Reihen, Sitzungsberichte der mathematisch-physikalischen Classe der Königlich Bayerischen Akademie der Wissenschaften. München, 1877, p. 157-187.

[St88] Volker Strehl, Endliche Funktionen und spezielle Funktionen: eine kombinatorische Theorie zu einer Identität von P. Brock und deren Erweiterungen, Publ. IRMA Strasbourg, vol. 348/S-17, 1988, p. 23-67.

[Ze95] Doron Zeilberger, Three recitations on Holonomic Systems and Hypergeometric Series, J. Symbolic Comp., vol. 20, 1995, p. 699– 724.

[Zen88] Jiang Zeng, Linéarisation de produits de polynômes de Meixner, Krawtchouk et Charlier, Publ. IRMA Strasbourg, vol. 348/S-17, 1988, p. 69-95.

Dominique Foata Institut Lothaire 1, rue Murner F-67000 Strasbourg, France

                            foata@math.u-strasbg.fr