L E Groupe

Sym Étrique

G Én

J.-C Aval

POLYN ÔMES QUASI-INVARIANTS ET SUPER-COINVARIANTS POUR

Un résultat classique d'Artin affirme que l'idéal engendré par les polynômes symétriques sans terme constant en n variables est de codimension n!. L'auteur, F. Bergeron et N. Bergeron ont récemment obtenu un analogue surprenant dans le cas des polynômes quasi-symétriques. Dans ce cas, l'idéal est de codimension C n , le n-ième nombre de Catalan. Les polynômes quasi-symétriques peuvent être vus comme invariants d'une action du groupe symétrique S n , définie par F. Hivert. Le but de ce travail est de généraliser ces travaux au produit en couronne S n ≀ Z m , connu sous le nom de groupe symétrique généralisé G n,m . Après avoir défini une action quasi-symétrisante de G n,m sur C[x 1 , . . . , x n ], nous obtenons une description des invariants, et la codimension de l'idéal associé, à savoir m n C n .

Introduction

Considérons l'alphabet X en n variables (x 1 , . . . , x n ). L'espace des polynômes prenant ses variables dans X et à coefficients complexes est noté C[X]. Soit G n,m = S n ≀ Z m le produit en couronne du groupe symétriques S n par le groupe cyclique Z m . Ce groupe est souvent applelé groupe symétrique généralisé (cf. [START_REF] Osima | On the representations of the generalized symmetric group[END_REF]). On peut se représenter un élément de G n,m comme une matrice carrée de taille n dans laquelle chaque ligne et chaque colonne comporte exactement une entrée non nulle (matrice de pseudo-permutation), et telle que ces entrées non nulles sont des racines m-ième de l'unité. L'ordre du groupe G n,m est par conséquent m n n!. Si m = 1, G n,m se réduit au groupe symétrique S n , et si m = 2, G n,m est le groupe hyperoctaèdral B n , i.e. le groupe des permutations signées ou groupe de Weil de type B (voir [START_REF] Lusztig | Irreducible representationsof finite reflections groups[END_REF] pour plus de détails). Le groupe G n,m agit sur les polynômes (action "classique") de la façon suivante :

(1. 1) ∀g ∈ G n,m , ∀P ∈ C[X], g.P (X) = P (X. t g), où t g est la transposée de la matrice g et X est vu comme vecteur ligne. Soit

Inv n,m = {P ∈ C[X] / ∀g ∈ G n,m , g.P = P } l'ensemble des invariants polynomiaux pour cette action G n,m . Notons de plus Inv + n,m l'ensemble des tels polynômes sans terme constant. Nous considérons le produit scalaire suivant sur C[X] :

(1.2)

P, Q = P (∂X)Q(X) | X=0 où ∂X représente (∂x 1 , . . . , ∂x n ) et X = 0 représente x 1 = • • • = x n = 0.
Cov n,m = {P ∈ C[X] / ∀Q ∈ Inv + n,m , Q(∂X)P = 0} = Inv + n,m ⊥ ≃ C[X]/ Inv +
n,m . L'égalité et l'isomorphisme précédent ne sont pas triviaux, mais une référence à ce sujet est [START_REF] Garsia | Orbit Harmonics and Graded Representations[END_REF].

Assez de définitions. Un résultat classique d'Artin [1] affirme que pour m = 1 (cas du groupe symétrique), la dimension de l'espace coinvariant H n = Cov n,1 (qualifié dans ce contexte d'harmonique) est égale à n!. Chevalley [START_REF] Chevalley | Invariants of finite groups generated by reflections[END_REF] (voir aussi [START_REF] Shephard | Finite unitary reflection groups[END_REF]) a généralisé ce résultat en montrant que :

(1.3) dim Cov n,m = |G n,m | = m n n! .
Dans le cas du groupe symétrique (m = 1), d'intéressants résultats ont été obtenus récemment [START_REF] Aval | Catalan Paths and Quasi-Symmetric Functions[END_REF][START_REF] Aval | Ideals of Quasi-Symmetric Functions and Super-Coinvariant Polynomials for S n[END_REF] en étudiant les coinvariants correspondant, non plus aux polynômes symétriques, mais aux polynômes quasi-symétriques. Notre but principal est ici d'obtenir une description analogue dans le cas m quelconque.

L'anneau QSym des fonctions quasi-symétriques a été introduit par Gessel [START_REF] Gessel | Multipartite P -partitions and products of skew Schur functions[END_REF] dans le cadre du calcul des fonctions génératrices des P -partitions [START_REF] Stanley | Enumerative Combinatorics[END_REF]. Ces fonctions quasi-symétriques sont la source de nombreux travaux récents dans plusieurs domaines de la combinatoire [START_REF] Bergeron | Pieri Operations on Posets[END_REF][START_REF] Malvenuto | Duality between quasi-symmetric functions and the Solomon descent algebra[END_REF][START_REF] Gelfand | Noncommutative symmetric functions[END_REF][START_REF] Stanley | [END_REF].

Dans [START_REF] Aval | Catalan Paths and Quasi-Symmetric Functions[END_REF][START_REF] Aval | Ideals of Quasi-Symmetric Functions and Super-Coinvariant Polynomials for S n[END_REF], Aval et. al. étudient l'espace SH n des polynômes super-coinvariants, defini comme l'orthogonal (par rapport à (1.2)) de l'idéal engendré par les polynômes quasi-symétriques sans terme constant, et ont prouvé que sa dimension en tant qu'espace vectoriel est donnée par le n-ième nombre de Catalan :

(1.4) dim SH n = C n = 1 n + 1 2n n .
Notre principal résultat est une généralisation de l'équation ci-dessus dans le cas du groupe symétrique généralisé G n,m . Cet article est organisé de la façon suivante. Dans la section 2, nous définissons et étudions une action quasi-symétrisante du groupe G n,m sur C[X]. Les invariants correspondant à cette action sont appelés quasi-invariants et correspondent aux fonctions quasi-symétriques pour m = 1. La Section 3 est consacrée à la preuve du théorème central (Théorème 2.4), qui donne la dimension de l'espace SCov n,m des polynômes super-coinvariants pour G n,m ; une utilisation (simple) des bases de Gröbner nous permet de calculer une base explicite de SCov n,m (et sa série de Hilbert).

Une action quasi-symétrisante du groupe G n,m

Nous utliserons la notation vectorielle pour les monômes. Plus précisément, pour ν = (ν 1 , . . . , ν n ) ∈ N n , nous noterons X ν le monôme (2.1)

x ν 1 1 x ν 2 2 • • • x νn n . Pour tout P ∈ Q[X], nous noterons [X ν ] P (X) le coefficient du monôme X ν dans P (X).
Notre première tâche est de définir une action quasi-symétrisante du groupe G n,m sur C[X]. Cette action doit répondre aux critères suivants : elle doit se réduire à l'action de Hivert (cf. [START_REF] Hivert | Hecke algebras, difference operators, and quasi-symmetric functions[END_REF]) dans le cas m = 1 et fournir des polynômes invariants intéressants. Par intéressant, nous entendons que ces invariants jouissent d'une jolie caractérisation, de même que les polynômes coinvariants. Il s'avère que le choix d'une telle action n'est pas unique. Celle que nous allons étudier est définie de la façon suivante. Soit A ⊂ X un sous-alphabet de X comportant l variables et K = (k 1 , . . . , k l ) un vecteur d'entiers strictement positifs. Nous ordonnerons un vecteur B constitué de variables x i distinctes multipliées par des racines de l'unité selon l'ordre des variables et le résultat sera noté (B) < . Voici maintenant comment agit un élément g ∈ G n,m :

(2.2) g • A K = w(g) c(K) (A. t |g|) < K
où w(g) est le poids de g, i.e. le produit de ses entrées non nulles, |g| est la matrice obtenue en prenant le module des entrées de g, et le coefficient c(K) est défini ainsi :

c(K) = 0 si ∀i, k i ≡ 0 [m] 1 sinon. Exemple 2.1. Si m = 3 et n = 3, et nous notons ζ le nombre complexe ζ = e 2iπ 3 , alors par exemple   0 0 j 1 0 0 0 j 0   • (x 2 1 x 2 ) = (j 2 ) 1     0 0 1 1 0 0 0 1 0   . (x 1 , x 2 )   (2,1) < = j 2 (x 3 , x 1 ) < (2,1) = j 2 (x 1 , x 3 ) (2,1) = j 2 x 2 1 x 3 .
Un simple calcul permet de vérifier que ceci définit bien une action du groupe G n,m sur C[X], qui se réduit à l'action de Hivert (cf. [START_REF] Hivert | Hecke algebras, difference operators, and quasi-symmetric functions[END_REF], Proposition 3.4) dans le cas m = 1.

Il va de soit que toute définition du coefficient c(K) donne une action du groupe G n,m . Parmi cette famille d'actions, celle définie ici respecte les critères énoncés plus haut. Dans le cas particulier du groupe B n , une action apparentée à celle définie ci-dessus (et fournissant les mêmes invariants) est étudiée dans [START_REF] Aval | Quasi-symmetric polynomials and Temperley-Lieb algebra of type B, en préparation[END_REF].

Étudions à présent les polynômes invariants et coinvariants de cette action. Nous devons rappeler quelques définitions.

Une composition α = (α 1 , α 2 , . . . , α k ) de l'entier positif d est une liste ordonnée d'entiers strictement positifs dont la somme vaut d. Pour un vecteur ν ∈ N n , notons c(ν) la composition obtenue en enlevant les éventuels zéros de ν. Un polynôme

P ∈ Q[X] est dit quasi-symétrique si et seulement si, pour tous ν et µ dans N n , nous avons l'égalité [X ν ]P (X) = [X µ ]P (X)
dès que c(ν) = c(µ). L'espace des polynômes quasi-symétriques en n variables est notée QSym n . Les polynômes invariants sous l'action (2.2) de G n,m sont qualifiés de quasi-invariant et l'espace des polynômes quasi-invariants est noté QInv n,m , i.e.

P ∈ QInv n,m ⇔ ∀g ∈ G n,m , g • P = P.
Rappelons (cf. [START_REF] Hivert | Hecke algebras, difference operators, and quasi-symmetric functions[END_REF], Proposition 3.15) que QInv n,1 = QSym n . La proposition suivante donne une caractérisation élégante de QInv n,m . Proposition 2.2. Nous avons La réciproque est évidente.

P ∈ QInv n,m ⇔ ∃Q ∈ QSym n / P (X) = Q(X m ) où Q(X m ) = Q(x m 1 , . . . , x m n ).
Définissons maintenant les polynômes super-coinvariants :

SCov n,m = {P ∈ C[X] / ∀Q ∈ QInv + n,m , Q(∂X)P = 0} = QInv + n,m ⊥ ≃ C[X]/ QInv + n,m
où le produit scalaire est définie dans (1.2). C'est l'analogue naturel de Cov n dans le cadre des actions quasi-symétrisantes et SCov n,m se réduit à l'espace des polynômes super-harmoniques SH n (cf. [START_REF] Aval | Ideals of Quasi-Symmetric Functions and Super-Coinvariant Polynomials for S n[END_REF]) quand m = 1.

Remarque 2.3. Il est clair que tout polynôme invariant sous l'action (2.2) est aussi invariant sous (1.1), i.e. Inv n,m ⊂ QInv n,m . En prenant l'orthogonal, on obtient SCov n,m ⊂ Cov n,m , ce qui justifie en un sens la terminologie.

Notre principal résultat est le suivant, qui est une généralisation de (1.4). On notera aussi une grande similarité avec (1.3). Théorème 2.4. La dimension de l'espace SCov n,m est donnée par

(2.3) dim SCov n,m = m n C n = m n 1 n + 1 2n n .
Remarque 2.5. Dans le cas du groupe hyperoctaèdral B n = G n,2 , C.-O. Chow [START_REF] Chow | Noncommutative Symmetric Functions of Type B[END_REF] a défini une classe BQSym(x 0 , X) de polynômes quasi-symétriques du type B en l'alphabet (x 0 , X). Il est intéressant de comparer son approche à la notre et de constater qu'elle est bien différente. On observe en particulier que :

BQSym(x 0 , X) = QSym(X) + QSym(x 0 , X).

Il est alors assez simple de voir que le quotient C[x 0 , X]/ BQSym + est isomorphe au quotient C[X]/ QSym + étudié dans [START_REF] Aval | Ideals of Quasi-Symmetric Functions and Super-Coinvariant Polynomials for S n[END_REF]. Expliquons cela en quelques mots pour le lecteur intéressé : si G est la base de Gröbner de QSym + construite dans [START_REF] Aval | Ideals of Quasi-Symmetric Functions and Super-Coinvariant Polynomials for S n[END_REF] (on pourra aussi se reporter à la section suivante), alors l'ensemble {x 0 , G} est une base de Gröbner de BQSym + (toute syzygie est réductible en vertu du premier principe de Buchberger, cf. [START_REF] Cox | Ideals, Varieties, and Algorithms[END_REF]).

La section suivante est consacrée à la preuve du Théorème 2.4.

Preuve du théorème principal

Nous allons prouver le Théorème 2.4 en construisant une base explicite du quotient C[X]/ QInv + n,m . Ceci repose en grande partie sur les travaux [START_REF] Aval | Catalan Paths and Quasi-Symmetric Functions[END_REF][START_REF] Aval | Ideals of Quasi-Symmetric Functions and Super-Coinvariant Polynomials for S n[END_REF]. Nous allons cependant rappeler ici brièvement les éléments nécessaires.

Commençons par rappeler (cf. [START_REF] Aval | Ideals of Quasi-Symmetric Functions and Super-Coinvariant Polynomials for S n[END_REF]) la bijection suivante qui associe à tout vecteur ν ∈ N n un chemin π(ν) dans le plan N × N. Ce chemin fait des pas Nord ou Est et est défini ainsi : si ν = (ν 1 , . . . , ν n ), le chemin π(ν) est

(0, 0) → (ν 1 , 0) → (ν 1 , 1) → (ν 1 + ν 2 , 1) → (ν 1 + ν 2 , 2) → • • • → (ν 1 + • • • + ν n , n -1) → (ν 1 + • • • + ν n , n).
Par exemple le chemin associé à ν = (2, 1, 0, 3, 0, 1) est donnée à la Figure 1.

π(ν) = Figure 1.
Nous distinguons alors deux types de chemins, suivant leur comportement par rapport à la digonale y = x. Si le chemin reste au-dessus de la diagonale, nous l'appelons un chemin de Dyck, et qualifions le vecteur correspondant de Dyck. Sinon, nous disons que le chemin (et le vecteur associé) est transdiagonal. Par exemple η = (0, 0, 1, 2, 0, 1) est de Dyck et ε = (0, 3, 1, 1, 0, 2) est transdiagonal (cf. Figure 2).

B n,m = {(X n ) m η+α / π(η) est un chemin de Dyck , 0 ≤ α i < m} est une base du quotient C[X n ]/ QInv + n,m .
Pour prouver ce résultat, le but est de construire une base de Gröbner pour l'idéal J n,m = QInv + n,m . Nous utiliserons les résultats de [START_REF] Aval | Catalan Paths and Quasi-Symmetric Functions[END_REF][START_REF] Aval | Ideals of Quasi-Symmetric Functions and Super-Coinvariant Polynomials for S n[END_REF]. L'ordre lexicographique sur les monômes est défini par (3.1)

X ν > lex X µ ssi ν > lex µ,
si et seulement si la première composante non nulle du vecteur ν -µ est positive. Pour toute partie S de Q[X] et tout entier strictement positif m, introduisons S m = {P (X m ) , P ∈ S}. Nous noterons G(I) l'unique base de Gröbner réduite (cf. [START_REF] Cox | Ideals, Varieties, and Algorithms[END_REF]) d'un idéal I. Le lemme suivant, en dépit d'une preuve très simple, est non seulement crucial dans notre contexte mais peut également fournir une preuve instantanée de l'égalité (1.3). Proposition 3.2. Avec les notations précédentes,

(3.2) G( S m ) = G( S ) m .
Preuve. C'est une application directe du critère de Buchberger (cf. [START_REF] Cox | Ideals, Varieties, and Algorithms[END_REF] pour une présentation claire du sujet). En effet, si pour toute paire g, g ′ d'éléments de G( S ), la syzygie S(g, g ′ ) se réduit à zéro (par hypothèse G( S ) est une base de Gröbner), alors la syzygie

S(g(X m ), g ′ (X m ))
se réduit aussi à zéro dans G( S m ) par exactement le même calcul.

Rappelons que dans [START_REF] Aval | Catalan Paths and Quasi-Symmetric Functions[END_REF] est construite une famille G de polynômes G ε , indexés par les vecteurs transdiagonaux ε, possédant les caractéristiques suivantes :

• le monôme dominant de G ε est LM(G ε ) = X ε ;

• G est une base de Gröbner de J n,1 .

Le résultat suivant est alors une conséquence des Propositions 2.2 et 3. ) [X] est l'espace des polynômes homogènes de degré k (incluant le polynôme nul).

SCov (k) n,m = SCov n,m ∩ Q (k) [X] où Q (k
Notons F n,m (t) la série de Hilbert de SCov n,m , i.e.

(3.4)

F n,m (t) = k≥0 dim SCov (k) n,m t k .
Rappelons que dans [START_REF] Aval | Ideals of Quasi-Symmetric Functions and Super-Coinvariant Polynomials for S n[END_REF] est calculée la série de Hilbert F n,1 :

(3.5) F n,1 (t) = F n (t) = n-1 k=0 n -k n + k n + k k t k
où apparaît le nombre de chemins de Dyck ayant un nombre fixé (à savoir n -k) de facteurs (cf. [START_REF] Kreweras | Sur les éventails de segments[END_REF]). Le Théorème 3.1 implique alors le Corollaire 3.4. Avec les notations de (3.5), la série de Hilbert de SCov n,m est donnée par

F n,m (t) = 1 -t m 1 -t F n (t m ) = 1 -t m 1 -t n-1 k=0 n -k n + k n + k k t mk .
De cette formule, on peut déduire la formule close suivante

n F n,m (t) x n = (1-t) -(1-t)(1 -t -4t m x(1 -t m )) -2x(1-t m ) (1 -t)(2t m -1) -x(1 -t m ) .

Extended abstract in English

In this extended abstract, the equations, propositions, . . . are numbered as in the French part.

Let X denote the alphabet in n variables (x 1 , . . . , x n ) and C[X] denote the space of polynomials with complex coefficients in the alphabet X. Let G n,m = S n ≀ Z m denote the wreath product of the symmetric group S n by the cyclic group Z m , sometimes known as the generalized symmetric group (cf. [START_REF] Osima | On the representations of the generalized symmetric group[END_REF]). It may be seen as the group of n × n matrices in which each row and each column has exactly one non-zero entry (pseudo-permutation matrices), and such that the non-zero entries are m-th roots of unity. The order of G n,m is m n n!. n,m . The previous equality and isomorphism are not obvious, and a reference on that topic is [START_REF] Garsia | Orbit Harmonics and Graded Representations[END_REF].

A classical result of Chevalley [START_REF] Chevalley | Invariants of finite groups generated by reflections[END_REF] (see also [START_REF] Shephard | Finite unitary reflection groups[END_REF]) states the following equality:

(1.

  Preuve. Soit P un élément de QInv n,m . Notons ζ la racine m-ième de l'unité ζ = e 2iπ m et g l'élément de G n,m dont la matrice est g• P + g 2 • P + • • • + g m-1 • P ) = Pimplique que tous les exposants apparaissant dans P doivent être des multiples de m. Donc il existe un polynôme Q ∈ C[X] tel que P (X) = Q(X m ). Pour conclure, il suffit de noter que S n ⊂ G n,m implique que P est quasi-symétrique, donc Q est aussi quasi-symétrique.

Figure 2 .

 2 Figure 2.

2 .

 2 Proposition 3.3. L'ensemble G m est une base de Gröbner de l'idéal J n,m . Pour conclure la preuve du Théorème 3.1, il est suffisant de remarquer que l'ensemble des monômes non divisibles par un monôme dominant d'un élément de G m , i.e. par un X mε pour ε transdiagonal, sont précisément les monômes apparaissant dans B n,m . Comme corollaire du Théorème 3.1, nous obtenons une formule explicite pour la série de Hilbert de SCov n,m . Pour k ∈ N, notons SCov

  When m = 1, G n,m reduces to the symmetric group S n , and when m = 2, G n,m is the hyperoctahedral group B n , i.e. the group of signed permutations, which is the Weyl group of type B. The group G n,m acts classically on C[X] by the rule (1.1)∀g ∈ G n,m , ∀P ∈ C[X], g.P (X) = P (X. t g),where t g is the transpose of the matrix g and X is considered as a row vector. LetInv n,m = {P ∈ C[X] / ∀g ∈ G n,m , g.P = P }denote the set of G n,m -invariant polynomials. Let us denote by Inv + n,m the set of such polynomials with no constant term. We consider the following scalar product on C[X]:(1.2) P, Q = P (∂X)Q(X) | X=0where ∂X stands for (∂x 1 , . . . , ∂x n ) and X = 0 stands forx 1 = • • • = x n = 0. Let S denotethe ideal generated by a subset S of C[X]. The space of G n,m -coinvariant polynomials is then defined by Cov n,m = {P ∈ C[X] / ∀Q ∈ Inv + n,m , Q(∂X)P = 0} = Inv + n,m ⊥ ≃ C[X]/ Inv +

  3) dim Cov n,m = |G n,m | = m n n!

  Utilisons la notation S pour l'idéal engendré par une partie S de C[X]. L'espace des polynômes G n,m -coinvariants est alors défini par

Recherche financée par le Programme IHRP

which reduces when m = 1 to the theorem of Artin [1] that the dimension of the harmonic space H n = Cov n,1 (cf. [START_REF] Garsia | Orbit Harmonics and Graded Representations[END_REF]) is n!.

Our aim is to give an analogous result in the case of a quasi-symmetrizing action. The ring QSym of quasi-symmetric functions was introduced by Gessel [START_REF] Gessel | Multipartite P -partitions and products of skew Schur functions[END_REF] as a source of generating functions for P -partitions [START_REF] Stanley | Enumerative Combinatorics[END_REF] and appears in more and more combinatorial contexts [START_REF] Bergeron | Pieri Operations on Posets[END_REF][START_REF] Stanley | [END_REF].

In [START_REF] Aval | Catalan Paths and Quasi-Symmetric Functions[END_REF][START_REF] Aval | Ideals of Quasi-Symmetric Functions and Super-Coinvariant Polynomials for S n[END_REF], Aval et. al. investigated the space SH n of super-coinvariant polynomials for the symmetric group, defined as the orthogonal (with respect to (1.2)) of the ideal generated by quasi-symmetric polynomials with no constant term, and proved that its dimension as a vector space equals the n-th Catalan number:

Our main result is a generalization of the previous equation in the case of supercoinvariant polynomials for the group G n,m .

In Section 2, we define and study a quasi-symmetrizing action of G n,m on C[X]. We want this action to give Hivert's action (cf. [START_REF] Hivert | Hecke algebras, difference operators, and quasi-symmetric functions[END_REF]) in the case m = 1 and to give interesting invariants and coinvariants. Such an action is not unique and we study the one defined as follows. Let A ⊂ X be a subset of X with l variables and K = (k 1 , . . . , k l ) a vector of positive (> 0) integers. We order a vector B consisting of distinct variables x i multiplied by roots of unity with respect to the variable order and the result is denoted by (B) < . Now the quasi-symmetrizing action of g ∈ G n,m is given by (see also Example 2.1):

(2.2)

where w(g) is the weight of g, i.e. the product of its non-zeero entries, |g| is the matrix obtained by taking the module of the entries of g, and the coefficient c(K) is defined as:

1 if not. We now study invariants and coinvariants relative to this action. A composition α = (α 1 , α 2 , . . . , α k ) of the positive integer d is an ordered list of nonnegative integers whose sum equals d. For ν ∈ N n , let c(ν) denote the composition obtained by erasing the zero parts of ν. A polynomial P ∈ Q[X] is quasi-symmetric if and only if, for any ν, µ ∈ N n , we have

as soon as c(ν) = c(µ). The space of quasi-symmetric polynomials in n variables is denoted by QSym n .

The invariant of the action (2.2) are said quasi-invariant and their space is denoted by QInv n,m . Recall (cf. [START_REF] Hivert | Hecke algebras, difference operators, and quasi-symmetric functions[END_REF], Proposition 3.15) that QInv n,1 = QSym n . The following proposition gives a characterization of quasi-invariant polynomials. Proposition 2.2.

We now define super-coinvariant polynomials:

Our main result is the following, which is a generalization of (1.4), but also shows similarity to (1.3).

Theorem 2.4. The dimension of SCov n,m is given by

The Section 3 is devoted to the proof of this result. More precisely, we construct an explicit basis of the quotient C[X n ]/ QInv + n,m (cf. Theorem 3.1) from which we deduce its Hilbert series, given by Corollary 3.4.

To do this, we use the results of [START_REF] Aval | Catalan Paths and Quasi-Symmetric Functions[END_REF][START_REF] Aval | Ideals of Quasi-Symmetric Functions and Super-Coinvariant Polynomials for S n[END_REF] to construct a Gröbner basis of the ideal QInv + n,m . The important point of this proof is the Proposition 3.2, so we shall say a few words about it.

The lexicographic order on monomials is defined by

if and only if the first non-zero entry of ν -µ is positive.

For any S ⊆ Q[X] and m ∈ N * , we introduce S m = {P (X m ) , P ∈ S}. We denote by G(I) the unique reduced monic Gröbner basis (cf. [START_REF] Cox | Ideals, Varieties, and Algorithms[END_REF]) of an ideal I. The following lemma has a simple proof but is the crucial tool in our context. Furthermore, despite its simplicity, it can provide a proof of (1.3) in a few lines.


H Vincent

M Arquier

J Bleyer

P De Buhan

YIELD DESIGN BASED NUMERICAL ANALYSIS OF THREE-DIMENSIONAL REINFORCED CONCRETE STRUCTURES

Keywords: reinforced concrete structures, yield design, semi-definite programming, homogenization

The objective of this contribution is to present some new recent developments regarding the evaluation of the ultimate bearing capacity of massive three-dimensional reinforced concrete structures which cannot be modelled as 1D (beams) or 2D (plates) structural members. The approach is based upon the implementation of the lower bound static approach of yield design through a discretization of the three-dimensional structure into tetrahedral finite elements, on the one hand, the formulation of the corresponding optimization problem in the context of Semidefinite Programming (SDP) techniques, on the other hand. Another key feature of the method lies in the treatment of the concrete-embedded reinforcing bars not as individual elements, but by resorting to an extension of the yield design homogenization approach. The whole procedure is first validated on the rather simple illustrative problem of a uniformly loaded simply supported beam, then applied to the design of a bridge pier cap taken as an example of more complex and realistic structure.

INTRODUCTION

The yield design [START_REF] Salençon | Yield Design[END_REF] or limit analysis [START_REF] Chen | Plasticity in reinforced concrete[END_REF] approach provides a suitable theoretical as well as computational framework for the Ultimate Limit State Design of structures in general and reinforced concrete structures in particular. In the situation when the structure is made of an assemblage of 1D (beams or arches) or 2D (plates or shells) structural members, its ultimate bearing capacity may be evaluated from a previously determined interaction yield criterion involving generalized stresses such as axial-membrane forces and bending moments. This method, which proves particularly attractive from an engineering point of view, has been quite recently used for spatial frame structures [START_REF] Bleyer | Yield surface approximation for lower and upper bound yield design of 3D composite frame structures[END_REF] and reinforced concrete plates [START_REF] Bleyer | Failure design of high-rise concrete panels under fire loading[END_REF] in combination with efficient convex optimization procedures.

On the other hand, assessing the ultimate load bearing capacity of constructions incorporating massive three-dimensional reinforced concrete components, which can no more be modelled as beams or plates, requires a specific analysis, such as the widely acknowledged "strut-and-tie" model (see among many other references [START_REF] Marti | Truss models in detailing[END_REF], [START_REF] Schlaich | Toward a consistent design of structural concrete[END_REF], [START_REF] Schlaich | Stress Fields for Nodes of Strut-and-Tie Models[END_REF] or [START_REF] Siao | Strut-and-tie model for shear behaviour in deep beams and pike caps failing in diagonal splitting[END_REF]) which, in some way, can be related to the lower bound static approach of yield design. With a special attention to evaluating the ultimate shear capacity of reinforced concrete deep beams, both the lower and upper bound methods of yield design have been implemented in the context of a finite element formulation with the help of linear programming optimization techniques [START_REF] Averbuch | Shear Design of Reinforced Concrete Deep Beams: A Numerical Approach[END_REF]. In this study, reinforced concrete was described according to a "mixed modelling" approach, in which plain concrete was modelled as a two-dimensional continuous medium under plane stress, while the reinforcement bars were treated as one dimensional flexible beams embedded in the concrete material.

The generalization to the more realistic situation of linear reinforcing inclusions placed into three-dimensional concrete bodies is posing a somewhat serious challenge as regards the possibility of treating such a case in a 1D-3D mixed modelling approach. Some attempts to circumvent this problem have already been proposed either in the context of the finite element formulation [START_REF] Llau | Finite element modelling of 1D steel components in reinforced and pre-stressed concrete structures[END_REF] or making use of an implicit homogenization method [START_REF] Nielsen | Limit Analysis and Concrete Plasticity[END_REF] or multiphase model [START_REF] Figueiredo | Three-dimensional finite element analysis of reinforced concrete structural elements regarded as elastoplastic multiphase media[END_REF].

The present contribution is devoted to applying the previously mentioned homogenization model, initially developed for reinforced soils, to the yield design of three-dimensional reinforced concrete structures. It is based on the combination of the following elements.

 Formulation of the plain concrete three-dimensional strength properties by means of a tension cut-off Mohr-Coulomb condition, characterized by the uniaxial tensile and compressive strengths of the concrete, along with its friction angle.

 Modelling the strength of each individual reinforcement with its surrounding concrete volume as a homogenized anisotropic continuum accounting for both the above mentioned plain concrete strength properties and axial strength of the reinforcing inclusion.

 Finite element formulation of the lower bound static approach of yield design based on a discretization of the structure into tetrahedral elements with a piecewise linear variation of the stresses.

 The final optimization procedure is carried out by means of Semi-definite Programming (SDP).

The whole design procedure is first illustrated and validated on the simple example of a uniformly loaded deep beam, and the obtained results are compared with those derived from a 1D modelling of the structure where the local resistance is defined by means of an interaction diagram. It is then applied to evaluating the ultimate bearing capacity of a reinforced concrete bridge pier cap subjected to concentrated vertical loads.

MODELLING STRENGTH PROPERTIES OF PLAIN AND REINFORCED CONCRETE

Plain concrete and reinforcing bars

Following the approach of [START_REF] Chen | Plasticity in reinforced concrete[END_REF] and [START_REF] Marti | Truss models in detailing[END_REF] or quite recently [START_REF] Bleyer | Failure design of high-rise concrete panels under fire loading[END_REF], the unreinforced or plain concrete will be modelled as a 3D homogeneous continuous medium, the strength properties of which will be described by means of a tension cut-off Mohr-Coulomb yield condition which may be formulated as: The concrete material is reinforced by one dimensional steel bars or rods, the strength condition of which may be expressed in terms of axial force n only, since their resistance to shear force v and bending moment m can be neglected:

  ( ) sup ; 0 c p M m c M t F K f f          (1)
0 0 , 0 kn n n v m      (2)
In the above condition, n0 denotes the tensile resistance of each individual reinforcing bar, while k is a non-dimensional parameter, ranging from 0 to 1, which accounts for a reduced resistance under compression, due to buckling for instance.

Reinforced concrete: a homogenized strength condition

Some significant regions of the reinforced concrete structure (such as deep beams: see for instance [START_REF] Chen | Plasticity in reinforced concrete[END_REF]) may be reinforced by such uniformly distributed bars (case of stirrups or open frames). Provided that the spacing between two neighbouring reinforcements is sufficiently small as compared with the size of the reinforced zone, the latter may be replaced by a zone where the homogenized constituent material obeys a macroscopic strength condition (see [START_REF] De Buhan | A homogenization approach to the yield strength of composite materials[END_REF] for composite materials, or [START_REF] Michalowski | Failure of fiber-reinforced granular soils[END_REF] for reinforced soils and [START_REF] Averbuch | Shear Design of Reinforced Concrete Deep Beams: A Numerical Approach[END_REF] for reinforced concrete). This macroscopic strength condition, which can be derived from using the yield design homogenization method [START_REF] De Buhan | Elastic, Plastic and Yield Design of Reinforced Structures[END_REF], may be expressed as follows:

                    (3)
where 1 e is the unit vector parallel to the reinforcing bars, and 0  is defined as the tensile resistance of these bars per unit transverse area:

2 0 0 / ns   (4)
where s is the spacing between the bars, which may also be expressed as:

2 0 / s s s yy A f s f   (5)
In the above equation, It is to be noted that the validity of the above macroscopic strength criterion (3) is subject to the verification of two important conditions (see [START_REF] De Buhan | Elastic, Plastic and Yield Design of Reinforced Structures[END_REF] for more details):

 The reinforcing bars are perfectly bonded to the surrounding concrete material, which means for instance that no slippage occurs at the bar/concrete interface.

 The reinforcement volume fraction remains sufficiently small (<<1), whereas the resistance of the reinforcing material is much higher than that of the concrete material and notably its tensile strength ( s yc ff  ). 3) expressed on an oriented facet of the homogenized reinforced concrete in the particular case when k=0 (no compressive resistance of the reinforcements). According to this figure, the corresponding strength domain in the (,)-plane can be drawn simply as the convex envelope of the plain concrete intrinsic failure curve and of the curve derived from that one through a translation of vector cos e  1 0 . Such a geometric representation thus gives a clear evidence of the strength anisotropy of the homogenized reinforced concrete in exactly the same way as for fibre composite materials.

It should be pointed out that, without any reference to the limit analysis or yield design homogenization theory, some authors [START_REF] Nielsen | Limit Analysis and Concrete Plasticity[END_REF] did make use of a strength criterion quite similar to [START_REF] Bleyer | Yield surface approximation for lower and upper bound yield design of 3D composite frame structures[END_REF], that is based on an intuitive additive decomposition of the total stress in reinforced concrete zones into stress components relating to the plain concrete and the reinforcements, each one complying with independently specified strength conditions.

The "mixed modelling" approach to reinforced concrete structures: a serious limitation

Referring now to the frequently encountered situation where only a small number of differently oriented reinforcements are incorporated in the concrete structure (case of longitudinal reinforcements in deep beams for instance), the above mentioned homogenization method is no more applicable and a so-called "mixed modelling" approach should be advocated. According to this approach, the reinforcements are treated as 1D structural elements with a strength condition defined by (2) embedded in the concrete material modelled as a 3D continuum, the strength of which is specified by [START_REF] Salençon | Yield Design[END_REF]. Unfortunately, this 1D-3D mixed modelling approach comes against a serious limitation concerning the establishment of equilibrium equations for such a composite system. Indeed, the equilibrium equation at any point of the reinforcing bar may be written as:

1 1 1 d ( ) + ( ) = 0 d Nx px x (6)
where p represents the linear density of axial force exerted by the surrounding concrete material onto the reinforcing bar (Fig. 3(a)).

(a) (b)

Figure 3. Interaction forces between concrete and reinforcement in the context of 1D-3D mixed modelling Now, the impossibility of connecting such a 1D distribution p of interaction forces with the three-dimensional stress fields prevailing in the surrounding concrete material may be illustrated from the following simple reasoning. Considering a circular cylindrical "control surface" of radius  with its axis placed along the reinforcement, as shown in Fig. 3(b), the interaction force density p may be obtained from applying along this surface a longitudinal shear stress , the average value of which along the circle drawn on this surface at point x1, could be expressed as:

1 1 () () 2 px x    (7)
According to the latter equation, the shear stress which should be developed in the concrete along the control surface for applying a given value of interaction force density p increases to infinity as the radius  tends to zero, so that the stress field in the concrete material would tend to infinity along the reinforcement axis. Such a singularity could possibly be taken into account in the context of a linear elastic behavior of the concrete, but definitely not as soon as yielding and failure of the latter is concerned, since in this case the yield strength condition (1) of the concrete would be systematically violated when approaching the 1D reinforcing bar.

An extended homogenization-based model

Of course, the only fully mechanically consistent and rigorous way of circumventing the above limitation, would be to model each reinforcing bar as a three-dimensional volume body. But, on account of the small diameter of such bars along with the sharp contrast between the reinforcing steel and the surrounding concrete in terms of strength properties, this would

   p N 1 x
undoubtedly imply prohibitive computational costs, due for instance to the highly refined discretization required when employing finite element techniques.

An alternative approach for the finite element modelling of 1D steel inclusions in 3D concrete volumes has been recently proposed by [START_REF] Llau | Finite element modelling of 1D steel components in reinforced and pre-stressed concrete structures[END_REF]. Likewise, in a more explicit reference to the homogenization procedure, three dimensional fem elastoplastic analyses on reinforced concrete structural elements have been performed by [START_REF] Figueiredo | Three-dimensional finite element analysis of reinforced concrete structural elements regarded as elastoplastic multiphase media[END_REF]. Their approach, which will be adopted in this contribution, may be described as follows.

Considering one individual 1D-inclusion embedded in a 3D-concrete block, a cylindrical volume of concrete with the inclusion placed along its axis is defined, as shown in Fig. 4(a). The intuitive idea is to replace the composite cylindrical volume, thus obtained, by a homogenized cylinder, at any point of which the strength condition is defined by Eqs. ( 3) and ( 4), where s represents the side of the squared cross-section of the cylindrical volume. The advantage of such a modelling procedure, is that the characteristic size of the homogenized zone (namely s) is significantly larger than the inclusion's diameter, thus allowing for example a much easier finite element discretization of the reinforced concrete structure as a 3D-3D composite, since a refinement of the mesh around the inclusion is no more required for obtaining accurate and reliable predictions. Of course, the choice of s being arbitrary, it will be necessary to make sure that the results of the computations performed on the basis of this model, remain rather insensitive to the value of s.

NUMERICAL IMPLEMENTATION OF THE LOWER BOUND STATIC APPROACH

Statement of the yield design problem

Assuming that the reinforced concrete structure under consideration is subject to one single loading parameter Q, the ultimate or failure load value Q + is defined, in the context of the yield design theory, as the maximum value of Q for which one can exhibit any stress field  :

 statically admissible (S.A.) with Q, i.e. verifying the equilibrium equation at any point of the structure:

div ( ) ( ) 0, x F x x V      (8) s concrete (3D) inclusion (1D) s homogenized zone (3D) s s concrete (3D)
where F denotes the body force volume density (material specific weight for example), along with the continuity of the stress-vector across possible stress jump surfaces   

( ) . ( ) 0, x n x x     (9)
as well as the stress boundary conditions associated with the loading Q;

 while complying with the strength conditions assigned to the plain concrete and reinforced concrete zones of the structure, respectively:

( ( )) 0 and ( ( )) 0 ,

c c rc rc c rc F x x V F x x V V V V          (10)
where c V (respectively rc V ) represents the part of the structure occupied by the plain concrete (resp. by the homogenized reinforced concrete).

3D finite element discretization

Applying the lower bound static approach consists in considering S.A. stress fields depending either on a small number of parameters in an analytical approach, or on a large but finite number of stress variables in a numerical approach, such as the finite element method. According to the latter, the geometrical domain V occupied by the three-dimensional structure is discretized into Ne tetrahedral finite element V e , such as the one depicted in Fig. 5(a), with a linear variation of the stress field inside each element so that the stress at any point inside such an element may be classically written as:

k ek k x V x N x       (11)
where N k , k=1 to 4, are four linear interpolation functions and  k is the value of the stress tensor at the node n°k of the element. It is to be noted that there are as many stress tensors  k attached to any geometrical node of the mesh as there are tetrahedral elements sharing this node as an apex.

Figure 5. Four nodded tetrahedral finite element used in the discretization of the reinforced concrete structure Furthermore, one may come across two situations.

 The considered element is located in the unreinforced plain concrete zone V c of the structure, so that the stress state at any node of this element is defined by one single tensor which should comply with the strength condition (1).

1

 2  3  4  e V k   e V  e V  k   n k   k   e V  e V  n
 The element is located in the homogenized reinforced concrete zone V rc and, as suggested by the corresponding homogenized strength condition (3), the stress state is defined by a stress tensor and an additional scalar stress variable which must satisfy separate independent strength conditions.

It follows that a total of, either 4x6=25 or 4x7=28 stress variables, is attached to each element V e of the mesh.

Formulation of equilibrium conditions as linear constraints on the stress variables

On account of [START_REF] Nielsen | Limit Analysis and Concrete Plasticity[END_REF], the equilibrium equation ( 8) inside each element may be rewritten as:

4 1 , div ( ) grad . kk e k x V x N F           ( 12
)
where it is assumed that the body force density is constant over the element. Since the gradient of each interpolation function is constant, Eq. ( 11) represents a linear constraint on the nodal stress variables  k of each element. It is worth noting that the linear equilibrium condition [START_REF] Nielsen | Limit Analysis and Concrete Plasticity[END_REF] involves the total stress in the homogenized reinforced concrete and not the "partial" stresses  c and  r which appear in the definition (3) of the reinforced concrete strength condition.

Likewise, Eq. ( 8) expresses the continuity of the (total) stress vector across any triangular facet common to two adjacent elements (see Fig. 5(b)). It also leads to linear constraints of the form:

+ (

). 0

   kk n ( 13
)
where n is the unit normal to the triangular facet connecting two such adjacent elements + e V and  e V . Owing to the linear variation of the stress fields and to the convexity of the strength conditions, checking the jump condition (13) at the nodal points is sufficient to make sure that it is verified at any point of the discontinuity triangular facet.

It follows that all the conditions that a discretized stress field must satisfy for being statically admissible with a load value Q may be formulated in a generic matrix form as:

        fem S.A. with with T QA Q BC          (14)
where    is a column-vector which collects all the nodal stress variables associated with the mesh discretization of the structure, that is the total stresses in the plain concrete zones and the partial stresses in the homogenized reinforced parts.

Consequently, the finite element implementation of the lower bound static approach of yield design reduces to the following maximisation problem:

            equilibrium Max subject to ( ) 0 strength criteria T lb BC Q Q Q A F              (15)
where   ( Σ ) 0 F  represents the conditions expressing the different strength criteria to be satisfied. Again, due to the linear variations [START_REF] Nielsen | Limit Analysis and Concrete Plasticity[END_REF] of the considered stress fields and to the convexity of the strength conditions, the latter have only to be verified at the nodal stress points.

Formulation as a SDP problem

Unlike the equilibrium conditions which involve the total stresses only, the strength criteria in the homogenized reinforced zones concern the partial stresses as shown by [START_REF] Bleyer | Yield surface approximation for lower and upper bound yield design of 3D composite frame structures[END_REF]. While the condition relating to the reinforcement writes in the form of a simple linear constraints ( 0 0 r -k    ), the strength condition of the plain concrete defined by (1) involves the maximal and minimal principal stress components. The latter thus needs a specific treatment so that the optimization problem (15) may be treated as a Semi-definite programming (SDP) optimization problem [START_REF] Martin | Finite-Element Limit Analysis of Mohr-Coulomb Materials in 3D Using Semidefinite Programming[END_REF] as briefly explained below.

Semi-definite Programming (SDP) allows to formulate optimization problems in terms of constraints on eigenvalues of symmetric matrices. It therefore provides a suitable framework for the tension cut-off Mohr-Coulomb criterion (1) which involves the maximal and minimal principal stress components (eigenvalues). Thus, the three-dimensional Mohr-Coulomb criterion can be enforced by applying the two following linear matrix inequalities (LMI):

1 0 and 1 0 Mm tt   1 ( 16
)
in conjunction with the equality constraint:

0 p M m c K t t f    (17)
p m p c m K t K f t    (18)
The second inequality of ( 18) can be expressed as:

1 0 and 0 m t X X     (19)
which allows the stress variable to be eliminated using the relationship:

1 m tX   (20)
so that the first inequality of (18) becomes:

11 (1 ) 1 1 p m p c X K t K f   (21)
or introducing Y as a second auxiliary symmetric matrix variable, the three dimensional Mohr-Coulomb strength criterion may finally be reformulated as: (1 ) 1 1 with 0 and 0

p m p c X Y K t K f XY      (22)
which lends itself very easily to the numerical treatment by a SDP solver such as [START_REF]The Mosek optimization software[END_REF].

1 where 0 . . 0 A x A x x   
Similarly, the Rankine-type cut-off strength criterion which limits the tensile stresses in the plain concrete material:

0 1 0 M t t ff      (22)
may be recast into the following constraints:

1 0 and 0

t Z f Z     (23)
where a third auxiliary symmetric matrix variable Z has been introduced.

A FIRST ILLUSTRATIVE TEST EXAMPLE

Problem description

A specific computer code implementing the whole above described numerical procedure, has been devised for calculating numerically optimized lower bounds to the ultimate loads of three dimensional reinforced concrete structures. A first illustrative application of this code is performed on the illustrative example of a beam of length L varying between 0,5 m and 16m and rectangular cross-section (H=0.5 m, b=0.2 m), subject to a uniform surface loading q applied onto the top of the beam (Fig. 6). The left end (X=0) of the beam is perfectly clamped (velocity vector equal to zero: U=0), while the boundary conditions at the right end (X=L) are: 0,

x xx y z T U U     (24)
which, in the framework of a 1D model of the beam, corresponds to a simple support free to move horizontally along the X-axis and rotate about the Y-axis (axial force N and bending moment M are set equal to zero). keeping in mind that, referring to a tension cut-off Mohr-Coulomb condition, the value internal friction angle  is taken equal to 37°.

The beam is reinforced by two longitudinal rebars of diameter equal to 2cm, made of a steel with a uniaxial strength equal to s y f =400 MPa. The bars are placed at the bottom part of the beam cross section as shown in Fig. 5. Two methods will now be employed to evaluate the ultimate load q + of this simple structure.

Modelling the structure as a 1D beam

The structure is first schematized as a 1D beam subjected to a uniform loading of linear density qb, so that the statically admissible distribution of axial force and bending moment is of the form (Fig. 7):

2 0, ( )= ( ) ( ) 2 qb N M X R L X L X     ( 26
)
where R is the unknown reaction at the right hand simply supported end (X=L). It may be classically shown that the exact limit load of this structure is obtained when the corresponding bending moment parabolic distribution is such that (see Fig. 7):

  0 0 ( 0)= , Max ( ),0 M X M M X X L M       ( 26
)
where 0 M  (respectively 0 M  ) is the strength of the beam under pure (that is for N=0) positive (resp. negative) bending. This leads to the following expression for limit load:

1D 0 0 0 0 0 2 2 2 2 ( ) q M M M M M bL               (27)
The actual values of 0 M  may be obtained from the interaction diagram of the reinforced concrete beam section, the geometrical and strength characteristics of which are shown in Fig. 8. More precisely, the interaction domain c G of the plain concrete section being defined as:

R X L  0 X  2 ( )= ( ) ( ) 2 qb M X R L X L X    0 M  0 M  2 ( )( ) ( , ) 2 ( )
for

c ct tc c c t t H N N N N N M G M NN bHf N N N bHf            (28)
the reinforced section interaction domain rc G is defined as (see [START_REF] Averbuch | A yield design-based approach to reinforced concrete structures[END_REF] and [START_REF] Pham | Interaction diagrams of reinforced concrete sections in fire: a yield design approach[END_REF] for more details concerning the yield design-based procedure used for determining such interaction domains):

  2 0 0 0 (1, ); 2 2 with ( / 4) rc c s y G G kn n n f           (29)
Figure 8. Interaction domains of plain concrete and reinforced concrete sections in the (N, M)plane.

Both domains have been represented in Fig. 8 for the set of selected values recalled in the same figure. The values of the resistance of the reinforced concrete section under pure bending correspond to the intersecting points of the boundary line of rc G with the M-axis:

    0 0 Max ; ( =0, ) 120 kNm Min ; ( =0, ) 19,5 kNm rc rc M M N M G M M N M G          (30)
Hence the final expression of the limit load as a function of the beam length L:

1D 2 5.18 (MPa) q L   (31)

3D-modelling of the structure:

The structure is now treated as a three dimensional parallelepipedic volume. According to the method described in section 2.4, each bar with its surrounding volume of concrete material is replaced by a homogenized material obeying the macroscopic strength condition (3) with: )

M 0 19.5 kNm M    0 120 kNm M   c G 0.2 m b  0.5 m H  0.2 m   0.5 MPa 40 MPa t c f f   0.02 m 400 MPa s y f    rc G
where s 2 is the cross section area of the homogenized volume.

First, several numerical analyses using the dedicated SDP optimization procedure described earlier are performed for the L=4m long reinforced concrete beam with different homogenized volume cross sections s 2 . The purpose of this study is to validate the proposed method, and notably the homogenization procedure. The results will then be compared to the 1D beam calculation developed in section 4.3.

As previously explained in section 2.4, the homogenized method consists in replacing each individual rebar by a larger surrounding volume with adapted macroscopic strength condition, thereby allowing to perform numerical analyses without the computational cost induced by a much refined meshing of each rebar. Thus, both bottom longitudinal rebars being replaced by such homogenized volumes, three cases with different homogenized volume cross sections, namely s 2 =(b/2) 2 =0.1x0.1 m 2 , s 2 =0.08x0.08 m 2 and s 2 =0.06x0.06 m 2 (configuration of Fig. 6) have been investigated. The results have been reported in Fig. 9 which shows the variations of the lower bound estimate for the ultimate load bearing capacity of the reinforced concrete beam ( 3D q  ) as a function of the mesh size (number of elements), for each of the three cases. The result of the 1Dbeam calculation performed in section 4.2 is also plotted in the same figure in the form of a horizontal straight line.

The following comments can be made.

 For each of the three configurations, several finite element analyses have been performed

where the number of finite elements has been increased from a few hundreds to about q  1D 0.323 MPa q   30 000. Figure 9 clearly shows that the corresponding lower bound estimate is also increasing with a stabilization as soon as the mesh size exceeds 10 000 elements.

 The results presented here clearly assess the validity of the proposed homogenization method for treating the case of a reinforcement by few individual inclusions. Indeed, the results of the evaluation of the ultimate load bearing capacity for the three cases are almost insensitive to the size of the proposed homogenized volume cross sections.

 Finally, even if it should be kept in mind that the obtained results are lower bound estimates for the exact ultimate bearing capacity of the beam, the strengthening effect due to the presence of the rebars in the concrete beam is strikingly apparent, since the evaluation of the ultimate failure load, equal to 40kPa for the plain concrete beam of length L=4m, is increased to more than 300kPa when the reinforcement by two longitudinal bars is taken into account. 3 GHz CORE in about 373 seconds (six minutes) for the most refined mesh (23352 tetrahedrae). This underlines the decisive advantage of the proposed homogenization method over a direct approach where the inclusions should have been very finely discretized in and around the inclusions, which may lead to an oversized numerical problem. Moreover, it is worth pointing out that a little less performing lower bound estimate for the ultimate load bearing capacity of the structure may be obtained (307kPa vs 315kPa) with a coarser mesh (composed of 12392 elements), leading to a computational time of 171 seconds. q  and 1D q  for different beam lengths

L=16 m L=8 m L=4 m L=2 m L=1 m 1D q  (
In order to compare the results derived from the 1D and 3D modellings of the structure, the effect of the length of the beam on its ultimate bearing capacity is now examined, all the other characteristics being kept unchanged. Several numerical analyses have been run to this end for different beam lengths (with s 2 =0.01 m 2 ). The corresponding results are presented in Table 1. It appears that both evaluations are in excellent agreement for 2m L 

, the 3D evaluation being slightly lower than the 1D calculation, which seems to be consistent with the fact that the 3D approach is a lower bound estimate.

On the other hand, as could be expected, both estimates are diverging for shorter beams, the 3D estimate being for instance 22.8% lower than the 1D calculation for L=1m. Of course, this discrepancy should be attributed to the fact that the 1D modelling is only applicable to sufficiently slender structures and not to "short" or "deep" beams where a limited shear resistance of the beam should be taken into account, which is implicitly made in the 3D calculation.

A PRACTICAL CASE STUDY: FAILURE DESIGN OF A BRIDGE PIER CAP

In order to assess the performance of the yield design numerical tool in situations where truly massive three dimensional structures are concerned, the following representative design case is now examined: a 3x3x1.5 m 3 parallelepiped concrete block is considered as a simplified model of bridge pier cap. The finite element lower bound static approach is performed on this structure subject to four vertical loads representing the action of the overlying bridge deck, as shown in Fig. 11. These loadings are applied in the form of a uniform pressure applied on top of small rigid square pads of 0.7x 0.7m 2 . The interaction with the underlying bridge pier is modelled by imposing a rigid connection on a 1.5x0.7 m 2 rectangular area placed at the centre of the bottom surface. The whole structure being discretized into 41904 tetrahedral finite elements, an optimal lower bound estimate for its ultimate load bearing capacity has been obtained using the SDP maximization procedure. Fig. 12 represents the distribution of the principal compressive stresses prevailing in the plain concrete material, while the principal tensile stresses mobilized in the (homogenized) reinforced zones are shown in Fig. 13. Both distributions have been superimposed in Fig. 14 which displays a perspective and a front views. Calculations were performed on the same computational server in approximately 1782 seconds (half an hour). The thus obtained lower bound estimate for the ultimate bearing capacity of the reinforced concrete structure is equal to 4.69 MPa applied on each of the four loading pads. By way of comparison, the lower bound evaluation of the ultimate bearing capacity of the same nonreinforced concrete structure is equal to 3.18MPa. This means that the presence of the reinforcements increases the global resistance of the pier cap by as much as 47%.

The proposed model of three-dimensional reinforced concrete structures advocated in this contribution, as well as the feasibility of the related numerical approach in the context of the finite element method, have thus been successfully tested here on a representative example of massive reinforced concrete structure. The front view of Fig. 14 in particular, gives a clear intuition of the optimized stress field equilibrating the applied loading, exhibiting compressive stresses (struts) in the concrete material and tensile stresses in the homogenized reinforced zones (ties).

CONCLUSION

A specifically dedicated finite element computer code has been set up aimed at producing rigorous lower bound (i.e. conservative) estimates for the ultimate load bearing capacity of threedimensional reinforced concrete structures in the context of the yield design approach. It relies upon two recent decisive breakthroughs: the numerical formulation of the corresponding optimization problem using efficient SDP optimization techniques, on the one hand, the adoption of a homogenization-inspired model for describing the mechanical behaviour of individual reinforcing inclusions embedded in a surrounding three-dimensional concrete matrix, on the other hand. The procedure may be further extended on two important points.

 The development of the same kind of numerical method and related computer tool in the framework of the yield design kinematic approach, which will provide upper bound estimates. Comparing the latter with the already determined lower bound estimates, will considerably help improve the accuracy and reliability of the design procedure.

 The adoption of a multiphase model, which may be perceived as an extension of the homogenization method [START_REF] De Buhan | Elastic, Plastic and Yield Design of Reinforced Structures[END_REF], making it possible to take a specific interaction failure condition between the reinforcements and the concrete material, into account.

Figure 1 .

 1 Figure 1. Geometrical representation of the tension-cut off Mohr-Coulomb criterion in the Mohr-plane In the above condition, and Mm  represent the major and minor principal stresses, respectively (tensile stresses are counted positive throughout the text), and tc ff denote the uniaxial tensile and compressive resistances and (1 sin ) / (1 sin ) p K

fFig

  Fig. 2(a) where 2

Figure 2 .Figure 2

 22 Figure 2. (a) Representative volume of reinforced concrete; (b) macroscopic strength condition relative to an oriented facet (case k=0) Figure 2(b) illustrates the macroscopic strength condition (3) expressed on an oriented facet of the homogenized reinforced concrete in the particular case when k=0 (no compressive resistance of the reinforcements). According to this figure, the corresponding strength domain in the (,)-plane can be drawn simply as the convex envelope of the plain concrete intrinsic failure curve and of the curve derived from that one through a translation of vector cos e

Figure 4 .

 4 Figure 4. Construction of a homogenized reinforced zone around an individual inclusion

11

 11

Figure 6 .

 6 Figure 6. Reinforced concrete beam of length under uniform loading (case L=4m).

Figure 7 .

 7 Figure 7. Statically admissible bending moment distribution in the structure modelled as a 1Dbeam

Figure 9 .

 9 Figure 9. Lower bound estimate of the beam ultimate bearing capacity as a function of the mesh size, for three different homogenized volume cross sections (L=4m)

Figure 10 .Figure 9

 109 Figure 10. Longitudinal views of the optimized stress field in the plain concrete (top picture), reinforced zones (intermediate picture) and entire structure (bottom picture) for L=4m

Figure 11 .

 11 Figure 11. Reinforced concrete pier cap subject to bridge deck loading

Figure 12 .Figure 13 .Figure 14 .

 121314 Figure 12. Perspective view of the optimized stress field in the concrete (compressions)

Table 1 .

 1 Comparison between 3D

	MPa) 0.0202	0.081	0.323	1.295	5.18
	3D q  (MPa) 0.0195	0.0794	0.3155	1.260	4.22
		+3.6%	+2%	+2.3%	+2.8%	+22.8%


MULTIVARIATE FUSS-CATALAN NUMBERS

. These integers are known to satisfy simple recurrence, which may be visualised in a "Catalan triangle", a lower-triangular two-dimensional array. It is surprising that the extension of this construction to 3 dimensions generates integers B 3 (n, k, l) that give a 2-parameter distribution of C 3 (n) = 1 2n+1 3n n , which may be called order-3 Fuss-Catalan numbers, and enumerate ternary trees. The aim of this paper is a study of these integers B 3 (n, k, l). We obtain an explicit formula and a description in terms of trees and paths. Finally, we extend our construction to p-dimensional arrays, and in this case we obtain a (p -1)-parameter distribution of C p (n) = 1 (p-1)n+1 pn n , the number of p-ary trees.

Catalan triangle, binary trees, and Dyck paths

We recall in this section well-known results about Catalan numbers and ballot numbers.

The Catalan numbers

C(n) = 1 n + 1
2n n are integers that appear in many combinatorial problems. These numbers first appeared in Euler's work as the number of triangulations of a polygon by mean of non-intersecting diagonals. Stanley [START_REF] Stanley | Enumerative Combinatorics[END_REF][START_REF] Stanley | Catalan Addendum[END_REF] maintains a dynamic list of exercises related to Catalan numbers, including (at this date) 127 combinatorial interpretations.

Closely related to Catalan numbers are ballot numbers. Their name is due to the fact that they are the solution of the so-called ballot problem: we consider an election between two candidates A and B, which respectively receive a > b votes. The question is: what is the probability that during the counting of votes, A stays ahead of B? The answer will be given below, and we refer to [START_REF] Bertrand | Calcul des probabilités. Solution d'un problème[END_REF] for Bertrand's first solution, and to [START_REF] André | Solution directe du problème résolu par M. Bertrand[END_REF] for André's beautiful solution using the "reflection principle".

Since our goal here is different, we shall neither define ballot numbers by the previous statement, nor by their explicit formula, but we introduce integers B(n, k) defined for a positive integer n and a nonnegative integer k by the following conditions:

• B(1, 0) = 1; • ∀n > 1 and 0 ≤ k < n, B(n, k) = k i=0 B(n -1, i); • ∀k ≥ n, B(n, k) = 0.
Date: November 6, 2007.

1

Observe that the recursive formula in the second condition is equivalent to:

(1.1) B(n, k) = B(n -1, k) + B(n, k -1).
We shall present the B(n, k)'s by the following triangular representation (zero entries are omitted) where moving down increases n and moving right increases k. The crucial observation is that computing the horizontal sums of these integers give : 1, 2, 5, 14, 42, 132. We recognize the first terms of the Catalan series, and this intuition will be settled in Proposition 1.1, after introducing combinatorial objects.

A binary tree is a tree in which every internal node has exactly 2 sons. The number of binary trees with n internal nodes is given by the n-th Catalan number. The nodes of the following tree are labelled to explain a bijection described in the next paragraph: internal nodes are labelled by letters and external nodes by numbers. A Dyck path is a path consisting of steps (1, 1) and (1, -1), starting from (0, 0), ending at (2n, 0), and remaining in the half-plane y ≥ 0 (we shall sometimes say "remaining above the horizontal axis" in the same sense). The number of Dyck paths of length 2n is also given by the n-th catalan number. More precisely, the depth-first search of the tree gives a bijection between binary trees and Dyck paths: we associate to each external node (except the left-most one) a (1, 1) step and to each internal node a (1, -1) step by searching recursively the left son, then the right son, then the root. As an example, we show below the Dyck path corresponding to the binary tree given above. The labels on steps correspond to those on the nodes of the tree. An important parameter in our study will be the length of the right-most sequence of (1, -1) of the path. This parameter equals 2 in our example. Observe that under the correspondence between paths and trees, this parameter corresponds to the length of the right-most string of right sons in the tree. We shall use the expressions last down sequence and last right string, for these parts of the path and of the tree. Now we come to the announced result. It is well-known and simple, but is the starting point of our work. Proposition 1.1. For n a positive integer, we have the following equality:

n-1 k=0 B(n, k) = C(n) = 1 n + 1 2n n .
Proof. Let us denote by C n,k the set of Dyck paths of length 2n with a last down sequence of length equal to nk.

We shall prove that B(n, k) is the cardinality of C n,k .

The proof is done recursively on n.

If n = 1, this is trivial. If n > 1, let us suppose that B(n -1, k) is the cardinality of C n-1,k for 0 ≤ k < n -1.
Let us consider an element of C n,k . If we erase the last step (1, 1) and the following step (1, -1), we obtain a Dyck path of length 2(n -1), with a last decreasing sequence of length n -1 -l with l ≤ k. If we keep track of the integer k, we obtain a bijection between C n,k and ∪ l≤k C n-1,l . We mention that this process is very similar to the ECO method [START_REF] Barcucci | ECO: a methodology for the enumeration combinatorial objects[END_REF]. This is a combinatorial proof of Proposition 1.1.

Remark 1.2. The integers B(n, k) are known as ballot numbers and are given by the explicit formula:

(1.2) B(a, b) = a -b a + b a + b a .
This expression can be obtained shortly by checking the recurrence (1.1). We can alternatively use the reflection principle (see [START_REF] Hilton | Catalan Numbers, their Generalizations, and their Uses[END_REF] for a clear presentation), or the cycle lemma (cf. [START_REF] Dershowitz | The Cycle Lemma and Some Applications[END_REF]), which will be used in the next sections to obtain a formula in the general case. The expression (1.2) constitutes a solution to the ballot problem. For this, we use a classical interpretation in terms of paths: we represent a vote for A by an up step, and a vote for B by a down step. The total number of countings of votes, or of paths from (0, 0) to (a + b, ab), is given by the binomial a+b a . The countings such that A stays ahead of B correspond to paths remaining above the horizontal axis. Their number is given by B(a, b). This implies that the probability asked for at the beginning of this section is a-b a+b . Of course , we could have used expression (1.2) to prove Proposition 1.1 by a simple computation, but our proof explains more about the combinatorial objects and can be adapted to ternary trees in the next section.

It should be mentionned here that our study of multivariate Fuss-Catalan has nothing to do with the many-candidate ballot problem, as considered for example in [START_REF] Zeilberger | André's reflection proof generalized to the many-candidate ballot problem[END_REF] or [START_REF] Nathanson | Ballot numbers, alternating products and the Erdös-Heilbronn conjecture[END_REF]. In particular, the multivariate ballot numbers considered in these papers do not sum to the Fuss-Catalan numbers C p (n) = the numbers studied in the present article do not give any answer to the generalized ballot problem. Remark 1.3. Our Catalan array presents similarities with Riordan arrays, but it is not a Riordan array. It may be useful to explicate this point. We recall (cf. [START_REF] Shapiro | The Riordan Group[END_REF]) that a Riordan array M = (m i,j ) ∈ C N×N is defined with respect to 2 generating functions

g(x) = g n x n and f (x) = f n x n
and is such that

M j (x) = n≥0 m n,j x n = g(x)f (x) j .
We easily observe that a Riordan array with the first two columns M 0 (x) and M 1 (x) of our Catalan array is relative to g(x) = 1 1-x and f (x) = x 1-x , which gives the Pascal triangle.

In fact, the Riordan array relative to g(x) = C(x) = C(n)x n and f (x) = x C(x) gives the ballot numbers, but requires knowledge of the Catalan numbers.

2. Fuss-Catalan tetrahedron and ternary trees 2.1. Definitions. This section, which is the heart of this work, is the study of a 3-dimensional analogue of the Catalan triangle of the previous section. That is we consider exactly the same recurrence, and let the array grow, not in 2, but in 3 dimensions. More precisely, we introduce the sequence B 3 (n, k, l) indexed by a positive integer n and nonnegative integers k and l, and defined recursively by:

• B 3 (1, 0, 0) = 1; • ∀n > 1, k + l < n, B 3 (n, k, l) = 0≤i≤k,0≤j≤l B 3 (n -1, i, j); • ∀k + l ≥ n, B 3 (n, k, l) = 0.
Observe that the recursive formula in the second condition is equivalent to:

(2.1) B 3 (n, k, l) = B 3 (n -1, k, l) + B 3 (n, k -1, l) + B 3 (n, k, l -1) -B 3 (n, k -1, l -1)
and this expression can be used to make some computations lighter, but the presentation above explains more about the generalization of the definition of the ballot numbers B(n, k).

Because of the planar structure of the sheet of paper, we are forced to present the tetrahedron of B 3 (n, k, l)'s by its sections with a given n.

n = 1 -→ 1 n = 2 -→ 1 1 1 n = 3 -→   1 2 2 2 3 2   n = 4 -→     1
      It is clear that B 3 (n, k, 0) = B 3 (n, 0, k) = B(n, k).
The reader may easily check that when we compute k,l B 3 (n, k, l), we obtain: 1, 3, 12, 55, 273. These integers are the first terms of the following sequence (cf. [START_REF] Sloane | A Handbook of integer sequences[END_REF]):

C 3 (n) = 1 2n + 1 3n n .
This fact will be proven in Proposition 2.1.

2.2. Combinatorial interpretation. Fuss1 -Catalan numbers (cf. [START_REF] Fomin | Generalized cluster complexes and Coxeter combinatorics[END_REF][START_REF] Hilton | Catalan Numbers, their Generalizations, and their Uses[END_REF]) are given by the formula

(2.2) C p (n) = 1 (p -1)n + 1 pn n ,
and C 3 (n) appear as order-3 Fuss-Catalan numbers. The integers C 3 (n) are known [START_REF] Sloane | A Handbook of integer sequences[END_REF] to count ternary trees, ie. trees in which every internal node has exactly 3 sons.

Ternary trees are in bijection with 2-Dyck paths, which are defined as paths from (0, 0) to (3n, 0) with steps (1, 1) and (1, -2), and remaining above the line y = 0. The bijection between these objects is the same as in the case of binary trees, ie. a depth-first search, with the difference that here an internal node is translated into a (1, -2) step. To illustrate this bijection, we give the path corresponding to the previous example of ternary tree:

We shall consider these paths with respect to the position of their down steps. The height of a down step is defined as the height of its end-point. Let D n,k,l denote the set of 2-Dyck paths of length 3n, with k down steps at even height and l down steps at odd height, excluding the last seqence of down steps. By definition, the last sequence of down steps is of length nkl. Proposition 2.1. We have

∀n > 0, k,l B 3 (n, k, l) = C 3 (n) = 1 2n + 1 3n n .
Moreover, B 3 (n, k, l) is the cardinality of D n,k,l .

Proof. Let k and l be fixed. Let us consider an element of D n,k,l . If we cut this path after its (2n -2)-th up step, and complete with down steps, we obtain a 2-Dyck path of length 3(n -1) (see figure below). It is clear that this path is an element of D n,i,j for some i ≤ k and j ≤ l. We can furthermore reconstruct the original path from the truncated one, if we know k and l. We only have to delete the last sequence of down steps (here the dashed line), to draw ki down steps, one up step, lj down steps, one up step, and to complete with down steps. This gives a bijection from D n,k,l to ∪ 0≤i≤k,0≤j≤l D n-1,i,j , which implies Proposition 2.1.

Remark 2.2. It is interesting to translate the bi-statistic introduced on 2-Dyck paths to the case of ternary trees. As previously, we consider the depth-first search of the tree, and shall not consider the last right string. We define T n,k,l as the set of ternary trees with n internal nodes, k of them being encountered in the search after an even number of leaves and l after and odd number of leaves. By the bijection between trees and paths, and Proposition 2.1, we have that the cardinality of T n,k,l is B 3 (n, k, l). Remark 2.3. It is clear from the definition that:

B 3 (n, k, l) = B 3 (n, l, k).
But this fact is not obvious when considering trees or paths, since the statistics defined are not clearly symmetric. To explain this, we can introduce an involution on the set of ternary trees which sends an element of T n,k,l to T n,l,k . To do this, we can exchange for each node of the last right string its left and its middle son, as in the following picture. Since the number of leaves of a ternary tree is odd, every "even" node becomes an odd one, and conversely.

2.3. Explicit formula. Now a natural question is to obtain explicit formulas for the

B 3 (n, k, l
). The answer is given by the following proposition.

Proposition 2.2. The integers B 3 (n, k, l) are given by

(2.3) B 3 (n, k, l) = n + k k n + l -1 l n -k -l n + k
Proof. We use a combinatorial method to enumerate D n,k,l . The method is a variation of the cycle lemma [START_REF] Dershowitz | The Cycle Lemma and Some Applications[END_REF] (called "penetrating analysis" in [START_REF] Mohanty | Lattice paths counting and application[END_REF]).

If we forget the condition of "positivity" (ie. the path remains above the line y = 0), and cut the last down sequence, a path consists in:

• at even height: n up steps, and k down steps;

• at odd height: n up steps and l down steps.

An important remark is to remember that an element of D n,k,l has an up step just before the last sequence of down steps! If we suppose that all these steps are distinguished, we obtain:

• (n+k)!
n!k! choices for even places;

• (n-1+l)!
(n-1)!l! choices for odd places (we cannot put any odd down step after the last odd step). Now we group the paths which are "even permutations" of a given path P . By even permutations, we mean cycle permutations which preserve the parity of the height of the steps. We want to prove that the proportion of elements of D n,k,l in any even orbit (i.e. in any orbit under even permutations) is given by n-k-l n+k . We suppose first that the path P is acyclic (as a word): P cannot be written as P = U p with U a word in the two letters (1, 1) and (1, -2). It is clear that such a path gives n + k different even permutations. Now we have to keep only those which give elements of D n,k,l . To do this we consider the concatenation of P and P ′ , which is a duplicate of P .

The cyclic permutations of P (not necessarily even) are the subpaths of P + P ′ of horizontal length 2n + k + l. The number of such paths that remain above the horizontal axis, and end with an up step, is the number of (up) steps of P in the light of an horizontal light source coming from the right. The only transformation is to put the illuminated up step at the end of the path. The number of illuminated up steps is 2n -2k -2l, since every down step puts two up steps in the shadow. Among these 2n -2k -2l permutations, only half are even (observe that the set of heights of the illuminated steps is an interval). Thus nkl paths among the n + k elements of the orbit are in D n,k,l . Now we observe that if P is p-cyclic, then its orbit has p times less elements, and we obtain p times fewer different paths, whence the proportion of elements of elements of D n,k,l in this orbit is:

(n -k -l)/p (n + k)/p = n -k -l n + k .
Finally, we obtain that the cardinality of D n,k,l is

(n + k)! n!k! (n -1 + l)! (n -1)!l! n -k -l n + k
which was to be proved.

Remark 2.5. The equation (2.3) is of course symmetric in k and l:

n + k k n + l -1 l n -k -l n + k = n + k -1 k n + l -1 l n -k -l n .
Remark 2.6. I made the choice to present a combinatorial proof of Proposition 2.2. The interest is to show how these formulas are obtained, and to allow easy generalizations (cf. the next section). It is also possible to check directly the recurrence (2.1).

2.4. Generating function. Let F denote the following generating series:

(2.4)

F (t, x, y) = 1 + 0≤k+l<n B 3 (n, k, l)t n x k y l .
In this expression, the term "1" corresponds to the empty 2-Dyck path. Thus F is the generating series of 2-Dyck paths with respect to their length (variable t), their number of down steps at even height -excluding the last down sequence-(variable x), and their number of down steps at odd height (variable y). We also introduce

(2.5) G(t, x, y) = 1 + 0≤k+l<n B 3 (n, k, l)t n x n-l y l ,
ie. G is the generating function of 2-Dyck paths with respect to their length, to the number of down steps at even height -including the last down sequence-and to the number of down steps at odd height.

To obtain equations for F and G, we decompose a non-empty 2-Dyck path by looking at two points: α, defined as the last return to the axis (except the final point (3n, 0)), and β defined as the last point at height 1 after α. This gives the following decomposition of a 2-Dyck path where G(t, x, y) is a solution of the algebraic equation tx 2 G 3 + (yx)G 2 + (x -2y)G + y = 0.

P = P 1 (
An alternate approach to the generating function is to use formula 2.3 to obtain what MacMahon called a "redundant generating function " (cf. [START_REF] Gessel | Super Ballot Numbers[END_REF]), since it contains terms other than those which are combinatorially significant. The integers C p (n) are order-p Fuss-Catalan numbers and enumerate p-ary trees, or alternatively p-Dyck paths (the down steps are (1, -p)). In this general case, the recursive definition of B p (n, k 1 , k 2 , . . . , k p-1 ) gives rise to p -1 statistics on trees and paths analogous to those defined in section 3. Remark 3.2. By the same method as in the previous section, it is possible to obtain an explicit formula for these multivariate Fuss-Catalan numbers:

B p (n, k 1 , k 2 , . . . , k p-1 ) = p-1 i=1 n + k i -1 k i n -p-1 i=1 k i n .
Comment. The numbers B 3 (n, k, l) first arose in a question of algebraic combinatorics (cf. [START_REF]Ideals and quotients of B-quasisymmetric functions[END_REF]). Let I n be the ideal generated by B-quasisymmetric polynomials in the 2n variables x 1 , . . . , x n and y 1 , . . . , y n (cf. [START_REF] Baumann | A Solomon theory for the wreath product G ≀ S n[END_REF]) without constant term. We denote by Q n the quotient Q[x 1 , . . . , x n , y 1 , . . . , y n ]/I n and by Q k,l n the bihomogeneous component of Q n of degree k in x 1 , . . . , x n and degree l in y 1 , . . . , y n . It is proven in [START_REF]Ideals and quotients of B-quasisymmetric functions[END_REF] that:

dim Q k,l n = B 3 (n, k, l) = n + k -1 k n + l -1 l n -k -l n .

  J.-C. AVAL Abstract. Catalan numbers C(n) = 1 n+1 2n n enumerate binary trees and Dyck paths. The distribution of paths with respect to their number k of factors is given by ballot numbers B(n, k) = n-k n+k n+k n

Proposition 3. 1 .

 1 k 1 ,...,k p-1 B p (n, k 1 , . . . , k p-1 ) = C p (n) = 1 (p -1)n + 1 pn n

  up) P 2 (up) P 3 (down), with P 1 , P 2 , P 3 any 2-Dyck path (maybe empty).By observing that the up steps after α and β change the parity of the height, this gives the two following equations : Proposition 2.3. The generating function F of the B 3 's is given by:

	α	β
	(2.6)
	F (t, x, y) =	1 1 -tG(t, x, y)G(t, y, x)

F (t, x, y) = 1 + G(t, x, y) × G(t, y, x) × t.F (t, x, y) and in the same way (2.7) G(t, x, y) = 1 + G(t, x, y) × G(t, y, x) × t.G(t, x, y).x. By permuting the variables x and y in (2.7), we obtain (2.8) G(t, y, x) = 1 + G(t, y, x) × G(t, x, y) × t.G(t, y, x).y and we can eliminate G(t, y, x) from (2.7) and (2.8) to obtain the following result.

(p-1)n+1 pn n . Conversely,

Nikolai Fuss (Basel, 1755 -St Petersburg, 1826) helped Euler prepare over

articles for publication over a period on about seven years in which he acted as Euler's assistant, and was from 1800 to 1826 permanent secretary to the St Petersburg Academy.

Acknowledgement. The author is very grateful to referees (and in particular to the anonymous "Referee 3") for valuable remarks and corrections.

To do this we extend the recursive definition of B 3 (n, k, l) as follows: we define B ′ 3 (n, k, l) for integers n > 0, and k, l ≥ 0 by: (2.9)

Of course when k + l > n, the integer B ′ 3 (n, k, l) is negative. As an example, here is the "section" of the array of

The equation (2.9) is equivalent to the following recursive definition:

The interest of this presentation is to give a simple (rational!) generating series. Indeed, it is quite simple to deduce from the recursive definition of B ′ 3 (n, k, l) that:

(2.10)

This formula then encodes the B 3 (n, k, l) since ∀k + l < n, B 3 (n, k, l) = B ′ 3 (n, k, l).

Fuss-Catalan p-simplex and p-ary trees

The aim of this final section is to present an extension of the results of Section 2 to p-dimensional recursive sequences. In the same spirit, we define the sequence B p (n, k 1 , k 2 , . . . , k p-1 ) by the recurrence:

• B p (1, 0, 0, . . . , 0) = 1;

. . , k p-1 ) = 0. Every result of Section 2 extends to general p. We shall only give the main results, since the proofs are straightforward generalizations of the proofs in the previous section.