O Bodini

A Jacquot
email: alice.jacquot@lip6.fr

BOLTZMANN SAMPLERS FOR COLORED COMBINATORIAL OBJECTS

In this paper, we give a general framework for the Boltzmann generation of colored objects belonging to combinatorial constructible classes. We propose an intuitive notion called profiled objects which allows the sampling of size-colored objects (and also of k-colored objects) although the corresponding class cannot be described by an analytic ordinary generating function.

1

Efficient generation of extremely large objects is needed in many situations. For instance in statistical physics for observing limit behaviors [START_REF] Bodini | Random sampling of plane partitions[END_REF], in biology for understanding and analysing genome properties [START_REF] Ponty | GenRGenS: Software for generating random genomic sequences and structures[END_REF], or in computer sciences for testing programs [START_REF] Denise | Uniform random sampling of traces in very large models[END_REF] or simulating and modelizing Network as Internet [START_REF] Darrasse | Degree distribution of random Apollonian network structures and Boltzmann sampling[END_REF][START_REF] Bodini | Distances in random Apollonian network structures[END_REF]. In 2003, Duchon, Flajolet, Louchard and Schaeffer [START_REF] Duchon | Boltzmann Samplers for the Random Generation of Combinatorial Structures[END_REF] proposed a new model, called Boltzmann model, which leads to systematically construct samplers for random generation of objects in combinatorial constructible classes. These samplers depends on a real parameter x and generate an object a in a combinatorial constructible class A with a probability essentially proportional to x |a| where |a| is the size of a. Hence they draw uniformely in the class A n of all the objects of size n in A. The size of the output is a random variable, and parameter x can be tuned for a targetted mean value. Moreover using rejection, one can obtain exact size samplers or approximate size samplers. This new approach differs from the "recursive method" introduced by Nijenhuis and Wilf [START_REF] Nijenhuis | Combinatorial Algorithms[END_REF] by giving the possibility of relaxing the constraint of an exact size for the output and this implies a significant gain in complexity: no preprocessing phase is needed and expected time complexity is linear in the size of the output.

Boltzmann model has been described both in the cases of unlabelled combinatorial constructible (also called specifiable or decomposable) classes [START_REF] Duchon | Boltzmann Samplers for the Random Generation of Combinatorial Structures[END_REF] and labelled combinatorial constructible classes [START_REF] Duchon | Boltzmann Samplers for the Random Generation of Combinatorial Structures[END_REF][START_REF] Flajolet | Boltzmann Sampling of Unlabelled Structures[END_REF], for the most classical constructions (+, ×, Seq, Set, Cyc,...). In this paper, we are interested in the generation under Boltzmann model of size-colored combinatorial objects. Let a be a combinatorial object with n atoms, we say that this object is size-colored or colored if each of its atoms can be colored with a color in {1, ..., n}. Our main motivation for this study stems from the following situation : Consider that the construction of an object of size n is distributed to n heterogenous processors. Each processors signs the atoms that it has build. A size-colored object is exactly a possible way to build such an object and we would like to highlight some properties about it. In order to do that, we are going to deal with well-known k-colored combinatorial object (in this case, each atom can be colored with a color in {1, ..., k}, and k does not depend on the size). k-colored classes can be found in numerous problems as the k-colored necklaces [START_REF] Fredricksen | Necklaces of beads in k colors and k-ary de Bruijn sequences[END_REF], expression trees with k types of n-ary functions, k-colored planar trees, k-colored Motzkin paths [START_REF] Sapounakis | On k-colored Motzkin words[END_REF],... For instance, all the 2-colored non-planar general trees of size 3 are :

1 1 1 1 1 2 1 2 1 1 2 2 2 1 1 2 1 2 2 2 1 2 2 2 1 1 1 1 1 2 (≡ 1 2 1 ) 1 2 2 2 1 1 2 1 2 (≡ 2 2 1 ) 2 2 2
Each object has to be drawn with the same probability 1 14 . This example points out that symmetries increase the difficulty to build an uniform sampler. That can be also observed by comparing Boltzmann sampler codes for labelled and unlabelled structures. In a naive approach, we could deal with in the classical Boltzmann model by duplicating k times atoms, but we give here a more general and efficient point of view. In particular, we obtain a relatively compressed storage that we explain in a later section and we can postpone the draw of the colors to avoid the unnecessary coloration during the rejection phase.

A profiled object is by definition an object associated with a set-partition of its atoms. This concept is derived from Polya theory [START_REF] Bergeron | Combinatorial species and tree-like structures[END_REF]. We prove that this structure is lifted to all k-colorations. Roughly speeking, the atoms belonging the same partition-class could be interpreted as having the same colors. More precisely, for every k, a sampler for profiled objects can be specialised (by a good choice of the parameters) to become a sampler for any k-colored objects, so that, in a sense, our model unifies all k-colorations. Espacially, profiled object samplers can be adapted to efficient sampling of colored object in approximative size. Profiles enable us to generate colored objects with Boltzmann methods even if the ordinary generating function is not analytic in 0 (which is an obstruction in classical Boltzmann theory). For instance, let A be the unlabelled constructible class Seq(Z), it is well known that the ordinary generating function is 1/(1z). In this case, the ordinary generating function for the class à of colored objects is k≥0 n n z n which is clearly not analytic in 0. At first sight, it seems impossible to have a Boltzmann-type sampler for this class, since the parameter x has to be in the disk of convergence of the generating function.

This paper is organised in four sections. The first section is devoted to the definitions of various taggings for combinatorial classes. We define a general framework, in terms of language, that allows to describe unlabelled and labelled classes as well as less studied classes such as semilabelled or colored classes. We also recall the notion of constructible classes which is central for Boltzmann sampler theory. The second section adresses the notion of profiled objects. We define the generating function associated to a profiled combinatorial class and express its relation with the generating functions of the associated k-colored classes.

In the third section, we construct Boltzmann samplers for the profiled combinatorial constructible classes and we show how to use it to obtain samplers for the k-colored combinatorial constructible classes.

In the last section, we propose an approximate size sampler for the colored combinatorial constructible classes. This sampler is based on a filter that allows to transform a sampler for n-colored objects into a sampler for colored objects.

Combinatorial Classes

Combinatorial classes are very well studied and classical objects [START_REF] Flajolet | Analytic Combinatorics[END_REF]. We propose in this section a general framework, in terms of language, that allows to describe extended tagged combinatorial classes. Our approach can be seen as an introduction to a very simplified species theory [START_REF] Bergeron | Combinatorial species and tree-like structures[END_REF]. Let A be the alphabet on the 7 following letters {}[](). The square is called the atom. The other letters correspond to three different types of parentheses.

We denote by L the language on A defined as follows :

•

, {}, (), [] belong to L • ∀k ∈ N * , A 1 , ..., A k ∈ L ⇒ (A 1 A 2 ...A k ) ∈ L, the sequences • ∀k ∈ N * , A 1 , ..., A k ∈ L ⇒ [A 1 A 2 ...A k ] ∈ L, the cyclic sequences • ∀k ∈ N * , A 1 , ..., A k ∈ L ⇒ {A 1 A 2 ...A k } ∈ L,
the multisets The elements of L are called the combinatorial proto-objects. The size of a proto-object A is the number of atoms contained in A. That is to say, the number of occurence of in A. For instance, ({[ ]( )} ) is a combinatorial proto-object of size 5.

Let A be a proto-object, we denote atom(A) the set of the occurences of in A. In particular, |atom(A)| is the size of A and each element of atom(A) corresponds exactly to one occurence of in A.

At this stage, we just have a support but we need to explain the meaning of the cycles and the multisets by some equivalences between proto-objects. In order to do that, let B be a set, a B-colored proto-object is a pair A, f where A is a word of L and f is a function from atom(A) to B. Let a be an atom of A, f (a) is called the color of a. We denote by L B the set of all B-colored proto-objects.

We define the equivalence ≡ B between B-colored proto-objects of L B as follows :

• Two B-colored squares are equivalent if and only if they are the same color :

, f ≡ B , f ′ ⇔ f ( ) = f ′ ( )
• Two sequences are equivalent if their corresponding substructures are equivalent :

∀A 1 , ..., A k , B 1 , ..., B k ∈ L, (A 1 A 2 ...A k ), f ≡ B (B 1 B 2 ...B k ), f ′ ⇔ ∀i, f (Atom(A i )) = f ′ (Atom(B i )) and A i , f | Atom(Ai) ≡ B B i , f ′ | Atom(Bi)
• Two cycles are equivalent if their substructures are equivalent up to a circular shift :

∀A 0 , ..., A k-1 , B 0 , ..., B k-1 ∈ L, [A 0 A 1 ...A k-1 ], f ≡ B [B 0 ...B k-1 ], f ′ ⇔ ∃n∀i, f (Atom(A i )) = f ′ (Atom(B i+n mod k )) and A i , f | Atom(Ai) ≡ B B i+n mod k , f ′ | Atom(B i+n mod k )
• Two sets are equivalent if their substructures are equivalent up to permutations (we denote by S k the symmetric group of order k) :

∀A 0 , ..., A k-1 , B 0 , ..., B k-1 ∈ L, {A 0 ...A k-1 }, f ≡ B {B 0 ...B k-1 }, f ′ ⇔ ∃σ ∈ S k , ∀i, f (Atom(A i )) = f ′ (Atom(B σ(i) )) and A i , f | Atom(Ai) ≡ B B σ(i) , f ′ | Atom(B σ(i) )
The set O B of B-colored combinatorial objects is L B / ≡ B . Now, we can define the fundamental notion of combinatorial classes as follows :

Definition 1.1. A B-colored combinatorial class is a sub-multiset of L B / ≡ B with a finite number of object of each size.
We opt in this definition for a multiset version which avoid the traditionnal problem of the disjoint union. The union A ∪ B of two multisets is the multiset obtained with all the existing elements and where the multiplicity of a in A ∪ B is the sum of the multplicity a in A and the multiplicity of a in B.

The size of a B-colored combinatorial object A is the size of any proto-object which represents it.

Every object of size 0 is called neutral object. For instance, {()()[]} is a neutral object. Clearly, O B contains an infinite number of neutral objects. we carefully avoid the confusion between the empty combinatorial class ∅ and a combinatorial class reduced to a neutral element ǫ.

For example, the following {1, 2}-colored combinatorial class C contains 3 objects. The both objects of size 3 are identical.

C = 1 , 2 1 1 , 1 1 2
Now, we can add some restrictions on f to obtain different types of tagged combinatorial objects. Some of them are classical (unlabelled, labelled), the other ones are more unusual but reasonable. For each of these tagged objects, we can easily define the notion of combinatorial classes.

We essentially study in this paper the notion of colored and k-colored classes. The semilabelled classes are the topic of another work.

Let A be a combinatorial (unlabelled) class, we denote by A n the set of objects of size n.

Constructible combinatorial classes. A constructible combinatorial class

A(Z) is a class which can be build from neutral classes and an atomic class Z by using some of these builders (+,×,Seq,M Set,P Set,Cyc,...). (the builders Seq, M Set, P Set, Cyc cannot be applied to classes having neutral objects.) For instance, M Set(Z × Seq(Z)). We also accept the recursive construction : T = f (T ). These constructions are exactly the ones that we recurrently find in modern theories of combinatorial analysis. We do not develop here the precise grammar of building. This can be found for instance in [START_REF] Flajolet | Analytic Combinatorics[END_REF].

A colored constructible combinatorial class

(resp. k-colored constructible combi- natorial class) is build from a constructible combinatorial class A(Z) as follows : Ã = ∞ n=0 A n (Z 1 + . . .+ Z n ) (resp. A [k] = A(Z 1 + . . .+ Z k ))
. The unique atom of the atomic class Z k corresponds to an atom colored with the color k. Strictly speaking, Ã and A [k] are not combinatorial tagged classes as defined in the previous section. But they can be obviously identify by expressing the colors in terms of function on the atoms.

In the sequel, we denote identically the colored constructible combinatorial class and its associated unlabelled combinatorial class. For instance, we could speak about the colored constructible combinatorial class M Set(Z × Seq(Z)) to say that we consider the colored constructible combinatorial class build from the unlabelled constructible class M Set(Z × Seq(Z)).

Profiled combinatorial classes

Let A be a set, a subset S of P(A) (the set of all parts of A) is called a setpartition of A if and only if the elements of S are disjoint, S does not contain ∅ unless that A = ∅ and the union of elements of S are equal to A.

A profiled combinatorial object a, σ a is a combinatorial object a equiped with a set-partition σ a of atom(a) which represents its profile or symmetry.

Remark : In the classical Polya theory [START_REF] Bergeron | Combinatorial species and tree-like structures[END_REF], we deal with an automorphism s of atom(a) but this is overdimensioned according to what we need. We only want to mark the undistinguished atoms, a partition is clearly sufficient. Definition 2.1. A profiled combinatorial class is a multiset of profiled combinatorial objects with a finite number of object of each size. Now, we can define the product and the diagonal of profiled combinatorial objects as follows :

Product (concatenation). We define the symmetry

σ m of m = b×c as σ b ∪σ c . In other words, b × c, σ b ∪ σ c .
Diagonal. We define δ k a = a...a where a is repeated k times. The symmetry of δ k a is defined as follows : Let {P 1 , ..., P m } be the symmetry of a then the symmetry of δ k a is { i P i 1 , ..., i P i m } where P i 1 corresponds to P i but on the atoms of the i-th occurence of a. For instance, let a, σ a = ({[ ]( )} ), {{1, 3}, {2, 5}, {4}} (the first is linked to the third ...), then δ 2 a, σ a is aa, {{1, 3} ∪ {6, 8}, {2, 5} ∪ {7, 10}, {4} ∪ {9}}

A coloration of a profiled object of size n and symmetry σ is consistant if on each subset of σ every atom has the same color. We also say that a profile is c-admissible for a coloration c if each part of σ is monocolor.

2.1. Constructible profiled combinatorial classes. the constructible profiled combinatorial classes are exactly the classes that we can buld with the following list of operators :

• Atomic class : Z = { }, the set-partition is reduce to the singleton.

• Union : A ∪ B is the multiset-union of the classes.

• Product : A × B = { a × b, σ a ∪ σ b ; a ∈ A, b ∈ B} • Sequence : Seq(A) = ∞ i=0 A i • Diagonal : ∆ k (A) = {δ k a; a ∈ A} • MultiSet : M Set(A) = {{B}; B a concatenation of diagonals of elements in A} • Cycle : Cyc(A) = {[B ]
; B a diagonal of concatened elements of A} A classical tool associated to combinatorial classes is the notion of generating functions. We explain below the building rules for the generating multivariate functions on the infinite many variables s 1 , s 2 , ... associated to constructible profiled combinatorial classes. The variable s i are going to express a set of i linked atoms.

For example, this profiled general non-planar tree of size 14 :

δ 1 δ 2 δ 3 δ 2
has s 2 1 .s 3 2 .s 6 as associated monomial.

In fact, the multivariate generating function associated to constructible profiled combinatorial classes can be defined inductively as follows :

• Neutral class : F E = 1 • Atomic class : F Z = s 1 • Sum : F A+B = F A + F B • Product : F A×B = F A × F B • Sequence : F Seq(A) = 1 1 -F A • Diagonal : F ∆ k (A) (s 1 , s 2 , ...) = F A (s k , s 2k , ...) • MultiSet : F MSet(A) = exp k≥1 1 k F ∆ k (A) • Cycle : F Cyc(A) = k≥1 -ϕ(k) k ln(1 -F ∆ k (A) )
Let us notice that F A is not an enumerative generating function for the profiled objects in A. But it has the following interesting property. Let us put f A (x, t) = F A (t.x, t.x 2 , ..., t.x k , ...). It is a classical result of Polya theory that [x n ]f A (x, t) = |A n (Z 1 + . . . + Z t )|. The subtitution of s i by t.x i only says that the set of i linked atoms represented by s i can exactly be colored in t different ways and it must be considered as an object of size x i . So, the function f A (x, t) is the ordinary generating function for the t-colored combinatorial class A [t] . In a sense, the generating function of F A contains the informations of all the generating functions for the t-colored combinatorial classes. In fact, this multivariate generating function is generally called cycle index sum and it is also fundamental in [START_REF] Bodirsky | An unbiased pointing operator for unlabeled structures, with applications to counting and sampling[END_REF]. For instance, consider S = M set(Z), the first terms of the profiled generating function are F MSet(Z) = 1 + s 1 + s 2 1 /2 + s 2 /2 + s 3 1 /6 + s 1 s 2 /2 + s 3 /3 + .... To obtain the enumerative generating function for the 3-colored M set(Z), it suffices to replace s i by 3x i . So, we find F MSet(Z) = 1 + 3x + 6x 2 + 10x 3 + ... Remark : In constructive profiled classes, every symetries are only obtained by the diagonal operator. So, in the implementation, we do not need to stock the partition, we simply keep the diagonals unexpanded. That's why our profiled samplers return only an "object" a, instead of a couple a, σ as in our proofs. Moreover, this choice induces a storage gain, as big as the object has symmetries.

Probability and Boltzmann Samplers

The principle of Boltzmann samplers can be describe as follows : Let A be a combinatorial unlabelled class and A(x) its ordinary generating function. Consider a non negative real number x in the convergence disk of A(x), a Boltzmann sampler ΓA is a random generator that draws each object a ∈ A with probability P(a) =

x |a| A(x) . There are simple rules, described in [START_REF] Duchon | Boltzmann Samplers for the Random Generation of Combinatorial Structures[END_REF] to build automatically Boltzmann samplers from the combinatorial specification of A.

For our purpose, we want to draw t-colored objects coming from a specified class A(Z) with the following Boltzmann probability P t,x (a) =

x |a| f A (x, t) .

We produce samplers for (non colored) profiled objects with the following Boltzmann distribution : the probability to obtain a profiled object a, σ such that σ

has n i parts of size i is [s n1 1 s n2 2 ...]F A (s (n)∈N * ).s n1 1 s n2 2 ... F A (s (n)∈N * )
. We then prove that after a consistant coloration and a good choice of the parameters, we also obtain a Boltzmann sampler for the t-colored objects. The notion of powersets is not very relevant on profiled combinatorial classes. Indeed, in a profiled object, some atoms are undistinguished, but there is no information on distinguished atoms, they can be the similar or not. Below, a tabular with the classical distributions of probability and the design rules for basic sampler constructions where ΓA designs a Boltzmann sampler for the class A.

Distribution Notation Definition Bernoulli

Bern(p) P(0) = 1p and P(1) = p (with 0 ≤ p ≤ 1) Geometric Geom(λ) Input: the parameters s 1 , s 2 ... Output: a multiset. let K be a random variable in N * verifying

P(k) = λ k (1 -λ) (with k ∈ N and 0 ≤ λ < 1) Poisson Pois(λ) P(k) = e -λ λ k k! (with k ∈ N and λ ∈ R + * ) Positive Poisson Pois ≥0 (λ) P(k) = 1 e λ -1 λ k k! (with k ∈ N * and λ ∈ R + * )
1 P(K ≤ k) = j>k exp( 1 j F A (s j , s 2j , ...))
Draw k following the law of K.

2 S ← ǫ 3 if k = 1 then 4
Draw q following a Poisson law of parameter F A (s 1 , s 2 , ...).

5

for i from 1 to q do 6 A i ← ΓA (s1,s2,...)

7

S ← Concat(S, A i ). Draw q following a Poisson law of parameter 1 j F A (s j , s 2j , ...).

12 for i from 1 to q do 13 A i ← Γ∆ j (A) (s1,s2,...)

14

S ← Concat(S, A i ).

15 Draw q following a Poisson ≥1 law of parameter 1 k F A (s k , s 2k , ...). Input: the parameters s 1 , s 2 ... Output: a cycle. let K be a random variable in N * verifying

16 for i from 1 to q do 17 A i ← Γ∆ k (A) (s1,s2,...) 18 S ← Concat(S, A i ).
1 P(K = k) = -1 F Cyc(A) ϕ(k) k ln(1 -F ∆ k (A) )
Draw k following the law of K.

2 let L be a random variable in N * verifying P(L = l) = -

(F ∆ k (A) ) l l 1 ln(1-F ∆ k (A) ) 3 Draw l following the law of L. 4 M ← ǫ 5 for i from 1 to l do 6 A i ← ΓA (s k ,s 2k ,...) 7 M ← Concat(M, A i ). 8 return [δ k M ]. 9
Proof of the proposition 3.1. We only prove that for the sampler for MSet and Cyc. The other ones are easy exercices. Let us begin with the MSet sampler. First, suppose that during the execution of the algorithm, we have drawn k = 1. So, P(K = 1) = exp(F A (s 1 , s 2 , ...)). After that, we have choosen q with probability :

P(q) = exp(-F A (s 1 , s 2 , ...)). F A (s 1 , s 2 , ...) q q!
and we have drawn q objects in A, each of them has profile σ such that the number of parts of σ of cardinal i is n i with probability :

P n = [s n ]F A (s (n)∈N * ).s n F A (s (n)∈N * ) .
where we denote s n1 1 s n2 2 ... by s n . So, the probability to obtain an object of profile σ such that the number of parts of σ of cardinal i is n i (when we draw k = 1) is the product of all these terms. This can be simplify in :

s n ∞ j=1 1 j F A (s j , s 2j , ...) ∞ q=0 (m1,...,mq); P d m d =n q d=1 [s m d ]F A (s (n)∈N * ) q! .
Now, for k > 1, in the same way, we can show that the probability is k>1 q1>0,...,q k >0 (m1,1,...,m k,q k );

k P i=1 q i P j=1 mi,j =n 1 1 q1 q 1 !...k q k q k ! . k p=1 qp d=1 [s m p,d ]F A (s (n)∈N * ).s m p,d ∞ j=1 1 j F A (s j , s 2j , ...)
.

So, using this sampler, the probability to obtain an object of profile σ such that the number of parts of σ of cardinal i is n i is k≥1 q1>0,...,q k >0 (m1,1,...,m k,q k );

k P i=1 q i P j=1 mi,j =n 1 1 q1 q 1 !...k q k q k ! . s n k p=1 qp d=1 [s m p,d ]F A (s (n)∈N * ) ∞ j=1 1 j F A (s j , s 2j , ...)
.

Indeed, this is all the ways to obtain an object of such a profile. Now, [

s n ]F MSet(A) (s 1 , s 2 , ...) = P j nj =n j [s n j ] exp( 1 j F A (s j , s 2j , ...)). Moreover, [s n j ] exp( 1 j F A (s j , s 2j , ...)) = ∞ α=0 1 α! α P p=1 nj,p=nj α p=1 [s nj,p ] F A (s j , s 2j ...) j . So, [s n ]F MSet(A) (s 1 , s 2 , ...) = ∞ P j=1 nj =n ∞ j=1 ∞ α=0 1 α! α P p=1 nj,p=nj α p=1 [s nj,p ] F A (s j , s 2j ...) j .
We have to change the order of the sums and products. We use two times that

∞ j=1 α∈A a α,j = α∈A ∞ ∞ j=1
a αj ,j , and we obtain that the probability to draw an object

of profile σ is s n .[s n ]F MSet(A) (s 1 , s 2 , ...) F MSet(A) (s 1 , s 2 , ...) .
Now, we analyse the sampler for Cyc. Suppose that the algorithm returns an object of size n and profile σ such that the number of parts of σ of cardinal i is n i .

The probability p n to draw such an object is k.l=n (m1,...,m l );

l P d=1 m d =n P(K = k).P(L = l). l i=1 p m l with P(K = k) = - 1 F Cyc(A) (s (n)∈N * ) ϕ(k) k ln(1 -F ∆ k (A) ), P(L = l) = - (F ∆ k (A) (s (n)∈N * )) l l 1 ln(1 -F ∆ k (A) (s (n)∈N * )) and ∀i ∈ {0...l}, p mi = [s mi ]F ∆ k (A) (s (n)∈N * ).s mi F ∆ k (A) (s (n)∈N * ) So, p n = k.l=n (m1,...,m l ); l P d=1 m d =n 1 F Cyc(A) (s (n)∈N * ) ϕ(k) k 1 l l i=1 [s mi ]F ∆ k (A) (s (n)∈N * ).s mi = [s n ]F Cyc(A) (s (n)∈N * ).s n F Cyc(A) (s (n)∈N * )
4. Boltzmann Samplers for t-colored classes and colored classes 4.1. The t-colored Boltzmann Samplers. In this section, we mention how to obtain from the sampler for profiled objects the samplers for the t-colored objects.

Proposition 4.1. Let us substitute s i by t.x i and generate a profiled object a, σ as previously. For each part p of σ, draw uniformaly a color c p in {1, ..., t} and let us assign the atoms in p with the color c p . This sampler is a valid Boltzmann sampler for the t-colored objects in the class A.

Proof. Let us consider a t-colored object a drawn by this sampler. Suppose that a is of size n and have n i atoms colored with the color i. The probability to obtain a is the sum on the a-admissible profiled objects times the probability to put the good colors. So, we have : Another proof of this proposition is just to observe that after the substitution of s i by t.x i , our sampler is syntaxically identical to a classical Boltzmann sampler for k-colored objects, except that we have postponed the Bernoulli choice of the color by the informations stored in the profile. So, we have valid Boltzmann samplers for the t-colored objects. We can use it for exact size generation as well as approximate size sampling. 4.2. Approximate-size Boltzmann Samplers for size-colored objects. Now, we want to use profiled object samplers to generate colored objects. Suppose that we want to generate a colored object of size n in a combinatorial class A. First, we have to solve the following equation to find the parameter x 0 which targets correctly the samplers : x.

P(a) = σadmissible profile (t.x i ) ni F A (t.
∂ ∂x f A (x, n) f A (x, n) = n.
We draw a profiled object with the parameters s i = n.x i 0 . Now, if we color this object with n colors, the sampler is uniform only on the class A

[n]
n that is to say when we have drawn a profiled object of size n. We unbiais the approximate size generator by adding some rejections. The following lemma explains how we filter the sampler in order to correct it.

′ i .p 1 p i .p ′ 1 is in [0, 1]. Put x i = p ′ i .p 1 p i .p ′ 1 , the probability to obtain x i is ∞ n=0 ( j p j xj ) n p i x i = p i x i 1 - j p j xj = p i x i j p j x j . In this expression, substitute x i by p ′ i .p 1 p i .p ′ 1 , we get p i p ′ i .p 1 p i .p ′ 1 j p j p ′ j .p 1 p j .p ′ 1 = p ′ i j p ′ j = p ′ i . The expected time is ∞ n=0 (n + 1)( j p j xj ) n p i x i .
A similar calculation shows that this is equal to

p ′ i p i .
Now, consider the problem for sampling for colored objects of size around n, a sampler is described in Algorithm 5. In a first time, we propose to observe its running on an example : Example 4.3. A generation for a colored general tree of specification T = Z + ZM Set(T ) by Algorithm 5, with parameters 14, x 0 . First, a profiled tree A is drawn by Algorithm 2 with s i = 14.x i 0 : We draw k=2. For j=1, we draw q=1, consequently we draw an only profiled object using Γ∆ 1 T (s1,s2,...) . Then, we draw q=2, this involves the sampling of 2 profiled object by Γ∆ 2 T (s1,s2,...) . After that, we get the following profiled tree A :

δ 1 δ 2 δ 3 δ 2
As the size of A is 14 = n (So lucky, we are), we just have to return a 14-coloration of A respecting its symetries. We find : Proof of the correctness of Γ colored . Using our sampler of profiled objects with the parameters s i = n.x i 0 , the probability to draw a profiled object of size ñ having a profile with ñi parts of cardinal i is P n (ñ) = n P ñi .x ñ.[s ñ]F A f A (x, n) . We have to add after that a filter in such a way that the probability becomes P ñ(ñ) = ñP ñi .x ñ.[s ñ]F A f A (x, ñ) .

O n.((1 -ǫ). f A (x, n) f A (x, (1 -ǫ)n) + (1 + ǫ) (1+ǫ)n . f A (x, n) f A (x, (1 + ǫ)n)
So, we only have to know for which profile the ratio P ñ(ñ) P n (ñ) is maximum. If ñ < n (resp. ñ > n), this happens when n i is minimum belongs the (n 1 , n 2 , ...) such that in i = ñ and [s n1 1 s n2 2 ...]F A (s 1 , s 2 , ...) = 0 (resp. when n i is maximum belongs the (n 1 , n 2 , ...) such that in i = ñ and [s n1 1 s n2 2 ...]F A (s 1 , s 2 , ...) = 0). Notice that the maximum is always ñ. The choice of the Bernoulli parameters follows directly from the lemma 4.2. Under classical conditions explain in [START_REF] Duchon | Boltzmann Samplers for the Random Generation of Combinatorial Structures[END_REF], the sampling in approximate-size of a k-colored constructible structure can be done in linear time. Now, it suffices to evaluate the cost of the added rejection phase. The average number of loops is (1ǫ).

f A (x, n) f A (x, (1ǫ)n) when ñ < n and (1 + ǫ) (1+ǫ)n . f A (x, n) f A (x, (1 + ǫ)n) otherwise.

Remark 4.5. At this stage, the explicit evaluation of the ratio f A (x, n) f A (x, (1 + ǫ)n) is out of reach, but it experimentaly seems that it is often better to choose ñ > n. In this case, it is more advisable to modify the line 4 in the previous algorithm by (4') if ñ / ∈ [n, (1 + ǫ)n] then restart Γ colored .

Conclusion

We have proved that the profiled objects are powerful tools to generate under Boltzmann model k-colored objects and to obtain a generator in approximate size for colored objects. Surprisingly, we only have to know the minimum in { n i ; in i = ñ and [s n1 1 s n2 2 ...]F A (s 1 , s 2 , ...) = 0} to unbiais the generation of colored objects. We also expect to develop our ideas to even more general coloration types as for instance to impose constraints on the number of atoms with the same colors. Finally, we would like to thank E. Fusy, C. Pivoteau and M. Soria for their precious comments and corrections.

Figure 1 .

 1 Figure 1. Different labellings.

Figure 2 .Proposition 3 . 1 .

 231 Figure 2. Distributions of use in Boltzmann sampling. In the sequel, the symbol ← designs the affection. • Neutral class : ΓE (s1,s2,...) := return () • Atomic class : ΓZ (s1,s2,...) := return • Sum : Γ(A + B) (s1,s2,...) := Draw X following a Bernoulli law of parameter Bern( F A (s 1 , s 2 , ...) F A+B (s 1 , s 2 , ...) ) If X = 1 return ΓA (s1,s2,...) else return ΓB (s1,s2,...) • Product : Γ(A × B) (s1,s2,...) := Let A ← ΓA (s1,s2,...) and B ← ΓB (s1,s2,...) return (AB) • Diagonal : Γ∆ k (A) (s1,s2,...) := let A ← ΓA (s k ,s 2k ,...) return δ k A. • Sequence : See Algorithm 1. • MultiSet : See Algorithm 2. • Cycle : See Algorithm 3. Proposition 3.1. The previous samplers are valid Botzmann samplers for profiled objects.

Algorithm 1 :

 1 ΓSeq(A) (s1,s2,...)Input: the parameters s 1 , s 2 ... Output: a sequence. Draw k following the geometric law Geom(F A (s 1 , s 2 , ...)).

1 for i from 1 to k do 2 A

 12 i ← ΓA (s1,s2,...) 3 return (A 1 ...A k ).

4 Algorithm 2 :

 42 ΓM Set(A) (s1,s2,...)

10 for j from 1

 101 to k -1 do 11

Algorithm 3 :

 3 ΓCyc(A) (s1,s2,...)

Algorithm 5 : 1 Let ñ ← size of a 2

 512 Γ colored Input: the parameters n, x 0 Output: a colored object. Draw a profiled object a with the parameters s i = n.x i 0 Let ñi the number of parts of the profile of cardinal i.

3 4 restart Γ colored 5 else 6 switch the value ñ do 7 case ñ = n 8 return a n-coloration of a. 9 case ñ < n 10 Let α be the minimum in 11 {

 4567891011 if ñ / ∈ [(1ǫ)n, (1 + ǫ)n] then n i ; in i = ñ and [s n1 1 s n2 2 ...]F A (s 1 , s 2 , ...) = 0} Draw X following a Bernoulli of parameter ( ñ n ) -α+ P ñi 12 if X = 1 then 13 return a ñ-coloration of a

  x, t.x 2 , ...) . κ σ .[s n ]F A (t.x, t.x 2 , ...) t profile κ σ .[s n ]F A (t.x, t.x 2 , ...) where κ σ is the number of ≡ B -equivalent coloration that corresponds to the color of a.

			P	ni	=
	x |a| f A (x, t)	.
	It can be proved that	κ σ .[s n ]F A (t.x, t.x 2 , ...) = 1.
		σadmissible profile

σadmissible

  Lemma 4.2. Let A = {x 1 , ..., x k } be a set of objects and Γ a sampler for A that draws the object x i with probability p i = 0. Let (p ′

	probability on A, and suppose that the the following sampler Γ ′ :	p ′ i p i	1 , ..., p ′ k ) another distibution of forms a decreasing sequence. Consider
	Algorithm 4: Γ ′
		Input: the distribution of p ′
	2
	3	Draw X following a Bernoulli law of parameter	p ′ i .p 1 p i .p ′ 1
	4	if X = 1 then
	5	return x
	6	else
	7	restart Γ ′
	p ′ i p i	Then Γ ′ draws the object x i with probability p ′ i . Moreover, Γ ′ calls on average times Γ to obtain an object.
	Proof. First, observe that the parameter	p

i Output: an object. Draw an object x with Γ 1 Let i such that x = x i


O Bodini

A Jacquot

Boltzmann Samplers for v-balanced Colored Necklaces

This paper is devoted to the random generation of particular colored necklaces for which the number of beads of a given color is constrained (these necklaces are called v-balanced ). We propose an efficient sampler (its expected time complexity is linear) which satisfies the Boltzmann model principle introduced by Duchon, Flajolet, Louchard and Schaeffer (7). Our main motivation is to show that the absence of a decomposable specification can be circumvented by mixing the Boltzmann samplers with other types of samplers.

Introduction

Necklaces are classical objects in combinatorics (10; 6; 13; 14). They naturally occur in the study of Lyndon words or in many other enumeration problems [START_REF] Cattell | Fast Algorithms to Generate Necklaces, Unlabelled Necklaces and Irreducible Polynomials over GF(2)[END_REF]. For v = (v 1 , ..., v k ) a k-tuple of positive integers, our interest lies in uniformly drawing v-balanced necklaces of n beads : the beads can take k distinct colors and the number n i of beads of color i verifies the v-balance (which we define as meaning that (n 1 , ..., n k ) is collinear to v). An additional reason to focus on v-balanced structures derives from the intrinsic difficulty to enumerate and describe such objects in terms of analytic combinatorics. In particular, the generating function of v-balanced cycles is neither holonomic nor closed-formed. We attempt to draw very large necklaces in order to conjecture some limit properties on them. To that purpose, we adopt the framework of Boltzmann samplers. This approach, like the recursive method [START_REF] Nijenhuis | Combinatorial Algorithms[END_REF], allows to "automatically" build a sampler from a decomposable specification of a combinatorial class. A Boltzmann sampler does not guarantee the size of the generated object, only that the drawn object has the same probability to be drawn as any other of the same size. More details on this point can be found in the preliminary section. But we can already state that for a large number of combinatorial classes this relaxation allows to generate an object of size n in expected linear time O(n) without preprocessing.

The main problem is that v-balanced necklaces do not admit decomposable s using traditional builders (+, ×, Seq, ...), except for some very special cases. The aim of this paper is to adapt an ad-hoc sampler for v-balanced sequences, in such a way that the sampling follows a Boltzmann model. After that, we will use this Boltzmann sampler (which cannot be built from a decomposable specification) to obtain a Boltzmann sampler for v-balanced cycles. To this end, we need to know how to obtain a Boltzmann sampler for a class A from a Boltzmann sampler for its pointing class ΘA.

This paper is organized in four sections. The first section defines the notations and concepts used throughout the article. After reflecting upon basic notions related to combinatorial classes and Boltzmann samplers, we define our classes of interest, namely, the v-balanced sequences and the v-balanced cycles. The second section addresses the sampler for (1, 1)-balanced cycles. We show two ways of building such a sampler. The first one uses a natural isomorphism with a decomposable combinatorial class involving Dyck paths. Unfortunately, this approach cannot be generalized, therefore we propose a second one based on an isomorphism between pointed (1, 1)-balanced cycles and the weighted sum of (1, 1)-balanced sequences. These sequences can be drawn with an ad-hoc sampler. In the third section, a generalization of the previous approach to v-balanced cycles is given, yielding an efficient Bolzmann sampler which, for our object of study, bypasses the need for a specification of the class. The fourth section concludes with some perspective works.

Preliminaries

An (unlabelled) combinatorial class is a couple C, s (generally abbreviated by C) where C is a set of objects and s is a function on C called size function which satisfies the conditions : (i) ∀a ∈ C, s(a) is a non-negative integer; (ii) the number of objects of any given size is finite. We naturally associate to a combinatorial class C the ordinary generating function C(x) = c n x n where c n is the number of objects of size n in C. A Boltzmann sampler for an unlabelled combinatorial class C is a random generator such that the probability to draw an object a of size n is P x (a) =

x n C(x) . These samplers were first introduced in (7) and extended, (in particular the sampler for unlabelled cycles) in [START_REF] Flajolet | Boltzmann Sampling of Unlabelled Structures[END_REF]. Let us notice that a Boltzmann sampler depends on a parameter x which can be tuned to focus on an expected output size. More precisely, let N be the random variable of the size of the output, we can solve the equation

E(N ) = x • C ′ (x) C(x)
to center the output distribution on an expected value.

Let us recall in the following table the samplers for the unlabelled operators that we need. Boltzmann samplers are very powerful tools to efficiently generate combinatorial structures (2; 8). In particular, It can be possible to automatically build a sampler according to the specification of a combinatorial class. Our aim is to with a generated by ΓxnA.

Let K be a random variable in N * verifying :

P(K = k) = -ϕ(k) kCycA(x) log(1 -A(x k ))
with CycA(x) the generating function of Cyc(A) ΓxCyc(C) Draw k according to the law of K.

Draw j according to a logarithmic law of parameter A(x k ). Let M by the concatenation of j calls to

Γ x k A Return M M...M | {z } k times .
Fig. 1. Some classical samplers with A, B and C combinatorial classes, A(x), B(x) and C(x) their respective generating functions. C must not have neutral objects.

consider Cyc v and Seq v defined below, as additional basic classes, to be added to the collection of classical constructions thus increasing the expressivity of the Boltzmann model.

Definition 1. We denote by Seq v (resp. Cyc v ) a sequence of atoms (objects of size 1), such that each atom can be colored by one of the color in {1, ..., k} and the numbers n i of beads of color i verifies the v-balanced condition. That is to say (n 1 , ..., n k ) is collinear to v.

From an easy observation, it can be seen that the generating function of

Seq (v1,...,v k ) is ( (n|v|)! ((v i n)!) )x n|v| where |v| = v i .
The following proposition is a trivial consequence.

Proposition 1 (see e.g (1)). The class Seq v is holonomic for every v.

Proof. Indeed, a quick calculation shows that this can be written as the hypergeometric function :

k F k-1 ( 1 |v| , 2 |v| , ..., |v| |v| ; 1 v 1 , 2 v 1 , ..., v 1 v 1 , 1 v 2 , ..., v 2 v 2 , ..., 1 v k , 2 v k , ..., v k -1 v k ; |v| |v| v vi i ×x |v| ).
The hypergeometric functions are holonomic by definition.

Remark: Nevertheless, the class Seq v is algebraic in only very few cases. For instance, Seq (1,1,1) is not algebraic. See (1) for a complete classification of the algebraic cases.

Generating (1,1)-balanced cycles

This section is dedicated to the random generation of (1, 1)-balanced cycles. This is a good example to illustrate our approach. A (1, 1)-balanced sequence (resp. cycle) is by previous definition a sequence (resp. cycle) of black atoms Z b and white atoms Z w such that the number of black atoms is equal to the number of white atoms. The generating function for

Seq (1,1) is S (1,1) = 1 F 0 (1/2, 4x 2 ) = (1- 4x 2 ) -1 2 .
In particular, Seq (1,1) is algebraic. We are going to use this important property in the following first approach.

First approach: through a decomposable specification

Both Seq (1,1) and Cyc (1,1) are specifiable. We can thus apply the unlabelled samplers described in the previous table. More precisely, Seq (1,1) is a classical combinatorial notion, names bridges. To generate Cyc (1,1) , we use an isomorphism between the (1, 1)-balanced cycles and the cycles of indecomposable Dyck paths.

Let D be the class of Dyck paths of specification D = Seq(ր D ց). Dyck paths are excursions from (0, 0) to (0, 2n) over the discrete lattice Z + × Z + , with displacements of (1, 1) and (1, -1). This can also be viewed as the class of wellformed parentheses strings. Bridges are defined by Seq((ր D ց) + (ց D ր)), where D is like D, but with the roles of ց and ր interchanged. So, we can generate Seq (1,1) by classical Boltzmann sampler principles.

The class of indecomposable Dyck paths is the class of specification ր D ց.

Proposition 2 (Raney's lemma). The balanced cycle can also be specified as

Cyc (1,1) ≃ Cyc(ր D ց),
where Cyc is the classical constructor for cycles.

Proof. (sketch) We can represent Cyc (1,1) as an excursion from (0, 0) to (0, 2n), with steps of (1, 1) and (1, -1), up to circular permutations. Such an excursion has a non-empty set S of points of minimal abscissa. As we deal with excursions up to circular permutations, we can consider that the excursion begin at any c in S (see Fig. 2). In this case, we have Dyck paths and we remark that they are exactly the same up to circular permutations of their indecomposable Dyck paths. Input: the parameter x Output: a (1,1)-balanced cycle Let K be a random variable in N * verifying :

Cycl(• • • • • • • •) ↔ a a c ≡ c c a ↔ Cycl( )
1 P(K = k) = -ϕ(k) kC (1,1) (x) log(1 -x 2k D(x k )) 2
Draw k according to the law of K. ].

8

This method is an efficient way to draw (1, 1)-balanced cycles. In particular, the basic rejection sampler µCyc (1,1) (x; n, ε) (see [START_REF] Duchon | Boltzmann Samplers for the Random Generation of Combinatorial Structures[END_REF] for details) has an O(n) overall cost in average. But it relies on a very singular property of the class : it can be decomposed with usual constructors. We are now interested in another way to generate these objects. This new approach will be extended to all vbalanced objects in the last section.

Second approach: mixed samplers

We are still focused on the generation of (1, 1)-balanced cycles, but now the use of an algebraic specification is avoided. The idea of our sampler can be summerized as follows : first, we adapt an ad-hoc sampler for the (1, 1)-balanced sequences in such a way that this sampling follows a Boltzmann model; second, we show an isomorphism (see proposition 4) between the class ΘCyc (1,1) of pointed balanced cycles and a sum involving duplications of Seq [START_REF] Beukers | Monodromy for the hypergeometric function n F n-1[END_REF][START_REF] Beukers | Monodromy for the hypergeometric function n F n-1[END_REF] . The notion of pointing classes is recalled in this part; finally, to obtain a Boltzmann sampler for Cyc (1,1) , we explain how to obtain a Boltzmann sampler for a class A from a Boltzmann sampler for its pointing class ΘA.

Sampler for Seq [START_REF] Beukers | Monodromy for the hypergeometric function n F n-1[END_REF][START_REF] Beukers | Monodromy for the hypergeometric function n F n-1[END_REF] . Let us start by introducing our Boltzmann sampler for Seq (1,1) and proving its correctness:

Algorithm 3: Γ x Seq (1,1)
Input: the parameter x Output: a balanced sequence of Z b and Z w . Let L be a random variable in

N * verifying P(L = l) = (2l)! (l!) 2 x 2l S (1,1) (x) 1
Draw l according to the law of L. Proof. Let α be an output of this algorithm. The probability to draw α is the probability to draw the right length and then to draw the right positions for Z b . So,

P(α) = |α|! ( |α| 2 !) 2 x |α| S (1,1) (x) . ( |α| 2 !) 2 |α|! = x |α| S (1,1) (x)
An isomorphism for ΘCyc [START_REF] Beukers | Monodromy for the hypergeometric function n F n-1[END_REF][START_REF] Beukers | Monodromy for the hypergeometric function n F n-1[END_REF] . Another classical operator, in structural combinatorics, is the pointing operator which can be defined as follows : Definition 2. Let C be a combinatorial class, the combinatorial class ΘC is formally defined as n>0 C n × {ǫ 1 , ..., ǫ n } where the ǫ i are distinct neutral objects (0-sized objects) and C n is the sub-class of C of the elements of size n.

The generating function of the pointed class

ΘC is C • (x) = x.
dC dx . We can interpret this operator by saying that each object in ΘC is an object in C with a tagged atom on it. Proof. Let C bic be the generating function for Cyc(Z w + Z b ), without any constraint on the number of beads (Z w and Z b ) of each color. We can write the generating function C bic as follows :

C bic = n>0 -ϕ(n) n log(1 -(Z n w + Z n b )) = n>0 ϕ(n) n k>0 1 k (Z n b + Z n w ) k C bic = n>0 ϕ(n) n k>0 1 k p1+p2=k k! p 1 !p 2 ! Z p1n b Z p2n w
The notion of diagonal for a bivariate generating function is needed for what follows. Let f (X, Y ) = i a i,j X i Y j be a bivariate generating function, the function g(Z) = a n,n Z 2n is called the (1,1)-diagonal of f (X, Y ) and it is denoted by ∆f .

So, by definition C (1,1) = ∆C bic and we can use the previous formula to obtain :

C (1,1) = l>0 ([Z l b Z l w ]C bic )X 2l = n>0 ϕ(n) n p>0 1 2p (2p)! (p!) 2 X 2np
Now, pointing the Cyc(1,1) class yields :

C • (1,1) = n>0 ϕ(n) p>0 (2p)! (p!) 2 X 2np C • (1,1) = n>0 ϕ(n)S (1,1) (X n )
At this stage, it is possible to draw an object of size n in Cyc (1,1) using classical recursive method [START_REF] Flajolet | A calculus for the random generation of labelled combinatorial structures[END_REF]. But here we pitch on Boltzmann point of view which avoids costly preprocessing calculus.

This isomorphism allows us to describe a Boltzmann sampler for ΘCyc (1,1) :

Algorithm 4: Γ x ΘCyc (1,1)
Input: the parameter x Output: a (1, 1)-balanced cycle of Z b and Z w . n := 1

1 S := ϕ(n)S (1,1) (x n ) C • (1,1) (x) 2
Draw a real number u uniformly in [0, 1] Proof. This is a corollary of the correctness of our general sampler, given in section four.

3 while u > S do 4 n := n + 1 5 S := S + ϕ(n)S (1,1) (x n ) C • (1,1) (x) 6 return [Γ x (Rep n (Seq (1,1) ))]
A Boltzmann Sampler for Cyc [START_REF] Beukers | Monodromy for the hypergeometric function n F n-1[END_REF][START_REF] Beukers | Monodromy for the hypergeometric function n F n-1[END_REF] . We have obtained a Boltzmann sampler for ΘCyc [START_REF] Beukers | Monodromy for the hypergeometric function n F n-1[END_REF][START_REF] Beukers | Monodromy for the hypergeometric function n F n-1[END_REF] . This is enough to uniformly generate (1,1)-balanced cycles. But, the sampler does not have a Boltzmann distribution for Cyc (1,1) , so it can not be called by another constructor. For instance, Cyc(ΘCyc (1,1) ) is not equal to Cyc(Cyc [START_REF] Beukers | Monodromy for the hypergeometric function n F n-1[END_REF][START_REF] Beukers | Monodromy for the hypergeometric function n F n-1[END_REF] ). Indeed, small objects are drawn with a smaller probability in ΘCyc [START_REF] Beukers | Monodromy for the hypergeometric function n F n-1[END_REF][START_REF] Beukers | Monodromy for the hypergeometric function n F n-1[END_REF] . To unbias the sampler, we are going to change its parameter according to a well-chosen density law f x (u). A similar idea occurs in [START_REF] Roussel | A Boltzmann sampler for the box operator[END_REF].

Lemma 2. Let C(x) = n>0 c n x n be a generating function (with C(0) = 0).

For any fixed x in the convergence disc of C, the function

f x (u) = C • (xu) uC(x) is a density of probability on [0, 1].
Proof. Clearly f is non negative. Now, it remains only to prove that

1 u=0 C • (xu) uC(x) du = 1.
We can expand the serie to C • (xu),

1 u=0 n>0 nc n (ux) n uC(x) du.
We now swap the sum and integral, we have :

n>0 nc n x n C(x) 1 u=0 u n-1 du = 1 C(x) n>0 nc n x n u n n 1 u=0 = 1.
Theorem 2. The following sampler (Algorithm 5) gives a valid Boltzmann sampler for C with parameter x from a Boltzmann sampler for ΘC.

Algorithm 5: Γ x C Input: the parameter x Output: an object in C.

Draw a real number u according to the density law

C • (xu) u(C(x) -c 0 ) . 1 if (Bernoulli( c 0 C(x)
) = 1) then 2 return an object in C 0 drawn uniformly. Proof. It is sufficient to evaluate the probability that the output be of size n.

If n = 0, we have drawn an object in C 0 . This occurs with probability

c 0 C(x) . If n > 0, the probability is (1 - c 0 C(x) ) • 1 u=0 nc n (ux) n uC(x) du = c n x n C(x)
. In every cases, this is a Boltzmann probability.

This sampler allows us to generate extremely large (1, 1)-cycles (more than 1000000 beads). Indeed, this sampler is clearly linear in the size of the output. The following figures (Fig. 3) show a (1, 1)-cycle of size 100 (Fig. 3(a)) (only 100 beads for the legibility.) It also shows that we can compose our sampler with the classical builder ( * , +, Seq, Cyc, M Set, P Set, ...). Figure 3(b) shows a random generated a necklace of (1, 1)-cycles. We can see that the necklaces do not contain a lot of (1, 1)-cycles. Moreover only one of these (1, 1)-cycles contains a lot of beads.

The general vectorial case

In this part, we extend the previous method to all cases, algebraic or not. Let v = (v 1 , v 2 , ...v m ), and |v| = m i=1 v i . Our goal here is to generate Cyc v : cycles of m colors, such that the number of occurences of each atom Z i verify the v-balance condition. We follow the same principles than in section 3.2 but the proofs are slightly more technical.

Sampler for Seq v

Let us recall S v , the generating function of v-balanced sequences:

S v = p>0 (|v|p)! m i=1 ((v i p)!) m i=1 Z vip i .
Algorithm 6: Γ x Seq v Input: the parameter t Output: a v-balanced sequence of Z i .

Let L be a random variable in

N * verifying P(L = l) = (|v|l)! m i=1 (v i l!) t ( m P i=1 vil) S v 1
Draw l according to the law of L.

2

Let M be a (|v|l)-uple, Proof. The proof can be easily transposed from (1, 1)-balanced one. The complexity result is trivial. Now, as with the example of (1, 1)-balanced cycles, we are going to use this sampler for v-balanced sequences to generate v-balanced cycles.

An isomorphism for ΘCyc

v Theorem 3. ΘCyc v is isomorphic to n>0 ϕ(n)Rep n (Seq v ).
Proof. Let C mcol be the generating function of cycles of m atoms Z 1 , ..., Z m .

C mcol = n>0 -ϕ(n) n log(1 -( m i=1 Z n i )) = n>0 ϕ(n) n k>0 1 k ( m i=1 Z n i ) k C mcol = n>0 ϕ(n) n k>0 1 k m P i=1 pi=k k! m i=1 (p i !) m i=1 Z npi i
Let C v be the generating function of Cyc v . This is the extraction of terms with the exponents verifying the v-balanced condition in C mcol .

C v = l>0 ([ m i=1 Z lvi i ]C mcol )X |v|l = n>0 ϕ(n) n p>0 1 |v|p (|v|p)! m i=1 ((v i p)!) X |v|np
We will now apply the same idea that we described for the (1, 1)-balanced case to ΘC v (the generating function of which is C

• v ). C • v = n>0 ϕ(n) p>0 (|v|p)! m i=1 ((v i p)!) X |v|np = n>0 ϕ(n)S v (X n )
This isomorphism can be used to obtain the following sampler:

Algorithm 7: Γ x ΘCyc v Input: the parameter x Output: a v-balanced cycle of Z i . n := 1 1 S := ϕ(n)Sv(x n ) C • v (x) 2
Draw a real number u uniformly in [0, 1]

3 while u > S do 4 n := n + 1 5 S := S + ϕ(n)Sv(x n ) C • v (x) 6 return [Γ x (Rep n (Seq (1,1)
))] 7 Proposition 3. Algorithm 7 is a valid Boltzmann sampler for ΘCyc v . Its arithmetic complexity is linear in the size of its output object.

Proof. Let us consider the generation of a pointing cycle c. It can be written as c = u p , where u a primitive sequence (i.e. without replication) and p is the primitive repetition order of c (|c| = p|u|). There are s = |u| shifts of u which produce equivalent cycles. In Algorithm 7, the generating sequence is not necessarily primitive. So, c can be drawn as any ũd , with d|p and ũ a shift of p d repetitions of u. So, the probability to draw u is the sum for all d|p of the probability to draw d as repetition order and to draw one of the s shift of ũ as motif : To obtain a v-balanced cycle from an object of ΘCyc v , we can now apply the general algorithm 5 to ΘCyc v . As proven previously, this provides us a Boltzmann sampler for Cyc v .

P(c) =

Conclusion

The random generation of constrained-colored structures is in general very difficult. In a previous paper (3), we already investigated the generation of the k-colored structures and size-colored structures. In this short paper, we have presented a way to efficiently generate v-balanced cycles. It is possible with our samplers to generate v-balanced cycles of sizes reaching up to one million. Nevertheless our methods can not be directly generalized to other balanced structures. For instance, we do not know how to generate (1, 1)-balanced general non planar (unlabelled) trees where general non planar trees can be specified as T = Z.M Set(T ). This problem is a work in progress and should be solved by a method involving multivariate Boltzmann sampler. Another perspective is the generation of semi-labelled structures. In these structures each atom can take a color in {1, ..., k} but, if we have an atom of color k > 1, we need to also have at least one atom of color k -1. Semi-labelling is a new interesting labelling which is in a sense between unlabelling and labelling. But very little is as of yet known about it.

Finally, we want to thank, B. Salvy for his precious knowledge on hypergeometric functions and Joachim Dehais, Jérémie Lumbroso and Yann Ponty for their careful reading of a preliminary version of the manuscript.

Fig. 2 .

 2 Fig. 2. Isomorphism between Cyc (1,1) and Cyc(ր D ց).

Algorithm 1 : 1 M := ε 2 for i from 1 to l do 3 M 4 return (M ). 5 Algorithm 2 :

 1123452 Γ x D Input: the parameter x Output: an object of D Draw l according to a geometric law of parameter x 2 D(x) := concat(M, •, Γ x D, •) Γ x Cyc (1,1)

3

  Draw j according to a logarithmic law of parameter x 2k D(x k ).

4 M := ε 5 for i from 1 to j do 6 M

 456 := concat(M, •, Γ x D, •) 7 return [M M...M k times

2

  Let M be a (2l)-uple, select uniformly l positions belongs the 2l entries in 3 M . This positions are the Z b entries of M , the other ones are the Z w entries. 4 return (M ).

5 Lemma 1 .

 51 Algorithm 3 is a valid Boltzmann sampler for Seq[START_REF] Beukers | Monodromy for the hypergeometric function n F n-1[END_REF][START_REF] Beukers | Monodromy for the hypergeometric function n F n-1[END_REF] .

Theorem 1 .

 1 ΘCyc (1,1) is isomorphic to n>0 ϕ(n)Rep n (Seq (1,1) ), where Rep n (A) is the class {aa...a n times ; a ∈ A}.

7 Corollary 1 .

 71 Algorithm 4 is a valid Boltzmann sampler for ΘCyc (1,1) .

3 else 4 return

 34 Γ ux (ΘC) and forget the point.

5

 5

  (a) random (1,1)-cycle of size 100. (b) A random necklace of (1,1)-cycles of size 200.

Fig. 3 .

 3 Fig. 3. Examples of Boltzmann sampling.

3 for i from 1 to m do 4

 34 Select uniformly lv i positions belongs the (|v|l) entries not yet affected 5 in M . This positions are the Z i entries of M . 6 return (M ).

7 Lemma 3 .

 73 Algorithm 6 is a valid Boltzmann sampler for Seq v . Its arithmetic complexity is linear in the size of its output object.

  i) = 1 |c| P(c) = x |c| C • v with i ∈ [|1, l|],the choice of i corresponding to the pointed atom. The complexity ensues from the results on Boltzmann sampling.


Olivier Bodini

Jérémie Lumbroso

Optimal Partial Tiling of Manhattan Polyominoes

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.

Optimal Partial Tiling of Manhattan Polyominoes

Olivier Bodini ⋆ and Jérémie Lumbroso LIP6, UMR 7606, CALSCI departement, Université Paris 6 / UPMC, 104, avenue du président Kennedy, F-75252 Paris cedex 05, France

Abstract. Finding an efficient optimal partial tiling algorithm is still an open problem. We have worked on a special case, the tiling of Manhattan polyominoes with dominoes, for which we give an algorithm linear in the number of columns. Some techniques are borrowed from traditional graph optimisation problems.

For our purpose, a polyomino is the (non necessarily connected) union of unit squares (for which we will consider the vertices to be in Z 2 ) and a domino is a polyomino with two edge-adjacent unit squares.

To solve the domino tiling problem [START_REF] Fournier | Tiling pictures of the plane with dominoes[END_REF][START_REF] Ito | Domino tilings on planar regions[END_REF][START_REF] Kenyon | A note on tiling with integer-sided rectangles[END_REF][START_REF] Rémila | The lattice structure of the set of domino tilings of a polygon[END_REF][START_REF] Thiant | An O (n log n)-algorithm for finding a domino tiling of a plane picture whose number of holes is bounded[END_REF][START_REF] Thurston | Conway's tiling groups[END_REF] for a polyomino P is equivalent to finding a perfect matching in the edge-adjacent graph G p of P 's unit squares. A specific point of view to study tiling problems has been introduced by Conway and Lagarias in [START_REF] Conway | Tiling with polyominoes and combinatorial group theory[END_REF]: they transformed the tiling problem into a combinatorial group theory problem. Thurston [START_REF] Thurston | Conway's tiling groups[END_REF] built on this idea by introducing the notion of height, with which he devised a linear-time algorithm to tile a polyomino without holes with dominoes. Continuing these works, Thiant [START_REF] Thiant | An O (n log n)-algorithm for finding a domino tiling of a plane picture whose number of holes is bounded[END_REF], and later Bodini and Fernique [START_REF] Bodini | Planar Tilings[END_REF] respectively obtained an O (n log n) algorithm which finds a domino tiling for a polyomino whose number of holes is bound, and an O n log 3 n algorithm with no constraint as to the number of holes. All these advances involved the "exact tiling problem".

Naturally, all aforementioned exact tiling algorithms are useless when confronted with polyominoes that cannot be perfectly tiled with dominos. Such algorithms will output only that the polyominoes cannot be tiled-and this is inconvenient because a perfect tiling is not necessarily required: we might want partial tilings with at most x untiled squares.

Thus, by analogy with matching problems in graph theory and the notion of maximum matching, it seems interesting to study the corresponding notion of optimal partial tiling. No algorithm has been specifically designed with this purpose in mind; and whether the optimal partial tiling problem for polyominoes can be solved by a linear-time algorithm has been an open problem for the past 15 years. In this paper, we are studying the partial optimal domino tiling problem on the Manhattan class of polyominoes (see figure 1).

A Manhattan polyomino is a sequence of adjacent columns that all extend from the same base line ("Manhattan" refers to the fact that this polyomino looks like a skyline). We are exhibiting an algorithm that makes solving this problem much more efficient than solving the corresponding maximum matching problem. Indeed, the best known algorithm for maximum matchings in bipartite graphs is in O ( √ nm) [START_REF] Gabow | Faster scaling algorithms for network problems[END_REF][START_REF] Hopcroft | An n 5/2 algorithm for maximum matchings in bipartite graphs[END_REF] (where n is the number of vertices and m the number of edges) and it yields an algorithm in O n 3/2 for the partial tiling problem, whereas our algorithm is linear in the number of columns. The choice of the Manhattan class of polyominoes is justified as a generalisation of the seminal result of Bougé and Cosnard [START_REF] Bougé | Recouvrement d'une pièce trapézoidale par des dominos[END_REF] which establishes that a trapezoidal polyomino (i.e. a monotic Manhattan polyomino, in which the columns are ordered by increasing height) is tilable by dominoes if and only if it is balanced. The partial tiling problem on more general classes seems to be out of reach at present. This paper first succinctly recalls some definitions on tilings, polyominoes in general and Manhahattan polyominoes in particular; we list the notations that we will use throughout the paper (section 1). Follows a presentation of the main idea of reducing the partial tiling problem to a network flow problem (section 2); we then prove this reduction to be valid (section 3). A greedy algorithm to solve this specific network problem is given (section 4), which allows us to conclude (section 5).

Definitions

An optimal partial tiling by dominoes of a polyomino P is a set {D 1 , . . . , D k } of vertical or horizontal dominoes placed in the discret plane such that:

(i) ∀i ∈ {1, . . . , k} D i ⊂ P ; (ii) the dominoes D 1 , . . . , D k have mutually disconnected interiors: for every i, j such that 1 i j k, we have

• D i ∩ • D j = ∅ where • D
is the interior of D for the topology endowed with the euclidean distance on R 2 ; (iii) k is maximal: if k ′ , k ′ k, and D ′ 1 , . . . D ′ k exists with the above two conditions, then k = k ′ .

A column is the union of unit squares placed one on top of the other. A Manhattan polyomino is the connected union of columns aligned on the same horizontal line.

We will identify a Manhattan polyomino with a tuple: the sequence of the heights of all the columns of the polyomino (ordered from left to right). For example, the polyomino in figure 1 is represented as (4, 2, 4, 4, 1, 2, 2, 2, 4, 4). This representation is clearly more convenient in memory space than, say, the list of all unit squares of a polyomino.

It is convenient to define inclusion, and we will do so using the tuple representation: polyomino P = (p 1 , p 2 , . . . , p n ) is said to be included in Q = (q 1 , q 2 , . . . , q n ) if ∀i, p i q i (both polyominoes can be padded with zero-sized columns if necessary).

In addition, the unit squares of a polyomino have a chessboard-like coloration; specifically1 , the unit square with position (i, j) (i.e.: unit square (i, j)+[0, 1[ 2 ) is white if i + j is even and black otherwise. A column is said to be white dominant (or black dominant ) if it has more white (or black) unit squares than black (or white) ones.

From polyominoes to flow networks

In this section, without loss of generality, we consider the polyominoes are balanced (a polyomino is balanced if it contains the same count of white and black unit squares). Indeed, a polyomino can always be balanced by adding the necessary number of isolated unit squares of the lacking color.

Notations. Let (h 1 , . . . , h n ) be a Manhattan polyomino P .

For i j, we define X(i, j) as the number min i k j {h k }, the height of the smallest column contained in the subset {h i , . . . , h j }.

We define B(P ) (and respectively W (P )) as the set of black unit squares, (or white unit squares) contained in P . Let I P (and resp. J P ) be the set of indices of black dominant columns (and resp. white dominant columns). We define s 1 , . . . , s n as the elements of I P ∪ J P sorted in ascending order.

Let G = (V, E) be a graph, and S ⊂ V . We define Γ (S) as the subset of neighbor vertices of S, i.e. the vertices y ∈ V such that there exists x ∈ S with (x, y) ∈ E or (y, x) ∈ E.

Construction of the flow network. For each polyomino P , we build a directed graph (flow network ) that we call F P :

its vertex set is {s 1 , . . . , s n } ∪ {s, t} where s and t are two additional vertices respectively called source and sink (be mindful of the fact that we use s i both to refer to the vertices, and to the actual columns);

its edge set E is defined by:

E = {(s i , s i+1 ) ; i ∈ {1, . . . , n -1}} ∪ {(s i+1 , s i ) ; i ∈ {1, . . . , n -1}} ∪ {(s, a); a ∈ I P } ∪ {(a, t); a ∈ J P } ,
and each arc of E is weighted by a function c called capacity function defined by:

c(e) =      X(si,si+1) 2 if e = (s i , s i+1 ) or e = (s i+1 , s i ) 1 if e = (s, a) with a ∈ I P 1 if e = (b, t) with b ∈ J P
where x → ⌈x⌉ is the ceiling function (which returns the smallest integer not lesser than x). This yields the set I P ∪ J P = {s 1 = 1, s 2 = 3, . . . , s 8 = 13} from which we can build the flow network in figure 3.

For instance, the capacity of arc (s 1 , s 2 ) is c ((s 1 , s 2 )) = 2 because the smallest column between the indices s 1 = 1 and s 2 = 3 is the column 3 and its height is 3 (what this boils down to is X(1, 3) = 3).

Main theorem: An overview

As might have been evident in the previous sections, oddly-sized columns, whether white or black dominant, are what make domino tiling of Manhattan polyomi-

t s 2 2 1 2 1 1 1 2 2 1 2 1 1 1 1 1 1 1 1 1 1 1
Fig. 3. Flow network associated with the polyomino of figure 2(a).

noes an interesting problem: indeed, evenly-sized columns (of a polyomino comprising only such columns) can conveniently be tiled with half their size in dominoes.

Sketch of the method

Let P be a polyomino. Our method can intuitively be summarized in several steps:

we devise a "planing" transformation which partially tiles the polyomino P in a locally optimal way (i.e.: such that it is possible to obtain an optimal partial tiling for P by optimally tiling the squares which remain uncovered after the transformation); this transformation, as illustrated in figure 4(c), "evens out " a black dominant column and a white dominant column; -we devise a way to construct a maximum flow problem that translates exactly how the planing transformation can be applied to the polyomino P ; -we prove that the solutions to the maximum flow problem constructed from P , and to the optimal partial tiling of P are closely linked (by a formula).

In truth, these steps are intertwined: the local optimality of the planing transformation is demonstrated using the maximum flow problem.

The planing (or leveling) transformation

The planing transformation we just mentionned can be expressed as a map φ, which can only be applied to a polyomino P which has two consecutive2 oddly-sized columns s i , s i+1 of different dominant colors. This condition3 can be summarized as ∃i, (s i ∈ I P and s i+1 ∈ J P or s i ∈ J P and s i+1 ∈ I P ) .

Let P = (h 1 , . . . h n ) be a Manhattan polyomino, and let i be the smallest integer such that s i , s i+1 are two oddly-sized columns of different dominant colors and c(s i , s i+1 ) = 0, then P ′ = φ(P ) is a new polyomino defined by

P ′ = h 1 , . . . , h si-1 , a, . . . , a, h si+1+1 , . . . , h n
where a = min h si -1, h si+1 -2, . . . , h si+1-1 -2, h si+1 -1 , i.e.: all columns from s i to s i+1 are leveled to height a, which is at least one unit square smaller than the smallest of s i and s i+1 and two unit squares smaller than the smallest even-sized column of P from s i to s i+1 .

Since we have only decreased the heights of the columns of P to obtain P ′ , φ(P ) = P ′ ⊂ P is trivial (following the definition of inclusion we gave in section 1).

We will show that this transformation is locally optimal: again, this means that if optimal tilings of φ(P ) have x non-covered unit squares, then so do optimal tilings of P (the number of non-covered unit squares is invariant with regards to the transformation).

Main theorem

Having constructed a flow network F P from a given Manhattan polyomino P , we now show that, if we call d(P ) the number of non-covered unit squares in an optimal partial tiling of P , then the value v(P ) of the maximum flow on F P is such that: The meaning of this equation is quite intuitive: it says that the number of uncovered squares d(P ), is exactly the number of single squares that come both from the black dominant columns I P and from the white dominant columns J P , from which we withdraw two squares for each of the v(P ) times we are able to apply the planing transformation (recall that this transformation evens out both a black dominant column and a white dominant column, hence the 2 factor).

|I P | + |J P | -2v(P ) = d(P ).
Lemma 1. Let P be a Manhattan polyomino. For all P ′ , such that P ′ = φ k (P ) (the planing transformation applied k times to P ), the following invariant holds:

|I P | + |J P | -2v(P ) = |I P ′ | + |J P ′ | -2v(P ′ )
where v(P ) and v(P ′ ) are the values of a maximum flow respectively in T P and

T P ′ .
Proof (by induction on k). Let f be a maximum flow on T P k-1 which minimizes e f (e) (i.e.: the flow takes the shortest path from s to t given a choice). Since it is possible to apply the planing transformation to P k-1 , then there must be two consecutive vertices s i and s i+1 corresponding to oddly-sized columns of different dominant colors (given several such pairs, we consider that for which i is the smallest).

Let us now build T P k , the flow network associated with P k = φ(P k-1 ) : the vertices of T P k are the vertices of T P k-1 from which we remove {s i , s i+1 }; the arcs of T PK are the trace of the arcs of the arcs of T P k-1 (trace is a non-standard term by which we mean all arcs that are incident neither to s i nor to s i+1 ) to which we add, should both vertices exist, the arcs (s i-1 , s i+2 ) and (s i+2 , s i-1 ) with capacity min (c ((

s i-1 , s i )) , c ((s i , s i+1 )) -1, c ((s i+1 , s i+2 ))) .
Suppose s i and s i+1 respectively represent a black and white dominant column (figure 6 illustrates the construction in this case); the other case is symmetrical.

Then, because e f (e) is minimal, maximum flow f routes a non-null amount through the path (s, s i , s i+1 , t).

t s 2 2 1 2 2 1 1 1 1 1 t s 2 -1 1 -1 1 -1 t s 1 1 min(2, 2-1, 1) = 1 min(2, 2, 1) = 1
Fig. 6. Building T P k from T P k-1 : a max flow for the network of figure 3 necessarily goes through the path (s, s 2 , s 3 , t). Here we show the impact of removing this path on the flow network's edges, vertices and capacities.

Thus the maximum flow f on T P k-1 induces a maximum flow f ′ on T P k , which is defined as the trace of f on T P k and updated, if necessary, by adding:

f ′ ((s i-1 , s i+2 )) = f ((s i-1 , s i )) = f ((s i+1 , s i+2 )) f ′ ((s i+2 , s i-1 )) = f ((s i , s i-1 )) = f ((s i+2 , s i+1 ))
.

Proving that f ′ is a maximum flow on T P k is straightforward (suppose there is a better flow, and reach a contradiction). We then immediately remark that v(P k-1 ) = v(P k ) + 1; and because the planing transformation applied to P k-1 levels both a black dominant column and a white dominant column to obtain P k , we have |I P k | = I P k-1 -1 and |J P k | = J P k-1 -1, thus:

I P k-1 + J P k-1 -2v(P k-1 ) = |I P k | + |J P k | -2v(P k ),
from which, by induction on k, we derive the lemma's invariant. ⊓ ⊔ Lemma 2. Let P be a Manhattan polyomino and v(P ) the value of a maximum flow in T P (cf. section 2). There is a partial tiling of P in which exactly |I P | + |J P | -2v(P ) squares are uncovered.

Proof. We prove the property by induction on the size of P . Let f be a maximum flow in T P . We consider whether there are two consecutive vertices s i and s i+1 which correspond to oddly-sized columns of different dominant colors, such that the flow of f going from s i to s i+1 is non-null.

Either: no such vertices s i and s i+1 exist 4 , in which case we have v(P ) = 0 (this would mean f is the zero flow ). Indeed, any path from s to t would use at least one transversal arc (s i , s i+1 ) because, by construction, a vertex s i cannot be simultaneously linked to s and t. We remark that the planing transformation cannot be applied. If we partially tile P , as in figure 4(b), with vertical dominoes alone, leaving one square uncovered per oddly-sized column, we obtain a partial tiling which globally leaves |I P | + |J P | squares uncovered-thus proving our property for this case.

Or: such vertices s i and s i+1 exist. We can then apply the planing transformation φ, P ′ = φ(P ). By induction, the property holds for P ′ . As we've seen, the (union of the) squares removed by the transformation is a domino-tileable Manhattan polyomino (figure 5); and by lemma 1,

|I P ′ | + |J P ′ | -2v(P ′ ) = |I P | + |J P | -2v(P ).
⊓ ⊔ Theorem 1. Let P be a Manhattan polyomino, and d(P ), the number of uncovered unit squares in an optimal partial tiling of P . The construction outlined in the proof of lemma 2 is optimal, i.e.:

|I P | + |J P | -2v(P ) = d(p).
Remark 1. We are now going to work on G P which is the edge-adjacency graph of polyomino P : the vertices of G P are the unit squares of P , and an edge connects two vertices of G P if and only if the two corresponding squares share an edge in P . (By contrast, T P is the flow network constructed in section 2.)

The idea behind the proof of theorem 1 is as follow: we isolate a subset B(P ) of black squares of P , such that the (white) neighbors (in graph G P ) to squares of B(P ) verify the relation We can then conclude, using Hall's theorem, that d(P ) |B(P )| -|Γ (B(P ))|. To construct B(P ), we use a minimal cut5 of graph T P , from which we deduce a list of "bottlenecks". These bottlenecks mark the boundary of zones containing squares of B(P ).

Intuitively, once bottlenecks are planed (that is to say when we have tiled them following the template given by our planing transformation), they isolate zones which have either too many white or too many black squares.

Greedy algorithm

Having proven that our optimal partial tiling problem can be reduced to a network flow problem, we will now present an algorithm to efficiently solve this t s Fig. 7. A polyomino P , its flow network T P (the transversal arcs are only hinted at, with dashed lines; the max flow is represented with snake-lines), and, in red, a minimal cut of T P which separates P in two zones (each zone is connected here, but that may not be the case). The black striped squares on the left belong to B(P ): in accordance with Hall's theorem, |B(P )| -|Γ (B(P ))| = 9 -7 = 2 is the number of uncovered squares in the optimal partial tiling. specific brand of network flow problem (indeed, a general-purpose network flow algorithm would not take into account those properties of our network which are a consequence of the way it was constructed).

We will first introduce the notion of f -tractability for two vertices of our flow network. The pair (s i , s j ) (for which we consider that i < j) is said to be f -tractable if:

s i and s j correspond to two oddly-sized columns of different dominant columns6 ; -if s i corresponds to a black-dominant column, then the arcs (s i , s i+1 ), ..., (s j-1 , s j ) are not saturated; -or else, if s i corresponds to a white-dominant column, then the arcs (s j , s j-1 ), ..., (s i+1 , s i ) are not saturated; -for every k, i < k < j, if s k ∈ I P (resp.

s k ∈ J P ) then (s, s k ) (resp. (s k , t))
is saturated.

This might seem like an elaborate notion, but in fact, it only translates whether, in terms of flow increase, we can apply our transformation. We are going to prove that the following algorithm builds a maximum flow:

1. we begin with a null flow f ; 2. while there exists two vertices s i and s j with i < j which are f -tractable:

(a) we take the first pair of vertices in lexicographic order which is ftractable, (b) and we augment the flow f by 1 on the arcs belonging to the path [s, s i , s i+1 , . . . , s j , t] or [s, s j , s j-1 , . . . , s i , t] (depending on the dominant color of s i ); 3. we return the flow f . Proof (Correctness of the greedy algorithm). Let (s i , s i+1 ) be the first pair of vertices in lexicographic order which, at the beginning of the algorithm, is ftractable. We suppose here that s i corresponds to a black dominant column (the other case is symetrical). We want to prove that there is a maximum flow f , which minimizes v∈TP f (v), such that none of the following values are null: f ((s, s i )), f ((s i , s i+1 )), f ((s i+1 , t)). If a maximum flow following this last condition does not exist, then one of those three arcs must be null and another one must be saturated, otherwise the flow f can be augmented. Now, by the minimality of v∈TP f (v), it follows that (s, s i ) is not saturated (otherwise we can remove 1 to f on every arc belonging to a minimal path from s to t using (s, s i ) with non-zero flow, and add 1 to f ((s, s i )), f ((s i , s i+1 )), f ((s i+1 , t)). We obtain a maximum flow which contradicts the minimality of v∈TP f (v).) The arc (s i , s i+1 ) cannot be saturated for the same reason. So, (s i+1 , t) is saturated. But in this case, as (s, s i ) and (s i , s i+1 ) are not saturated, we can remove 1 to f on every arc belonging to a non-zero flow path from s to t using (s i+1 , t), and add 1 to f ((s, s i )), f ((s i , s i+1 )), f ((s i+1 , t)). We again obtain a new maximum flow with total weigth at most v∈TP f (v). That proves what we want. Now, the next recursive steps of the algorithm are exactly proved by the same way but on transport networks obtained by convenient diminution of the arc capacities.

To briefly but correctly analyze the complexity of this algorithm, we have to describe the representation of the entry. If the Manhattan polyomino is given by the list of its column heights, it can be stored in O(l log(max(h i ))) bits where l is the number of columns. We can consider two steps. The first one consists in obtaining the transport network T P from P . This can be done in one pass and we make O(l) elementary operations (min, division by 2). The second part consists in solving the transport networks problem. Using stacks, the algorithm can solve the problem making a unique pass on the vertices of T P . So, its complexity is in O(|I P |). Thus, globally the algorithm works in O(l) elementary operations. If we make the hypothesis that the number of columns is approximatively the average of the height of the columns. Our algorithm is clearly sublinear in n the number of unit squares. Moreover, if we consider the complexity according to the size of the input, this algorithm is linear.

Conclusion

In this paper, we have illustrated that particular optimal partial domino tiling problems can be solved with specific algorithms. We have not yet been able to evidence a linear algorithm for the general problem of partial domino tiling of polyominoes without holes. This appears to be an attainable goal, as [START_REF] Thurston | Conway's tiling groups[END_REF] has devised such an algorithm for the exact domino tiling problem.

Currently, the best known complexity for the general partial domino tiling problem is O(n • √ n) using a maximum matching algorithm in bipartite graphs. To improve this bound, it seems irrelevant to obtain an analogue to the notion of height which is a cornerstone of the tiling algorithms. Nevertheless, it can be proven that two optimal partial tilings are mutually accessible using extended flips (which contain classical flips [START_REF] Bodini | Generalized Tilings with Height Functions[END_REF][START_REF] Rémila | The lattice structure of the set of domino tilings of a polygon[END_REF] and taquin-like moves). This fact involves in a sense a weak form of "lattice structure" over the set of optimal partial tilings. This is relevant and could be taken into account to optimize the algorithms.

5 Annexe (proof of theorem 1) So, we have proved that on the sequence of Manhattan polyominoes obtained by successive planing transformations, the function |I | + |J | -2v( ) is invariant. We need another invariant to conclude that |I P |+|J P |-2v(P ) ≤ d(P ). It follows from a list of "bottlenecks" which prevent the matching of columns.

We denote by P red = (h red 1 , ..., h red n ) the Manhattan polyomino obtained from P after v(P ) planing transformations.

We can suppose that the least x such that (x, x ′ ) belongs to Y P (the set of edges of F P that crosses the minimal cut) corresponds to a black dominant column (if this is not the case, we can inverse the colors). Let g(x, x ′ ) be the smallest k ∈ {x, . . . , x ′ } such that h k = X(x, x ′ ). We denote by G = {g(x, x ′ ); (x, x ′ ) ∈ Y P } the list of bottlenecks of P and we sort the elements of G in ascending order. G = g 0 1 , . . . , g 0 k . Now, if i is odd (resp. even) and is the index of a white dominant column, we put g i = g 0 i -1 (resp. g i = g 0 i +1) otherwise we put g i = g 0 i . With the hypothesis, we can observe that (h 1 , h 2 , . . . , h g1 ) has more black unit squares than white ones. We put H P = B ((h 1 , h 2 , . . . , h g1 )) ∪ B ((h g2 , . . . , h g3 )) ∪ . . .

Fig. 1 .

 1 Fig. 1. A Manhattan polyomino.

  The union IP ∪ JP of black and white dominant columns (with s1 = 1, s2 = 3 and so on).

Fig. 2 .

 2 Fig. 2. Construction of a {s 1 , . . . , s n } set.

  A naïve tiling for P2 (the uncovered squares are those of the oddlysized columns). s1 s2 s3 (c) After applying the planing transformation to P2 once.

Fig. 4 .

 4 Fig. 4. Tilings of P 2 , which has three oddly-sized columns.

  ... at least two unit squares smaller than the smallest even-sized column.

Fig. 5 .

 5 Fig. 5. Generic examples of the planing transformation.

  |B(P )| -|Γ (B(P ))| = |I P | + |J P | -2v(P ).

  and K P = W ((h 1 , h 2 , . . . , h g1 )) ∪ W ((h g2 , . . . , h g3 )) ∪ . . . We have 2(|H P | -|Γ (H P )|) ≤ d(P ) and we want to prove that 2(|H P | -|Γ (H P )|) = |I P | + |J P | -2v(P ). In order to do that, let P ′ be the Manhattan polyomino obtained from P by a planing transformation as we have processed previously. Firstly, we are going to show that |H P |-|Γ (H P )| = |H P ′ |-|Γ (H P ′ )| where H P ′ = B h ′ 1 , h ′ 2 , ..., h ′ g1 ∪ B h ′ g2 , ..., h ′ g3 ∪ ... We put B(H P ) (resp. W(H P )) the number of odd black dominant columns (resp. white) in P which belongs to the columns of indices in E = {1, 2, ...g 1 } ∪ {g 2 , ..., g 3 } ∪ .... An easy observation allows us to see that|H P | -|Γ (H P )| = |H P | -|K P | -v∈YP c(v) = B(H P ) -W(H P ) -v∈YP c(v)When we apply the planing transformation on P , we delete :a black dominant column in E and a white column in E c andv∈Y P ′ c(v) = v∈YP c(v) -1,a black dominant and a white dominant column in E or a black dominant and a white column in E c andv∈Y P ′ c(v) = v∈YP c(v).This fact proves that |H | -|Γ (H )| is invariant on every sequence of Manhattan polyominos obtained by successive planing transformations. Now, let us remark that |H P red | -|Γ (H P red )| = B(H P red ) = |I P red | (W(H P red ) = v∈YP red c(v) = 0) and that |I P red | = |I P |v(P ). Indeed, we have made v(P ) planing transformations and each of them reduces by 1 the number of black dominant columns. So, |H P | -|Γ (H P )| = |H P red | -|Γ (H P red )| = |I P |v(P ). Moreover, we have assumed initially that the polyomino is balanced. So, |I P | = |J P |. Consequently, we have proved that 2(|H P | -|Γ (H P )|) = |I P | + |J P | -2v(P ). Thus, we can conclude that |I P | + |J P | -2v(P ) ≤ d(P ).

And regardless of the basis, as both colors are symmetrical in purpose (i.e.: it doesn't matter whether a given unit square is white or black, so long as the whole polyomino is colored in alternating colors).

By this we mean that the two dominant columns are consecutive in the s1, s2, . . . ordering (and this does not necessarily imply that they are adjacent in P ); in figure4(c), dominant columns s1 and s2 are consecutive (so are s2 and s3).

Wherein it is obvious that the or is mutually exclusive.

This case arises when there are no oddly-sized columns, or only oddly-sized columns of a given color.

Recall that a cut of graph G = (V, E) is a partition of its vertices in two subsets X1 and X2; let EC be the set of edges such that one vertex is in X1 and the other in X2: the value of the cut is the sum of the capacity of each edge in EC; a minimal cut is a cut which minimizes this sum. In the case of flow networks, a cut separates the source s from the sink t.

Recall that this is almost the condition under which the planing transformation can be applied: the planing transformation requires, in addition, that si and sj be so that j = i + 1 -per the ordering which have defined in section 2.

contract GAMMA, "Génération Aléatoire Modèles, Méthodes et Algorithmes", BLAN07-2 195422.