domain: math info

text:
Andrei Asinowski

Cyril Banderier

Frank Ruskey

Torsten Mütze

Joe Sawada

From geometry to generating functions: rectangulations and permutations

Keywords: Rectangulations, permutations, pattern avoidance, generating functions

We enumerate several classes of pattern-avoiding rectangulations. We establish bijective links with pattern-avoiding permutations, prove that their generating functions are algebraic, and confirm several conjectures by Merino and Mütze. We also analyze a new class of rectangulations, called whirls, using a generating tree.

Introduction

A rectangulation of size n is a tiling of a rectangle by n rectangles such that no four rectangles meet in a point. In the literature, rectangulations are also called floorplans or rectangular dissections.

Such structures appear naturally for architectural building plans, integrated circuits (see Figure 1), and were investigated since the 70s with some graph theory, computational geometry, and combinatorial optimization point of views [START_REF] John | Synthesis and optimization of small rectangular floor plans[END_REF][START_REF] Philip | Architectural Morphology[END_REF]. Then, in the 2000s, rectangulations began to be investigated with more combinatorial approaches [START_REF] Ackerman | A bijection between permutations and floorplans, and its applications[END_REF][START_REF] Asinowski | Orders induced by segments in floorplans and (2-14-3, 3-41-2)-avoiding permutations[END_REF][START_REF] Asinowski | Separable d-permutations and guillotine partitions[END_REF][START_REF] Eppstein | Area-universal and constrained rectangular layouts[END_REF][START_REF] Reading | Generic rectangulations[END_REF]: it was shown that some important families of rectangulations are enumerated by famous integer sequences (e.g., Baxter, Schröder, Catalan numbers) and that they have strong links with pattern-avoiding permutations (as studied in the seminal article [START_REF] Rong | The number of Baxter permutations[END_REF]). . c) A book on the geometry of building plans [START_REF] Philip | Architectural Morphology[END_REF]. Its cover is not a rectangulation according to our definition (as it contains instances of 4 rectangles meeting in a point). d) This solution to Tutte's famous "Squaring the square" is a rectangulation.

Patterns in rectangulations and summary of our results

Two rectangulations are isomorphic if one can push (horizontally or vertically) some of their segments (without meeting an extremity of any other segment) so that they become identical. This leads to a natural notion of pattern containment. E.g., in the following rectangulations, we highlight an occurrence of (in green), (in blue), (in red).

Note that amongst these three rectangulations, only the first two are isomorphic. We are interested in the enumeration of different natural classes of rectangulations, where the goal is to count the number of non-isomorphic rectangulations of size n. E.g., -avoiding rectangulations are enumerated by Baxter numbers [START_REF] Ackerman | A bijection between permutations and floorplans, and its applications[END_REF][START_REF] Rong | The number of Baxter permutations[END_REF]. Recently, Arturo Merino and Torsten Mütze tackled the question of the exhaustive generation of rectangulations avoiding any subset of t , , , , , , , u.

In [START_REF] Merino | Combinatorial generation via permutation languages[END_REF], they present an efficient algorithm to generate such rectangulations 1 . This led to a surprising observation: many sequences coincide (at least up to size 12) with integer sequences which already appeared in the literature, for apparently unrelated problems.

In Section 3, we solve all the cases related to rectangulations that avoid . These are guillotine diagonal rectangulations, and they correspond to separable permutations (i.e. 2413, 3142q-avoiding permutations). When they avoid further patterns, we prove the following table (where we use the notion of vincular patterns in permutations, see Bóna's overview [START_REF] Bóna | Combinatorics of permutations[END_REF]), and in Theorem 1 we provide generating functions for all these cases.

Entry in [START_REF] Merino | Combinatorial generation via permutation languages[END_REF]Table 3] Guillotine diagonal rectangulations avoiding. . . Separable permutations avoiding. . . G.f. OEIS

Guillotine diagonal rectangulations

The patterns P 1 , P 2 , P 3 , P 4

were considered in some earlier work (for example [START_REF] Ackerman | A bijection between permutations and floorplans, and its applications[END_REF][START_REF] Cardinal | A note on flips in diagonal rectangulations[END_REF]) since they characterize some special kinds of rectangulations.

A rectangulation R is guillotine if it is of size 1, or if it has a cut (a segment whose endpoints lie on opposite sides of R) that splits it into two guillotine rectangulations. It is well known [START_REF] Ackerman | A bijection between permutations and floorplans, and its applications[END_REF] that a rectangulation is guillotine if and only if it avoids P 1 and P 2 (these two patterns are called windmills).

A rectangulation R is called diagonal if it avoids P 3 and P 4 .

This notion is due to the fact that such a rectangulation can be drawn so that the NW-SE diagonal of R intersects all the rectangles. At the same time, diagonal rectangulations are frequently seen as canonical representatives of rectangulations up to the "weak equivalence" [START_REF] Asinowski | Combinatorics of rectangulations: Old and new bijections[END_REF][START_REF] Cardinal | A note on flips in diagonal rectangulations[END_REF]. These two classes have -in different ways -stronger structural properties than the general case. Therefore we expected that families that avoid these four patterns and any other subset of patterns of t , , , u will yield noteworthy results. There are essentially ten different such models, all listed in [16, Table 3]. Amongst these 10 cases, 3 of them can be solved by ad-hoc bijections with trees (see [START_REF] Asinowski | Orders induced by segments in floorplans and (2-14-3, 3-41-2)-avoiding permutations[END_REF][START_REF] Asinowski | Separable d-permutations and guillotine partitions[END_REF]), 2 are conjectured by Merino and Mütze to lead to algebraic generating functions, and for the remaining 5 no conjectures were provided. Below we present a unified framework which allows us to solve these 10 cases (confirming en passant the conjectures of Merino and Mütze). The main result of this section is Theorem 1, which, in particular, states that all these cases are in fact algebraic! Theorem 1. The generating functions for the ten guillotine cases are algebraic.

The generating function of rectangulations avoiding is

Fptq

1 ¡ t ¡ c 1 ¡ 6t t 2 2 .
2. The generating function of rectangulations avoiding satisfies tF 3 2tF 2 p2t ¡ 1qF t 0.

The generating function of rectangulations avoiding

) satisfies t 4 pt¡2q 2 F 4 tpt¡2qp4t 3 ¡7t 2 6t¡1qF 3 p2t 4 ¡t 3 ¡2t 2 5t¡1qF 2 ¡p4t 3 ¡7t 2 6t¡1qF t 2 0.

The generating function of rectangulations avoiding is

Fptq

1 ¡ 3t t 2 ¡ c 1 ¡ 6t 7t 2 ¡ 2t 3 t 4 2t .

The generating function of rectangulations avoiding is

Fptq p1 ¡ tqp1 ¡ 2tq ¡ p1 ¡ tqp1 ¡ 5tq 2tp2 ¡ tq .

6. The generating function of rectangulations avoiding satisfies t 8 pt¡2q 2 F 4 ¡t 3 pt 2 ¡3t 2qpt 5 ¡7t 4 4t 3 ¡6t 2 5t¡1qF 3 ¡tpt¡1qp4t 7 ¡22t 6 37t 5 ¡42t 4 53t 3 ¡35t 2 10t¡1qF 2 ¡p5t 6 ¡16t 5 15t 4 ¡28t 3 23t 2 ¡8t 1qpt¡1q 2 F¡p2t 5 ¡5t 4 4t 3 ¡10t 2 6t¡1qpt¡1q 2 0.

The generating function of rectangulations avoiding is

Fptq tp1 ¡ 16t 11t 2 ¡ 434t 3 1045t 4 ¡ 1590t 5 1508t 6 ¡ 846t 7 252t 8 ¡ 30t 9 q p1 ¡ 2tq 4 p1 ¡ 3t t 2 q 2 p1 ¡ 4t 2t 2 q .

The generating function of rectangulations avoiding is

Fptq

1 ¡ 3t ¡ t 2 2t 3 ¡ c 1 ¡ 6t 7t 2 2t 3 t 4 2t 2 p2 ¡ tq .

The generating function of rectangulations avoiding is

Fptq tp1 ¡ tqp1 ¡ 7t 16t 2 ¡ 11t 3 2t 4 q p1 ¡ 4t 2t 2 qp1 ¡ 3t t 2 q 2 .
10. The generating function of rectangulations avoiding is

Fptq tp1 ¡ 2tq 1 ¡ 4t 2t 2 .
We now present separable permutations -a fundamental class which will be used in the proof of this theorem.

Rectangulations avoiding , and separable permutations

A permutation π is separable if it is either of size 1, or if it is (recursively) a direct sum of separable permutations (in this case π is called ascending separable) or a skew sum of separable permutations (in this case π is called descending separable). We refer to [START_REF] Bóna | Combinatorics of permutations[END_REF] for these notions. Accordingly, separable permutations are precisely the non-empty p2413, 3142q-avoiding permutations [START_REF] Bose | Pattern matching for permutations[END_REF].

The first key step in the proof of Theorem 1 is "translating" (sets of) geometric patterns into (sets of) permutation patterns. In all 10 cases we obtain a bijection between a subclass of guillotine rectangulations and a subclass of separable permutations. We provide details for the first three cases, and just give the key decompositions for the other cases.

Case 1: Guillotine diagonal rectangulations. They are in bijection with separable permutations (see, e.g., [START_REF] Ackerman | A bijection between permutations and floorplans, and its applications[END_REF][START_REF] Asinowski | Separable d-permutations and guillotine partitions[END_REF]). Here is a natural recursive bijection: the rectangulation of size 1 is mapped to the permutation of size 1, and the recursive steps are illustrated in the following drawing. The left and the middle illustrations describe the transformation for horizontal and vertical cuts, and the right illustration is an example of size 11.

G 1 δ(G 1 ) G 2 G k δ(G 2 ) δ(G k ) G 1 G 2 G k δ(G 1 ) δ(G 2 ) δ(G k ) δ δ δ
The recursive definition of separable permutations translates directly to a system of equations that binds Aptq, Dptq, and t Aptq Dptq, the generating functions for ascending, descending, and all separable permutations. Since an ascending (resp. descending) separable permutation can be seen as a sequence of singletons and descending (resp. ascending) separable permutations ("blocks"), we obtain the system , the generating function of Schröder numbers (A006318).

Case 2:

-avoiding guillotine diagonal rectangulations. Lemma 2. A guillotine diagonal rectangulation R avoids if and only if δpRq avoids 2143.

Proof (sketch). This result follows from the bijection δ described above. An occurrence of in R means that there are four rectangles a, b, c, d as in the drawing, where the segment that separates a and b from c and d is a cut at some step of the recursive decomposition of R. It follows that in δpRq we have

Case 3:

-avoiding guillotine diagonal rectangulations. First we show that a guillotine diagonal rectangulation R avoids if and only if δpRq avoids 21354. As in Lemma 2, the proof directly follows from the definition of δ.

Thus, we need to enumerate 21354-avoiding separable permutations. Let π be a direct sum of several singletons and 21354-avoiding descending separable permutations. If π has at most one descending block, then it avoids 21354; and if π has at least three descending blocks, then it contains 21354. If π has precisely two descending blocks, then π is 21354avoiding if and only if these descending blocks are adjacent; the first is 213-avoiding, and the second is 132-avoiding. In its turn, an ascending 213-avoiding permutation is either the identity permutation of size ¥ 2, or consists of at least one singleton and precisely one 213-avoiding descending block (the last block). Let S A and S D be generating functions for ascending and, respectively, descending 213-avoiding (and, equivalently, 132-avoiding) permutations. Then, we have

3 S A t 2 1¡t tS D 1¡t , S D pt S A q 2 1¡pt S A q A
, and for 21354-avoiding separable permutations we have

3 A t 2 1¡t ¡ 1 p1¡tq 2 ¡ 1 © D S 2 D p1¡tq 2 , D pt Aq 2 1¡pt Aq A
. Solving these systems yields Theorem 1(3).

The treatment of other cases in Theorem 1 is similar. That is, we first translate geometric patterns into permutation patterns, thus obtaining some subclass of separable permutations. Then its combinatorial specification yields a system of equations that binds Aptq, the generating functions for ascending permutations in this class, and Dptq for descending permutations. In some cases we use an auxiliary family (as in Case 3 above). Here we omit the details and only list permutation patterns, systems that bind Aptq and Dptq, and, when relevant, auxiliary families and systems for their generating functions S A and S D .

Case 4: t , u-avoiding guillotine diagonal rectangulations. Such rectangulations are called one-sided guillotine rectangulations [START_REF] Felsner | Aspect ratio universal rectangular layouts[END_REF]. This family corresponds to p2143, 3412qavoiding separable permutations. Due to the symmetry of the model, we have Aptq Dptq, and, therefore, just one equation:

A t 2 1¡t ¢ 1 p1¡tq 2 1 1¡ tA 1¡t ¡ 1 A.
Case 5: t , u-avoiding guillotine diagonal rectangulations. They correspond to 2143avoiding separable permutations, the system is

3 A t 2 1¡t ¡ 1 p1¡tq 2 ¡ 1 © D, D pt Aq 2 1¡pt Aq A .
Case 6: t , u-avoiding guillotine diagonal rectangulations. They correspond to p2143, 45312q-avoiding separable permutations. The auxiliary class is p2143, 231q-avoiding permutations. The system for the auxiliary class is

4 S A t 2 1¡t ¢ 1 1¡ tS D 1¡t 1 p1¡tq 2 ¡ 1 S D , S D t 2 1¡t
tS A 1¡t A

. The system for p2143, 45312q-avoiding separable permutations is

4 A t 2 1¡t ¢ 1 p1¡tq 2 1 1¡ tD 1¡t ¡ 1 D, D t 2 1¡t ¡ 1 p1¡tq 2 ¡ 1 © A S 2 A p1¡tq 2 B .
Case 7: t , , u-avoiding guillotine diagonal rectangulations. They correspond to p21354, 45312q-avoiding separable permutations. The auxiliary class is p45312, 213qavoiding permutations. The system for the auxiliary class is

3 S A t 2 1¡t S D 1¡t , S D t 2 1¡t ¡ 1 p1¡tq 2 ¡ 1 © S A ¡ 1 1¡t t 2 1¡2t © 2 B
. The equation for p21354, 45312q-avoiding separable permutations is

A t 2 1¡t ¡ 1 p1¡tq 2 ¡ 1 © A S 2 D p1¡tq 2 .
Case 8: t , , u-avoiding guillotine diagonal rectangulations. They correspond to p2143, 3412q-avoiding separable permutations. The system is

3 A t 2 1¡t ¡ 1 p1¡tq 2 ¡ 1 © D, D t 2 1¡t ¢ 1 p1¡tq 2 1 1¡ tA 1¡t ¡ 1 A B .
Case 9: t , , u-avoiding guillotine diagonal rectangulations. They correspond to p2143, 45312q-avoiding separable permutations. The auxiliary class is p2143, 231q-avoiding permutations. The system for the auxiliary class is

3 S A t 2 1¡t ¡ 1 p1¡tq 2 ¡ 1 © S D , S D t 2 1¡t
tS A 1¡t A

. The system for p2143, 45312q-avoiding separable permutations is

3 A t 2 1¡t ¡ 1 p1¡tq 2 ¡ 1 © D, D t 2 1¡t ¡ 1 p1¡tq 2 ¡ 1 © A S 2 A p1¡tq 2 A .
Case 10: t , , , u-avoiding guillotine diagonal rectangulations. They correspond to p2143, 3412q-avoiding separable permutations. The equation for this symmetric model is

A t 2 1¡t ¡ 1 p1¡tq 2 ¡ 1 © A.

Vortex rectangulations and whirls

In this section we consider a class harder to enumerate, as it is not a guillotine case:

rectangulations that avoid t u (that is, we forbid all our patterns except P 2 ). We denote this class of rectangulations by V, and call them vortex rectangulations. Our ultimate goal is to prove the following conjecture by Merino and Mütze [START_REF] Merino | Combinatorial generation via permutation languages[END_REF].

Theorem 3. The generating function of V is Vptq tC 2 ptqp1 t 2 C 4 ptqq, where Cptq 1¡ c 1¡4t 2t
is the generating function of Catalan numbers. The enumerating sequence of V is A026029.

A vortex either avoids or contains the pattern P 2 . Vortices that avoid constitute Case 10 from Theorem 1. It remains to enumerate vortices with at least one : such rectangulations will be called whirls. The interior of a windmill is the (possibly further partitioned) rectangular area bounded by its segments. The entire rectangle being partitioned by a given rectangulation will be denoted by R. Lemma 4. If a whirl contains several windmills, then they are all nested. In other words: for any two windmills, one of them entirely lies in the interior of the other.

Proof (sketch). Let W be a whirl, and consider some specific occurrence of . Starting from the right vertical segment of this windmill, we alternately go along the segments downwards to their lower endpoint and rightwards to their right endpoint, until we reach the SE corner of R. Similarly we define four alternating paths: see Figure 2 where they are shown by red.

These alternating paths partition R into five areas: R 1 , R 2 , R 3 , R 4 , and the interior of the windmill. In our drawings we color these areas by blue, red, yellow, green, and grey. Then every rectangle in R 1 and in R 3 has its top and bottom sides on the alternating paths, and every rectangle in R 2 and in R 4 has its left and right sides on the alternating paths (see Figure 2). To prove this, for example for R 1 , one scans this area from the left to the right: then the assumption that some rectangle in R 1 violates this condition leads to an occurrence of , or . Moreover, for every rectangle in R 1 its NW corner has the shape and its SW corner has the shape . It follows that if another windmill -not in the interior of the given one -exists, then its segments belong to four different areas R 1 , R 2 , R 3 , R 4 . Hence, the given windmill is entirely included in this another one.

A whirl with an empty interior can be drawn in such a way that all the rectangles in R 1 and R 3 have width 1, and all the rectangles in R 2 and R 4 have height 1 (such a representation is unique). See Figure 2(a) for an example of a whirl which has two nested windmills (the corners of their interiors are shown by small dots).

A whirl is peelable if it has a rectangle that extends from the top to the bottom or from the left to the right side of R. From every peelable whirl it is possible to obtain a unique non-peelable whirl by peeling (i.e., successively deleting such rectangles). Figure 2(b) shows a non-peelable whirl which is obtained from 2(a) by peeling.

Finally, a simple whirl is a non-peelable whirl with precisely one windmill whose interior is not further partitioned. See Figure 2(c) for an example of a simple whirl.

An intriguing functional functional equation

Theorem 5 (Algebraicity of simple whirls). Let Fpt, x 1 , x 2 , x 3 , x 4 q be the multivariate generating function of simple whirls, where z counts their size, and each x i counts the number of rectangles of color i touching their border. This generating function is algebraic and given by the closed form Fpt, x 1 , x 2 , x 3 , x 4 q t 5 1 2α

¢ β ¡ β 2 ¡ 4αe 2 4 (4.1)
with α :

± 4 i1 p1 ¡ x i tx 2
i q and β : p2e 4 t 2 ¡ 4tpe 4 ¡ 3e 3 2e 2 q e 4 ¡ e 3 e 2 ¡ e 1 2qe 4 , where e m : rt m s ± 4 i1 tx i q is the elementary symmetric polynomial of total degree m. In particular, the generating function of simple whirls is Fptq Fpt, 1, 1, 1, 1q t 5 Cptq 4 , where Cptq is the generating function of Catalan numbers.

Proof. The generating tree from Section 4.1.1 translates to the functional equation

Fpt, x 1 , x 2 , x 3 , x 4 q t 5 x 1 x 2 x 3 x 4 tx 1 x 2 x 3 x 4 rx 3 x 4 sFpt, 1, x 2 , x 3 , x 4 q tx 1 x 3 x 4 rx 1 x 4 sFpt, x 1 , x 2 , x 3 , x 4 q ¡ x 2 rx 1 x 4 sFpt, x 1 , 1, x 3 , x 4 q x 2 ¡ 1 tx 1 x 4 rx 1 sFpt, x 1 , x 2 , x 3 , x 4 q ¡ x 3 rx 1 sFpt, x 1 , x 2 , 1, x 4 q x 3 ¡ 1 tx 1 Fpt, x 1 , x 2 , x 3 , x 4 q ¡ x 4 Fpt, x 1 , x 2 , x 3 , 1q x 4 ¡ 1 . ( 4.2)
Unfortunately, there are currently no generic methods to solve this type of catalytic functional equation. Luckily, in our case, we were able to solve this equation; we invite the readers to give it a try before going on with their reading!

Here is how we solved it. First, recall that the valuation of a series f ptq °n¥0 f n t n is the smallest integer n such that f n $ 0 (and valp f ptqq V if f ptq 0). Thus, Equation (4.2) is a contraction in the metric space of formal power series (equipped with the distance dp f ptq, gptqq 2 ¡valpfptq¡gptqq ). Therefore, the Brouwer fixed-point theorem ensures that there is a unique series F satisfying Equation (4.2). Now, it can be checked (by substitution) that the closed form (4.1) satisfies the functional equation (4.2); this proves the theorem.

Let us also explain how we guessed this closed form, as it offers a useful heuristic for dealing with similar equations. The classical guessing technique using Padé approximants is too costly, so, instead, we used linear algebra to identify an algebraic equation of degree 2 (in F) and degree 8 (in x 1 ) for Fpt, x 1 , 11, 31, 71q. It is not obvious from the functional equation that Fpt, x 1 , x 2 , x 3 , x 4 q is a symmetric function in the x i 's -yet, this follows from the fact that any rotation of a whirl is still a whirl. Therefore, its minimal polynomial should also have symmetric coefficients in the x i 's. Then, when one obtains a monomial like 532642x 1 2x 1 ¢ 11 2 ¢ 31 ¢ 71, it makes sense to rewrite it as 2x 1 x 2 2 x 3 x 4 , and all the symmetric versions of this monomial will also appear as coefficients. This leads to the minimal polynomial αF 2 ¡ βF e 4 2 , the solution of which gives the closed form (4.1).

Enumeration of whirls and vortices

We go back from simple whirls to possibly peelable whirls with empty interior by alternately adding sequences of rectangles on the two horizontal and the two vertical sides. This yields the generating function Pptq

t 5 C 4 ptq ¤ ¥ 2 1¡ ¢ 1 p1¡tq 2 ¡1 ¡ 1 .
Such whirls can be transformed into a whirl with ¡ 1 windmills by substituting the interior by another whirl (see Figure 2). Therefore, whirls W with empty interior of the innermost windmill are enumerated as a sequence of Pptq{t.

Conclusion

In this article, we solved several conjectures related to families of pattern-avoiding rectangulations and permutations. We proved that all our generating functions are Nalgebraic2 , and we provide an interesting example of N-algebraic structure (the simple whirls, counted by t 5 C 4 ptq) for which no context-free grammar is known.

Merino and Mütze [16, Table 3] are mentioning a few more families of rectangulations for which the enumeration is still open. Some of them are in fact tractable with variants of methods presented in our article. These results will be included in the long version of our article. It would also be of interest to consider further forbidden patterns, e.g., to determine which patterns lead to algebraic, D-finite, D-algebraic generating functions. Also, is it the case that they all lead to a Stanley-Wilf-like conjecture: is the number of such rectangulations bounded by A n , for some constant A?

In conclusion, the rectangulations, while having a very simple definition, are an inexhaustible source of challenging problems for generating function lovers!

Figure 1 :

 1 Figure 1: a) VLSI are rectangulations playing an important role for integrated circuits. b) The artwork Composition décentralisée, 1924, by Theo van Doesburg (1883-1931).c) A book on the geometry of building plans[START_REF] Philip | Architectural Morphology[END_REF]. Its cover is not a rectangulation according to our definition (as it contains instances of 4 rectangles meeting in a point). d) This solution to Tutte's famous "Squaring the square" is a rectangulation.

3 A

 3 pt Dq 2 1¡pt Dq , D pt Aq 2 1¡pt Aq A . Due to the symmetry Aptq Dptq, we have A pt Aq 2 1¡pt Aq . This yields Fptq 1¡t¡ c 1¡6t t 2 2

1 D

 1 a b c d such that a and b belong to a descending block, and c and d belong to the next descending block. This yields occurrence of 2143 in δpRq. The converse direction is based on similar considerations. Now we enumerate 2143-avoiding separable permutations. Let π be such a permutation. If π is ascending, then it either consists of at least two singletons, or it has one or several descending blocks, which are separated by at least one singleton (see the drawing). For descending permutations the decomposition is identical to Case 1, since the skew sum of 2143-avoiding ascending blocks cannot create a new occurrence of 2143. This leads to the system 4 , D pt Aq 2 1¡pt Aq B . Solving this system (for example by computer algebra) yields Theorem 1(2).

Figure 2 :

 2 Figure 2: Three whirls: (a) is peelable, (b) is non-peelable, (c) is simple.

  Thus we obtain the generating function Wptq 1 1¡Pptq{t . Finally, to get the family V of vortices (i.e. the rectangulations that avoid , , , , , , ), we replace the innermost windmill by a rectangulation that avoids all eight patterns (i.e., Case 10 from Theorem 1, counted by Zptq tp1¡2tq 1¡4t 2t 2 ). This leads to Vptq WptqZptq p1 ¡ 2tq 1 ¡ 4t 2t 2 p1 ¡ 2tq c 1 ¡ 4t 2t 3 tC 2 ptqp1 t 2 C 4 ptqq, which is exactly the generating function of the sequence A026029, as conjectured in [16, Table 3, entry 1345678]. This concludes the proof of Theorem 3. Note that, like for any algebraic generating function [6], the corresponding sequence satisfies a linear recurrence, pn 4qv n ¡6pn 2qv n¡1 4p2n¡1qv n¡2 0, from which one can compute v n in time Op c n ln nq, and singularity analysis [15] gives v n 4 n 2 { c

πn ¡3{2 .

* Supported by FWF -Austrian Science Fund, Grant P32731.

This is the class of generating functions counting words of length n generated by unambiguous context-free grammars. It has many noteworthy structural and asymptotic properties[START_REF] Banderier | Formulae and asymptotics for coefficients of algebraic functions[END_REF][START_REF] Bousquet-Mélou | Rational and algebraic series in combinatorial enumeration[END_REF][START_REF] Chomsky | The algebraic theory of context-free languages[END_REF].

Enumeration of simple whirls

In this section we prove the following remarkable result: simple whirls are enumerated by t 5 C 4 ptq. Our proof combines geometric-structural considerations, the generating tree method [START_REF] Banderier | Generating functions for generating trees[END_REF], and solving a functional equation with catalytic variables. It would be interesting to find an independent bijective proof.

Generating tree

Denote by S 1 , S 2 , S 3 , S 4 the eastern, southern, western, northern sides of R. A signature of a simple whirl is the quadruple pa 1 , a 2 , a 3 , a 4 q, where the component a i is the number of rectangles from R i¡1 that touch S i . (The addition of indices of R i 's and S i 's is mod 4.) For example, the signature of the simple whirl from Figure 2(c) is p3, 2, 1, 2q.

For every i 1, 2, 3, 4, there is precisely one exterior rectangle that belongs to R i and has a ("long") side included in S i and a ("short") side included in S i 1 . (If we assume that this condition is violated, we obtain either a forbidden pattern or a peelable whirl.) Given a simple whirl W, we can construct another simple whirl W I by adding a new exterior rectangle of R i that would completely cover the exterior rectangle of R i in W and possibly extend more towards the side S i¡1 (but not reach it). Some rectangles of R i¡1 will be then extended to reach the modified S i . In W I , a i 1 increases by 1, and a i can assume all the values from 1 to the (original) a i This generation algorithm has the drawback that some simple whirls are generated several times. To generate every simple whirl precisely once, we consider only those possibilities in which the added exterior rectangle of W I belongs to R i with the largest possible i (that is, the largest i such that in W I we have a i 1 ¡ 1). To obtain this, one starts from the initial configuration p1, 1, 1, 1q (only the unique simple whirl of size 5 has this signature), and applies the following rewriting rules


Alessio Silvetti

Francesco Draicchio

Giorgia Chini

Tiwana Varrecchia

Sonny Tarbouriech

Benjamin Navarro

Andrea Cherubini

Alberto Ranavolo

Preliminary results of a biomechanical risk assessment of an actual industrial use-case executed with and without a dual-arm CoBot

à la diffusion 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.

Introduction

Industry 4.0 is the implementation of intelligent technologies to increase productivity and reduce the associated biomechanical risks [1]. From a general perspective, the integration of ergonomics and human factors requirements in human-robot collaborative (HRC) systems, such as collaborative robots (CoBots), represents a new option to reduce the physical effort of workers during the performance of manual material handling (MMH) activities and to introduce new ergonomic interventions for the prevention of work-related musculoskeletal disorders (WMDs). As the use of CoBots in manufacturing has recently increased significantly, all potential benefits need to be thoroughly investigated and proven, especially in the MMH activities where the physical interaction of the worker with the CoBot takes place. While the safety in this new hybrid scenario is widely studied, the effects on workers' health are still limited [2]. The present study aims to investigate the biomechanical parameters of workers performing an industrial use case with (wB) and without (woB) a dual-arm CoBot.

Methods

Four participants (all male; age: 27.8±7.4 years; height: 180.2±2.4 cm; weight: 78.4±10.7 kg; body mass index: 22.2±3.7 kg/m2) took part in the study. We reproduced in the laboratory an industrial application case. The apparatus consisted of the CoBot BAZAR, four tables, and one cylindrical load (5 kg) to be moved and cleaned. The task is to move the cylindrical load between the four tables in a predefined order and to clean it with a brush. The video (available at: https://youtu.be/vul8iLO0Sdw) shows the experiment. We carried out a task analysis with and without Bazar. We identified three main phases in which there were relevant differences in the performance of the task i) phase 1: an initial phase where the worker handled the cylinder; ii) phase 2: the principal phase where the worker holds the cylinder with one hand and brushes it with the other; phase 3: the final phase where the worker placed the brushed cylinder in the packaging area. For the assessment, we used the 3D Static Strength Prediction Program (3DSSPP), which reproduces the workers' posture by superimposing an avatar model on a selected frame. The software calculate various biomechanical parameters: percentage of maximum voluntary contraction (%MVC), static (continuous) allowed exertion time and low back spine compression force (L4Ort). The paired sample t-test (the data was normally distributed) was then used to evaluate whether the help of the CoBot had determined significant changes in each parameter. The significance level for all statistical analyses was set at p-value < 0.05.

Results

The results refer only for phase 2, which is the one that best fits the 3DSSPP because it's a static task. We didn't report values for the left upper arm because we didn't find significant %MVC values, which were all below 5% MVC. We didn't find unfavorable parameters when using a CoBot. We found several parameters that support the use of the CoBot. We found differences in orthogonal force at L4/L5 level (585.8N vs 1171.0N, p≤0.01). We found difference in %MVC of the right arm in favor of CoBot use for wrist flexion/extension (2.5% vs. 44.8%, p≤0.01), wrist rotation (0.0% vs. 22.5%, p≤0.01), shoulder humeral rotation (8.0% vs. 55.3%, p=0.03) and trunk flexion (9.0% vs. 19.8%, p=0.02). We found differences in maximum holding time for wrist flexion/extension (1200 s vs. 74.3 s, p≤0.01) and wrist uln/rad deviation (1200 s vs. 415.8 s, p=0.03), elbow flexion/extension (1200 s vs. 531.5s, p≤0.01), shoulder humeral rotation (873 s vs. 125.2 s, p≤0.01) and shoulder back/forward (1200 s vs. 656.9 s, p≤0.01).

Discussion

Our results seem to support using CoBots in the industrial scenario analyzed. We find benefits for the right wrist, shoulder, and trunk flexion in phase 2. Moreover, it could be possible to automate phase 3. These preliminary positive results should be confirmed and strengthened with a larger sample.


Jonathan D'ambrosio

Romain Morvezen

Sophie Brard-Fudulea

Anastasia Bestin

Pierrick Haffray

Mathilde Dupont-Nivet

Florence Phocas

Factors of variation of genomic selection accuracy for female reproduction traits with a constant reference population size of rainbow trouts

Factors

  of variation of genomic selection accuracy for female reproduction traits with a constant reference population size of rainbow trouts D'Ambrosio J. a,b , Morvezen R. b , Brard-Fudulea S. b , Bestin A. b , Haffray P. b , Dupont-Nivet M. a , Phocas F. a a GABI, INRA, AgroParisTech, Université Paris-Saclay, 78350 Jouy-en-Josas, France b SYSAAF, Campus de Beaulieu, Batiment 16A, Allée Henri Fabre, 35042 Renne cedex, France Aims of the study Material & methods  Reference population : 1346 phenotyped fish (G 14 and F 15 cohorts), genotyped with Axiom TM Trout Genotyping array (57K SNP)  155 parents 57K-genotyped out of 87 dams and 72 sires in the pedigree.  After QC : 29,799 SNP analysed Cohorts  Using BLUPf90 software for (G)EBV estimation and 3 scenarios for training sets : t1: full G 14 cohort t2 : full F 15 cohort t3 : 673 individuals at random in G 14 +F 15 Traits & statistical parameters Impact of kinship between reference and candidate populations Accuracy estimates for BLUP (light colors) and GBLUP (dark colors) according to 3 scenarios for training set (horizontal line bars : t1 ; brick bars : t2 ; plain bars : t3)  Accuracy r : correlation between adjusted phenotypes and (G)EBV divided by the square root of heritability  Mean and standard error of r across 40 replicates of Monte-Carlo 'leave-one group-out' Cross Validation per evaluation scenario for the (G 14 + F 15 ) random training set Accuracy of (G)EBV with BLUP on training set (white) or full phenotype set (light gray), GBLUP (dark gray) and ssGBLUP (black) Conclusion  No gain in accuracy is observed considering multitrait GEBV  Accuracy of (G)EBV increases with the degree of kinship between training and candidate populations. Gain in accuracy of GBLUP compared to BLUP is drastically higher for candidates weakly related to the training population.  Assessing GEBV accuracy for rainbow trout reproduction traits : female body weight at spawning (FW), spawn weight (SW), spawn weight adjusted for FW (SW FW ) and individual egg weight (EW). Investigating changes in accuracy according to (i) the degree of kinship between reference and candidate populations and (ii) the number of phenotypes used : multitrait GBLUP (mGBLUP) or single step GBLUP (ssGBLUP). Accuracy estimates for BLUP (light colors) and GBLUP (dark colors) according to unitrait (plain bars) and multitrait models (stippling bars) Heritability on the diagonal, genetic and phenotypic correlations above and below diagonal, respectively  mGBLUP cannot permit to increase accuracy when all traits are recorded and weakly correlated b) Adding 1711 SW phenotypes from all individuals in A 08 to E 12 cohorts to estimate (G)EBV for SW trait  Including ancestors' phenotypes increases GEBV accuracy by 37% for candidates with all dams phenotyped (t2) and by 6% for a random set (t3) of candidates with phenotyped (G14) and unphenotyped (F15) dams.  GEBV accuracy is significantly higher when candidates are strongly related to the reference population  Adding phenotypes of non-genotyped ancestors through ssGBLUP is usefull to increase GEBV accuracy a) Considering multitrait versus single trait evaluations Truite » projet funded by FEAMP (RFEA47 0016 FA 1000016) and ANRT (n°2017/0239) Cohorts