Mikhail Khovanov
email: khovanov@math.columbia.edu

Radmila Sazdanovic
email: rsazdanovic@math.ncsu.edu.

A Categorification of One-Variable Polynomials

Keywords: categorification, diagrammatic algebra, Grothendieck ring, Bernstein-Gelfand-Gelfand reciprocity, crossing less matchings

de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Inspired by the general idea of categorification, introduced by L. Crane and I. Frenkel, we construct a categorification of the polynomial ring Z[x], more precisely of polynomials (x -1) n that can be generalized to orthogonal one-variable polynomials, including Chebyshev polynomials of the second kind and the Hermite polynomials. In this paper, we interpret the ring Z[x] as the Grothendieck ring of a suitable additive monoidal category A-pmod of (finitely generated) projective modules over an idempotented geometrically defined ring A. Monomials x n become indecomposable projective modules P n , while polynomials (x-1) m turn into so-called standard modules M m . Ring A has one more distinguished family of modules -simple modules L n . A remarkable feature of these three collections of modules is the Bernstein-Gelfand-Gelfand (or BGG) reciprocity property [START_REF] Bernstein | Category of g-modules[END_REF]. Projective modules P n have a filtration by standard modules M m , for m ≤ n, and the multiplicities satisfy the relation:

[P n : M m ] = [M m : L n ].
Original examples of algebras and modules with this property are due to J. Bernstein, I. Gelfand, and S. Gelfand and come up in infinite-dimensional representation theory of simple Lie algebras. The algebra A has a purely topological-geometric definition, yet satisfies the BGG property. Moreover, the standard modules M n have a clear geometric interpretation. An additional sophistication appears due to nonunitality of algebras A. Instead, they contain an infinite collection of idempotents 1 n , n ≥ 0, serving as a substitute for the unit element 1. Projectives P n and standard modules M n are infinite-dimensional, and the multiplicity [M m : L n ] should be understood in the generalized sense, as dim(1 n M m ). We hope that our approach will lead to geometric interpretation of the BGG reciprocity in many other cases, including the ones considered by J. Bernstein, I. Gelfand, and S. Gelfand. In the sequel we will generalize this constructions to categorify the Hermite and Chebyshev polynomials. form k-algebra A as a vector space with the basis B and the multiplication generated by the concatenation of elements of B. The product is zero if the resulting diagram has an arc which is not attached to the lines x = 0 or x = 1, called floating arc, Fig. 2. Also, if y ∈ m B n , z ∈ k B l and n = k, then the concatenation is not defined and we set yz = 0. Thus, for any two elements y, z of B the product yz is either 0 or an element of B.

The composition induces an associative k-algebra structure on A. For each n there exists a unique diagram in n B n without sarcs. We denote this diagram and its image in A by 1 n . These elements are minimal idempotents in A.

We have A = n,m≥0 n A m , where n A m is the vector space with the basis n B m . A is a non-unital associative algebra with a system of mutually orthogonal idempotents {1 n } n≥0 . We consider left modules M over A with the property

M = ⊕ n≥0 1 n M .
This property is analogous to the unitality condition 1M = M for modules over a unital algebra. For a module M , we write M m for the direct sum of m copies of M . Let P n = A1 n be the projective A-module P n with a basis consisting of all diagrams in B n . Define M n , called the standard module, as the quotient of P n by the submodule spanned by all diagrams which have right sarcs. Therefore, a basis of M n is the set of diagrams in B n with no right sarcs. In particular, if A left A-module M is called finitely-generated if for some finite subset

1 m M n = 0 then m ≥ n.
{m 1 , m 2 , . . . , m k } of M we have M = Am 1 + • • • + Am k . M is finitely generated if and only if it is a quotient of N n=0
P an n for some

a n ≥ 0, N ∈ N.
Let A-mod be the category of finitely-generated left A-modules and A-pmod the category of finitelygenerated projective left A-modules.

Let L n = k1 n be the one-dimensional module over A on which any element of B other than 1 n acts by zero.

Lemma 2.1 Any simple A-module is isomorphic to L n , for some n ≥ 0.

Theorem 2.2 Any finitely-generated projective left A-module P is isomorphic to a finite direct sum of indecomposable projective modules P n ,

P ∼ = N ⊕ n=0 P an n .
The multiplicities a n ∈ Z + are invariants of P .

The projective module P n has a filtration by standard modules M m , over m ≤ n. Specifically, consider the filtration

P n = P n (≤ n) ⊃ P n (≤ n -1) ⊃ • • • ⊃ P n (≤ 0) = 0, (1)
where P n (≤ m) is spanned by the diagrams in B n of width at most m (equivalently, with at least nm right sarcs). Left multiplication by a basis vector cannot increase the width, hence P n (≤ m) is a submodule of P n . The quotient P n (≤ m)/P n (≤ m -1) has a basis of diagrams of width exactly m.

These diagrams can be partitioned into n m classes enumerated by positions of the n-m right sarcs. The quotient P n (≤ m)/P n (≤ m -1) is isomorphic to the direct sum of n m copies of the standard module M m . Consequently, we have an equality in the Grothendieck group of the additive category A-mod:

[P n ] = n m=0 n m [M m ]. (2)
Next, we prove that the non-unital algebra A is Noetherian, hence the category A-mod is abelian.

Proposition 2.3 A submodule of a finitely-generated left A-module is finitely-generated.

The involution of the set B which reflects a diagram about a vertical axis takes n B m to m B n and induces an anti-involution of A. Hence the ring A is right Noetherian as well.

Definition 2.4 Grothendieck group K 0 (A) of finitely generated projective A-modules is an abelian group generated by symbols [P ] of finitely-generated projective left A modules P , with defining relations

[P ] = [P ] + [P ] if P ∼ = P ⊕ P . Proposition 2.5 K 0 (A) is a free abelian group with basis {[P n ]} n≥0 .
Proposition 2.5 follows from Theorem 2.2.

Observe that the existence of the filtration (1) of projective modules P n by standard modules M m implies that M m has a finite projective resolution P (M m ) by P n 's, for n ≤ m. Consequently, we can view M m as an object of the category C(A-pmod) of bounded complexes of finitely-generated projective A-modules. Morphisms in this category are homomorphisms of complexes modulo zero-homotopic homomorphisms. Grothendieck groups of categories A-pmod and C(A-pmod) are canonically isomorphic:

K 0 (C(A-pmod)) ∼ = K 0 (A-pmod)
via the isomorphism taking the symbol of

Q = (. . . → P i → P i+1 → . . . ) ∈ C(A-pmod) to [Q] = i∈Z (-1) i [P i ] ∈ K 0 (A).
Hence, the equality (2) can be interpreted within K 0 (A).

The transformation matrix from the basis of the symbols [P n ] of indecomposable projective modules to the basis of symbols [M m ] of standard modules is upper-triangular, with ones on the diagonal and nonzero coefficients being the binomials n m . The entries of the inverse matrix are (-1) n+m n m . Thus we have the following equation in K 0 (A):

[M n ] = n m=0 (-1) n+m n m [P m ]. (3)
We identify the projective Grothendieck group K 0 (A) with Z[x] by sending the symbols of projective modules [P n ] to monomials x n , and define an inner product on the basis {x n } n≥0 by

(x n , x m ) = dim Hom(P n , P m ) = | n B m | = n + m m (4)
This identification can be justified by introducing a monoidal structure on A-pmod under which P n ⊗ P m ∼ = P n+m , [START_REF] Khovanov | Categorification of the polynomial ring[END_REF].

Under this identification, equation (3) gives

[M n ] = m≤n (-1) n+m n m x m = (x -1) n , (5)
so the symbols of standard modules [M n ] correspond to (x -1) n .

Equation (3) hints at the existence of a projective resolution of M n which starts with P n and has n m copies of P m in the (n -m)-th position: , respectively. Proposition 2.6 The complex (6) with the differential defined above is exact.

0 → P 0 → . . . → P   n m   n-m → . . . → P   n 2   n-2 → P   n 1   n-1 → P n → M n → 0 (
A finite-dimensional A-module M has a finite filtration with simple modules L n as subquotients. Due to one-dimensionality of L n the multiplicity of L n in M , denoted by [M : L n ], equals dim1 n M . A finitely-generated A-module M is not necessarily finite dimensional but it satisfies the following property dim(1 n M ) < ∞, for n ≥ 0, which we call a locally finite-dimensional property.

For locally finite-dimensional module M we define the multiplicity of L n in M as:

[M : L n ] = dim(1 n M ). ( 7
)
This definition is compatible with the usual notion of multiplicity of L n in M as the number of times L n appears in the composition series of M when M is finite-dimensional.

Let us now specialize to standard modules M m . We have

[M m : L n ] = dim(1 n M m ) =    n m , for n ≥ m; 0, if n < m. (8)
Recall that [P n : M m ] = n m , hence

[P n : M m ] = [M m : L n ]. (9)
Thus, our diagrammatically defined algebra possesses the Bernstein-Gelfand-Gelfand (BGG) reciprocity property. Indecomposable projective modules P n have filtration by standard modules M m , with m ≤ n and [P n : M n ] = 1. The multiplicity in the RHS in the equality (9) is understood in the generalized sense, as explained above.

Proposition 2.7 Homological dimension of slarc algebra standard module M n is n.

For detailed construction of a resolution of a simple module L k by standard modules M m for m ≥ k :

d -→ M   k + m m   k+m d -→ • • • d -→ M   k + 2 2   k+2 d -→ M   k + 1 1   k+1 d -→ M k d -→ L k -→ 0. (10)
Notice that the m-th term of the resolution is a direct sum

M   k + m m   k+m of standard modules M k+m .
On the level of diagrams, multiplicity k + m m represents the number of ways to add m right sarcs to a diagram in M k to obtain a diagram in M k+m . Let I m = {i 1 , i 2 , . . . , i m } ⊆ {1, 2, . . . , k + m} be the set describing positions of added larcs. Each summand M Im k+m is labeled by one of these subsets, and the differential will take summand labeled by I m into summands labeled by I m,-l , for 0 < l ≤ m, by composing on the right with diagrams containing a single short right arc and no left sarcs, see Fig. 4.

Informally, on the level of Grothendieck groups we have the following relation:

[L n ] = ∞ k=0 (-1) k n + k k [M n+k ] = ∞ k=0 (-1) k n + k k (x -1) n+k = (x -1) n x n+1 .
This infinite sum does not play a direct role in our categorification, but we can obtain projective resolution of a simple module L n via constructing a bicomplex, with a projective resolution (6) of M n+k , k ≥ 0 lying above each copy of a standard module in the resolution (10) of simple modules L n by standard modules M m , m ≥ n.

This construction can be summarized by saying that suitably defined Grothendieck ring of category of bounded complexes of projective modules is isomorphic to the one-variable polynomial ring Z[x] with the following correspondence:

[P n ] = n m=0 n m [M m ] ↔ x n = n m=0 n m (x -1) m [M n ] = m≤n (-1) n+m n m [P m ] ↔ (x -1) n = m≤n (-1) n+m n m x m
for more details and the background see [START_REF] Benson | Representations and cohomology I[END_REF], [START_REF] Weibel | An introduction to homological algebra[END_REF], [START_REF] Gelfand | Methods of homological algebra[END_REF], [Mil], and [START_REF] Khovanov | Categorification of the polynomial ring[END_REF]. This construction can be generalized to the categorification of various orthogonal polynomials by varying the underlying diagrammatic algebra.

Approximations of the identity

Various operations on polynomials can be lifted to the categorified setting. In this section we define a functor which corresponds to the truncation of polynomials on the level of Grothendieck group. Recall that B(≤ k) = k i=0 B(i) denotes diagrams in B of width less than or equal to k. Let A(≤ k), k ≥ 0 denote the subspace of A spanned by diagrams in B(≤ k). This subspace is an A-subbimodule of A.

Let A(k) be the quotient subbimodule A(≤ k)/A(≤ k -1). Let n P denote a right projective module n P = 1 n A and, analogously to the standard modules M n , let n M be the quotient of n P by the submodule spanned by all diagrams with a left sarcs. One can think of diagrams of n M as reflections along vertical axis of diagrams in M n .

Proposition 3.1 A(≤ k)/A(≤ k -1) ∼ = M k ⊗ k k M as A-bimodules (Fig. 6).
For a given k ≥ 0 , define a right exact functor F k : A-mod → A-mod by for an A-module M. The image of the standard module M m under functor F k is:

F k (M ) = A(≤ k) ⊗ A M, (11)
A(≤ k) ⊗ A M m = M m , if k ≥ m; 0, otherwise. (12)
By definition

P m = A1 m , hence A(≤ k) ⊗ A P m = A(≤ k) ⊗ A A1 m = A(≤ k)1 m ,
and this is a submodule of P m spanned by diagrams of width less than or equal to k:

F k (P m ) = A(≤ k) ⊗ A P m = P m , if k ≥ m; P m (≤ k), if k < m. (13)
In the Grothendieck group, projective modules P n correspond to x n and standard modules M n to (x -1) n . Modules P n (≤ k) have finite homological dimension, since they admit finite filtrations with successive quotients isomorphic to standard modules. Therefore, functor F k descends to an operator on the Grothendieck group K 0 (A), denoted by

[F k ]. The action of [F k ] on [P n ] = n m=0 n m [M m ] is equal to: [F k ][P n ] =      [P n ] = x n , if k ≥ n; k m=0 n m [M m ] = k m=0 n m (x -1) m , if k < n. (14)
Since all higher derived functors of F k are zero on standard modules, for k ≥ n operator [F k ] acts via identity on [P n ], and for k < n it approximates identity and can be viewed as taking the first k + 1 terms

k m=0 n m [M m ] in the expansion of [P n ] in the basis {(x -1) m } m≥0 .

Cabling functors

For every A-module M and a positive integer k construct the corresponding cabled module [k] M in the following way: Given a diagram y ∈ s B l , construct a diagram [k] y ∈ sk B lk , called the k-cabling of y, by taking k parallel copies of each arc (Fig. 7). For example, [k] 1 n = 1 nk . By definition, the action of an element α ∈ A on [k] M n is the regular action of its k-cabling α k .

1 n [k] M = 1 nk M, hence [k] M = ⊕ n≥0 1 nk M . (15)
What is the result of k-cabling simple, standard and projective modules? It is easy to see that, if k divides n, the of the simple module L n is the module L n/k :

1 m [k] L n = 1 km L n = k, if km = n; 0, otherwise. (16)
If k does not divide n the result is zero, [k] L n = 0.

Recall that basis elements of standard A modules M n correspond to diagrams in B n with n through arcs and an arbitrary number of left sarcs. Let S(n, k, i) denote the number of ways to select n numbers between 1 and ki such that each of the sets {kj + 1, . . . , k(j + 1)} 0≤j<i contains at least one of the selected numbers. Example 4.2 We compute cabling modules of M n for small values of n:

• [k] M 0 = M 0 , [k] M 1 = M k 1 , • [k] M 2 = M k 2 2 ⊕ M k 2 1 ,

Fig. 1 :

 1 Fig. 1: A diagram in mBn.

2Fig. 2 :

 2 Fig. 2: Concatenation of these two diagrams equals zero since the resulting diagram contains a floating arc.

Fig. 3 :

 3 Fig. 3: For any diagram a representing an element of a standard module and a diagram b ∈ B with right sarcs the product b • a = 0.

Fig. 4 :Fig. 5 :are determined by composing on the right by diagrams b 3 4 and b 4 4 obtained from diagrams b 3 7 and b 7 7 d

 4547 Fig. 4: Diagrams i bn-1 and b i n used in defining differentials in projective resolution of standard modules and resolution of simple by standard modules.

Fig. 6 :

 6 Fig. 6: Diagram in B(4) viewed as a product of elements in M4 and 4M .

Fig. 7 :

 7 Fig.7: A diagram y ∈ 11B6 and 2-cable[2] y ∈ 22B12.

  The proof is left to the reader following examples shown on Fig. 8. S(n, k, i) is the sum of products possible partitions λ = (λ 1 , . . . , λ i ) of n into i blocks of length at most k. 2

Acknowledgements

MK would like to thank the NSF for partial support via grant DMS-1005750. RS was fully supported by the Postdoctoral Fellowship at MSRI, Berkeley during the early stages of this project, and NSF 0935165 and AFOSR FA9550-09-1-0643 grants towards the end. Both authors are grateful to the reviewers for the corrections, comments, and ideas.

•

Studying cablings of projective modules reduces to the case of standard modules: [k] P n has a filtration with the i-th term of n i

[k] M i , based on the filtration (1) of P n by P n (i), i ≤ n.

Cabling functor [k] is exact, sending an A-module M to its k-cabled module [k] M , and categorifies the following operator on the Grothendieck group:

In the following paper we will further explore the structure and functors this categorification admits. For example, notice that [s][k] M ∼ = [ks] M functorially in M . This identity indicates that the cabling operator may correspond to a certain plethysm on the polynomial ring. Moreover, we will generalize this construction using a slightly different diagrammatics to category certain classes of orthogonal polynomials, such as Chebyshev and Hermite.


Élie De Panafieu
email: depanafieuelie@gmail.com.

Enumeration and structure of inhomogeneous graphs

Keywords: generating functions, analytic combinatorics, multivariate Laplace method, inhomogeneous graphs

 on the enumeration of properly colored graphs. We also discuss applications related to social networks.

) et proche des graphes inhomogènes de Söderberg (2002). Nous analysons la somme des poids de ces graphes et leur structure. Ces résultats nous permettent d'obtenir une nouvelle preuve d'un théorème de Wright (1972) sur l'énumération des graphes bien colorés, ainsi que sur un modèle lié aux réseaux sociaux.

The success of graphs relies on two contradictory properties. They are simple enough to appear naturally in many applications, but at the same time rich enough to enjoy non-trivial mathematical properties. Extensions such as hypergraphs and digraphs, and various notions of randomness on those objects have been proposed to address a wider range of applications. In this article, we focus on a model of inhomogeneous graphs introduced by de Panafieu and Ravelomanana [START_REF] De | Analytic description of the phase transition of inhomogeneous multigraphs[END_REF] and similar to the inhomogeneous graph model of Söderberg [START_REF] Öderberg | General formalism for inhomogeneous random graphs[END_REF]. Our main contributions are the computation of the total weight of inhomogeneous graphs with a given number of vertices and edges, and the analysis of their structure in the subcritical regime, without restriction on the weights matrix R. The emphasis is on the development of the theoretical basis of the model. Our tool is analytic combinatorics, and this work has been influenced by the articles of Flajolet, Knuth and Pittel [START_REF] Flajolet | The first cycles in an evolving graph[END_REF] and Janson, Knuth, Łuczak and Pittel [START_REF] Janson | The birth of the giant component[END_REF].

In Section 1, we present the model and two applications. Section 2 provides theorems for the enumeration of inhomogeneous graphs with a given number of vertices n and edges m. The set of inhomogeneous graphs that contain no component with more than one cycle is analyzed in Section 3. We prove in Section 4 that when m n is small enough, almost all inhomogeneous graphs belong to this set, and derive more explicit results than in Section 2 on the global enumeration of inhomogeneous graphs. Section 5 extends the previous results to inhomogeneous graphs without loops nor multiple edges.

1 Notations, models and applications

Notations

The row vector (u 1 , . . . , u q ) is denoted by u, and the column vector (u 1 , . . . , u q ) by u. The diagonal matrix û has main diagonal u, and 1 is the vector with all coefficients equal to 1. We adopt the notation u v for the product i u vi i . The functions log and exp are applied coefficient-wise to the vectors, i.e. log( u) = (log(u 1 ), . . . , log(u q )). When i n i = n, the multinomial notation n n denotes n!/ i n i !. The adjugate of a matrix M , equal to the transpose of the cofactor matrix, is adj(M ). Open intervals, closed intervals and integer intervals are denoted by ]x, y[, [x, y] and [a..b].

Models

The uniform graph model, also called multigraph process, has been studied using analytic combinatorics in [START_REF] Flajolet | The first cycles in an evolving graph[END_REF] and [START_REF] Janson | The birth of the giant component[END_REF]. This model produces a random vertex-labelled graph with n vertices and m edges by drawing 2m vertices v 1 w 1 . . . v m w m uniformly independently in [1..n], and adding to the graph the edges

v i w i for i from 1 to m: edge(G) = {v i w i | 1 ≤ i ≤ m}.
The graph is simple if it contains neither loops nor multiple edges. If the output of the process is conditioned to be simple, the model reduces to the classic G(n, m) graph model of Erdős and Rényi. The number of ordered sequences of vertices

v 1 w 1 . . . v m w m that correspond to a graph G is denoted by seqv(G) seqv(G) = |{v 1 w 1 . . . v m w m | {v i w i | 1 ≤ i ≤ m} = edge(G)}|.
Observe that a graph G with m edges is simple if and only if its number of sequences of vertices seqv(G) is equal to 2 m m!. For this reason, [START_REF] Janson | The birth of the giant component[END_REF] introduced the compensation factor κ(G) = seqv (G) 2 m m! . The total weight of graphs in a family is defined as the sum of their compensation factors. For example, the total weight of multigraphs with n vertices and m edges is n 2m 2 m m! . The original inhomogeneous graph model was introduced in [START_REF] Öderberg | General formalism for inhomogeneous random graphs[END_REF] as a generalization of the classic G(n, p) random graph model, and extended by Bollobás, Janson and Riordan [START_REF] Ás | The phase transition in inhomogeneous random graphs[END_REF]. We consider in this paper a variant of this model, introduced in [START_REF] De | Analytic description of the phase transition of inhomogeneous multigraphs[END_REF] and closer to the uniform graph model. Its parameters are an irreducible symmetric q × q matrix R and a vector r of size q, both with non-negative coefficients. We call inhomogeneous graph, or (R, r)-graph, a labelled graph where

• each vertex v has a type t(v) which is an integer in [1..q] and a weight r t(v) ,

• each edge vw receives a weight R t(v),t(w) .

The weight ω(G) of an (R, r)-graph G is the product of the compensation factor of the underlying graph (which is equal to 1 if the graph is simple), the weights of the vertices and the weights of the edges

ω(G) = κ(G) u∈G r t(u) vw∈G R t(v),t(w) .
One can also think of the parameters (r i ) and (R i,j ) as variables marking the vertices and the edges according to their types and the types of their ends. We define the total weight of (R, r)-graphs in a family as the sum of their weights. An (n, m)-(R, r)-graph is an (R, r)-graph with n vertices and m edges. Let n(G) denote the number of vertices of a graph G and F be a family of (R, r)-graphs, then the generating function F (z) of F is defined by

F (z) = G∈F ω(G) z n(G) n(G)! .
We use this definition in Section 3. Observe that an (R, r)-graph that contains an edge of weight zero has weight zero, and thus does not contribute to the total weight of (R, r)-graphs.

Lemma 1 Let G * R, r denote the set of (R, r)-graphs with non-zero weight. If the matrix R is reducible, then there exist a non-trivial partition

T 1 • • • T k = [1.
.q] of the set of types, symmetric irreducible matrices S 1 , . . . , S k and vectors s 1 , . . . , s k such that G * R, r is in bijection with the Cartesian product

G * S1, s1 × • • • , ×G * Ss, s k . Specifically, for any graph G in G * R, r ,
• for all i = j, there is no edge between a vertex of type in T i and one of type in T j ,

• for all i, the graph induced by G on the vertices with types in T i is in G * Si, si .

Proof: Let ( e 1 , . . . , e q ) denote the canonical basis of R q . Since R is reducible, there is a partition T 1 , . . . , T k of [1.

.q] such that the matrix of R on the basis ( e T1 [START_REF] De Panafieu | Algorithmic barriers from phase transitions[END_REF] , e T1 [START_REF] Bergeron | Combinatorial Species and Tree-like Structures[END_REF] , . . . , e T2 [START_REF] De Panafieu | Algorithmic barriers from phase transitions[END_REF] , e T2 [START_REF] Bergeron | Combinatorial Species and Tree-like Structures[END_REF] , . . .) has a block-diagonal shape diag(S 1 , . . . , S k ). For each i, we set s i = (r Ti [START_REF] De Panafieu | Algorithmic barriers from phase transitions[END_REF] , r Ti [START_REF] Bergeron | Combinatorial Species and Tree-like Structures[END_REF] , . . .). There can be no edge between types in T i and in T j for i = j because its weight would be 0. Therefore, any component of

G * R, r
with a vertex of type in T i has all its types in T i . By construction, such a component is in

G * Si, si . 2
The matrix R is therefore always assumed to be irreducible. In this paper, we analyze asymptotic properties of (n, m)-(R, r)-graphs when n goes to infinity, m is equal to cn and R, r and c are fixed.

Applications

Inhomogeneous graphs have been used in [START_REF] De | Analytic description of the phase transition of inhomogeneous multigraphs[END_REF] to analyze the phase transition of satisfiability problems. We present new applications to illustrate the expressiveness of the model, and motivate the theoretical analysis conducted in the next sections. In the properly q-colored graphs, each vertex has a color in [1..q] and no edge links two vertices with the same one. We give a new proof of [START_REF] Wright | Counting coloured graphs III[END_REF]Theorem 3] on their enumeration, which is not to be confused with an enumeration of q-colorable graphs, a problem addressed in [START_REF] De Panafieu | Algorithmic barriers from phase transitions[END_REF].

Application 2 Let R (col) denote the q × q matrix with all coefficients equal to 1 and 0s on the diagonal, then the number of properly q-colored (n, m)-graphs is equal to the total weight of (n, m)-(R (col) , 1)graphs. When m n is in a fixed closed interval of R >0 , its asymptotics is

n 2m 2 m m! 1 + 2 q -1 m n -q-1 2 1 - 1 q m q n + o(1).
For properly q-colored simple graphs, the previous asymptotics is multiplied by exp m n 2 q q-1 .

Proof: Let us identify the types and the colors. If an (R (col) , 1)-graph is properly colored, the product of the weights of its edges is 1, otherwise it is 0, hence the first assertion of the theorem. The eigenvalues of R (col) are q -1 and -1, with multiplicities 1 and q -1. The asymptotics is then a direct application of Theorem 14 and the remark following Theorem 16. 2

As a second example, we consider a world where each person has a number k of topics of interest among a set of size t ≥ 2k, and where two people can only become friend if they share at least one common topic of interest. We call friendship graph the graph where each vertex represents a person and each edge a friendship relation. The graph is naturally assumed to be simple. To analyze the friendship graphs, we introduce the following notations. Let σ denote a numbering of the subsets of size k of [1..t], and R (fs) the adjacency matrix of the complement of the Kneser graph (see for example [START_REF] Godsil | Algebraic Graph Theory[END_REF]). This matrix of dimension q = t k is defined by

R (fs) i,j = 1 if |σ(i) ∩ σ(j)| ≥ 1, 0 otherwise.

Application 3

The number of friendship graphs with n people and m friendship relations is equal to the total weight of simple (n, m)-(R (fs) , 1)-graphs. When m n is in a closed interval of ]0, 1 2 [, almost all friendship graphs contain no component with more than one cycle. There is a value β > 1 2 such that when

m n is in a closed interval of ]0, β[, the asymptotics of friendship graphs is n 2m 2 m m! t k - t -k k m t k n-m C + o(1)
where the value C, bounded with respect to n, is

C = exp - t k t k -t-k k m n 1 + m n k j=1 1 -(-1) j 2m n t-k-j k-j t k -t-k k -1 2 (( t j )-( t j-1 )
) .

Proof: Identifying each type i with the set of topics of interest σ(i), the definition of the matrix R (fs) implies that the weight of a simple (R (fs) , 1)-graph is 1 if it is a friendship graph, and 0 otherwise. The spectrum of the Kneser graph is known, and available in [START_REF] Levenshtein | Association schemes and coding theory[END_REF]. The spectrum of its complement follows: the dominant eigenvalue is t k -t-k k and for all j from 1 to k, (-1) j t-k-j k-j is an eigenvalue with multiplicity t j -t j-1 . The result is then a consequence of Theorem 14 and the remark that follows Theorem 16, with parameters Tr(R (fs) ) = t k and Tr((

R (fs) ) 2 ) = t k -t-k k . 2
Inhomogeneous graphs can as well handle generalizations of the model. For example, the weight of a friendship could be a real value, function of the number of common topics of interest.

Global enumeration

In this section, we reduce the problem of deriving the asymptotics of (n, m)-(R, r)-graphs to the location of the minimums of a function parameterized by R, r and m n . We start with an explicit formula. Theorem 4 The total weight of (n, m)-(R, r)-graphs is

G R, r (n, m) = 1 2 m m! { n∈N q | 1 n=n} n n r n nR n m . (1)
Proof: Let us consider a fixed partition of the set of labels [1.

.n] into q sets V 1 , . . . , V q of sizes n 1 , . . . , n q , and denote by G( n, m) the set of (n, m)-(R, r)-graphs where the type of the vertices in V i is i. Then the total weight of graphs in G( n, m) is expressed by summation over all sequences of vertices as

G∈G( n,m) ω(G) = 1 2 m m! q i=1 r ni i v1,w1,...,vm,wm∈[1..n] 2m m i=1 R t(vi),t(wi) .
Switching the sum and the product, the previous equation becomes

G∈G( n,m) ω(G) = 1 2 m m! q i=1 r ni i 1≤i,j≤q n i n j R m = r n ( nR n) m 2 m m! .
Equation ( 1) is obtained by summation over all possible partitions

V 1 • • • V q = [1..n]. 2
To obtain the asymptotics of G R, r (n, m), we will apply in the proof of Theorem 7 a multivariate Laplace method (i) . This method requires to give to the previous expression a more suitable shape.

Lemma 5 Let S denote the set { x ∈ R q ≥0 | 1 x = 1}. The exact total weight of (n, m)-(R, r)-graphs is G R, r (n, m) = n 2m 2 m m! 1 (2πn) q-1 2 { n∈N q | 1 n=n} A n n n e -nΦ m n ( n n ) , (2)
where, with the usual conventions 0 log(0) = 0 and 0 0 = 1, the functions A n and Φ c are defined on S by

A n ( x) = n! n n e -n √ 2πn q i=1 (nx i ) nxi e -nxi √ 2πnx i Γ(nx i + 1) 1 √ x i , Φ c ( x) = log( x) -log( r) x -c log xR x .
Proof: In Expression (1), we divide and multiply each factorial from the multinomial coefficient by its Stirling approximation, and rescale each n i by a factor 1/n

G R, r (n, m) = n 2m 2 m m! 1 (2πn) q-1 2 n∈N q 1 n=n n! n n e -n √ 2πn q i=1 n ni i e -ni √ 2πn i n i ! n i /n r n/n ( n/n) n/n n n n R n n m .
The functions A n and Φ c are then introduced to simply this expression.

2

Let E denote a q × (q -1) matrix with left-kernel of dimension 1 containing the vector 1 , e.g.

E =    1 0 ••• 0 0 1 . . . . . . . . . . . . . . . 0 0 ••• 0 1 -1 ••• ••• -1    .
Two vectors u and v belong to S only if there is a vector of dimension q -1 for which u = v + E . The following lemma provides tools to locate the minimums of the function Φ c .

Lemma 6 For all c > 0, the Taylor expansion of Φ c near any point x in the interior of S is

Φ c ( x + E ) = Φ c ( x) + ∇ Φc( x) + 1 2 H Φc( x) + O( 3 ),
where the gradient vector and the Hessian matrix have dimension q -1 and are defined by

∇ Φc( x) = log( x) -log( r) - 2c xR x xR E, H Φc( x) = E x-1 + 2c xR x 2 xR x R x xR -R E.
If ϕ is a minimum of Φ c , then ϕ is in the interior of S, ∇ Φc( ϕ) = 0 and H Φc( ϕc) is positive-semidefinite.

Proof: Let Ψ c denote the function x → log( x) -log( r) x -c log xR x from [0, 1] q \ { 0} to R.
Its restriction to S is equal to Φ c and its Taylor expansion starts with

Ψ c ( x + ) = Ψ c ( x) + ∇ Ψc( x) + 1 2 H Ψc( x) + O( 3 )
where the gradient ∇ Ψc( x) and the Hessian matrix H Ψc( x) of Ψ c are computed using partial derivations. It follows that the Taylor expansion of Φ c near any point x in the interior of S is

Φ c ( x + E ) = Φ c ( x) + ∇ Ψc( x) E + 1 2 E H Ψc( x) E + O( 3 ).
Observing the limit of the gradient ∇ Φc( x) of Φ c when one coordinate of x vanishes, we conclude that the local minimums of Φ c cannot be reached on the boundary of S, and must therefore cancel ∇ Φc( x) . 2

Gathering the previous results, we can finally apply the multivariate Laplace method. Proof: We inject in the integral representation of the sum (2) the following relations

A n ( ϕ + E ) ∼ q i=1 ϕ -1/2 i + O( ), e -nΦc( ϕ+E ) = r ϕ ϕ ϕ n ϕR ϕ m e -1 2 n H Φc ( ϕc ) +O(n 3 ) ,
valid for any minimum ϕ of Φ c , and apply the multivariate Laplace method (see [START_REF] Wilson | Analytic Combinatorics in Several Variables[END_REF]Chapter 5]). 2

The previous theorem requires to locate the minimums of Φ c , and to avoid the values of c for which those minimums cross or merge. Even when the dimension of the matrix R is 2, those minimums can exhibit interesting behaviors. For example, for R = ( 2 1 1 2 ), Φ c has a unique minimum when c ≤ 1/6 and two local minimums when c > 1/6. Investigating the link between the inhomogeneous graph model and the Stochastic Block Model from [START_REF] Holland | Stochastic blockmodels: First steps[END_REF] may provide an explanation for this change in Φ c . Theorems 12 and 14 provide two examples of families of parameters R, r and m n for which Φ c has a unique minimum and a more explicit asymptotics for the total weight of (n, m)-(R, r)-graphs can be derive.

Trees and unicycles

An (R, r)-tree is a connected (R, r)-graph that contains no cycle. Such a graph is rooted if one vertex, called the root, is marked. An (R, r)-unicycle is a connected (R, r)-graph with exactly one cycle. A classic result of Erdős and Rényi [START_REF] Ényi | On the evolution of random graphs[END_REF] states that almost all (n, m)-graphs with m n < 1 2 contain only trees and unicycles. In this section, we derive a similar result for (R, r)-graphs. We also give a more explicit asymptotics for the total weight of (n, m)-(R, r)-graphs than in Theorem 7 when m n is smaller than a value β, defined in Theorem 12.

Lemma 8 Let T i (z), U (z) and V (z) denote the generating functions of (R, r)-rooted trees with root of type i, (R, r)-trees and (R, r)-unicycles, and let T (z) denote the vector (T 1 (z), . . . , T q (z)) , then

T (z) = zr exp R T (z) , U (z) = 1 T (z) - 1 2 T (z)R T (z), V (z) = - 1 2 log det I -T (z)R .
Proof: An (R, r)-rooted tree is a root with a set of sons which are (R, r)-rooted trees themselves. Let i denote the type of the root, and j the type of the root of one of those sons, then the root has weight r i and the weight of the edge linking the root to the son is the coefficient R i,j . Using the Symbolic Method (see for example the book of Flajolet and Sedgewick [START_REF] Flajolet | Analytic Combinatorics[END_REF]) the previous combinatorial description translates into the first relation on T (z). The expression for U (z) is obtained using the Dissymmetry Theorem presented in [START_REF] Bergeron | Combinatorial Species and Tree-like Structures[END_REF]. The proof of the expression of

V (z) is a variation of [9, Proposition V.6]. 2
Lemma 9 The generating functions T (z) has the following singular expansions

T (z) = τ -γ 1 -z/ρ + O(1 -z/ρ)
where the value ρ and the vectors τ and γ have positive coefficients and are characterized by the system

τ = ρr exp (R τ ) , (I -τ R) γ = 0, 1 2 γRγR γ = 1 γ. ( 3
)
Proof: The square-root singular expansion of T (z) is a consequence of [6, Proposition 3]. The constraints on its coefficients are obtained by injection of this expansion into the relation T (z) = zr exp(R T (z)) and identification of the coefficients corresponding to the same power of 1 -z/ρ. 2

We can now build (R, r)-graphs that contain only trees and unicycles.

Theorem 10 We set α = 1 2 τ R τ 1 τ
. For c = m n in any closed interval of ]0, α[, let ζ c and ϕ c be characterized by 1 2

T (ζ c )R T (ζ c ) 1 T (ζ c ) = c and ϕ c = T (ζ c ) 1 T (ζ c ) , ( 4
)
then the total weight of (n, m)-(R, r)-graphs that contain only trees and unicycles is

G (U,V ) R, r (n, m) ∼ n 2m 2 m m! C -1/2 c, ϕc r ϕc ϕ ϕc c n ϕ c R ϕ c m ,
where

C c, x = 1 c (1 -c) 1 I - 2c xR x xR -1 x -1 det I - 2c xR x xR . (5)
Proof: A tree with n vertices has n -1 edges, and a unicycle with n vertices has n edges. Therefore, an (n, m)-(R, r)-graph that contains only trees and unicycles is a set of n -m trees and a set of unicycles

G (U,V ) R, r (n, m) = n![z n ] U (z) n-m (n -m)! e V (z) .
We apply [START_REF] Flajolet | Analytic Combinatorics[END_REF]Theorem VIII.8] to extract its asymptotics. The saddle-point equation is Equation ( 4). We then introduce the notation ϕ, which satisfies the relation

T (ζ c ) = 2c ϕ c R ϕ c ϕ c ,
and apply Stirling approximations to rearrange the expression. 2

In a longer version of this article, we plan to enumerate connected (n, m)-(R, r)-graphs when m -n ≥ 1 is fixed, and to prove that such components appear with a non-zero probability when m = αn + O(n 2/3 ). This would extend to (R, r)-graphs the result obtained for graphs in [START_REF] Janson | The birth of the giant component[END_REF] with α = 1 2 . Therefore, we conjecture that m n = α is the threshold for the emergence of components with at least two cycles. Following the approach of [START_REF] Flajolet | The first cycles in an evolving graph[END_REF], one could as well derive the limit law of the number of edges when the first cycle appear in a random (n, m)-(R, r)-graph.

The following lemma links the determinant of the Hessian matrix H Φc( x) to the value C c, x .

Lemma 11 Let τ , C c, x and H Φc( x) be defined by Equations (3), ( 5) and Lemma 6, and set α to

1 2 τ R τ 1 τ
, then for all c ∈ [0, α[ and x ∈ S, the following identity holds

C c, x = det(H Φc( x) ) q i=1 x i .
Proof: We introduce the matrix M = xR x 2c

x-1 -R and the vector v = 2/( xR x) x. Since E is a q × (q -1) matrix, it becomes a square matrix F if we concatenate to its right the column vector v. The determinant of F M F can be expressed as det(F ) 2 det(M ) or using a block-determinant formula. The equality between those two expressions is

2 xR x det(M ) = ( vM v + 1) det(E M E) -det(E (M + M v vM )E). (6)
The properties of the matrix E imply

det(E M E) = det(M ) 1 M -1 1 and E (M + M v vM )E = xR x 2c H Φc( x) .
The result is obtained by injection of those relations in Equation ( 6) and rearrangement of the terms. 2

4 Global enumeration when Φ c has a unique minimum

In this section, we present two cases where the result of Theorem 7 can be made more specific.

Theorem 12

We set β = sup{c | ∀ x ∈ S, det(H Φc( x) ) > 0}, then β is greater than α (defined in Theorem 10). The equation ∇ Φc( ϕ) = 0 defines implicitly on [0, β[ a unique solution ϕ c , given by Equation (4)

when c ∈]0, α]. Finally, when m n is in a closed interval of ]0, β[, the asymptotics of (n, m)-(R, r)-graphs is G R, r (n, m) ∼ n 2m 2 m m! r ϕc ϕ ϕc c n ϕ c R ϕ c m det(H Φc( ϕc) ) q i=1 ϕ i .
Proof: When c = 0, for all x ∈ S the matrix H Φ0( x) is positive-definite. By continuity of its eigenvalues with respect to c and x, H Φc( x) stays positive-definite for all c ∈ [0, β[ and x ∈ S, so the function Φ c is convex. According to Lemma 6, Φ c has no minimum on the boundary of S, so it has a unique minimum, which cancels its gradient ∇ Φc( x) . The asymptotics is then a consequence of Theorem 7. For c ∈]0, α[, let us define ϕ c as in Equation ( 4). A direct computation shows that log( ϕ c ) -log( r) -2c ϕR/( ϕR ϕ) is collinear to 1 , so ϕ c cancels ∇ Φc( x) . We extend continuously ϕ c for c = 0 and c = α with

ϕ 0 = lim z→0 T (z) 1 T (z) = r 1 r , ϕ α = lim z→ρ T (z) 1 T (z) = τ 1 τ
.

The last point we need to prove is that β > α. According to Lemma 11, det(H Φc( x) ) vanishes only if C c, x does, and Theorem 10 implies in particular C c, ϕc > 0 when c ∈]0, α[. Observe that H Φc( x) is independent of r and that for each x ∈ S, there is a vector r ∈ R q >0 such that ϕ c = x. This proves β ≥ α. For c = α, ϕ α is equal to τ /( 1 τ ). The definitions (3) of τ and (5) of C c, ϕc then imply

det I - 2α ϕ α R ϕ α φα R = 0 and C α, ϕα = 1 -α α 1 adj(I -τ R) τ 1 τ
.

The value of the generating function of unrooted (R, r)-trees 1 T (z) -T (z)R T (z)/2 is positive at its dominant singularity ρ, and τ = T (ρ), so α = τ R τ /(2 1 τ ) is smaller than 1. By definition of τ , the irreducible matrix τ R has dominant eigenvalue 1 of dimension 1 with eigenvector γ, defined in Equation (3). Therefore, adj(I -τ R) is proportional to γ γ, which has positive coefficients. This implies C α, ϕα > 0, so det(H Φα( x) ) is positive for all x in S and Φ α is still strictly convex. Therefore, β is greater than α. 2

The following corollary is obtained by comparison of the asymptotics of G When R is the adjacency matrix of a regular graph, then 1 is an eigenvector and ϕ c becomes explicit.

Theorem 14 Let λ 1 ≥ • • • ≥ λ q denote the eigenvalues of R, and assume that 1 is an eigenvector of R, then when m n is in a closed interval of ]0, β[, the asymptotics of (n, m)-(R, 1)-graphs is

G R, 1 (n, m) ∼ n 2m 2 m m! λ m 1 q n-m q i=2 1 -2 λ i λ 1 m n -1/2
.

If λ 2 is positive, β < λ1 2λ2 , otherwise the previous asymptotics holds for m n in any closed interval of R >0 .

Proof: R has non-negative coefficients and is irreducible. The Perron-Fröbenius theorem implies that its dominant eigenvalue is positive and corresponds to the unique eigenvector with positive coefficients, thus R 1 = λ 1 1. The first assertion of the theorem is then a consequence of Theorem 12 with ϕ c = 1/q, ∇ Φc( 1/q) = 0 and det(H Φc( 1/q) ) =

q q 1 -2c det I - 2c λ 1 R = q q q i=2 1 -2c λ i λ 1 .
Observe that det(H Φc( 1/q) ) vanishes at c = λ1 2λ2 . Let us now consider the case λ 2 ≤ 0. The function log( x) x reaches its unique minimum on S at 1/q. To prove that the function Φ c ( x) = log( x) xc log( xR x) does the same, it is then sufficient to prove that xR x reaches at 1/q its global maximum. Since x is in S, there is a vector y ∈ R q-1 that satisfies x = 1/q + E y. Since 1 E is equal to 0 , we obtain

xR x = λ 1 q + yE RE y.
The symmetry of R implies the existence of an orthogonal matrix Q with first row 1 / √ q such that R = Q diag(λ 1 , . . . , λ q )Q. The first row of QE is 0 . Let P denote the (q -1) × (q -1) matrix in the lower block of QE. Then P is invertible, and E Q diag(λ 1 , . . . , λ q )QE = P diag(λ 2 , . . . , λ q )P.

We set z = P y and obtain xR x = 1 q + q i=2 λ i z 2 i . Therefore, xR x reaches its global maximum λ 1 /q when z = 0, which implies y = 0 and x = 1/q. 2 A future direction of research is the expansion of the family of parameters R, r and c for which we can link the asymptotics of (n, m)-(R, r)-graphs to the spectrum of R. Information on the location of the minimums of Φ c for c greater than β would also be instructive.

Simple (R, r)-Graphs

The previous sections focused on (R, r)-graphs where loops and multiple edges were allowed. We now extend those results to simple (R, r)-graphs, starting with a theorem similar to Theorem 4.

Theorem 15

The total weight of simple (n, m)-(R, r)-graphs is

SG R, r (n, m) = [w m ] 1 n=n n n r n 1≤i<j≤q (1 + R i,j w) ninj q i=1 (1 + R i,i w) ni(ni-1)/2 . ( 7
) Proof: We consider a partition V 1 • • • V q = [1.
.n] of the set of vertices and define n i = |V i | for all i.

Let SG( n, m) denote the set of simple (n, m)-(R, r)-graphs where each vertex of V i has type i. When i = j, there are n i n j available edges between vertices of V i and V j , and for all i, there are n i (n i -1)/2 possible edges between vertices of V i . Therefore, the total weight of graphs in SG( n, m) is

G∈SG( n,m) ω(G) = [w m ] r n 1≤i<j≤q
(1 + R i,j w) ninj q i=1

(1 + R i,i w) ni(ni-1)/2 .

The result of the Lemma is obtained by summation over all partitions The end of the proof is the same as in Theorem 7. to avoid loops and double edges in the cycle. The end of the proof is the same as in Theorem 10. 2

V 1 • • • V q = [1..n]. 2

Theorem 7

 7 Let [a, b] be a fixed closed interval such that the function (c, x) → det(H Φc( x) ) from [a, b]×S to R does not vanish, and let ϕ c,1 , . . . , ϕ c,s denote the local minimums of Φ c , then when n is large while c = m n is in [a, b], the asymptotics of the total weight of (n, m)-(R, r)-graphs is G R, r (n, m) ∼ n 2m 2 m m! ϕ∈{ ϕc,1,..., ϕc,s}

(

  U,V ) R, r (n, m) from Theorem 10 and G R, r (n, m) from Theorem 12, using the relation C c, x = det(H Φc( x) ) q i=1 x i from Lemma 11. Corollary 13 When c = m n is in a closed interval of ]0, α[, then almost all (n, m)-(R, r)-graphs contain only trees and unicycles.

Theorem 16 1 + R i,j w n nxinxj q i=1 1 + 2 . 2 ( 1 +( 2 ( 1 +

 161122121 With the notations of Theorem 7, for all c = m n in [a, b], the asymptotics of simple (n, m)-(R, r)-graphs is SG R, r (n, m) ∼ n 2m 2 m m! ϕ∈{ ϕc,1,..., ϕc,s} Starting with the exact expression (7), we replace w with nwSG R, r (n, m) = n m 1 n=n n n r n [w m ]e Fn( n/n,w) ,(8)whereF n ( x, w) = log 1≤i<j≤q R i,i w n nxi(nxi-1)/An expansion of the logarithm reduces this expression toF n ( x, w) = n xR x w xR) 2 )w 2 + O(n -1 ).With c = m n bounded, we apply [9, Theorem VIII.8] with saddle-point ζ = 2c/( xR x):[w m ]e Fn( x,w) = n m 2 m m! ( xR x) m exp -O(n -1 ))holds uniformly for x ∈ S. Adopting the notation Φ c of Lemma 5, Equation (8) then becomes SG R, r (n, m) nx i ) nxi e -nxi √ 2πnx i Γ(nx i + 1O(n -1 )).

2

 2

Theorems12 and 14

 14 extend to simple (R, r)-graphs in the same way.Corollary 17 When m n is in a closed interval of ]0, α[, almost all simple (n, m)-(R, r)-graphs contain only trees and unicycles.Proof: We verify that the asymptotics of simple (n, m)-(R, r)-graphs containing only trees and unicycles is equal to the asymptotics of all simple (n, m)-(R, r)-graphs, derived in Theorem 16. The generating function U (z) of (R, r)-trees is the same for graphs and simple graphs. The generating function SV (z) of simple (R, r)-unicycles becomes SV (z) = V (z) -

(i) We thank Nathanaël Fijalkow and Antoine Crouzet for the time spent with us on this asymptotics.

This work was partially founded by the Austrian Science Fund (FWF) grant F5004, the Partenariats Hubert Curien (PHC) AMADEUS and the CNRS PEPS project HYDrATA 1365-8050 c 2015


Lenny Tevlin
email: ltevlin@nyu.edu

Statistics on Lattice Walks and q-Lassalle Numbers

Keywords: lattice walks, statistics on words, q-integers

de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

1 Introduction to Lassalle's Sequences and their q-analogs.

Michel Lassalle [START_REF] Lassalle | Two integer sequences related to Catalan numbers[END_REF] has discussed two related sequences of numbers A k and α k . {A k } is generated by the following recurrence:

A n = (-1) n-1 C n + n-1 j=1 (-1) n-j-1 2n -1 2j -1 A j C n-j , A 1 = 1
The second sequence is

α n = 2A n C n
He proved that both A n and α n are positive integers and each sequence is increasing (and more). (It turns out that the second sequence is simply related to power sums of zeros of Bessel function J 0 (z)). It is intriguing to inquire whether there is a natural q-analog of these numbers. It may be generated by a q-analog of the above recurrence (with C n (q) = 1 n + 1 q 2n n q , a q-Catalan):

A n (q) = (-1) n-1 q n-1 C n (q) + n-1 j=1

(-1) n-j-1 q n-j 2n -1 2j -1 q A j (q)C n-j (q),

but a slightly renormalized version looks neater:

A n (q) = (-1) n-1 q 3-2n C n (q) + (-1) n q 3-2n 2n -1 q C n-1 (q) + n-1 j=2 (-1) n-j-1 q 2j-2n 2n -1 2j -1 q A j (q)C n-j (q) (2)

with A 1 (q) = 1. It turns out that A n (q) are monic unimodal palindromic polynomials in q with positive integer coefficients. Here are some examples:

Example 1 A 2 (q) = 1 A 3 (q) = 1 + q + q 2 + q 3 + q 4
A 4 (q) = 1 + 2q + 3q 2 + 5q 3 + 6q 4 + 7q 5 + 8q 6 + 7q 7 + 6q 8 + 5q 9 + 3q 10 + 2q 11 + q 12

A 5 (q) = 1 + 3q + 6q 2 + 12q 3 + 19q 4 + 29q 5 + 41q 6 + 54q 7 + 67q 8 + 80q 9 + 89q 10 + 96q The second Lassalle's sequence α k has the following q-analog:

α n = (1 + q n )A n (q) C n (q) (3)
And each of α n (q) is also a monic unimodal palindromic polynomial in q with positive integer coefficients.

Here are examples of α n (q)

Example 2

α 1 (q) = 1 + q α 2 (q) = 1 α 3 (q) = 1 + q α 4 (q) = 1 + 2q + 2q 2 + 2q 3 + q 4
α 5 (q) = 1 + 3q + 5q 2 + 8q 3 + 9q 4 + 9q 5 + 8q 6 + 5q 7 + 3q 8 + q 9

The proof of positivity of α k relies (in addition to certain divisibility properties) on the positivity of

n k -1 n k - n k -2 n k + 1
and Lassalle used the combinatorial interpretation of this difference of binomial coefficients as a generating function of the number of NSEW walks on a square lattice that start at the origin and finish at (2k -n -1, 1) [START_REF] Guy | Lattice paths, reflections, and dimension-changing bijections[END_REF]. Similarly, the positivity of α k (q) requires the positivity of

n k -1 q n k q -q 2 n k -2 q n k + 1 q (4)
However in this case a combinatorial interpretation has to be developed.

Introduction to q-enumeration of Lattice walks

To understand the positivity of (4) combinatorially, i.e. as a generating function of certain weighted lattice walks, I first interpret the q-version of the generating function of all NSEW walks as a generating function of a certain (new) inversion statistics on lattice walks. The total number of lattice walks from (0, 0) to (c, d) of length n is given by [DR84] c,d)). The q-analog of the walk enumeration formula is the following generating function.

n 1 2 (n -c + d) n 1 2 (n -c -d)
W N EN = 2 • 1 + 1 = 3 EN W N = 1 + 1 = 2 N W N E = 1 + (2 + 2 • 1) = 5 N EN W = 1 + (2 + 1) = 4 W N N E = 2 + 2 • 1 = 4 EN N W = 1 + 2 = 3
Proposition 1 n 1 2 (n -c + d) q n 1 2 (n -c -d) q = w∈Pn((0,0)|(c,d))
q winv(w) (5)

The following is true for the walks restricted to the upper half plane. Denote the set of walks starting at (0, 0) and ending at (c, d) in n steps and never going below the x-axis by

P + n ((0, 0) | (c, d)), then Proposition 2 n 1 2 (n + c + d) q n 1 2 (n + c -d) q -q d+1 n 1 2 (n + c + d) + 1 q n 1 2 (n + c -d) -1 q = w∈P + n ((0,0)|(c,d))
q winv(w) (6)

In Section 6 I will also introduce an analog of a major index, wmaj(w), which is, conjecturally, equally distributed with winv(w) over lattice walks.

3 q-Lassalle Numbers

The purpose of this section is to derive a bilinear recursion relations for A k (q) and α k (q), from which the positivity and integrality follow. The strategy is to rewrite the recursion relation between A (q) (as in (1)) as a difference equation. Then, using the q-difference equation for the generating function of q-Catalan, to obtain the q-difference equation for the generating function of the q-Lassalle numbers.

A n (q) = (-1) n-1 q n-1 C n (q) + n-1 j=1 (-1) n-j-1 q n-j 2n -1 2j -1 q A j (q)C n-j (q) - (-1) n q n 2n q C n (q) 2n q ! = qA n (q) 2n -1 q ! + n-1 j=1 qA j (q) 2j -1 q ! (-1) n-j q n-j C n-j (q) 2n -2j q ! (7)
Introduce generating functions and the finite q-difference operator:

H(t; q) = k≥0 (-1) k q k C k (q)t 2k 2k q ! ≡ k≥0 (-1) k q k t 2k k q ! k + 1 q ! P (t; q) = k≥1 qA k (q)t 2k-1 2k -1 q ! D q f (t) = f (t) -f (qt) (1 -q)t
then ( 7) is equivalent to -D q H(t, q) = P (t; q)H(t; q) (8) Recall Jackson's basic q-Bessel function ([Ism82]):

J (1) ν (x; q) = (q ν+1 ; q) ∞ (q; q) ∞ n≥0 (-1) n (q; q) n (q ν+1 ; q) n x 2 2n+ν , where (a; q) n = n-1 j=0 (1 -aq i ) (9) For ν = 1 J (1) 1 (x; q) = 1 1 -q n≥0 (-1) n (q; q) n (q 2 ; q) n x 2 2n+1 = n≥0 (-1) n n q ! n + 1 q ! x 2(1 -q) 2n+1 So that H(t; q) = 1 √ q t J (1)
1 (2(1 -q) √ q t; q), i.e.

q-Bessel function J

(1) 1 (x; q) is a generating function for q-Catalan numbers. J

(1) 1 (x; q) satisfies the following q-Bessel difference equation:

J (1) 1 (qx; q) -q 1 2 + q -1 2 J (1) 1 ( √ q x; q) + 1 + x 2 4 J (1) 1 (x; q) = 0 (10)
For H(t; q), (10) translates to:

H(qt; q) -1 + 1 q H( √ qt; q) + 1 q + (1 -q) 2 t 2 H(t; q) = 0 (11)
Through the q-difference equation (8) this implies the following ungainly looking q-difference equation for P (t; q):

(1 + q + q(1 -q) 2 t 2 )q(1 -q) √ qtP ( √ qt; q) + q 2 (1 -q) 2 tP (t; q) √ qtP ( √ qt; q)+ + (1 + q + q(1 -q) 2 t 2 )q 2 (1 -q) 2 t 2 + q 2 (1 -q) 2 t 2 q(1 -q)tP (t; q) = (1 -q 2 )tP (t; q) -q(1 -q)(1 -q 2 )t 2
But collecting coefficients of t 2n on both sides makes things look better:

A 1 (q) = 1 A 2 (q) = q 2 [2] q [s + 1] q [2s -1] q ! A s (q) = q 3 + q s+1 [2s -3] q ! A s-1 (q) + s-2 k=2 q k+3 A k (q)A s-k (q) [2k -1] q ![2s -2k -1] q ! It's time to rescale, so let A k (q) = q 3k-4 A k (q)
then the recursion relation for A k (q) is:

A s (q) = [2s -1] q [2] q [s + 1] q s-1 k=1 q k-1 [2s -2] q ! [2k -1] q ![2s -2k -1] q ! A k (q)A s-k (q) (12)
Translating this recursion into that for α n (q) (as in (3)) produces:

α n (q) = 1 2 q n q n-1 k=1 q k-1 n k + 1 q n k -1 q α k (q)α n-k (q) (13)
The ratio of the q-binomial coefficients can be rewritten as

1 n q n k + 1 q n k -1 q = 1 [2] q n -1 r -1 q n -1 r q -q 2 n -1 r -2 q n -1 r + 1 q
Therefore, the proof depends on

• positivity and integrality of

c n,k (q) = n -1 r -1 q n -1 k q -q 2 n -1 k -2 q n -1 k + 1 q
• divisibility of c n,k (q) and α k (q) by powers of 2 q .

As may be seen from ( 6), the positivity and integrality of c n,k (q) follows from its combinatorial interpretation as the generating function of winv statistics of upper half-plane lattice walks, namely the walks that start at (0, 0) and end up at (2k -n -1, 1) in (n -1) steps. Therefore I continue with the lattice walk part of the story.

Walk Inversion Generating Function

In order to prove the walk inversion generating function formula, as in ( 5)

n 1 2 (n -c + d) q n 1 2 (n -c -d) q = w∈Pn((0,0)|(c,d))
q winv(w)

I will need the following lemma. Denote the set of all walks of length n from (0, 0) to (c, d) with exactly k W steps by P n ((c, d); k). Of course this fixes the number of S steps, r as well. The total number of steps in n, (c + k) of which are E, k -W, (d + r) -N, and r -S.

r = 1 2 (n -c -d) -k
As words, these walks are permutations of each other. Their total number is n!

(c+k)!k!(d+r)!r! . Lemma 1 The generating function of the walk inversion statistics of n-step walks with k W steps is given by

q k 2 +ck [n] q ! [c + k] q ![ 1 2 (n -c + d) -k] q ![k] q ![ 1 2 (n -c -d) -k] q ! = w∈Pn((c,d);k) q winv(w) (14)
Now, in general, to get to (c, d) from (0, 0) in n steps one might take just one W step, or two, etc. The maximal number of W steps (i.e. no S steps) is

1 2 (n -c -d)

So that

Lemma 2 The walk inversion generating function is w∈Pn((0,0)|(c,d))

q winv(w) = 1 2 (n-c-d) k=0 q k 2 +ck [n] q ! [c + k] q ![ 1 2 (n -c + d) -k] q ![k] q ![ 1 2 (n -c -d) -k] q ! (15)
Now, consider how a walk can end up at (c, d) in n steps, i.e. where could it be at the previous step?

• either at (c -1, d), with the last step E; adding an E step changes winv by

#S + #N + 2#W = r + (d + r) + 2k = d + 2r + 2k = n -c
The contribution of walks coming from the West is

q n-c 1 2 (n-c-d) k=0 q k 2 +(c-1)k [n -1] q ! [c -1 + k] q ! 1 2 (n -c -d) -k q ![k] q ! 1 2 (n -c + d) -k q !
• or at (c, d + 1) with the last step S; adding an S step does not change winv.

The contribution of the walks coming from the North:

1 2 (n-c-d)-1 k=0 q k 2 +ck [n -1] q ! [c + k] q ! 1 2 (n -c + d) -k -1 q ![k] q ! 1 2 (n -c -d) -k -1 q !
Now consider a generic w with blocks of S and N letters: with

w 2 = S . . . S s1
n 1 + n 2 + . . . + r = d + 1 winv(w) -winv( w) = {n 1 (s 1 + k) -n 1 (s 1 -1 + k)} + {n 2 (s 1 + s 2 + k) -n 2 (s 1 + s 2 -1 + k)} + . . . + {r(s 1 + . . . + s i + k) -r(s 1 + . . . + s i -1 + k)} + {(n i -r)(s 1 + . . . + s i + k) -(n i -r)(s 1 + . . . + s i + k)}+ + . . . + {n r (s 1 + . . . + s r ) -n r (s 1 + . . . + s r )} = i n i + r = d + 1 winv( w) = q -(d+1) winv(w)
So the total contribution of negative walks is q winv(w) = w∈Pn((0,0)|(c,d))

q d+1 P n ((0, -2) | (c, d)) = q d+1 n 1 2 (n + 2 + c + d) q n 1 2 (n -2 + c -d) q Hence (6).

Major Walk Index

q wmaj(w) (17)

• w∈P + n ((0,0)|(c,d)) q winv(w) = w∈P + n ((0,0)|(c,d))
q wmaj(w) (18)

7 q-Integers Associated with q-super Ballot Numbers

Computer experiments indicate that there is a family of q-numbers related to several generalizations of q-Catalan. For instance, following [START_REF] Gessel | Super ballot numbers[END_REF] define q-super Ballot numbers

B n,k,r (q) = [k + 2r] q ![2n + k -1] q ! (k -1) q !r q !n q ![n + k + r] q !
Then, I venture to make the following conjecture Conjecture 2 Define a new sequence A n,k,r (q) with A 1,k,r = B 0,k,r (q) through the recurrence (-1) n-1 A n,k,r (q) = q n-1 B n,k,r (q) + n-1 j=1 (-1) j q n-j-1 2n -1 2j -1 q A j,k,r (q)B n-j,k,r (q) (19) then the A n,k,r (q) are polynomials in q with positive integers coefficients for all values of n, k, r > 0.

Example 4

A 2,1,1 (q) = 1 + 2q + 4q 2 + 4q 3 + 3q 4 + q 5

A 2,2,1 (q) = 1 + 3q + 7q 2 + 11q 3 + 13q 4 + 12q 5 + 8q 6 + 4q 7 + q 8

A 2,2,2 (q) = 1 + 3q + 9q 2 + 18q 3 + 33q 4 + 51q 5 + 72q 6 + 89q 7 + 100q 8 + 101q 9 + 93q 10 + 77q 11 + 57q 12 + 38q 13 + 22q 14 + 11q 15 + 4q 16 + q 17

A 3,1,1 (q) = 1 + 3q + 9q 2 + 17q 3 + 28q 4 + 38q 5 + 44q 6 + 43q 7 + 35q 8 + 24q 9 + 13q 10 + 5q 11 + q 12 A 3,2,1 (q) = 1 + 5q + 19q 2 + 51q 3 + 110q 4 + 199q 5 + 307q 6 + 412q 7 + 484q 8 + 499q 9 + 452q 10 + 358q 11 + 245q 12 + 143q 13 + 69q 14 + 26q 15 + 7q 16 + q 17

A 3,2,2 (q) = 1 + 5q + 22q 2 + 68q 3 + 181q 4 + 414q 5 + 848q 6 + 1567q

  Think of a given walk as a word w composed of letters N, S, E, W . Then, the walk inversion statistics is defined Definition 1 winvN (w) = N ∈w #S to the left of N winvW (w) = W ∈w #S + #N + #E to the left of W winvE(w) = E∈w #S + #N + 2#W to the left of E wpinv(w) = winvN (w) + winvW (w) + winvE(w) Example 3 Here are the inversions of the walks (from left to right) on Fig. 1:

Fig. 1 :

 1 Fig.1: Some walks from (0, 0) to (0, 2) with n = 4 steps.

w2

  s i = dBy swapping the last S in the each string of s i with the last N letter in n i until d + 1 letters N have been moved, transforms w 2

  Setting up the following order S > N > E > W , and with the usual definition of a descent set desN (w) = {i : S occurs as i th letter and N occurs as i + 1 st letter} majN (w) = i∈desN (w) i desE(w) = {i : S or N occur as i th letter and E occurs as i + 1 st letter} majE(w) = i∈desE(w) i desW (w) = {i : S, N, or E occur as i th letter and W occurs as i + 1 st letter} majW (w) = i∈desW (w) i one can give the following Definition 2 wmaj(w) = majN (w) + majE(w) + majW (w) + #E × #W (16) Notice the unusual last term... Nevertheless, experiments show that winv and wmaj are equally distributed over all lattice walks as well as over upper half-plane walks. Conjecture 1 • w∈Pn((0,0)|(c,d))

  7 + 2652q 8 + 4134q 9 + 5980q 10 + 8058q 11 + 10155q 12 + 11997q 13 + 13313q 14 + 13892q 15 + 13639q 16 + 12597q 17 + + 10937q 18 + 8913q 19 + 6802q 20 + 4845q 21 + 3206q 22 + 1958q 23 + 1094q 24 + +552q 25 + 247q 26 + 95q 27 + 30q 28 + 7q 29 + q 30

Acknowledgements

I would like to thank Jean-Christophe Novelli and Jean-Yves Thibon for an interesting and useful conversation.

• or at (c + 1, d) with the last step W; adding a W step changes winv by #S + #N + #E = r + (d + r)

The contribution of walks coming from the East is

• or at (c, d -1) with the last step N; an addition of an N step with r prior S steps changes winv by

The contribution of the walks coming from the South:

The sum of these contributions gives a recursion that establishes (5).

Upper Half-Plane walks

Following the logic of walks reflection [START_REF] Guy | Lattice paths, reflections, and dimension-changing bijections[END_REF], to every negative path from (0, 0) to (c, d) will associate a walk from (-2, 0) to (c, d) so that the change in winv is the same for every walk.

Here is the algorithm.

1. Separate each negative walk in two segments w = w 1 • w 2 , where • means concatenation of words:

(a) w 1 : the part of the walk that starts at (0, 0) and ends at ( * , 0) (before it dips below the x-axis the first time) (b) w 2 : the rest of the walk that runs from ( * , 0) to (c, d); Notice that w 2 starts with S and necessarily has at least d + 1 N steps. More precisely, if the walk has k S steps, it has d + k N steps.

2. w1 : move w 1 down two steps, so that it starts at (0, -2) and ends at ( * , -2);


Daniel Grau
email: daniel.grau@iutbayonne.univ-pau.fr

GENERALIZATION OF USUAL CAPABILITY INDICES FOR UNILATERAL TOLERANCES

Keywords: Process Capability Indices, Unilateral Tolerances, Non-normal Processes. ''

Capability indices are dimensionless quantities measuring the aptitude of a process to manufacture items whose characteristics must be within a specified tolerance ranges. The usual indices p C , pk C , pm C , and pmk C are used for a process of normal distribution and a target located at the center of the tolerance interval. Various indices derived from the previous family allow to consider more complex situations when asymmetrical tolerances and non-normal distributions are taken into account. In this paper we study the case where a single tolerance is imposed because the shifts in the direction of this tolerance appear much more serious than in the opposite direction. We propose a family of four indices having interpretations and properties similar to those of the usual family.

Introduction

The quality of an industrial process is assured by the monitoring of one or more variables of interest. The process will be considered of good quality if it is able to produce items whose variable of interest is within the tolerances L and U (Lower and Upper tolerance limits) and close to a specified target value T. Accordingly, the capability indices used to measure the quality of the process are linked to the location and the dispersion of the supervised variable. For a target centered in its tolerance interval and a variable of normal distribution, the first work of Kane [START_REF] Kane | Process Capability Indices[END_REF] was completed to lead to a family of four indices generally used. X being the supervised characteristic of normal distribution N(μ,σ), one defines .

When asymmetrical tolerances and normal data are concerned, many proposals have been made, the most coherent of which as the generalization of the usual family, is given by the family '' p C , " pk C , '' pm C , and " pmk C introduced by Pearn, Chen, and Lin in various articles [START_REF] Chen | A new generalization of pm C for processes with asymmetric tolerances[END_REF][START_REF] Chen | Capability indices for processes with asymmetric tolerances[END_REF][START_REF] Pearn | Estimating process capability indices for non-Normal Pearsonian populations[END_REF][START_REF] Pearn | On the generalizations of the capability index pmk C for asymmetric tolerances[END_REF][START_REF] Pearn | Estimating process capability index " pmk C for asymmetric tolerances: distributional properties[END_REF].

In the case of non-normal distributions, Clements [START_REF] Clements | Process capability calculations for non-normal distributions[END_REF] proposes to generalize the indices p C and pk C replacing the mean μ by the median M and the dispersion 6σ by Up -Lp where Up and Lp are the 99.865 and 0.135 percentiles. In the same way, Pearn and Kotz [START_REF] Pearn | Application of Clements' method for calculating second and third generation process capability indices for Non-normal personian populations[END_REF] provide a extension of the indices pm C and pmk C . However let us note that considering the difficulty to obtain reliable estimations of Up and Lp, many other proposals have been provided the bibliography of which can be found in the articles of Tang and Than [START_REF] Shore | Non-normal populations in quality applications: a revisited perspective[END_REF], Mac Cormack, Harris, Hurwitz, and Spagon [START_REF] Mccormack | Capability indices for non-normal data[END_REF], or Ding [START_REF] Ding | A method of estimating the process capability index from the first four moments of non-normal data[END_REF].

The literature related to the processes limited by two tolerance limits is important, but it is not the same in the less frequent situation where only one limit is imposed. In this case two situations can be considered. The first one occurs when the variable of interest, because of its nature, cannot exceed a certain level which represents the target of the process. It is the case for example for concentricity or circularity where the observed measure is obviously positive or null, the target being equal to 0. The second one occurs when a drift of the mean in a direction appears much less serious to the user, so that he is induced to define only one single tolerance. It is this second situation which is the subject of this paper. We recall the rare indices which one finds in the literature, then propose a family of four indices having interpretations and properties, similar to the ones of the usual family p C , pk C , pm C , and pmk C . For normal data, the densities and the moments of the natural estimators are given. The expressions used in the case of a normal distribution can be easily generalized to the case of non-normal distributions by replacing the mean μ by the median M, and the natural variation 3σ by Up -M or M -Lp. The estimation of the extreme percentiles Up and Lp is however far from reliable on samples of reasonable size when one uses the traditional moment estimation, as Clements does [START_REF] Clements | Process capability calculations for non-normal distributions[END_REF]. The work of Shore [START_REF] Shore | A new approach to analysing non-normal quality data with application to process capability analysis[END_REF][START_REF] Shore | Approximating an unknown distribution when distribution information is extremely limited[END_REF] enables us to obtain estimations much more reliable which will be developed in an example.

Existing indices

Starting from the definition of ( )

min -, - = 3 pk U L C μ μ σ , Kane [8] defines ( )/3 CPU U μ σ = - and ( ) / 3 CPL L μ σ
=in order to measure the capability of a process in the unilateral tolerance situation. Let us note that the CPU and CPL indices do not take into account the existence of a target which, for the index pk C , is supposedly, implicitedly located at the center of the tolerance interval. When the target is not centered, Kane [START_REF] Grau | On the choice of a capability index for asymmetric tolerances[END_REF] suggests an index referred to as * pk C from which he gets the indices

( ) * 3 CPU U T T μ σ = --- and
( ) * 3 CPL T L T μ σ = ---
, in the case of a unilateral tolerance. In the same way as with the usual indices, the value of these indices is equal to 0 if the previous calculus leads to a negative value. Chan, Cheng and Spiring [START_REF] Chan | A new measure of process capability : C pm[END_REF], in the case where one-sided tolerance is required, have suggested generalizing pm C to ( )

* 2 2 3 pmu U T C T σ μ - = + -

and

( )

* 2 2 3 pml T L C T σ μ - = + - .
On the same principle, Vänmann [START_REF] Vännman | Families of capability indices for one-sided specification limits[END_REF] suggests generalizing pmk C to

( ) 2 2 3 pmku U C T μ σ μ - = + - and ( ) 2 2 3 pmkl L C T μ σ μ - = + -
. Moreover in order to generalize all the previous suggestions, Vänmann [START_REF] Vännman | Families of capability indices for one-sided specification limits[END_REF] puts forward two families of indices, , although these indices are not maximum when µ is on the target T (fig 1). This drawback is not deemed too serious by the author, since a shift of μ away from T to the left (for

2 2 ( , ) 3
( ) pau U u T C u v v T μ μ σ μ -- - = + - and 2 2 ( , ) 3
( ) pal L u T C u v v T μ μ σ μ -- - = + - on the one hand, 2 2 ( , ) 3
( ) pvu U T u T C u v v T μ σ μ -- - = + - and 2 2 ( , ) 3 (
( , ) pau C u v ) is less
important considering the expected percentage of nonconforming than a shift of μ away from T towards U.

Suggestions of indices for a normal distribution

Our items when the mean is on the target, and is equal to 1 for a proportion of 0,27% of non conforming. Moreover it is meant as the potential capability of the process, that is to say the maximum capability which one can obtain for a given dispersion, when the mean is on the target. The modern standard of quality deems that a process should not be considered capable if μ is far away from T, even if σ is small. p C which is unrelated to T does not satisfy this requirement. For this reason the indices pk C , pm C , and pmk C , which take into account the location of the process mean as well as the process variability, have been introduced. The 3 of them are maximum and equal to p C when the mean is on the target. The deviation of the mean is taken linearly into account by pk C , so that it is null when the mean reaches the tolerance limits. Thus, the ratio pk p C C allows to determine the position of the mean between the target and the tolerance towards which it deviates. pm C takes the deviation into account in a quadratic way. Thus, it is not null at the tolerance limits, but takes the same value. pmk C being the combination of pk C and pm C allows to take the deviation into account in a "quadratic" way and to obtain a null index when the mean reaches one of the tolerances. Thus, in the case of unilateral tolerance, in order to keep interpretations similar to the bilateral case, we will require a) that the potential capability indices pu C and pl C take value 1 for a 0,135% proportion of non conforming, when the mean is on the target b) that the indices of capability taking the position of the mean related to the target into account, are maximum and equal to potential capability when the mean is on the target. c) that the indices pku C and pkl C decrease linearly and take value 0 when the mean reaches the tolerance limit d) that the indices pmu C and pml C decrease in a quadratic way e) that the indices pmku C and pmkl C decrease in a "quadratic" way and take value 0 when the mean reaches the tolerance limit. The main difficulty in the building of indices lies in the fact that we have no knowledge of the risk taken when the mean moves away from the target in the opposite direction to the tolerance limit. However, even if there is no tolerance limit, obviously, a production manager cannot accept a too large deviation in a direction even if, a priori, it does not seem too serious to him. Thus, it appears fundamental to us that he should quantify the "not too serious". Is this twice, five times, ten times less serious? We consider thereafter that it has been decided that the risk is k time less serious. The choice of the constant k (>1) being rather approximate we require a last condition: f) when the means deviates towards the tolerance limit, the capability indices must be independent of the choice of k. Let us consider for the moment the case of an upper tolerance U, and note

( ) ( ) ( ) ( ) ( ) ( ) max / , / u T U T T k U T α μ μ = - - - - , and
( )

u u U T δ α σ = -
. The new indices suggested are defined by :

3 pu U T C σ - = , ( )
1 pku u pu C C α = - ( ) ( ) max , / 3
U T T T k μ μ σ -- - - = ,
( )

1 2 2 1 pmu u pu C C δ - = + ( ) ( ) 2 2 3 max , / U T T T k σ μ μ - = ⎡ ⎤ + - - ⎣ ⎦ , ( ) ( ) ( ) ( ) 1 1 2 2 2 2 1 1 1 1 pmku u pmu u pku u u pu C C C C α δ α δ - - = - = + = - + ( ) ( ) ( ) ( ) 2 2 max , / 3 max , / U T T T k T T k μ μ σ μ μ -- - - = ⎡ ⎤ + - - ⎣ ⎦
.

By using notations similar to Vänmann's [START_REF] Vännman | Families of capability indices for one-sided specification limits[END_REF], we can write the general formula

( ) ( ) ( ) ( ) 2 2 max , / ( , ) 3 m a x , / pu U T u T T k C u v v T T k μ μ σ μ μ -- - - = ⎡ ⎤ + - - ⎣ ⎦ * 2 2 * 3 u u U T uA vA σ -- = +
, where

( ) ( ) * max , / u A T T k μ μ = - -
. This expression gives the four indices for the couples ( , ) u v = (0,0), (1,0), (0,1) and (1,1) again. Note that the letter u used in subscript is an abbreviation of the word upper and is independent of the first parameter of the indices family. The indices ( , )

pu C u v are identical Vännman's ( , ) pvu C u v indices [23] when 0 T μ -> , but are different when 0 T μ -< . It is obvious that when T μ = and pu C = 1, 3 U T σ -=
, and a proportion of 0.135% of items according to the variations of the mean μ, in the case where the deviation to the left is considered to be three times less important than to the right. In a similar way, if the single tolerance is a lower limit L, we obtain the general formulation

is thus beyond U, that satisfies a). If T μ = , then 0 u u α δ = = , thus pku C = pmu C = pmku C = pu C , which satisfies b). If U μ = , pku C = pmku C = 0.
( ) ( ) ( ) ( ) 2 2 max / , ( , ) 3 m a x / , pl T L u T k T C u v v T k T μ μ σ μ μ -- - - = ⎡ ⎤ + - - ⎣ ⎦ * 2 2 * 3 l l T L uA vA σ -- = + . Assume that ( ) ( ) ( )( ) ( ) ( ) max / , / l T k T L T T L α μ μ = - - - - , and
( )

l l T L δ α σ = -
, we find similar algebraic expressions, ( )

1 pkl l pl C C α = - , ( )
1 2 2 1 pml l pl C C δ - = + , and
( )

1 pmkl l pml C C α = - ( ) ( ) ( ) 1 1 2 2 2 2 1 1 1 l p k l l l p l C C δ α δ - - = + = - +
, as well as the same properties stated in the case of an upper tolerance.

Suggestions of indices for a non-normal distribution

As in the bilateral case, we replace the mean μ by the median M and the natural variation 3σ by p U M or p M L according to each case. Hence the formulas

( ) ( ) ( ) ( ) 2 2 max , / ( , ) 3 m a x , / 3 pu p U T u M T T M k C u v U M v M T T M k -- - - = - ⎛ ⎞ ⎡ ⎤ + - - ⎜ ⎟ ⎣ ⎦ ⎝ ⎠ , 0 0,2 0,4 0,6 0,8 1
( ) ( ) ( ) 2 2 max / ; ( , ) 3 m a x /; 3 pl p T L u M T k T M C u v M L v M T k T M -- - - = - ⎛ ⎞ ⎡ ⎤ + - - ⎜ ⎟ ⎣ ⎦ ⎝ ⎠ . When ( , ) u v = (0,0), (
( ) ( ) ( ) ( ) ( ) max / , / u M T U T T M k U T α = - - - - , ( ) 3 ( )
u u p U T U M δ α = - - , ( ) ( ) ( ) ( ) ( ) max / , / l M T k T L T M T L α = - - - - , and
( ) 3 ( ) l l p T L M L δ α = - -
, we find the same algebraical expressions and thus the same properties as those stated in the case of a normal distribution. Practically, to be able to use these results we need to estimate the percentiles M, p U , and p L . The determination of a percentile is easy when the distribution from which the observations ensue is known. To identify this distribution, the most usual method consists in fitting the distribution to a member of a family covering a great number of usual distributions. To achieve this adjustment the method of the moments requires the identification of 3 or 4 parameters according to the family being used. If the estimate of the mean and of the standard deviation is rather reliable, it is no longer the same for skewness and kurtosis, which are manifestly known for their great dispersion. Thence, the resulting estimates are not at all reliable for the extreme percentiles p U and p L . Thus for a non negative variable, Shore [START_REF] Shore | A new approach to analysing non-normal quality data with application to process capability analysis[END_REF] suggests approaching the p percentile p Q by the relation

1 2 2 1 when 1 2 1 ln when 1 2 1 B p p A p p Q p A B p p ⎧ ⎛ ⎞ ⎪ < ⎜ ⎟ - ⎪ ⎝ ⎠ = ⎨ ⎛ ⎞ ⎪ + ≥ ⎜ ⎟ ⎪ - ⎝ ⎠ ⎩
. By identification of the complete moments ( ) ( ) ( )

i i i x M M x dF x x f x d x ≥ = = ∫ ∫
of order i smaller or equal to 2, he obtains the coefficients

[ ] { } 1 1 1 exp 2 ( ) 0.6931 A Z B μ = + , [ ] { } 0.5 2 1 2 1 1.7099 0.5 ( ) ( ) B Z Z μ μ = - , [ ] 2 2 1 2 2 ( ) 2 ( ) 0.6840 M Y M Y A - = , and
[ ] 2 1 2 2 ( ) 0.6931 B M Y A = - where ln( ) pour 0 pour Y Y M Z Y M < ⎧ = ⎨ ≥ ⎩ , Y the subjacent distribution, ( ) i Z
μ the ith moment of Z, and ( ) i M Y the ith partial moment of Y. Shore's method leads to better estimates of the percentiles than those obtained by Clements's method [START_REF] Chen | Capability indices for processes with asymmetric tolerances[END_REF], insofar as the expected values being similar, the mean squared error is much lower by Shore's method [START_REF] Shore | A new approach to analysing non-normal quality data with application to process capability analysis[END_REF][START_REF] Shore | Approximating an unknown distribution when distribution information is extremely limited[END_REF][START_REF] Shore | Non-normal populations in quality applications: a revisited perspective[END_REF].

Distribution and moments of the estimators of the indices suggested for a normal distribution.

The studied characteristic of the process is supposed normally distributed with mean μ and variance σ² . Two natural estimators of 3

u pu n n u U T uA C u v S vA - - -- = + ,
where

{ } * ˆmax , ( ) / u A X T T X k = - - , ( ) 1 n i i X X n = = ∑ , ( ) 2 2 1 n n i i S X X n = = - ∑ , and
( ) ( ) 2 2 1 1 1 n n i i S X X n - = = - - ∑ .
The two estimators are related by In the case of a single upper tolerance U, considering that the risk of a deviation towards the left of the target is k time less serious than towards the upper limit U can be interpreted as the positioning of a lower limit L so that l u T L D kD -= = . In these conditions ( )

( ) ( ) ( ) ( ) 1 2 , 1 , ˆ( , ) 1 ,
1 2 u d k D = + , * u d D = , ( ) { } * * max , u A A T T k μ μ = = - - , ( ) * * * 1 2 A dA d k A = = + , and
( ) ( ) * * * 2 " * 2 2 2 * 2 * 2
( , ) , [START_REF] Chen | A new generalization of pm C for processes with asymmetric tolerances[END_REF] 3

u u pu p u D uA d uA C u v C u v d d vA v d d A σ σ - - ⎛ ⎞ = = = ⎜ ⎟ ⎝ ⎠ + + ( ) ( ) 2 " , 4 1 p C u v k = + . ( 1
)
Assuming that

p n C u v in the form ( ) ( ) ( ) ( ) * 2 2 '' , 0 0 1 2 ˆ( , ) ( ) ( , ) 3 ! 2 2 r i j j r r i p n n r i j r c a b D e E C u v u i j i j c λ δ γ π - - ∞ = = Γ -Γ ⎛ ⎞ ⎛ ⎞ = - × ⎜ ⎟ ⎜ ⎟ Γ ⎝ ⎠⎝ ⎠ ∑ ∑ , (2)
with

( ) ( ) ( ) * * 2 1 2 1 ( , ) , ; ; 1 , ; ; i i j n u l u l d d i j F a b c z F a b c z D D γ ⎡ ⎤ ⎛ ⎞ ⎛ ⎞ ⎢ ⎥ = +- ⎜ ⎟ ⎜ ⎟ ⎢ ⎥ ⎝ ⎠ ⎝ ⎠ ⎣ ⎦
, where ( ) i u should be interpreted as 1 when i = 0, also for the case u = 0, and

( ) 2 1
, ; ; F a b c z is the Gaussian hypergeometric function (Abramowitz and Stegun [START_REF] Abramowitz | Handbook of Mathematical functions with formulas, graphs, and mathematical tables[END_REF]) with parameters 2 a r = , ( )

1 2 b i j = + + , ( ) 2
c n i j = + + , ( ) 2 1 u u z d D v = - , and
( )

2 1 l l z d D v = - .
In order to distinguish the properties of the estimators of the indices ( , )

pu n C u v , ( )
( ) ( ) ( ) 2 2 , , 0 0 1 2 ˆ( , ) ( ) ( , ) 3 ! 2 2 r i j j r r i u pu n u n r i j r c a b B e E C u v u i j i j c λ δ γ π - - ∞ = = Γ -Γ ⎛ ⎞⎛ ⎞ = - × ⎜ ⎟⎜ ⎟ Γ ⎝ ⎠ ⎝ ⎠ ∑ ∑ , (3) with ( ) ( ) ( ) 2 , 21 2 1
( , ) , ; ;1 1 , ; ;1 /

j i u n i j F a b c v k F a b c v k γ - ⎡ ⎤ = -+ - - ⎣ ⎦ .
In the same way we obtain ( ) , ˆ( , ) ( , ) , ; ;1 / 1 , ; ;1

j i l n i j k F a b c v k F a b c v γ - ⎡ ⎤ = - +- - ⎣ ⎦ .

Estimation and distribution of pu C and pl C

As previously, if we consider that the choice of the constant k can be interpreted as the positioning of a lower limit L so that ˆp n C -given by Kotz and Lovelace [START_REF] Kotz | Process Capability Indices in Theory and Practice[END_REF], we obtain

( ) ( ) ( ) 2 , 1 ( 1)/2 ( 1)/2 ˆ( 3)/2 ( 1) ( ) , 0 ( 1) 2 2 pu pu n n n n C x pu n C pu C n f x e x C n x - - -- - ⎛ ⎞ - = > ⎜ ⎟ Γ - ⎝ ⎠ ,
and ( ) (

) ( ) ( ) ( ) ( ) 2 , 1 1 2 ˆ( 1) 2 1 2 r r r pu n pu n r E C n C n - Γ -- = - Γ - .
In particular ( )

1 , 1 ˆpu n f pu E C b C - - = and ( ) 2 2 , 1 1 ˆ3 pu n f pu n V C b C n - - - ⎛ ⎞ = - ⎜ ⎟ - ⎝ ⎠ where ( ) ( ) ( ) ( ) 1 2 2 1 2 2 f n b n n Γ - = -Γ - . Moreover, since ( ) ( ) 1 2
, , 1

ˆ1 pu n pu n C n n C - = - , ( ) ( ) ( )( ) 2 , 1 2 / 2 ˆ( 3)/2 ( ) , 0 ( 1) 2 2 pu pu n n n n C x pu n C pu C n f x e x C n x - - - ⎛ ⎞ = > ⎜ ⎟ Γ - ⎝ ⎠ , and ( ) ( ) ( ) ( ) ( ) ( ) 2 , 1 2 ˆ2 1 2 r r r pu n pu n r E C n C n Γ -- = Γ - .
In particular ( )

1 , ˆpu n f pu E C c C - = and ( ) 2 2 , ˆ3 pu n f pu n V C c C n - ⎛ ⎞ = - ⎜ ⎟ - ⎝ ⎠ where ( ) ( ) ( ) ( )
1 2 2 2 2 f n c n n Γ - = Γ - .
In a similar way we obtain the density and the moments of

Estimation and distribution of pku C and pkl C

If we consider that the choice of the constant k can be interpreted as the positioning of a lower limit L so that

pku n C J x t dt x f x J x t dt x ∞ ⎧ - < ⎪ = ⎨ ⎪ > ⎩ ∫ ∫ , where ( ) ( ) ( ) 2 2 2 2 1 1 1 2 ( , ) 3 3 u u u K Y u u B t B t B J x t f f B t x x x ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ - - ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ = ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎝ ⎠ ⎝ ⎠ ⎝ ⎠
, and

( ) ( ) ( ) 1
u pku n u B C B J x t dt x f x J x t dt x ∞ ⎧ - < ⎪ = ⎨ ⎪ > ⎩ ∫ ∫ , where ( ) 2 2 ' 1 2 ( , ) 3 3 u u K Y u B t B t J x t f f t x x x ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ - - ⎜ ⎟ = ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎝ ⎠ ⎝ ⎠ ⎝ ⎠ . Since ( ) ( ) 1 2
, 1 ,

ˆ1 pku n pku n C n n C -= - , we deduce , 1 1 1 ˆ1 1 0 ( , ) , 0 ( ) ( , ) , 0 pku n C L x t dt x f x L x t dt x - ∞ ⎧ - < ⎪ = ⎨ ⎪ > ⎩ ∫ ∫ , where ( ) ( ) ( ) 2 2 2 2 1 1 1 2 1 1 ( , ) 3 3
u u u K Y u u B t B t B n n L x t f f B t n x x n x ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ - - - - ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ = ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎝ ⎠ ⎝ ⎠ ⎝ ⎠ . Since * u D B = , we find the density of '' , 1 , 1 ˆpk n pku n C C - - =
given by Pearn, Lin and Chen [START_REF] Pearn | The " pk C index for asymmetric tolerances: implications and inference[END_REF].

Only the moments of order 1 and 2 of '' , 1

ˆpk n C -are explicitly given by Pearn and Chen [START_REF] Pearn | New generalization of process capability index pk C[END_REF].

Thus, we use the equation (3) for the r-th moment which, in addition, leads to expressions of the first two moments simpler than those given by Pearn and Chen [START_REF] Pearn | New generalization of process capability index pk C[END_REF].

(

ˆ( 1) 3 1 2 2 2 r i r r i u pku n r i n r r B e E C i n λ π - - = Γ -- ⎛ ⎞⎛ ⎞ = - × ⎜ ⎟⎜ ⎟ Γ - ⎝ ⎠ ⎝ ⎠ ∑ ( ) ( ) 2 0 2 1 2 (, ) ! j j u j i j i j j δ γ ∞ = × Γ + + ∑ , ) ( ) ( ) ( ) ( ) 2 , 0 1 2 1
i u i j k γ - = + - . In particular, Grau [8], ( where ( ) ( , ) 1 1 j
( ) 2 1 2 1 , 1 ˆ3 2 pku n f pku k e E C c C n δ δ δ π - - -⎡ ⎤ ⎛ ⎞ + = + Φ - - ⎢ ⎥ ⎜ ⎟ ⎜ ⎟ ⎢ ⎥ ⎝ ⎠ ⎣ ⎦ , )
2 1 2 2 2 , 2 1 ˆ( 3) 9 2 pku n pku U T k n e E C C n n δ δ δ σ π - - ⎡ - + ⎛ ⎞ ⎢ = - -Φ- ⎜ ⎟ ⎜ ⎟ -⎢ ⎝ ⎠ ⎣ ( ) ( ) ( ) { } 2 2 2 2 1 1 1 1 2 18 9 2 2 k k e n n δ δ δ δ δ δ π - - - ⎤ - ⎛ ⎞ + ⎥ + + -Φ - + -Φ - ⎜ ⎟ ⎜ ⎟ ⎥ ⎝ ⎠ ⎦ . ( ) , 1 ˆr pku n E C -, ( ) ( )( ) ( )
ˆpku n E C -and ( )

ˆpku n E C -are obtained without difficulty since (

Estimation and distribution of pmu C and pml C

If we consider that the choice of the constant k can be interpreted as the positioning of a lower limit L so that

l u T L D kD -= = , then ( ) 2 '' * (0,1) 0, pmu pu p C C C d d ⎛ ⎞ = = ⎜ ⎟ ⎝ ⎠ according to (1).
From the appendix, , ) , 0

pmu n C f x J x t dt x = > ∫ , where ( ) ( ) ( ) ( ) 2 1 2 ( , ) ( ) 1 ( ) 2 ( )
K Y u J x t f G x t f G x t x G x - = - , and ( ) ( ) 2 ( ) 3 u
G x B x = , or , ( ) ' ˆ2 0
( ) ( , ) , 0

pmu n G x C f x J x t dt x = > ∫ , where
( ) ( ) ' 1 2 ( , ) ( ) 2 ( ) K Y u J x t f G x t f t x G x - = - . Since ( ) ( ) ( ) ( ) 1 2
, 1 , ˆ1 0 , 1

pmu n pu n C n n C n n -= - - , we deduce , 1 1 ˆ2 0
( ) ( , ) , 0

pmu n C f x L x t dt x - = > ∫ where ( ) ( ) ( ) ( ) ( ) ( ) 2 1 2 ( , ) ( 1 ( ) 1 ( ) 2 ( 1 ( )
K Y u L x t f n n G x t f G x t n n x G x - = - - - .
The moments are obtained from the equation (

, , 0

1 2 ˆ( ) 3 ! 2 2 r j j r u pmu n u n r j c a b B e E C j j c λ δ γ π - ∞ = Γ -Γ ⎛ ⎞ = × ⎜ ⎟ Γ ⎝ ⎠ ∑ , ( )
( ) ( ) ( ) 2 2 2 , 1 , 1 0 1 1 2 ˆ( ) 3 ! 2 2 r r j j r u pmu n u n r j c a b B n e E C j n j c λ δ γ π - ∞ - - = Γ -Γ - ⎛ ⎞ ⎛ ⎞ = × ⎜ ⎟ ⎜ ⎟ Γ ⎝ ⎠ ⎝ ⎠ ∑ , where 2 a r = , ( 1
) 2 b j = + , ( ) 2 c n j = + , ( ) ( ) 2 , 2 1
( ) 1 1 , ; ;1

j u n j F a b c k γ - = + - - , and
( ) ( ) ( ) 1 1 2 , 1 2 1 2 1 ( ) , ; ; 1 , ; ;1 ( 1)
u n j γ - by ( )( ) ( ) 1 2 1 , 1 2 1 2 1 ( ) , ; ;1 ( 1) 1
, ; ;

j l n j F a b c n n k F a b c n γ -- - - =
--+ -.

Estimation and distribution of pmku C and pmkl C

If we consider that the choice of the constant k can be interpreted as the positioning of a lower limit L so that

l u T L D kD -= = , then ( ) 2 '' * (1,1) 1, pmku pu p C C C d d ⎛ ⎞ = = ⎜ ⎟ ⎝ ⎠ . From the appendix, we obtain , 1 ˆ1 0 1 ( , ) , 0 3 ( ) ( , ) , 0 pmku n C J x t dt x f x J x t dt x ∞ ⎧ - -< < ⎪ = ⎨ ⎪ > ⎩ ∫ ∫ where ( ) 2 2 ( ) ( ) 2 ( ) ( , ) ( ) ( ) 3 3 u u K Y u B tH x B tH x H x J x t f tH x f tH x x x x ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ - - ⎜ ⎟ = - ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎝ ⎠ ⎝ ⎠ ⎝ ⎠
, and

( ) 2 ( ) 1 3 u H x B x = + ⎡ ⎤ ⎣ ⎦ , or , ( ) ˆ( ) 0 1 '( , ) , 0 3 ( ) '( , ) , 0 pmku n H x C H x J x t dt x f x J x t dt x ∞ ⎧ - -< < ⎪ = ⎨ ⎪ > ⎩ ∫ ∫ where 2 2 2 '( , ) ( ) 3 3 u u K Y u B y B y J x t f y f y x x x ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ - - ⎜ ⎟ = - ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎝ ⎠ ⎝ ⎠ ⎝ ⎠ . Since ( ) ( ) ( ) ( ) 1 2 , 1 , ˆ1 1 , 1 pmku n pu n C n n C n n -= - - , we deduce , 1 1 2 1 ˆ1 0 1 ( , ) , 0 3 1 ( ) ( , ) , 0 pmku n C n L x t dt x n f x L x t dt x - ∞ ⎧ ⎛ ⎞ - - < < ⎪ ⎜ ⎟ ⎪ - ⎝ ⎠ = ⎨ ⎪ > ⎪ ⎩ ∫ ∫ where ( ) 2 2 ( ) ( ) 1 2 ( ) 1 ( , ) ( ) ( ) 3 3 u u K Y u B tH x B tH x n H x n L x t f tH x f tH x n x x n x ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ - - - - ⎜ ⎟ ⎜ ⎟ = - ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎝ ⎠ ⎝ ⎠ ⎝ ⎠ ⎝ ⎠
.

The moments are obtained from the equation ( 3): when the deviation takes place on the right, the smaller the risk is, the closer to the potential capability the indices of real capability are.

( ) ( ) ( ) ( ) 2 2 , , 0 0 1 2 ˆ( 1) ( , ) 3 ! 2 2 r i j j r r i u pmku n u n r i j r c a b B e E C i j i j c λ δ γ π - - ∞ = = Γ -Γ ⎛ ⎞⎛ ⎞ = - × ⎜ ⎟⎜ ⎟ Γ ⎝ ⎠ ⎝ ⎠ ∑ ∑ , ( )
( ) ( ) ( ) 2 2 2 , 1 , 1 0 0 1 1 2 ˆ( 1) ( , ) 3 ! 2 2 r i r j j r r i u pmku n u n r i j r c a b B n e E C i j i n j c λ δ γ π - - ∞ - - = = Γ -Γ ⎛ ⎞ - ⎛ ⎞ ⎛ ⎞ = - × ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ Γ ⎝ ⎠ ⎝ ⎠ ⎝ ⎠ ∑ ∑ ,

Conclusion

In this paper we first review the existing generalizations of the basic capability indices p C , pk C , pm C , and pmk C which have been proposed to handle one-sided tolerances processes. In this situation, the risk of a deviation towards the side opposed to the limit of tolerance is not considered very serious and thus, in general, not quantified. However, for problems of cost among other things, this risk cannot be completely ignored. When a ratio is established, at least approximately, between the risks taken for deviations to the left and to the right of the target, we introduce indices of capability preserving the properties and interpretations of the . For a process of normal distribution, the densities and moments of the estimators are given. They ensue from the properties established for the family " ( , ) p C u v , used in the case of asymmetrical tolerances. When the distribution of the process is not normal, we propose simple extensions using the median and the quantiles of order 0.00135 and 0.99865. Finally an example shows the way to calculate these quantities on a real example of non-normal data, using the method of Shore [START_REF] Pearn | The " pk C index for asymmetric tolerances: implications and inference[END_REF] in order to estimate the extreme quantiles.

K Y D h tK x D h tK x K x J x t f vtK x f tK x x x x ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ - - ⎜ ⎟ = - ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎝ ⎠ ⎝ ⎠ ⎝ ⎠ .
Let us note that when u > 0 and v = 0, the previous expression is still valid if we consider that ( )

3 h v - =-∞.
For u = 0 and v > 0, the expression is also valid when x > 0, the density being null when x < 0.

In the particular case where u > 0, v = 0, we obtain [ ]

K Y D t D t D D J x t f f t x u x u x ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ - - ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ = ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎝ ⎠ ⎝ ⎠ ⎜ ⎟ ⎝ ⎠ ⎝ ⎠ ⎝ ⎠ ⎝ ⎠ .
In the particular case where 0 u = , v > 0, we obtain

K Y D D t D J x t f t f x x v xv x ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ ⎜ ⎟ ⎜ ⎟ = - ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎝ ⎠ ⎝ ⎠ ⎝ ⎠ ⎝ ⎠ ⎝ ⎠
.

  points out, the fact that there is an unilateral tolerance can be interpreted in such a way that a shift of μ away from T towards that tolerance is more serious than a shift of μ towards the opposite side. The indices derived from ( , ) pvu C u v and ( , ) pvl C u v , which are symmetrical around the target are thus of little interest. From the properties of the estimators of the indices ( , )

  Figure 1. (0, 4) pau C

.

  In addition, from the previous algebraic expressions, when μ moves away from the target, it is obvious that pku C decreases linearly and pmu C in a quadratic way, hence the conditions c), d), and e). For 0 T μ -> , μ moves away towards U, and ( , ) pu C u v is thus independent of k, which satisfies the condition f). Finally, let us notice some additional properties identical to those of the usual family. From the previous algebraic relations, we have obviously pu to pu C , gives a precise idea of the position of the mean in the [ ] ; T U interval. Indeed, if / for h = ½ by example, the mean is halfway between the target and the tolerance limit. For T Thus a pmu C value of 1 and T μ > , implies that the process mean μ is in the middle third of the interval [T;U]. For T T μ > , implies that the process mean μ is in the middle fourth of the interval [T;U]. To visualize the properties of the four indices, figure 2 represents the evolution of pu C , pku C , pmu C , and pmku C

Figure 2

 2 Figure 2. pu C , pku C , pmu C

  can be considered, differing in the way the variance σ² is estimated. We define the estimators ,

  properties of these estimators is facilitated insofar as ( , ) pu C u v can be expressed according to Chen's and Pearn's '' ( , ) p C u v index[START_REF] Chen | Capability indices for processes with asymmetric tolerances[END_REF]. Let us recall that for an interval [L;U] and a target T not centered, they introduce the family

  that case is equal to * D . From relations (1) and (2) we deduce the r-th moment of , ˆ( , )

Figure 3 .

 3 Figure 3. Histogram of the data

  Figure 3 gives the histogram of the 86 observations studied. A khi square test carried out on the classes of this histogram gives a p-value of 0.003. This p-value leads us to reject the normality of the observations. Thus we use the indices defined for a non-normal distribution and estimate the quantiles by the method of Shore[START_REF] Pearn | The " pk C index for asymmetric tolerances: implications and inference[END_REF]. We obtain M = 685, 1 unit is below the tolerance, but that the median estimated at 685 ppm is largely above the target T = 480 ppm. However, even if the company assesses that this deviation is less serious than in the other direction, the resulting additional cost requires the use of indices of real capability taking into account the position of the median according to the target. As an example we will consider the 2 situations where the gravity was judged 3 times (k = 3), then 10 times (k = 10) less important. For k=3, we obtain ˆpkl

	660 700 685 490 610 685 590 620 700 730 750 780 730 770 760 780 640 830 785
	780 680 650 585 650 600 610 640 640 575 630 610 665 690 650 640 645 630 700
	800 685 650 675 640 655 610 625 580 610
					A = 677.715,
	1 B = 0.050, 2 A = 48.307, 2 B = 695.712, from which 0.00135 L	= 486.606, 0.99865 Û	=1014.840,
	and ˆpl C = 0.40. The low value of ˆpl C indicates that the process is potentially not capable
	because the dispersion is too important according to the interval [ ] ; L T . The histogram shows
	however that no C = 0.06, ˆpml C =
	0.28, and ˆpmkl C	= 0.04, and for k = 10, ˆpkl C = 0.30, ˆpml C = 0.39, and ˆpmkl C	= 0.29. Of course,
	where	a r =	2	,

(

)

( , ) 1 1 , ; ;1

For

, and , 1 ( , )

, ; ;

Example

To illustrate how these indices can be used, we present a study carried out within the chemistry company Atofina (France). This company manufactures polymer granulates. Before polymerization, an additive, the maleic anhydride, is blended. The target for this additive is 480 ppm and the necessary minimal value is 400 ppm, which represents the lower limit of tolerance. The cost of this additive not being very important, no upper limit has been fixed. Analyses are made regularly on the granulates at the end of the process. 86 values of this variable have been collected and are given below : ( )

the probability density of which ( )

the probability density of a N(0,1), and