---

Combinatorics / Combinatoire
(C. Chauvre, S. Corteel and P. Leroux, Organizers)

---

F. BERGERON, Université du Québec à Montréal, C.P. 8888, Succ. Centre-Ville, Montréal, Québec  H3C 3P8
Ideals of quasi-symmetric polynomials and related varieties

For many nice families of ideals generated by quasi-symmetric polynomials in n variables, x₁¼x_n, we give explicit description of their (reduced) Gröbner basis. This implies that we have explicit combinatorial descriptions for basis of the quotient of the ring of polynomials in x₁¼x_n by each of these ideals. The dimension (and Hilbert series) of these spaces are very nice from a combinatorial view point.

M. BOUSQUET, LaCIM, UQAM, Case Postale 8888, succursale Centre-ville, Montréal, Québec  H3C 3P8
Dénombrement de 2-arbres solides

Le but de ce travail est d'obtenir l'énumération des 2-arbres solides selon le nombre d'arêtes (ou de triangles) ainsi que selon la distribution des degrés des arêtes. Nous obtenons d'abord le dénombrement des 2-arbres solides orientés en utilisant les méthodes de la théorie des espèces. Pour obtenir le dénombrement des 2-arbres solides non orientés, nous utilisons la notion d'espèce quotient qui provient d'une spécialisation de la théorie de Pólya.

The main goal of thiswoorkr is to enumerate solid 2-trees according to the number of edges (or triangles) and also according to the edge degree distribution. We first enumerate oriented solid 2-trees using the general methods of the theory of species. In order to obtain non oriented enumeration formulas we use quotient species which consists in a specialization of Pólya theory.

M. BOUSQUET-MELOU, CNRS, Université Bordeaux 1, Talence Cedex, France
Walks in a quarter plane

We study planar walks that start from a given point (i₀,j₀), take their steps in a finite set \frak S, and are confined in the first quadrant x ³ 0, y ³ 0. Their enumeration can be attacked in a systematic way: the generating function Q(x,y;t) that counts them by their length (variable t) and the coordinates of their endpoint (variables x,y) satisfies a linear functional equation encoding the step-by-step description of walks. For instance, for the square lattice walks starting from the origin, this equation reads

æ è xy -t(x+y+x2y+xy2) ö ø Q(x,y;t)=xy-xtQ(x,0;t)-ytQ(0,y;t).

The central question addressed in this talk is the nature of the series Q(x,y;t). When is it algebraic? When is it D-finite (or holonomic)? Can these properties be derived from the functional equation itself?

Our first result is a new proof of an old theorem due to Kreweras, according to which one of these walk models has, for mysterious reasons, an algebraic generating function. Then, we provide a new proof of a holonomy criterion recently proved by M. Petkovsek and the author. Finally, we exhibit a simple model with a non-holonomic generating function (joint work with M. Petkovsek). In all cases, we work directly from the functional equation.

GERARD DUCHAMP, Rouen
Algèbres de Hopf de fonctions quasi-symétriques non commutatives / Hopf algebras of non commutative quasi-symmetric functions

On construit diverses algèbres de Hopf généralisant celles des fonctions symétriques et quasi-symtriques.

We contruct various Hopf Algebras generalizing the Hopf Algebras of Symmetric and Quasi-Symmetric Functions.

I. GESSEL, Brandeis University, Waltham, Massachusetts  02454, USA
Two-stack-sortable multipermutations

To ``stack-sort'' a permutation we represent the permutation as a binary decreasing tree, and then read the tree in postorder. A permutation is called two-stack-sortable if stack-sorting it twice yields an identity permutation.

Doron Zeilberger proved Julian West's conjecture that the number of two-stack-sortable permutations of {1,2,¼,n} is 2(3n)!/((n+1)! (2n+1)!). Bousquet-Mélou, Bóna, and Travis independently refined Zeilberger's result by showing that the number of two-stack-sortable permutations of {1,2,¼, i+j+1} with i descents is

(2i+j+1)! (i+2j+1)! (i+1)! (2i+1)! (j+1)! (2j+1)! .

We consider a generalization of the stack-sorting operation in which binary decreasing trees are replaced by (r+1)-ary decreasing trees. These trees correspond to certain multiset permutations called ``r-permutations'', which reduce to ordinary permutations when r=1. We generalize the result of Bousquet-Mélou, Bóna, and Travis to r-permutations. We classify the descents of r-permutations into r types and show that the number of two-stack-sortable r-permutations with i_l descents of type l for l=1,¼,r is

1 n2 r Õ l=0  n n-il \binom2n-il-1il,

where n=1+i₀+¼+i_r.

This is joint work with Dapeng Xu.

IAN GOULDEN, University of Waterloo, Waterloo, Ontario  N2L 3G1
Hurwitz numbers and combinatorics

>From a geometric point of view, Hurwitz numbers count ramified covers of the sphere by a Riemann surface of specified genus, with branching above infinity specified by a specified partition, and simple branching above other prescribed points. From a combinatorial point of view, these are equivalent to a particular class of ordered factorizations in the symmetric group. We describe recent results and conjectures for Hurwitz numbers and generalizations that have been obtained from this combinatorial point of view.

A. GOUPIL, Université du Québec à Montréal, Montréal, Québec  H3C 3P8
Polynômes de classes de S_n / Class Polynomials of S_n

A chaque classe de conjugaison C_m du groupe sym\' etrique S_n, nous associons un polynôme symétrique w_m(x) que nous appelons polynôme de classe. Lorsque les polynômes w_m(x) `sont' valués sur les contenus d'un partage l de n, on obtient le caractère irréductible normalisé [(|C_m|)/(f^l )]c^l_m. Les polynômes de classes forment une nouvelle base de l'espace L des polynômes symétriques. De plus, le produit w_m(x) w_a(x) se décompose dans la base { w_m(x)}_m comme le produit de classes C_m *C_l se décompose dans la base {C_m}_m du centre de l'algèbre C[S_¥] du groupe symétrique infini. Nous utilisons les polynômes w_m(x) pour mettre au point des formules énumératives pour le nombre de tableaux standards gauches f(l/m) et pour les nombres de Kostka K_l/m. De plus, nous construisons des q-analogues des polynômes w_m(x) pour l' algèbre de Hecke du groupe symétrique.

To each conjugacy class C_m of the symmetric group S_n, we associate a symmetric polynomial w_m(x) that we call class polynomial. When the polynomial w_m(x) is evaluated on the content of a partition l of n, we obtain the normalized irreducible character [(|C_m|)/(f^l )]c^l_m. The set of class polynomials forms a new linear basis for the space L of symmetric polynomials. Furthermore, the product w_m(x)w_a(x) decomposes in the basis {w_m(x)}_m precisely as the product of classes C_m*C_l decomposes in the basis {C_m}_m of the center of the algebra C[S_¥] of the infinite symmetric group. We use the polynoms w_m(x) to establish enumerative formulae for the number f(l/m) of skew standard tableaux and for the Kostka numbers K_l/m. We also construct q-analogs of the polynomials w_m(x) for the Hecke algebra of S_n.

G. LABELLE, Université du Québec à Montréal, Montréal, Québec
Structures partiellement étiquetées asymétriques

Soit Z_F la série indicatrice des cycles d'une espèce F. En conformité avec la théorie de Pólya, on a la formule Z_F°G = Z_F°Z_G, même lorsque G(0) ¹ 0. Cependant, dans le cas de la série indicatrice d'asymétrie, G_F, des exemples simples montrent que l'égalité n'a généralement pas lieu, c.-à-d., G_F°G ¹ G_F°G_G, lorsque G(0) ¹ 0; bien qu'elle ait toujours lieu lorsque G(0)=0. Nous introduisons une variante, G_{F, x}, de la série G_F qui satisfait l'égalité G_F°G = G_{F, x}°G_G, où x = G(0). Nous étudions le comportement de la série G_{F, x} face aux opérations combinatoires, en présentons divers exemples explicites et les appliquons au dénombrement de quelques classes de structures partiellement étiquetées asymétriques.

P. LALONDE, LaCIM, UQAM
Partitions planes descendantes et dualité de chemins

Les partitions planes descendantes apparaissent dans les conjectures de Mills, Robbins et Rumsey : elles seraient en bijection avec matrices à signes alternants. Ces partitions forment un ensemble partiellement ordonné qui possède un unique anti-automorphisme, noté t. D après les conjectures, t se traduirait en une op'eration très simple sur les matrices à signes alternants : la réflexion suivant un axe vertical. Pourtant, la description directe de t dans le cadre des partitions planes descendantes est assez complexe.

On peut cependant utiliser la méthodologie de Gessel-Viennot pour coder ces partitions en configurations de chemins sans intersection. On retrouve alors une description simple de t : il s agit de la dualité de chemins, mise en évidence (dans d autres contextes) par ces mêmes auteurs.

V. LISKOVETS, Institute of Mathematics, National Academy of Sciences of Belarus, Minsk, 220072  Belarus
Some asymptotic distribution patterns for planar maps

We focus mainly on two different asymptotic cardinality patterns for planar maps. They are of the form Cn^bRⁿ (as n, the number of edges, tends to infinity), where b=-5/2 or -3/2 and C and R > 1 are constants depending on the maps under consideration. The value -5/2 of the ``critical exponent'' b is known to be valid for a large family of classes of rooted maps such as arbitrary, non-separable, polyhedral, cubic and Eulerian maps. On the contrary, b=-3/2 for various classes of rooted outerplanar maps (including plane trees) as well as maps of some singular types. We retrieve both of these values as particular cases of a general unified pattern and present some evidence and some simple arguments that justify this approach. This idea is illustrated in more detail for two specific classes of maps: Eulerian and self-dual.

Another pattern to be discussed briefly concerns the tail distribution of vertices by valency. We also touch on counting the total number of vertices in rooted maps.

PETER MCNAMARA, MIT

MARNI MISHNA, LaCIM/UQAM

J. MORSE, University of Pennsylvania
k-Schur functions and Kostka coefficients

We introduce a family of symmetric functions called the k-Schur functions and show how these elements generalize the Schur functions. We then discuss how a new type of tableaux could lead to finding expansion coefficients for the Hall-Littlewood and Macdonald polynomials in terms of k-Schur functions.

I. PAK, MIT, Cambridge, Massachusetts, USA
Fighting the involution principle

About 20 years ago, Garsia and Milne introduced the involution principle, which quickly became a powerful tool for creating bijections out of existing analytic proofs. Despite its popularity, the resulting bijections often lack simplicity and transparency, in contrast with many ``traditional'' bijections. This is our first attempt to understand and explain this striking phenomenon.

In this talk we restrict ourselves to the well studied case of Andrews' partition identities, which generalize the classical Euler's identity (the number of partitions of n into odd parts is equal to the number of partitions of n into distinct parts.) These were later extended by Cohen and Remmel. The latter also found a bijective proof by the involution principle, which was studied further by O'Hara. We will generalize these identities even further, and present an algebraic approach to bijection in these cases.

F. RUSKEY, University of Victoria, Victoria, British Columbia
Counting aperiodic strings with given elementary symmetric function evaluations

For fixed k and values t[1¼k] we try to count the number of aperiodic strings a[1¼n] for which S_k(a) = t_k, where S_k is the k-th elementary symmetric function. The alphabet of the string a is a ring R. After setting up a general framework, specific results are given for the following cases:

(a) R is Z(q), the ring of integers mod q, and k=1, or q=4 and k=2.
(b) R is F(q), the finite field of q elements, and k = 3.

Using (b), we are able to count the number of odd degree monic irreducible polynomials over F(q) whose next 3 leading coefficients are prespecified and whose degree is odd. The efficacy of our formulae will be stated in rops, the number of ring operations necessary to evaluate them. Part of the development involves a new multivariate form of Mobius inversion.

C. SAVAGE, North Carolina State University, Raleigh, North Carolina, USA
Anti-lecture hall compositions

In 1997, Bousquet-Mélou and Eriksson proved a surprising result, known as the Lecture Hall Theorem: The number of partitions l = (l₁,¼,l_k) of n satisfying

l1 k ³ l2 k-1 ³ ¼ ³ lk-1 2 ³ lk 1 ³ 0

is equal to the number of partitions of n into odd parts of size at most 2k-1. In this talk, we prove the Anti-lecture Hall Theorem, a corresponding result about the number of compositions l = (l₁,¼,l_k) of n satisfying

l1 1 ³ l2 2 ³ ¼ ³ lk k ³ 0.

To our knowledge this is a new result that complements the family of the lecture hall theorems. This is joint work with Sylvie Corteel.

G. SCHAEFFER, Loria-CNRS, ampus Sciences, Vandoeuvre-les-Nancy
The diameter of random planar maps

A planar map is a proper embedding of a graph in the sphere, considered up to homeomorphisms of the sphere. Following the work of Tutte in the sixties, various families of planar maps (triangulations, quadrangulations, eulerian, etc.) have been (and still are) enumerated with respect to their number of edges, vertices (see Liskovets' talk here).

We shall consider the uniform distribution on quadrangulations with n faces, and view them as random discretised surfaces. Combining bijections and enumerative results with probabilistic ideas, we show that one can study distances in these random quadrangulations. In particular the diameter of a random quandrangulation with n faces behave like n⁽1/4).

R. STANLEY, MIT, Cambridge, Massachusetts, USA
Kerov's character polynomial and irreducible symmetric group of rectangular shape

Shortly before his untimely death in 2000 Sergei Kerov introduced in a lecture a polynomial S_k(R₂,R₃,...,R_k+1) which encodes the value c^l(w) of any irreducible character c^l of the symmetric group S_n (for any n) at a k-cycle w. For instance, S₂=R₃, S₃=R₄+R₂, S₄=R₅+5R₃, S₅ = R₆+15R₄+5R₂²+8R₂. This polynomial is not well-understood, e.g., it is not known whether its coefficients are nonnegative. The coefficients of the linear terms R_i, however, have a combinatorial interpretation, first obtained by P. Biane. There is an alternative proof based on a new formula for c^l(w), for any w Î S_pq, when l has p parts all equal to q. It is an interesting open problem to extend this result to more general l.

B. VAN RENSBURG, York University, Toronto, Ontario  M3J 1P3
Exchange relations, Dyck paths and copolymer adsorption

A certain model of directed copolymer adsorption is equivalent to the enumeration of Dyck paths. We exploit a type of symmetry (we call this an exchange relation) to solve a specific model of an infinite family of periodically coloured copolymers adsorbing in a wall. We also find an asymptotic expression for the critical adsorption point in these models as a function of the period of the colouring. This is collaborative work with Andrew Rechnitzer.

X. VIENNOT, LaBRI, Université Bordeaux I, 33405  Talence, France
Gravitation quantique Lorentzienne et empilements de dominos / Lorentzian quantum gravity and heaps of dimers

La théorie des empilements de pièces fut introduite par l'orateur en 1985 afin de donner une vision ``géométrique'' de la théorie algébrique des monoïdes de commutations développée par Cartier et Foata en 1969. Ces empilements de pièces permettent d'unifier ou d'interpréter diverses théories combinatoires (polynômes orthogonaux, polynômes chromatiques, etc).

Des interactions et applications ont été développées par l'école bordelaise vers la physique statistique: modèles des animaux dirigés, de gaz avec particules dures, le modèle SOS, polyominos et fonctions q-Bessel, etc...

Cet exposé a pour but de relater une nouvelle application des empilements de pièces vers un tout autre domaine de la physique thé orique: la gravitation quantique Lorentzienne en dimension 2. Cette application fut développée récemment par P. Di Francesco, E. Guitter, C. Kristjansen, faisant suite aux travaux de J. Ambjorn et R. Loll. L'espace temps est discrétisé par des triangulations dites Lorentziennes. Le modèle de physique revient à expliciter certaines sé ries génératrices relatives à ces objets combinatoires. La résolution du modèle donnée par ces physiciens provient de lemmes et bijections de base sur les empilements de pièces.

The theory of heaps of pieces was introduced by the author in 1985 in order to give a ``geometric'' version of the algebraic theory of commutation monoids developed by Cartier and Foata in 1969. These heaps of pieces unify and give interpretations of various combinatorial theories (orthogonal polynomials, chromatic polynomials, etc).

Interactions and applications with statistical mechanics have been developed by the Bordeaux school: directed animal model, gaz model with hard core interactions SOS model, polyominoes and q-Bessel functions, etc...

The purpose of this talk is to expose a new application of the theory of heaps of pieces to another chapter of theoretical physics: 2D Lorentzian quantum gravity. This application has been recently developed by P. Di Francesco, E. Guitter, C. Kristjansen, following work of J. Ambjorn and R. Loll. The space time is discretized by some triangulations called Lorentzian. The physics model is equivalent to give explicit expressions for certain generating functions related to these combinatorial objects. The solution of the model given by these physicists comes from some basic lemma and bijections about heaps of pieces.

T.R. WALSH, Department of Computer Science, UQÀM, Montreal, Quebec  H3C-3P8
Génération de chaque mot d'un code gray en temps constant / Constant time generation of each word of a gray code

Un mot de longueur n est une suite finie g[1],g[2],...,g[n] de lettres, qui sont des membres d'un ensemble fini, un alphabet. Un code Gray est une famille infinie L1, L2,..., où Ln est une liste de mots, tous de longueur n, telle que chaque mot sauf le premier dans chaque liste Ln est obtenue de son prédécesseur en changeant un nombre de lettres borné indépendamment de n. Il y a des codes Gray pour beaucoup d'objets combinatoires: chaînes binaires, combinaisons, permutations, compositions d'un entier, partages d'un ensemble, partages d'un entier, mots de Dyck et d'autres représentations des arbres binaires. Pour quelques-uns de ces codes Gray-chaînes binaires, combinaisons, permutations, compositions d'un entier et partages d'un ensemble-G. Ehrlich a trouvé des algorithmes pour engendrer chaque mot sauf le premier en temps borné indépendamment de la longueur des mots et sa mé thode a été appliquée par d'autres chercheurs aux autres codes Gray. Dans cette confér ence il est démontré que sa méthode marche pour tout code Gray tel que tous les mots dans une liste avec le même pré fixe g[1],g[2],...,g[i-1] forment un intervalle de mots consécutifs dans lequel la prochaine lettre g[i] atteint au moins deux valeurs distinctes. En plus, sa méthode est généralisée pour permettre g[i] de n'atteindre qu'une seule valeur si un seul mot a le préfixe g[1],g[2],...,g[i-1]-cette condition est satisfaite par la vaste majorité de codes Gray dans la littérature. Un nouveau code Gray est présenté pour les compositions d'un entier avec chaque partie bornée entre 0 et un entier positif et pour les permutations de {1,2,...,n} avec r inversions dont les vecteurs d'inversions sont les compositions de r avec n-1 parties bornées par n-1,n-2,...,2,1; la généralisation de la méthode d'Ehrlich permet la génération de ces objets en temps constant.

A length-n word is a finite chain g[1],g[2],...,g[n] of letters which are elements of a finite set, an alphabet. A Gray code is an infinite family L1, L2,..., where Ln is a list of length-n words such that every word except the first one in each list Ln is obtained from its predecessor by changing a number of letters bounded independently of n. There are Gray codes for many combinatorial objects: binary chains, combinations, permutations, integer compositions, set partitions, integer partitions, Dyck words and other representations of binary trees. For some of these Gray codes-binary chains, combinations, permutations, integer compositions and set partitions-G. Ehrlich found algorithms for generating each word except the first one in a time bounded independently of the word length and his method has been applied by other researchers to other Gray codes. In this talk we prove that his method works for any Gray code such that all the words in a list with the same prefix g[1],g[2],...,g[i-1] form an interval of consecutive words in which the next letter g[i] takes at least two distinct values. Furthermore, we generalize his method to allow g[i] to take only one value if only one word has the prefix g[1],g[2],...,g[i-1]-this condition is satisfied by the vast majority of Gray codes in the literature. We present a new Gray code for integer compositions with each part bounded between 0 and a positive integer and for the permutations of {1,2,...,n} with r inversions whose inversion vectors are the compositions of r with n-1 parts bounded by n-1,n-2,...,2,1; using the generalisation of Ehrlich's method we generate each of these objects in constant time.

J. WEST, University of Victoria, Victoria, British Columbia
Somos sequences and perfect matchings

Linear recurrences (and, with them, ordinary generating functions) are ubiquitous in combinatorics, as part of a broad general framework that is well-studied and well-understood; in contrast, bilinear recurrences such as s_n+4 = (s_n+1s_n+3+s_n+2²)/s_n are encountered far less often, and these encounters tend to be viewed in isolation from one another.

The bilinear recurrence relation quoted above is the Somos-4 recurrence, part of a general family of ën/2û-degree sequences. Although these have received a fair bit of attention in the past few years, until recently algebra remained one step ahead of combinatorics, leaving us temporarily in the unusual position of being able to enumerate combinatorial objects for which we lack a combinatorial description.

In this talk, we produce a family of graphs whose perfect matchings are enumerated by the Somos-4 sequence, and a second family whose perfect matchings are enumerated by Somos-5. The recurrences that govern these sequences are also special cases of the Gale-Robinson family of recurrences: S(n)=[S(n-i₁)S(n-i₂)+S(n-j₁)S(n-j₂)]/S(n-k), where k=i₁+i₂=j₁+j₂. The results for Somos-4 and Somos-5 thus give us some hope that a similar family of graphs can be constructed for any Gale-Robinson recurrence.

This is joint work with Jim Propp and Mireille Bousquet-Melou. Many of these results have also been obtained independently by Propp's team of undergraduate researchers at Harvard.

C. YAN, Texas A&M University, College Station, USA
Goncarov polynomials and parking functions

The Goncarov polynomials g_n(x;a₀,a₁,¼,a_n-1) are polynomials defined by the biorthogonality relation:

e(ai) Di gn(x;a0,a1,¼,an-1) = n! din,

where e(a) is evaluation at a. Goncarov polynomials form a natural basis for generalized parking functions. In particular, expanding xⁿ as a linear combination of Goncarov polynomials leads to a decomposition of an arbitrary sequences of positive integers into two subsequences: a maximum parking function and a subsequence of higher values. From this combinatorial decomposition, we derive linear recursions for sum enumerators, expected sums of u-parking functions, and higher moments of sums of u-parking functions. These recursions yield explicit formulas for these quantities in terms of Goncarov polynomials.

DORON ZEILBERGER, Rutgers University, New Brunswick, New Jersey  08903, USA
Deranged Wilf classes

Aaron Robertson found a surprising and deep refinement of the classical enumerative results that the number of 132-avoiding permutations equals the number of 123-avoiding permutations. This is probably but the tip of a beautiful deranged theory of Wilf Classes.

J. ZENG, Institut Girard Desargues, Universite Lyon 1, 43, Bd du 11 Novembre 1918, 69622  Villeurbanne Cedex, France
New identities of Hall-Littlewood polynomials and new identities of Rogers-Ramanujan type

Starting from Macdonald's summation formula of Hall-Littlewood polynomials over bounded partitions and its even partition analogue, Stembridge (Trans. Amer. Math. Soc. (2) 319(1990), 469-498) derived sixteen multiple q-identities of Rogers-Ramanujan type. Inspired by our recent results on Schur functions (Adv. Appl. Math. 27(2001), 493-509) and based on computer experiments we obtain two further such summation formulae of Hall-Littlewood polynomials over bounded partitions and derive six new multiple q-identities of Rogers-Ramanujan type. This talk is base on joint works with F. Jouhet.