Michael Huber
email: michael.huber@uni-tuebingen.de

On the existence of block-transitive combinatorial designs

Keywords: Combinatorial design, block-transitive group of automorphisms, 3-homogeneous permutation group

Block-transitive Steiner t-designs form a central part of the study of highly symmetric combinatorial configurations at the interface of several disciplines, including group theory, geometry, combinatorics, coding and information theory, and cryptography. The main result of the paper settles an important open question: There exist no non-trivial examples with t = 7 (or larger). The proof is based on the classification of the finite 3-homogeneous permutation groups, itself relying on the finite simple group classification.

Introduction

One of the outstanding problems in combinatorial design theory concerns the existence of Steiner t-designs (i.e., t-(v, k, 1) designs) with t > 5. In particular the existence of Steiner t-designs admitting an interesting group of automorphisms is of great interest. The known examples for t ≤ 5 often encompass a high degree of regularity and establish deep connections to permutation group theory, geometry, combinatorics, coding and information theory, and cryptography.

There has been recent progress on the existence problem by characterizing Steiner t-designs which admit a flag-transitive group of automorphisms (cf. [START_REF] Huber | Flag-transitive Steiner Designs[END_REF]). In this paper, we focus on the existence problem of Steiner t-designs under the weaker condition of block-transitivity. P. Cameron and C. Praeger [START_REF] Cameron | Block-transitive t-designs, II: large t[END_REF] proved the non-existence of block-transitive (Steiner) t-designs for t > 7. Moreover, they conjectured that there are no non-trivial examples for t = 6. Recently, the author [START_REF] Huber | Steiner t-designs for large t[END_REF][START_REF] Huber | On the Cameron-Praeger conjecture[END_REF] essentially confirmed the non-existence of block-transitive Steiner 6-designs. The main result of the present paper settles now the challenging remaining question for t = 7.

Main Theorem There is no non-trivial Steiner 7-design D admitting a block-transitive group G ≤ Aut(D) of automorphisms.

The paper is organized as follows: Preliminary results which are important for the remainder of the paper are collected in Section 2. In Section 3, a detailed account on previous and related work is presented. In Section 4, the proof of the Main Theorem will be given. It is based on the classification of the finite 3-homogeneous permutation groups, itself relying on the classification of the finite simple groups.

t-Designs

Combinatorial design theory is a fascinating subject on the interface of several disciplines, including group theory, geometry, combinatorics, coding and information theory, and cryptography. In particular, the study of designs with high symmetry properties has a very long history and establishes deep connections between these areas. One of its highlights surely is the remarkable interrelation between the Mathieu-Witt designs, Golay codes, sporadic simple Mathieu groups, Leech lattice, and Kissing Numbers and Sphere Packing problems (cf., e.g., [START_REF] Conway | Sphere Packings, Lattices and Groups[END_REF][START_REF] Huber | Coding theory and algebraic combinatorics[END_REF][START_REF] Macwilliams | The Theory of Error-Correcting Codes[END_REF]). A recent connection with cryptography is given in [START_REF] Huber | Authentication and secrecy codes for equiprobable source probability distributions[END_REF].

Combinatorial designs may be regarded as generalizations of finite projective planes. More formally: For positive integers t ≤ k ≤ v and λ, we define a t-(v, k, λ) design to be a finite incidence structure D = (X, B, I), where X denotes a set of points, |X| = v, and B a set of blocks, |B| = b, satisfying the following regularity properties: each block B ∈ B is incident with k points, and each t-subset of X is incident with λ blocks. A flag of D is an incident point-block pair (x, B) ∈ I with x ∈ X and B ∈ B.

For historical reasons, a t-(v, k, λ) design with λ = 1 is called a Steiner t-design (sometimes also a Steiner system). We note that in this case each block is determined by the set of points which are incident with it, and thus can be identified with a k-subset of X in a unique way. If t < k < v, then we speak of a non-trivial Steiner t-design. As a simple example, the vector space Z n 2 (n ≥ 3) with block set B taken to be the set of all subsets of four distinct elements of Z n 2 whose vector sum is zero is a (boolean) Steiner 3-(2 n , 4, 1) design. There are many infinite classes of Steiner t-designs for t = 2 and 3, however for t = 4 and 5 only a finite number are known. For a detailed treatment of combinatorial designs, we refer to [START_REF] Th | I and II[END_REF][START_REF]Handbook of Combinatorial Designs[END_REF][START_REF] Hughes | Design Theory[END_REF][START_REF] Stinson | Combinatorial Designs: Constructions and Analysis[END_REF]. In particular, [START_REF] Th | I and II[END_REF][START_REF]Handbook of Combinatorial Designs[END_REF] provide encyclopedic accounts of key results and contain existence tables with known parameter sets.

We consider automorphisms of a t-design D as pairs of permutations on X and B which preserve incidence, and call a group G ≤ Aut(D) of automorphisms of D block-transitive (respectively flag-transitive, point t-transitive, point t-homogeneous) if G acts transitively on the blocks (respectively transitively on the flags, t-transitively on the points, t-homogeneously on the points) of D. For short, D is said to be, e.g., block-transitive if D admits a block-transitive group of automorphisms.

For D = (X, B, I) a Steiner t-design with G ≤ Aut(D), let G x denote the stabilizer of a point x ∈ X, and G B the setwise stabilizer of a block B ∈ B. For x, y ∈ X and B ∈ B, we define

G xy = G x ∩ G y .
For any x ∈ R, let x denote the greatest positive integer which is at most x. All other notation is standard.

Combinatorial Existence Results

We recall some standard combinatorial results which we use in this paper. For the existence of t-designs, basic necessary conditions can be obtained via elementary counting arguments (see, for instance, [START_REF] Th | I and II[END_REF]):

Proposition 1 Let D = (X, B, I) be a t-(v, k, λ
) design, and for a positive integer s ≤ t, let S ⊆ X with |S| = s. Then the total number of blocks incident with each element of S is given by

λ s = λ v-s t-s k-s t-s .
In particular, for t ≥ 2, a t-(v, k, λ) design is also an s-(v, k, λ s ) design.

It is customary to set r := λ 1 denoting the total number of blocks incident with a given point (referring to the 'replication number' from statistical design of experiments, one of the origins of design theory).

Corollary 2 Let D = (X, B, I) be a t-(v, k, λ) design. Then the following holds:

(a) bk = vr.

(b) v t λ = b k t . (c) r(k -1) = λ 2 (v -1) for t ≥ 2. Corollary 3 Let D = (X, B, I) be a t-(v, k, λ) design. Then λ v -s t -s ≡ 0 mod k -s t -s
for each positive integer s ≤ t. (a) [START_REF] Tits | Sur les systèmes de Steiner associés aux trois "grands" groupes de Mathieu[END_REF]

): v ≥ (t + 1)(k -t + 1). (b) (Cameron 1976): v -t + 1 ≥ (k -t + 2)(k -t + 1) for t > 2. If equality holds, then (t, k, v) = (3, 4, 8), (3, 6, 22), (3, 12, 112), (4, 7, 23), or (5, 8, 24).
We note that in general Part (a) is stronger for k < 2(t -1), while Part (b) is stronger for k > 2(t -1).

For k = 2(t -1) both assert that v ≥ t 2 -1. As we are in particular interested in the case when t = 7, we deduce from Part (b) the following upper bound for the positive integer k.

Corollary 5 Let D = (X, B, I) be a non-trivial Steiner 7-design. Then

k ≤ √ v + 11 2 .
We finally state two classical results on the existence of t-designs. The first is due to D. Ray-Chaudhuri and R. Wilson [START_REF] Ray-Chaudhuri | On t-designs[END_REF]Thm. 1], and the second is by L. Teirlinck [START_REF] Teirlinck | Non-trivial t-designs without repeated blocks exist for all t[END_REF]: [START_REF] Teirlinck | Non-trivial t-designs without repeated blocks exist for all t[END_REF]. For every positive integer value of t, there exists a non-trivial t-design.

Theorem 6 (Ray-Chaudhuri & Wilson 1975). Let D = (X, B, I) be a t-(v, k, λ) design. If t is even, say t = 2s, and v ≥ k + s, then b ≥ v s . If t is odd, say t = 2s + 1, and v -1 ≥ k + s, then b ≥ 2 v-1 s . Theorem 7
However, although Teirlinck's recursive methods are constructive, they only produce examples with tremendously large values of λ. Via computer search, t-(v, k, λ) designs with t ≥ 6 and smaller values of λ (where λ is at least 4) have been constructed in recent years by the method of orbiting under a group (see [START_REF] Khosrovshahi | t-designs with t ≥ 3[END_REF] for an overview). Until now no non-trivial Steiner t-design with t ≥ 6 is known.

Problem 8 Does there exist any non-trivial Steiner t-design with t ≥ 6?

Previous and Related Work

We focus on t-designs which admit groups of automorphisms with high symmetry properties. One of the early important results is due to R. Block The author [START_REF] Huber | Steiner t-designs for large t[END_REF][START_REF] Huber | On the Cameron-Praeger conjecture[END_REF] recently confirmed the non-existence of block-transitive Steiner 6-designs, modulo two special cases that remain elusive. Theorem 14 (Huber 2010). Let D = (X, B, I) be a non-trivial Steiner 6-design. Then G ≤ Aut(D) cannot act block-transitively on D, except possibly when G = P Γ L(2, p e ) with p = 2 or 3 and e is an odd prime power.

Previously, the author classified all flag-transitive Steiner t-designs with t > 2 (see [START_REF] Huber | Classification of flag-transitive Steiner quadruple systems[END_REF][START_REF] Huber | The classification of flag-transitive Steiner 3-designs[END_REF][START_REF] Huber | On Highly Symmetric Combinatorial Designs[END_REF][START_REF] Huber | A census of highly symmetric combinatorial designs[END_REF][START_REF] Huber | The classification of flag-transitive Steiner 4-designs[END_REF] and [START_REF] Huber | Flag-transitive Steiner Designs[END_REF] for a monograph). These results answered a series of 40-year-old problems and generalized theorems of J. Tits [START_REF] Tits | Sur les systèmes de Steiner associés aux trois "grands" groupes de Mathieu[END_REF] and H. Lüneburg [START_REF] Lüneburg | Fahnenhomogene Quadrupelsysteme[END_REF]. Earlier, F. Buekenhout, A. Delandtsheer, J. Doyen, P. Kleidman, M. Liebeck, and J. Saxl [START_REF] Buekenhout | Linear spaces with flag-transitive automorphism groups[END_REF][START_REF] Delandtsheer | Finite flag-transitive linear spaces with alternating socle[END_REF][START_REF] Kleidman | The finite flag-transitive linear spaces with an exceptional automorphism group[END_REF][START_REF] Liebeck | The classification of finite linear spaces with flag-transitive automorphism groups of affine type[END_REF][START_REF] Saxl | On finite linear spaces with almost simple flag-transitive automorphism groups[END_REF] had essentially characterized all flag-transitive Steiner 2-designs. All these classification results rely on the classification of the finite simple groups. As flag-transitivity clearly implies block-transitivity, these results provide nice examples of block-transitive Steiner designs. An encyclopedic survey of further results, in particular on point-imprimitive blocktransitive t-designs, is given by [START_REF] Delandtsheer | Block-transitive designs[END_REF].

Proof of the Main Theorem

We prove in this section our Main Theorem stated in Section 1. In order to investigate the existence problem of non-trivial block-transitive Steiner 7-designs, we can as a consequence of Proposition 11 (a) make use of the classification of all finite 3-homogeneous permutation groups, which itself relies on the classification of all finite simple groups (cf. [START_REF] Cameron | Finite permutation groups and finite simple groups[END_REF][START_REF] Gorenstein | Finite Simple Groups. An Introduction to Their Classification[END_REF][START_REF] Kantor | k-homogeneous groups[END_REF][START_REF] Liebeck | The affine permutation groups of rank three[END_REF][START_REF] Livingstone | Transitivity of finite permutation groups on unordered sets[END_REF]). We remark that the list given in [7, List 2.2] is slightly incomplete.

Finite 3-homogeneous Permutation Groups

The list of groups is as follows: Let G be a finite 3-homogeneous permutation group on a set X with |X| ≥ 4. Then G is either of (A) Affine Type: G contains a regular normal subgroup T which is elementary Abelian of order v = 2 d . If we identify G with a group of affine transformations

x → x g + u of V = V (d, 2)
, where g ∈ G 0 and u ∈ V , then particularly one of the following occurs:

(1) G ∼ = AGL(1, 8), AΓ L(1, 8), or AΓ L(1, 32) (2) G 0 ∼ = SL(d, 2), d ≥ 2 (3) G 0 ∼ = A 7 , v = 2 4
or (B) Almost Simple Type: G contains a simple normal subgroup N , and N ≤ G ≤ Aut(N ). In particular, one of the following holds, where N and v = |X| are given as follows:

(1) A v , v ≥ 5

(2) P SL(2, q), q > 3, v = q + 1

(3) M v , v = 11, 12, 22, 23, 24 (Mathieu groups) (4) M 11 , v = 12
We note that if q is odd, then P SL(2, q) is 3-homogeneous for q ≡ 3 (mod 4), but not for q ≡ 1 (mod 4), and hence not every group G of almost simple type satisfying (2) is 3-homogeneous on X. where x and y are two distinct points in X and B is a block in B. We will see that this arithmetical condition in combination with the combinatorial tools from Section 2 gives immediately strong results for some of the cases to be examined.

If we assume that k ≥ 27, then obviously

k(k -1)(k -2)(k -3) < 2[(k -5)(k -6)] 2 ,
and hence (q -2)(q -3)(q -4) |G B | • n < 2(q -5) 2 (k -4) • a ≤ 2(q -5) 2 q + 1 + 3 2

• a in view of Inequality (2) and Corollary 5. Taking into account that always a ≤ log 2 q, it follows immediately that |G B | • n = 1 for each possible value of q = 32. Hence, in particular q must be even. But then the right hand side of Equation ( 1) is always divisible by 16 but never the left hand side, a contradiction.

The case q = 32 as well as the few remaining possibilities for k < 27 can easily be ruled out by hand using Equation (1) and Inequality (2).

This completes the proof of the Main Theorem. 2

  1365-8050 c 2010 Discrete Mathematics and Theoretical Computer Science (DMTCS), Nancy, France 2 Preliminary Results

  For non-trivial Steiner t-designs lower bounds for v in terms of k and t can be given (see P. Cameron [5, Thm. 3A.4], and J. Tits [37, Prop. 2.2]): Proposition 4 If D = (X, B, I) is a non-trivial Steiner t-design, then the following holds:

[ 2 ,

 2 Thm. 2]: Proposition 9 (Block 1965). Let D = (X, B, I) be a non-trivial t-(v, k, λ) design with t ≥ 2. If G ≤ Aut(D) acts block-transitively on D, then G acts point-transitively on D.

For a 2 -

 2 (v, k, 1) design D, it is elementary that the point 2-transitivity of G ≤ Aut(D) implies its flagtransitivity. For 2-(v, k, λ) designs, this implication remains true if r and λ are relatively prime (see, for instance,[START_REF] Dembowski | Finite Geometries[END_REF] Chap. 2.3, Lemma 8]). However, for t-(v, k, λ) designs with t ≥ 3, it can be deduced from Proposition 9 that always the converse holds (see[START_REF] Buekenhout | Remarques sur l'homogénéité des espaces linéaires et des systèmes de blocs[END_REF] or [14,Lemma 2]):Proposition 10 Let D = (X, B, I) be a non-trivial t-(v, k, λ) design with t ≥ 3. If G ≤ Aut(D)acts flag-transitively on D, then G acts point 2-transitively on D. Investigating highly symmetric t-designs for large values of t, P. Cameron and C. Praeger [7, Thm. 2.1] deduced from Theorem 6 and Proposition 9 the following assertion: Proposition 11 (Cameron & Praeger 1993). Let D = (X, B, I) be a t-(v, k, λ) design with t ≥ 2. Then, the following holds: (a) If G ≤ Aut(D) acts block-transitively on D, then G also acts point t/2 -homogeneously on D. (b) If G ≤ Aut(D) acts flag-transitively on D, then G also acts point (t + 1)/2 -homogeneously on D. As for t ≥ 7 the flag-transitivity, respectively for t ≥ 8 the block-transitivity of G ≤ Aut(D) implies at least its point 4-homogeneity, they obtained the following restrictions as a consequence of the finite simple group classification (cf. [7, Thm. 1.1]): Theorem 12 (Cameron & Praeger 1993). Let D = (X, B, I) be a t-(v, k, λ) design. If G ≤ Aut(D) acts block-transitively on D then t ≤ 7, while if G ≤ Aut(D) acts flag-transitively on D then t ≤ 6. Moreover, they formulated the following far-reaching conjecture (cf. [7, Conj. 1.2]): Conjecture 13 (Cameron & Praeger 1993). There are no non-trivial block-transitive 6-designs.

Remark 15 - 1 )

 151 If G ≤ Aut(D) acts block-transitively on any Steiner t-design D with t ≥ 6, then by Proposition 11 (a), G acts point 3-homogeneously and in particular point 2-transitively on D. Applying Corollary 2 (b) yields the equation |G xy | |G B | ,

Michael Huber

Acknowledgements

The author gratefully acknowledges support by the Deutsche Forschungsgemeinschaft (DFG) via a Heisenberg grant (Hu954/4).

Groups of Automorphisms of Affine Type

Using the notation as before, let us assume for the rest of the section that D = (X, B, I) is a non-trivial Steiner 7-design with G ≤ Aut(D) acting block-transitively on D. Clearly, we may assume that k > 7 as we do not consider trivial designs. We will examine in this subsection those cases where G is of affine type.

Case (1): G ∼ = AGL [START_REF] Th | I and II[END_REF][START_REF]Handbook of Combinatorial Designs[END_REF], AΓ L(1, 8), or AΓ L [START_REF] Th | I and II[END_REF][START_REF] Macwilliams | The Theory of Error-Correcting Codes[END_REF]. As k > 7, the case v = 8 is not possible. For v = 32, we have |G| = 5v(v -1) and k ≤ 11 by Corollary 5. The few possibilities can easily be ruled out using Corollary 2 together with Remark 15.

Let e i denote the i-th standard basis vector of the vector space V = V (d, 2), and e i the 1-dimensional vector subspace spanned by e i . We will prove by contradiction that G ≤ Aut(D) cannot act blocktransitively on any non-trivial Steiner 7-design D.

We may assume that v = 2 d > k > 7. We remark that clearly any seven distinct points are noncoplanar in AG(d, 2) and hence generate an affine subspace of dimension at least 3. Let E = e 1 , e 2 , e 3 denote the 3-dimensional vector subspace spanned by e 1 , e 2 , e 3 . Then SL(d, 2) E , and therefore also G 0,E , acts point-transitively on V \ E. If the unique block B ∈ B which is incident with the 7-subset {0, e 1 , e 2 , e 3 , e 1 + e 2 , e 2 + e 3 , e 1 + e 3 } contains some point outside E, then it would already contain all points of V \ E. But then k ≥ 2 d -8 + 7 = 2 d -1, a contradiction to Corollary 5. Hence, B lies completely in E. The block-transitivity of G now implies that each block must be contained in a 3-dimensional affine subspace. On the other hand, any seven distinct points that do not lie in a 3-dimensional affine subspace must also be incident with a unique block by the definition of Steiner designs, a contradiction. 4 , we have k ≤ 9 by Corollary 5. But, Corollary 2 (c) obviously eliminates the cases when k = 8 or 9.

Groups of Automorphisms of Almost Simple Type

When G is of almost simple type, then the Cases (B) (1), ( 3) and (4) of Section 4.1 cannot occur as elementarily proved in [7, Sect. 2, mainly Prop. 2.4]. Hence, we only have to consider Case (2): N = P SL(2, q), v = q + 1, q = p e > 3.

Here Aut(N ) = P Γ L(2, q), and |G| = (q + 1)q (q-1) n a with n = (2, q -1) and a | ne. We may assume that q ≥ 8. We will show that G ≤ Aut(D) cannot act block-transitively on any non-trivial Steiner 7-design D.

From Remark 15, we obtain

Due to Proposition 4 (b), we have q -5 ≥ (k -5)(k -6).

Hence, from Equation (1) follows (q -2)(q -3)(q -4)


Guy Louchard
email: louchard@ulb.ac.be

Asymptotics of the Stirling numbers of the first kind revisited: A saddle point approach

Keywords:

Using the saddle point method, we obtain from the generating function of the Stirling numbers of the first kind » n j and Cauchy's integral formula, asymptotic results in central and non-central regions. In the central region, we revisit the celebrated Goncharov theorem with more precision. In the region j = n -n α , α > 1/2, we analyze the dependence of » n j on α.

Introduction

Let n j be the Stirling number of the first kind (unsigned version). Their generating function is given by

φ n (z) = n-1 0 (z + i) = Γ(z + n) Γ(z) , φ n (1) = n!.
In the sequel all asymptotics are meant for n → ∞.

An asymptotic expansion for j = O(1) is given in Wilf [START_REF] Wilf | The asymptotic behavior of the Stirling numbers of the first kind[END_REF], which has been extended to the range j = O(ln n) by Hwang [START_REF] Hwang | Asymptotic expansions for the Stirling numbers of the first kind[END_REF]. The generalized Stirling numbers have been considered by Tsylova [START_REF] Tsylova | Probabilistic methods for obtaining asymptotic formulas for generalized Stirling numbers[END_REF] and Chelluri et al. [START_REF] Chelluri | Asymptotic estimates for generalized Stirling numbers[END_REF]. The q-Stirling numbers are studied in Kyriakoussis and Vamvakari [START_REF] Kyriakoussis | On asymptotic for the signless noncental q-Stirling numbers of the first kind[END_REF].

In Sec.2, we revisit the asymptotic expansions in the central region and in Sec.3, we analyse the noncentral region j = n -n α , α > 1/2. We use Cauchy's integral formula and the saddle point method.

Central region

Consider the random variable J n , with probability distribution

P[J n = j] = Z n (j), Z n (j) := n j n! .
The mean and variance are given by

M := E(J n ) = n-1 0 1 1 + i = H n = ψ(n + 1) + γ, σ 2 := V(J n ) = n-1 0 i (1 + i) 2 = ψ(1, n + 1) + ψ(n + 1) - π 2 6 + γ,
where ψ(x) is the digamma function, ψ(k, x) is the kth polygamma function, and

M ∼ ln(n) + γ + 1 2n + O 1 n 2 , σ 2 ∼ ln(n) - π 2 6 + γ + 3 2n + O 1 n 2 .

It is convenient to set

A n := ln(n) -π 2 6 + γ = ln ne γ-π 2 /6 , and to consider all our next asymptotics (n → ∞) as functions of A n . Of course, all asymptotics can be reformulated in terms of ln(n).

We have

M ∼ A n + π 2 6 + O 1 n , σ 2 ∼ A n + O 1 n .
A celebretated central limit theorem of Goncharov says that

J n ∼ N (M, σ) ,
where N is the Gaussian distribution, with a rate of convergence O(1/ ln(n)). This can also be deduced from the Quasi-Power theorem of Hwang [START_REF] Hwang | Théorèmes limites pour les structures aléatoires et les fonctions arithmétiques[END_REF], [START_REF] Hwang | On convergence rates in the central limit theorems for combinatorial structures[END_REF].

In this Section, we want to obtain a more precise local limit theorem for J n in terms of x := Jn-M σ and A n . Actually, we obtain the following theorem, where we use B n := √ A n to simplify the expressions.

Theorem 2.1

Z n (j) ∼ 1 √ 2πB n e -x 2 /2 • • 1 + x 3 /6 -x/2 B n + 3x 2 /8 -x 4 /6 -1/12 + x 6 /72 B 2 n + -π 2 x 3 /18 + 37x 5 /240 -355x 3 /144 + x/8 -x 7 /48 + x 9 /1296 + π 2 x/6 -ζ(3)x + ζ(3)x 3 /3 B 3 n + . . . . Proof: By Cauchy's theorem, Z n (j) = 1 2πi Ω φ n (z) z j+1 n! dz = 1 2πi Ω e S(z) dz,
where Ω is inside the analyticity domain of the integrand and encircles the origin and

S(z) = S 1 (z) + S 2 (z), S 1 (z) = n-1 i=0 ln(z + i)) -ln(n!), S 2 (z) = -(j + 1) ln(z).
We will use the Saddle point method (for a good introduction to this method, see Flajolet and Sedgewick [START_REF] Flajolet | Analytic combinatorics[END_REF], ch.V III). Set

S (i) := d i S dz i .
These derivatives can be expressed in terms of ψ(k, z + n) and ψ(k, z).

First we must find the solution of S (1) (z) = 0

with smallest module. Set z := z * -ε, where z * = lim n→∞ z. Here, it is easy to check that z * = 1. Set j = M + xσ, x fixed and B n := √ A n . This leads, to first order (keeping only the ε term in (1)), to

ε := -x B n + x 2 -1 B 2 n + . . . + 1 n 3x 4B 3 n + . . . + O 1 n 2 B 4 n .
This shows that, asymptotically, ε is given by a series of powers of n -1 , where each coefficient is given by a series of powers of B -1 n . To obtain more precision, we set again j = M + xσ, expand in powers of n -1 , and equate each coefficient to 0. . This leads to (here and in the following, we provide only a few terms but Maple knows more)

ε = -x B n - 1 B 2 n + 0 B 3 n + . . . + 1 n 3x 4B 3 n + x 2 + 3/2 B 4 n + . . . + O 1 n 2 B 4 n . We have, with z := z * -ε = 1 -ε, Z n (j) = 1 2πi Ω exp S(z) + S (2) (z)(z -z) 2 /2! + ∞ l=3 S (l) (z)(z -z) l /l! dz.
Note that the linear term vanishes. Set z = z + iτ . This gives

Z n (j) = 1 2π exp[S(z)] ∞ -∞ exp S (2) (z)(iτ ) 2 /2! + ∞ l=3 S (l) (z)(iτ ) l /l! dτ. (2)
The justification of the integration procedure is given in the Appendix. Let us first analyze S(z). We obtain

S(z) = -x 2 /2 + x 3 /6 -x B n + -x 4 /12 + x 2 /2 -1/2 B 2 n + -x 3 /3 + x 5 /20 + x/2 -π 2 x 3 /18 + ζ(3)x 3 /3 B 3 n + . . . + O 1 nB 3 n . Also, S (2) (z) = B 2 n -B n x -1 + x 2 + . . . , S (3) (z) = -2B 2 n + 4B n x -π 2 /3 + 2ζ(3) -6x 2 + 4 + . . . , S (4) (z) = 6B 2 n -18B n x + 36x 2 -18 + π 2 -π 4 /15 + . . . , S (l) (z) = O B 2 n , l ≥ 5.
We need these many terms in the following. Note that, with z = ze iθ , this leads to

S (2) (z) (z -z) 2 2 ∼ - 1 2 ln(n)θ 2 . ( 3
)
We can now compute (2), for instance by using the classical trick of setting

S (2) (z)(iτ ) 2 /2! + ∞ l=3 S (l) (z)(iτ ) l /l! = -u 2 /2.
Computing τ as a truncated series in u, this gives, by inversion,

τ = u(1 + x/(2B n ) + . . .) + u 2 (i/(3B n ) + . . .) + u 3 (-1/(36B 2 n ) + . . .) /B n + . . . Setting dτ = dτ du du, expanding w.r.t. B n and integrating on [u = -∞..∞], this gives 1 √ 2πB n 1 + x 2B n + 5/12 -x 2 /8 B 2 n + x(8π 2 -10 -93x 2 -48ζ(3)) 48B 3 n + . . . . 0
√ 2πσ exp h -`j-M σ ´2. 2 i , n = 3000
Finally (2) leads to

Z n (j) ∼ 1 √ 2πB n e -x 2 /2 • • exp x 3 /6 -x B n + -x 4 /12 + x 2 /2 -1/2 B 2 n + -x 3 /3 + x 5 /20 + x/2 -π 2 x 3 /18 + ζ(3)x 3 /3 B 3 n + . . . • • 1 + x 2B n + 5/12 -x 2 /8 B 2 n + x(8π 2 -10 -93x 2 -48ζ(3)) 48B 3 n + . . . , or Z n (j) ∼ R 1 , R 1 = 1 √ 2πB n e -x 2 /2 • • 1 + x 3 /6 -x/2 B n + 3x 2 /8 -x 4 /6 -1/12 + x 6 /72 B 2 n + -π 2 x 3 /18 + 37x 5 /240 -355x 3 /144 + x/8 -x 7 /48 + x 9 /1296 + π 2 x/6 -ζ(3)x + ζ(3)x 3 /3 B 3 n + . . . . 2
For n = 3000, a comparison between Z n (j) and 1

√ 2πσ exp -j-M σ 2
2 is given in Figure 1.

Fig. 2: Zn(j)

.h

1 √ 2πσ exp h -`j-M σ ´2. 2 ii , color=red, Zn(j)/R1, color=blue, n = 3000
Of course, only few values of j are significant and also the quality of the Gaussian is low, all asymptotic expressions depend actually on powers of A -1 n , but A n is not large. A comparison of Z n (j)

1 √ 2πσ exp -j-M σ 2 2 with Z n (j)/R 1 , with 2 terms in R 1 , is given in Figure 2.
The precision of R 1 is of order 10 -2 . Using 3 terms in R 1 leads to a less good result: A n is not large enough to take advantage of the A -3/2 n term: A n = 6.94 here, we deal with asymptotic series, not necessarily convergent ones. More terms can be computed in R 1 (which is almost automatic with Maple).

3 Large deviation, j = n -n α , 1 > α > 1/2

The case j = O(n) is analyzed in Timashev [START_REF] Timashev | On asymptotic expansions of Stirling numbers of the first and second kind[END_REF]. But he obtains a series of powers of n -1 , determined by a power series of a certain function that depends on the solution of a given non-linear differential equation of the first order. The coefficients obey some linear recurrence relations in the complex plane. The case j = n -c, c constant, is considered in Grünberg [START_REF] Grünberg | On asymptotics, Stirling numbers, Gamma function and polylogs[END_REF]. As previous work for the case j = n -n α , let us mention Bender [START_REF] Bender | Central and local limit theorems applied to asymptotics enumeration[END_REF], Temme [START_REF] Temme | Asymptotic estimates of Stirling numbers[END_REF], Moser and Wyman [START_REF] Moser | Asymptotic development of the Stirling numbers of the first kind[END_REF] (see also the comments by Odlyzko in [START_REF] Graham | Handbook of Combinatorics[END_REF], p.1182). They all use, explicitly or not, the Saddle point method. For α < 1/2, Moser and Wyman (6.9) give an explicit asymptotic expression. For α > 1/2, they first compute in (4.52) the numerical solution zn of S (zn) = 0 and give in (4.51) an asymptotic expression. This is rather precise: for n = 50, this gives a precision of order 10 -4 . [START_REF] Bender | Central and local limit theorems applied to asymptotics enumeration[END_REF] and [START_REF] Temme | Asymptotic estimates of Stirling numbers[END_REF] also compute numerically zn.

However, all these results do not shed light on the dependence of [z j ]φ(z) on n α . This is what we want to explicit in this Section. It appears that the range α > 1/2 is more delicate than the other range.

Recall that

φ n (z) = n-1 0 (z + i) = Γ(z + n) Γ(z) .
We have

G n (z) := Γ(z + n) Γ(z)z j+1 = exp[S(z)],
with

S(z) = S 1 (z) + S 2 (z), S 1 (z) = n-1 0 ln(z + i), S 2 (z) = -(j + 1) ln(z).
We first compute z such that S (z) = 0.

We have

S (z) = ψ(z + n) -ψ(z) - j + 1 z .
Similarly (we need these expressions later on)

S (2) (z) = ψ(1, z + n) -ψ(1, z) + j + 1 z 2 , S (k) (z) = ψ(k -1, z + n) -ψ(k -1, z) + (-1) k (k -1)! j + 1 z k .
Some experiments with some values for α (α = 5/8 is a good choice) show that z must be a combination of x = n α and y = n 1-α and x y 1. Note that both x and y are large. We will derive series of powers of x -1 , where each coefficient is a series of powers of y -1 . We obtain the following theorem Theorem 3.1 Proof: Let us summarize the different steps of the proof. First we compute z and S(z) as S(z) = T 1 T 2 , where T 1 is the dominant term and T 2 is a series of powers of x -1 , where each coefficient is a series of powers of y -1 . We expand T 3 := e T2 . Next the integration procedure leads to y 2 √

[z j ]φ n (z) ∼ 1 √ 2π
y 2 √ x 2
x 2 T 4 , where T 4 is again a series of powers of x -1 , where each coefficient is a series of powers of y -1 . We set T 5 := 1 √ 2π

y 2 √ x 2 e T1 . Finally, we obtain [z j ]φ n (z) ∼ T 5 T 3 T 4 . (5)
The first terms in the asymptotics of z are easy to compute: set z = nβ. Equation (4) leads to

ψ(n(1 + β)) -ψ(nβ) = 1 β - 1 yβ + 1 nβ .
But ψ(n) ∼ ln(n). So we have

ln 1 + 1 β ∼ 1 β - 1 yβ + 1 nβ , or 1 β - 1 2β 2 ∼ 1 β - 1 yβ ,
or β ∼ y 2 . More generally, we have

β = y 2 1 + a 1 y + a 2 y 2 + a 3 y 3 + . . . + 1 x 1 + b 1 y + b 2 y 2 + . . . + 1 x 2 1 + c 1 y + c 2 y 2 + . . . + O 1 x 3 .
Note that 1 y 3 can be of the same order than

+ 1 x 3 [1 + . . .] +O 1 x 4 . ( 6
)
Note that the choice of dominant terms in the bracket of ( 6) depends on α. For instance, for α = 3/4, the dominant terms (in decreasing order) are

1, 1 y , 1 y 2 , 1 x , 1 y 3 , 1 xy , 1 y 4 , 1 xy 2 , 1 y 5 , 1 x 2 , 1 xy 3 , 1 y 6 , .
. . Now we must compute S(z) and its asymptotics. First we compute ln(z + i), take the asymptotics wrt x, sum on i, and again take the asymptotics wrt x (recall that n = xy). this leads to

S 1 (z) = x (-ln(2) + 2 ln(y) + ln(x))y - 1 3 + 4 405y 2 + 2 405y 3 + . . . + y - 2 3 - 2
S(z) = S 1 (z) + S 2 (z) ∼ x 1 -ln(2) + 2 ln(y) + ln(x) - 2 3y + . . . + ln(2) -2 ln(y) -ln(x) + 1 3y + 1 3y 2 + . . . + 1 x - 1 2 + 1 3y - 1 2y 2 + . . . + 1 x 2 - 1 6 + 19 18y 2 . . . + O 1 x 3 .
Now we split S(z) into two parts:

T 1 = x 1 -ln(2) + 2 ln(y) + ln(x) - 2 3y + . . . + ln(2) -2 ln(y) -ln(x), T 2 = 1 3y + 1 3y 2 + . . . + 1 x - 1 2 + 1 3y - 1 2y 2 + . . . + 1 x 2 - 1 6 - 17 18y 2 . . . + O 1 x 3 .
Note that the dominant term of T 1 is given by

T 1 ∼ (2 -α)n α ln(n). (7)
We obtain exp(S(z)) = e T1 e T2 = e T1 T 3 , with

T 3 = e T2 =
+ O 1 x 3 .
Here we have given all terms compatible with the expansion (6). Also, with more precision, Now we must consider S (k) (z). By direct expansion, this gives the following expressions (again we provide only the first few terms). We must use up to six derivatives to get a sufficient precision (of order x -2 ) in the Saddle integrals. -4 y 4 + . . .

T 1 = x 1 -ln(2) + 2 ln(y) + ln(x) - 2
+ O 1 x 5 y 4 , (8)
Note that, with z = ze iθ , this leads to We proceed now as in Section 2. Again, the justification of the integration procedure is given in the Appendix. This leads to We give only a 1 : Set

S (2) (z) (z -z) 2 2 ∼ - 1 2 n α θ 2 . ( 9
τ = y 2 √ x 2 ua 1 + u 2 a 2 x 1/2 + u 3 a 3 x + u 4 a 4 x 3/2 + u 5 a 5 x 2 + O u 6 x 5/
a 1 = 1 - 2
T 5 := 1 √ 2π y 2 √ x 2 e T1 .
This leads to

[z j ]φ n (z) ∼ T 5 T 3 T 4 . (10)
We can of course combine T 3 and T 4 : Let us consider the precision of our asymptotics. The quality of asymptotic ( 6) is given in Figure 3 and4, for n = 500, and x ∈ [ √ n, n 0.9 ] (first range) so that y ∈ [n 0.1 , √ n]. For some values of j = n -x, we show z/zn, where, as mentioned, zn is the numerical solution of S (zn) = 0. In the full range j ∈ [n -n 0.9 , n -√ n], the precision is of order 10 -5 , in a restricted range, the precision is of order 10 -6 .

T 6 := T 3 T 4 = 1 - 3
Also a comparison of G n (z) and G n (zn) is given in Figure 5, showing again a precision of order 10 -6 .

To check the quality of asymptotic (6), we give in Figure 6 the comparison between the expression (8) and S (2) (z). The precision is of of order 10 -2 .

In a restricted range, given in Figure 7, the precision is of order 10 -4 . α ≤ 0.84 in this range.

We have made several experiments with [START_REF] Moser | Asymptotic development of the Stirling numbers of the first kind[END_REF], with n up to 500. The result is unsatisfactory, only values of x of order √ n give reasonable results. Also using e T2 instead of T 3 does not improve the precision. Actually, only very large values of n lead to good precision. So we turn to another formulation: instead of using e T1 T 3 for e S(z) , we plug directly z into G n (z), ie we set

T 7 = G n (z), leading to [z j ]φ n (z) ∼ 1 √ 2π
y 2 √ x 2
T 7 T 4 =: T 8 say.

For n = 500, using two and three terms in T 4, we give in Figures 8 and9, the quotient [z j ]φ n (z)/T 8 . The precision is of order 10 -5 .

Conclusion

Using an almost mechanized program in Maple, we have obtained some asymptotic expressions for Stirling numbers in central and non-central regions. We intend to use these techniques in other non-central ranges.

Acknowledgement

The pertinent comments of the referee led to improvements in the presentation.

A Appendix. Justification of the integration procedure

A.1 The central region

We proceed as in Flajolet and Sedgewick [START_REF] Flajolet | Analytic combinatorics[END_REF], ch.V III. We can choose here z = 1. This leads, with z = e iθ , to S(z) ∼ S0(z) + O " p ln(n)θ " + constant term,

S ( 2 )

 2

Fig. 7 :

 7 Fig. 7: The quotient of the expression (8) and S (2) (z), as function of j, n = 500. Restricted range, α ≤ .84

Fig. 8 :Fig. 9 :

 89 Fig. 8: The quotient [z j ]φn(z)/T8, two terms in T4, as function of j, n = 500

  )

			S (3) (z) =	1 x 2 -	32 y 6 + . . .
	1			+	1 x 3	128 y 6 + . . .
	0.99999995			+	1 x 4 -	192 y 6 + . . .
	0.9999999			+	1 x 5	128 y 6 + . . .
				+ O	1 x 6 y 6 ,
	0.99999985
			S (4) (z) =	1 x 3	288 y 8 + . . .
	0.9999998	250	300	+	350 1 x 4 -	400 1440 y 8 + . . .	450
				+	1 x 5	2880 y 8 + . . .
		Fig. 5: Gn(zn)/Gn(z), n = 500, as function of j + 1 x 6 -2880 y 8 + . . .
				+ O	1 x 7 y 8 ,
			S (5) (z) =	1 x 4 -	3072 y 10 + . . .
	0.998 1			+	1 x 5	18432 y 10 + . . .
	0.994 0.996			+ O	1 x 6 y 10 ,
	0.992		S (6) (z) =	1 x 5	38400 y 12 + . . .
	0.99
	0.988			+	1 x 6	268800 y 12 + . . .
	0.984 0.986			+ O	1 x 7 y 12 .
		250	300		350		400	450
	Fig. 6: The quotient of the expression (8) and S (2) (z) as function of j, n = 500

  2 .

	1.0003
	1.0002
	1.0001
	1
	0.9999
	0.9998
	320	340	360	380	400	420	440	460

1365-8050 c 2010 Discrete Mathematics and Theoretical Computer Science (DMTCS), Nancy, France

with

We have

which conforms to (3). The function h(θ) is the same as in [START_REF] Flajolet | Analytic combinatorics[END_REF], Ex.V III.3, which proves the validity of our integration procedure: we use here Hn ∼ ln(n) instead of n. The complete asymptotic expansion is justified as in [START_REF] Flajolet | Analytic combinatorics[END_REF], Ex.V III.4.

A.2 The non-central region

We choose here z = ny 2 = n 2-α 2 := δ, say . We have

Set z = δe iθ , this leads, with Euler-Maclaurin formula, with the first correction (the other corrections are negligible), to

Set now n = ρδ, ρ = 2n α-1 1 and expand wrt ρ. This gives

Note that the dominant constant contribution is given by 1 2 ρ 2 δ ln(δ) = (2 -α)n α ln(n), which conforms to [START_REF] Hwang | Théorèmes limites pour les structures aléatoires et les fonctions arithmétiques[END_REF]. The first term gives a variable part O(ρ). The second term gives a variable part 2n α h(θ) + O(ρ 2 ), with

The third term give O(n 2α-1 ) n α . Note that 2n α h(θ) ∼ -1 2 n α θ 2 , which conforms to [START_REF] Kyriakoussis | On asymptotic for the signless noncental q-Stirling numbers of the first kind[END_REF]. The function ˛eh(θ) ˛= e cos(θ)/2 is unimodal with peak at 0 and h(0) = 1/2. Let us introduce a splitting value θ0 such that

For instance, we choose θ0 = n β , β = -5α 12 . By unimodality property of the cosine, the tail integral K (1) n :=

for some C > 0. The tail integral is exponentially small. As h(θ) ∼ -θ 2 4 , the central approximation and the tail completion are immediate.


Li Dong

Zhicheng Gao

Daniel Panario

Bruce Richmond

Asymptotics of Smallest Component Sizes in Decomposable Combinatorial Structures of Alg-Log Type

Keywords: decomposable structures, restricted pattern, labeled and unlabeled structures, generating functions, alg-log type

A decomposable combinatorial structure consists of simpler objects called components which by themselves can not be further decomposed. We focus on the multi-set construction where the component generating function

when z is near the dominant singularity ρ. We provide asymptotic results about the size of the smallest components in random combinatorial structures for the cases 0 < α < 1 and any β, and α < 0 and β = 0. The particular case α = 0 and β = 1, the so-called exp-log class, has been treated in previous papers. We also provide similar asymptotic estimates for combinatorial objects with a restricted pattern, that is, when part of its factorization pattern is known. We extend our results to include certain type of integers partitions.

Introduction

A decomposable combinatorial structure consists of simpler objects called components which by themselves can not be further decomposed. For example, permutations decompose into cycles, graphs into connected components, and polynomials over finite fields into irreducible factors.

We assume that the component generating function C(z) is of alg-log type, that is, near the singularity ρ, C(z) behaves like A precise definition is given in the following sections. We call α the algebraic exponent and β the logarithmic exponent.

In the particular important case when α = 0 and β = 1, the components are called of logarithmic type, and the objects are said to be in the exp-log class. Several results have been proven for these objects. Flajolet and Soria [START_REF] Flajolet | Gaussian limiting distribution for the number of components in combinatorial structures[END_REF] introduced the exp-log class of combinatorial structures and studied the behavior of the number of components for structures in this class. Chapter 5 in Gourdon's thesis [START_REF] Gourdon | algorithmique et géométrie des polynômes[END_REF] studies the size of the rth largest component for objects of the exp-log type. The problem of the distribution of the rth smallest component in this class has been studied by Panario and Richmond [START_REF] Panario | Smallest components in decomposable structures: exp-log class[END_REF]. Arratia, Barbour and Tavaré [START_REF] Arratia | Random combinatorial structures and prime factorizations[END_REF] also studied decomposition of random combinatorial structures in the exp-log class from a probabilistic standpoint. Finally, the study of objects in the exp-log class with a restricted pattern combined with information on the smallest components' sizes was done by Dong et al. [START_REF] Dong | Enumeration of combinatorial decomposable structures with restricted patterns[END_REF][START_REF] Dong | The size of the rth smallest component in decomposable structures with a restricted pattern[END_REF].

The class of generic alg-log component generating functions (that is, not for the particular exp-log case) was introduced by Flajolet and Soria [START_REF] Flajolet | General combinatorial schemas: Gaussian limiting distributions and exponential tails[END_REF] when studying the number of components in combinatorial structures. Gourdon in Chapter 6 of his thesis [START_REF] Gourdon | algorithmique et géométrie des polynômes[END_REF] (see also [START_REF] Gourdon | Largest component in random combinatorial structures[END_REF]) study the size of the rth largest components for objects of the alg-log type.

In this paper we focus on components of the alg-log type and treat the cases 0 < α < 1 with any β, and α < 0 and β = 0. We carry out the asymptotic analysis using two different approaches: the first case is treated using singularity analysis; the case α < 0, β = 0 is done using the saddle point method (Hayman's approach).

We now give the structure and main results of this paper. Generating functions are the main combinatorial technique that we consider. We use exponential generating functions for labeled objects and ordinary generating functions for unlabeled objects composed using the multi-set construction. In Section 2, we review the generating functions of labeled and unlabeled decomposable structures with a restricted pattern, as well as the definition of components of the alg-log type. We also provide in that section most of the notation needed for the rest of the paper. In Section 3, we use similar techniques to Flajolet and Odlyzko [START_REF] Flajolet | Singularity analysis of generating functions[END_REF], and Flajolet and Sedgewick's book [START_REF] Flajolet | Analytic combinatorics[END_REF], to prove our main results about number of objects with restricted pattern and algebraic exponent 0 < α < 1 in the labeled and unlabeled case, respectively (Theorem 3.1 and Theorem 3.2). We also provide the respective probabilities (Corollary 3.1 and Corollary 3.3). We give the probability that we have a restricted pattern and the rth smallest component size is bigger than a value k and for both labeled and unlabeled objects (Theorem 3.3 and Theorem 3.4). As important corollaries, we get the particular cases when there are no restricted patterns (Corollary 3.5 and Corollary 3.6). In Section 4, we use the saddle point method to obtain similar studies to the ones in the previous section but for negative algebraic exponent (Theorem 4.1, Theorem 4.2 and Theorem 4.3). In Section 5, we give examples of our results. Section 6 extends our results of Section 4 to include certain type of restricted integers partitions. Finally, in Section 7, we state some open problems for further research.

Background

We recall the following definition of restricted pattern from [START_REF] Dong | Enumeration of combinatorial decomposable structures with restricted patterns[END_REF].

Definition 2.1

The restricted pattern of an object of size n is a mapping S : J → N, where J is a set of components' sizes, N is the set of nonnegative integers, and S(j) is the number of components of size j. If we do not have a restricted pattern, J is the empty set. For convenience we also use the notation

S =   j∈J j S(j)   .
We emphasize that we want to count objects such that the components with sizes outside J may appear any number of times but there are exactly S(j) components of size j for each j ∈ J.

Throughout this paper, we use C(z) to denote the generating function for the components. In the labeled case, we have

C(z) = k≥1 C k z k k! . In the unlabeled case we have C(z) = k≥1 C k z k .
We also use C(z; J) to denote the generating function for the components whose sizes are in the given set J. So C(z; J) = j∈J C j z j j! for the labeled case and C(z; J) = j∈J C j z j for the unlabeled case.

For convenience we shall use the following notation

S =    j∈J Cj j! S(j) 1 S(j)! for labeled case, j∈J Cj +S(j)-1 S(j)
for unlabeled case.

We also let m = j∈J jS(j) denote the size of the restricted pattern, and m = n -m be the total size of the unrestricted components. The following simple lemma can be found in [START_REF] Dong | Enumeration of combinatorial decomposable structures with restricted patterns[END_REF].

Lemma 2.1 Let S : J → N be a given restricted pattern and F (z; S) be the generating function of structures with the restricted pattern S. For the labeled case, we have

F (z; S) = S z m exp (C(z) -C(z; J)) . (1)
For the unlabeled case, we have

F (z; S) = S z m exp   k≥1 C(z k ) -C(z k ; J) k   . (2)
We observe that F (z, ∅) = F (z).

In the following we give the definition of component generating function of the alg-log type.

Definition 2.2 Let ∆ ρ (ν, θ) = {z : |z| ≤ ρ(1 + ν), z = ρ, |Arg(z -ρ)| ≥ θ}
for some constants ρ > 0, ν > 0, and 0 < θ < π/2 (see figure). We say that C(z) is of alg-log type at singularity ρ with algebraic exponent α and logarithmic exponent β, if C(z) is analytic in ∆ ρ (ν, θ), and for some constants c and d,

C(z) = c + d(1 -z/ρ) α ln 1 1 -z/ρ β (1 + o(1)), (3)
as z → ρ in ∆ ρ (ν, θ). 3 Alg-log components with positive algebraic exponent

In this section we treat the case 0 < α < 1 and any β. We split the study in restricted patterns in the labeled case, restricted patterns in the unlabeled case and rth smallest component sizes.

Labeled case

Since 0 < α < 1, we have from ( 1) and ( 3)

F (z, ∅) = e c + de c (1 -z/ρ) α ln 1 1 -z/ρ β (1 + o(1)),
as z → ρ in ∆ ρ (ν, θ). It follows from (3) and Flajolet and Odlyzko's transfer theorem [START_REF] Flajolet | Singularity analysis of generating functions[END_REF] that

C n n! ∼ d Γ(-α) ρ -n n -α-1 (ln n) β , (4)
and

[z n ]F (z; ∅) ∼ de c Γ(-α) ρ -n n -α-1 (ln n) β . (5)
Theorem 3.1 Assume 0 < α < 1, ĵ = max{j : j ∈ J} = O(m/ ln m), and

j∈J j -α (ln j) β = o(m 1-α (ln m) β-1 ).
Then, as m → ∞,

[z n ]F (z; S) ∼ de c S Γ(-α) ρ -m m -α-1 (ln m) β exp (-C(ρ; J)) ,
where the asymptotics is uniform in all S.

Proof:

We shall use the Cauchy integration formula. We choose a contour similar to the one in [START_REF] Flajolet | Singularity analysis of generating functions[END_REF]. Let γ = γ 1 ∪ γ 2 ∪ γ 3 ∪ γ 4 be positively oriented, where

γ 1 = {z : |z -1| = 1/m, θ < Arg(z -1) < 2π -θ}, γ 2 = {z : 1/m ≤ |z -1| ≤ E ln m/m, Arg(z -1) = θ}, γ 3 = {z : |z| = 1 + 3 ln m/m, θ < Arg(z -1) < 2π -θ}, γ 4 = {z : 1/m ≤ |z -1| ≤ E ln m/m, Arg(z -1) = 2π -θ},
where the real number E satisfies

1 + E ln m m e iθ = 1 + 3 ln m/m.
Then we have

[z n ]F (z; S) = ρ -n [z n ]F (ρz; S) = ρ -m S 1 2πi γ f (z)dz, (6)
where f (z) = z -(m+1) exp(C(ρz) -C(ρz; J)).

Since |z| ≤ 1 + 3 ln m/m and ĵ = O(m/ ln m), we have

|z j | ≤ 1 + 3 ln m m j = 1 + O(j ln m/m) = O(1).
We have from ( 4)

j∈J C j ρ j j! = O(1). (7)
Hence, when |z| ≤ 1 + 3 ln m/m, j∈J

C j (ρz) j j! = O(1). (8)
Applying (3) and Taylor expansion, on the contour γ, we obtain

f (z) = z -(m+1) exp   c + d(1 -z) α ln 1 1 -z β (1 + o(1)) - j∈J C j (ρz) j j!   = exp   c - j∈J C j ρ j j!   z -(m+1) × exp   d(1 -z) α ln 1 1 -z β (1 + o(1)) + j∈J C j ρ j j! (1 -z j )   = exp   c - j∈J C j ρ j j!   z -(m+1) 1 + g(z, J) + O(g 2 (z, J)) , (9)
where

g(z, J) = d(1 -z) α ln 1 1 -z β (1 + o(1)) + j∈J C j ρ j j! (1 -z j ).
In the last line, we can expand the exponential function because of ( 7), ( 8) and 0 < α < 1. Substituting (9) for f (z) in ( 6), we obtain

[z n ]F (z; S) = ρ -m S exp   c - j∈J C j ρ j j!   1 2πi γ z -(m+1) 1 + g(z, J) + O(g 2 (z, J)) dz = ρ -m S exp   c - j∈J C j ρ j j!   × 1 2πi γ z -(m+1) dz + γ z -(m+1) g(z, J)dz + γ z -(m+1) O(g 2 (z, J))dz = ρ -m S exp c -j∈J C j ρ j j! 2πi γ z -(m+1) g(z, J)dz + γ z -(m+1) O(g 2 (z, J))dz ,
where the term γ z -(m+1) dz in the second line is 0.

In the following, we first discuss the integral γ z -(m+1) g(z, J)dz. Then, we show that the

second integral γ z -(m+1) O(g 2 (z, J))dz is negligible compared with γ z -(m+1) g(z, J)dz. Case I.a: Estimation of γ z -(m+1) g(z, J)dz on γ 1 ∪ γ 2 ∪ γ 4 : Let z = 1 + w m .
From the definition of γ 1 , γ 2 , and γ 4 , we notice that w = O(ln m). Since

z j = 1 + w m j = 1 + O(jw/m),
applying (4) and j∈J

(ln j) β j α = o m 1-α (ln m) β-1 , we get j∈J C j ρ j j! (1 -z j ) = j∈J C j ρ j j! O jw m = O w m j∈J jC j ρ j j! = O   w m j∈J (ln j) β j α   = o (ln m) β m α .
Hence,

g(z, J) = d - w m α ln - m w β (1 + o(1)) + j∈J C j ρ j j! (1 -z j ) = d(ln m) β m α (-w) α (1 + o(1)), (10)
where the o( 1) is uniform as m → ∞ for w on the contour

γ 1 ∪ γ 2 ∪ γ 4 . Let γ = γ 1 + γ 2 + γ 4
where

γ 1 = {w : |w| = 1, θ < Arg(w) < 2π -θ}, γ 2 = {w : 1 ≤ |w| ≤ E ln m, Arg(w) = θ}, γ 4 = {w : 1 ≤ |w| ≤ E ln m, Arg(w) = 2π -θ}. Then 1 2πi γ1∪γ2∪γ4 z -(m+1) g(z, J)dz = 1 2πim γ d(ln m) β m α (-w) α (1 + o(1)) 1 + w m -(m+1) dw = 1 2πim γ d(ln m) β m α (-w) α e -w (1 + o(1))dw = d(ln m) β 2πim 1+α γ (-w) α e -w dw + o (ln m) β m 1+α γ (-w) α e -w dw .
Applying the Gamma function we obtain We also have

1 2πi γ1∪γ2∪γ4 z -(m+1) g(z, J)dz ∼ (ln m) β m 1+α d Γ(-α) . (11)
|z -(m+1) | = |(1 + 3 ln m/m) -(m+1) | = O(1/m 3 ). (12)
Therefore,

1 2πi γ3 z -(m+1) g(z, J)dz = O(m -3 ). ( 13
)
Since we have 0 < α < 1, the integral on γ 3 is negligible compared with the integral on γ 1 ∪γ 2 ∪γ 4 .

Case II.a:

Estimation of γ z -(m+1) O(g 2 (z, J))dz on γ 1 ∪ γ 2 ∪ γ 4 : Let z = 1 + w m . From (10), g 2 (z, J) = d 2 (ln m) 2β m 2α (-w) 2α (1 + o(1)).
Using arguments similar to those used to derive [START_REF] Henrici | Applied and computational complex analysis[END_REF], we have

γ1∪γ2∪γ4 z -(m+1) g 2 (z, J)dz = O (ln m) 2β m 1+2α .
Case II.b: Estimation of γ z -(m+1) O(g 2 (z, J))dz on γ 3 :

In this case we get

γ3 z -(m+1) g 2 (z, J)dz = O(m -3 ),
which is negligible compared with the integral on

γ 1 ∪ γ 2 ∪ γ 4 . Since 0 < α < 1, it is clear that the integral ρ -m S exp c -j∈J C j ρ j j! 2πi γ z -(m+1) g(z, J)dz is the dominant part in [z n ]F (z; S).
Throughout this paper, a random structure is always chosen uniformly at random from a given family of structures. Hence

P (S, n) = [z n ]F (z; S) [z n ]F (z; ∅)
is the probability that a random decomposable combinatorial structure of size n has a restricted pattern S. Using the previous theorem and ( 5) we immediately obtain the following corollary. We have, as m → ∞,

P (S, n) ∼ n m 1+α ln m ln n β j∈J 1 S(j)! C j ρ j /j! S(j) e -Cj ρ j /j! .
For a restricted pattern of small size, we have the following independence result.

Corollary 3.2 Suppose, in addition to the conditions in Corollary 3.1, the restricted pattern

S =   j∈J j S(j)   also satisfies j∈J jS(j) = o(n), that is, m ∼ n. We have, as n → ∞, P (S, n) ∼ j∈J P j S(j) , n ∼ j∈J 1 S(j)!
C j ρ j /j! S(j) e -Cj ρ j /j! .

Unlabeled case

In the unlabeled case, the generating function of decomposable combinatorial structures is

F (z) = F (z, ∅) = exp C(z) + C(z 2 ) 2 + C(z 3 ) 3 + • • • .
As usual, for the unlabeled case, we assume 0 < ρ < 1. Therefore, C(z 2 )

2

+ C(z 3 ) 3 + • • • has a radius of convergence bigger than ρ. As z → ρ, we have F (z, ∅) = exp (C(z) + r 0 ) (1 + o(1)). ( 14
)
where

r 0 = k≥2 C(ρ k ) k .
It is easy to see that F (z, ∅) is also of alg-log type. Flajolet and Odlyzko's transfer theorem [START_REF] Flajolet | Singularity analysis of generating functions[END_REF] entails

C n ∼ d Γ(-α) ρ -n n -1-α (ln n) β , (15)
and

[z n ]F (z; ∅) ∼ de c+r0 Γ(-α) ρ -n n -1-α (ln n) β . ( 16
)
Theorem 3.2 Suppose ĵ = max{j : j ∈ J} = O(m/ ln m) and j∈J j -α (ln j) β = o(m 1-α (ln m) β-1 ).
Then, as m → ∞,

[z n ]F (z; S) ∼ de c+r0 S Γ(-α) m -α-1 (ln m) β ρ -m j∈J 1 -ρ j Cj .
Proof: The proof is similar to the labeled case so we only sketch the differences. We use the same contour as in Theorem 3.1 but now

f (z) = 1 z m+1 exp   k≥1 C((ρz) k ) k - k≥1 C((ρz) k ; J) k   .
Using ( 14) and ( 9), for z ∈ γ, we get

exp C(ρz) + C((ρz) 2 ) 2 + C((ρz) 3 ) 3 + • • • = e c+r0 exp (C(ρz)) (1 + o(1)) = e c+r0 exp d(1 -z) α ln 1 1 -z β (1 + o(1)) (1 + o(1)). ( 17
)
The remaining of the proof follows in the same way as in Theorem 3.1 by noting exp

  k≥1 ρ jk /k   = 1 -ρ j -1 .
Using the previous theorem and ( 16) we immediately obtain the following corollary. We have, as m → ∞,

P (S, n) ∼ n m 1+α ln m ln n β j∈J C j + S(j) -1 S(j) ρ jS(j) 1 -ρ j Cj .
As in the labeled case, we have the following independence result for small patterns.

The rth smallest component size

Let X

[r]

n denote the size of the rth smallest component in a random structure of size n, and let X The focus of this section is to derive asymptotic expressions for P (X

n (S) > k) = 0 when d(k) ≥ r.
The following simple lemma will be required later.

Lemma 3.1 Let a and b be real constants such that 0 < a < 1.

Then k j=1 (ln j) b j a ∼ 1 1 -a k 1-a (ln k) b , as k → ∞. Proof: Let k = e b a + 1. It is easy to check that (ln x) b x a is a decreasing function for x ≥ k . Hence k k (ln x) b x a dx + (ln k) b k a ≤ k j=k (ln j) b j a ≤ k k (ln x) b x a dx + (ln k ) b k a . ( 18
)
Setting x = e t , we have

k k (ln x) b x a dx = ln k ln k t b e (1-a)t dt = 1 1 -a e (1-a)t t b ln k ln k - b 1 -a ln k ln k t b-1 e (1-a)t dt = 1 1 -a k 1-a (ln k) b + O(k 1-a (ln k) b-1 ), as k → ∞.
Now Lemma 3.1 immediately follows from (18). ). As m → ∞, we have

Labeled case

P (X [r] n (S) > k) ∼ P (S, n) exp(-C(ρ; N k \ J)) r-1-d(k) j=0 C j (ρ; N k \ J) j! ,
where P (S, n) is given in Corollary 3.1.

Proof: Define the augmented pattern S : J → N where J = J ∪ N k , and S (j) = S(j) as j ∈ J, and, for j ∈ N k \ J, S (j) is specified below. We note that each structure with restricted pattern S and the rth smallest component with size greater than k corresponds to structures with an augmented pattern S such that

j∈N k \J S (j) ≤ r -1 -d(k). (19)
Hence we have

P (X [r] n (S) > k) = P (S , n), (20)
where the sum is over all the augmented patterns S satisfying (19). Let m = n -j∈J∪N k jS (j). Since k = o(m/ ln m) and

j∈N k (ln j) β j α = o m 1-α (ln m) β-1 .
Therefore, each augmented pattern S satisfies the requirements of Corollary 3.1. It follows from (20) that

P (X [r] n (S) > k) ∼ n m 1+α ln m ln n β ρ n-m exp (-C(ρ; J ∪ N k )) j∈J∪N k C S (j) j (j!) S (j) S (j)! ∼ n m 1+α ln m ln n β S ρ n-m exp (-C(ρ; J) -C(ρ; N k \ J))   j∈N k \J C S (j) j ρ jS (j) (j!) S (j) S (j)!   ∼ P (S, n) exp (-C(ρ; N k \ J))   j∈N k \J C S (j) j ρ jS (j) (j!) S (j) S (j)!   , (21)
where all the sums are over S satisfying (19). It follows from the multinomial formula

(Y 1 + Y 2 + • • • + Y k ) j = a1+a2+•••+a k =j j a 1 , a 2 , . . . , a k Y a1 1 Y a2 2 . . . Y a k k = j! a1+a2+•••+a k =j k i=1 Y ai i a i ! that P (X [r] n (S) > k) ∼ P (S, n) exp(-C(ρ; N k \ J)) r-1-d(k) j=0 C j (ρ; N k \ J) j! .
The following corollary treats the special case when there is no restricted pattern. The corresponding problem for the exp-log class was treated in [START_REF] Panario | Smallest components in decomposable structures: exp-log class[END_REF].

Corollary 3.5 Let r = O(ln n) and k = o n(ln n) 1 α-1 . As n → ∞, we have P (X [r] n > k) ∼ exp(-C(ρ; N k )) r-1 j=0 C j (ρ; N k ) j! .

Unlabeled case

In the unlabeled case, we require the singularity point 0 < ρ < 1 which is not a required condition in the labeled case. . As m → ∞, we have

P (X [r] n (S) > k) ∼ P (S, n) exp   - ≥1 C(ρ ; N k \ J)   r-1-d(k) j=0 [z j ] exp zC(ρ; N k \ J) + z 2 C(ρ 2 ; N k \ J) 2 + • • • ,
where P (S, n) is given in Corollary 3.3.

Proof: Let S and m be as defined as in the proof of Theorem 3.3. For the same reason as in the labeled case, we have

P (X [r] n (S) > k) = P (S , n),
where
P (X [r] n (S) > k) ∼ n m 1+α ln m ln n β j∈J∪N k C j + S (j) -1 S (j) (1 -ρ j ) Cj ρ n-m ∼ P (S, n) j∈N k \J (1 -ρ j ) Cj j∈N k \J C j + S (j) -1 S (j) ρ jS (j) ,
where, as before, the sum is over all S satisfying (19). Using

(1 -ρ i z) -Ci = ≥0 C i + -1 ρ i z ,
we get

j∈N k \J C j + S (j) -1 S (j) ρ jS (j) = r-1-d(k) u=0 [z u ] j∈N k \J (1 -ρ j z) -Cj = r-1-d(k) u=0 [z u ] exp   - j∈N k \J C j ln(1 -ρ j z)   = r-1-d(k) u=0 [z u ] exp   i≥1 j∈N k \J C j ρ ij z i /i   = r-1-d(k) u=0 [z u ] exp z(C(ρ; N k ) -C(ρ; J ∩ N k )) + z 2 C(ρ 2 ; N k ) -C(ρ 2 ; J ∩ N k ) 2 + • • • .
To complete the proof we only need to notice that

j∈N k \J (1 -ρ j ) Cj = exp   - ≥1 C(ρ ; N k \ J)   .
The case when there is no restricted pattern gives the following simple result.

Corollary 3.6 Let r = O(ln n) and k = o n(ln n) 1 α-1 . As n → ∞, we have P (X [r] n > k) ∼ exp   - k≥1 C(ρ k ; N k ) k   r-1 j=0 [z j ] exp zC(ρ; N k ) + z 2 C(ρ 2 ; N k ) 2 + • • • .

Expectation of the rth smallest component size

In this section, we discuss the expectation of the rth smallest component with a given restricted pattern. We use d to denote the total number of components in the given restricted pattern, namely d = j∈J S(j). If r ≤ d, it is clear that P (X

[r]

n (S) > k) = 0 when j∈J∩N k S(j) ≥ r. Hence we have E(X [r] n (S)) =

i [r] -1 k=0 P (X [r] n (S) > k),
where i [r] is the size of the rth component in the pattern S.

E(X [1] n ) ∼ ne -c .
In the unlabeled case, we have E(X [1] n ) ∼ ne -c-r0 .

Algebraic components with negative algebraic exponent

In this section, we assume that the component generating function has the following special form

C(z) = d(1 -z/ρ) -p + c + o(1) as z → ρ in the open disk |z| < ρ,
where c, d, and p are constants with p, d > 0, and C(z) is analytic in the open disc |z| < ρ. We use -p, p > 0, instead of α to avoid confusion. Let h(z) = d(1 -z) -p . The asymptotic behavior of [z n ] exp(h(z)) has been studied by Wright [START_REF] Wright | The coefficients of a certain power series[END_REF] and Hayman [START_REF] Hayman | A generalization of Stirling's formula[END_REF]. Hayman showed that exp(h(z)) is admissible in |z| < 1. Although their results cannot be applied directly to our generating functions involving a restricted pattern, the same saddle point method does apply as well. We note that the contour used here is substantially different from that used in the previous section where the exponent is positive. The contour here is a circle inside the unit disk.

Let ĵ = max{j : j ∈ J}. Throughout this section we assume

ĵ = o m 1 p+1 , j∈J j p-1 = o m p 6(p+1)
, and

j∈J j p = o m 1 p+1 . (22)
We note that, when p ≥ 1, the third condition implies the first condition.

Labeled case

We consider labeled structures in this section. Let R = R(m) be defined by

Rh (R) = m, 0 < R < 1. (23)
Theorem 4.1 Suppose the pattern S satisfies Condition (22) and let R be defined in (23). Then as m → ∞, Rρ) .

[z n ]F (z; S) ∼ 1 2πp(p + 1)d   j∈J 1 S(j)! C j j! S(j) e -Cj ρ j /j!   (Rρ) -m m pd -p+2 2(p+1) e C(
Proof: We first note that by (1)

[z n ]F (z; S) = j∈J 1 S(j)! C j j! S(j) ρ -m [z m ] exp(h(z) -C(ρz; J) + c + o(1)). (24)
Using the Cauchy integral formula, we obtain

[z m ] exp(h(z) -C(ρz; J) + c + o(1)) = 1 2π R -m π -π exp h(Re iθ ) -C(Rρe iθ ; J) -imθ + c + o(1) dθ. (25)
It follows from ( 23) and Lagrange inversion that

1 -R = k≥1 1 k 1 p+1 k -1 (-1) k-1 pd m k p+1 = pd m 1 p+1 + O 1 m 2 p+1 . ( 26
)
As in [START_REF] Hayman | A generalization of Stirling's formula[END_REF], we define

b(R) = Rh (R) + R 2 h (R) ∼ p(p + 1)d m dp p+2 p+1
.

Let δ = m -1 p+1 -5p 12(p+1) .
For δ ≤ |θ| ≤ π, we have

1 -Re iθ = 1 + R 2 -2R cos θ 1/2 ≥ 1 + R 2 -2R cos δ 1/2 = 1 -Re iδ .
Hence, we have 1

-Re iθ -p ≤ 1 -Re iδ -p = 1 -2R cos δ + R 2 -p/2 .
Using the Taylor expansion for cos δ we obtain

1 -Re iθ -p ≤ (1 -R) -p - p 2 R(1 -R) -p-2 δ 2 + O(δ 4 ).
We observe that

(1 -R) -p-2 δ 2 ∼ pd m -p+2 p+1 m -2 p+1 -5p 6(p+1) = Am p 6(p+1) ,
for some positive constant A. Therefore, we have

exp(h(Re iθ )) ≤ exp h(R) -Am p 6(p+1) , (27)
as m → ∞, uniformly for δ ≤ |θ| ≤ π.

For |θ| ≤ δ, we have

h(Re iθ ) = d(1 -R) -p + ipdR(1 -R) -p-1 θ - b(R) 2 θ 2 + O (1 -R) -p-3 θ 3 = d(1 -R) -p + ipdR(1 -R) -p-1 θ - b 2 (R) 2 θ 2 + o(1)
.

We now break the integral (25) into the following two parts: Using ( 4) with α = -p, by ( 22) and ( 23), and for |θ| ≤ δ, we have

I 1 = δ -δ exp h(Re iθ ) -C(Rρe iθ ; J) -imθ + c + o(1)
C(Rρe iθ ; J) = j∈J C j j! (Rρ) j e ijθ = j∈J C j j! ρ j 1 - pd m 1 p+1 + O m -2 p+1 j (1 + O(jδ)) = C(ρ; J) + j∈J jC j ρ j j! O m -1 p+1 = C(ρ; J) + O m -1 p+1 j∈J j p = C(ρ; J) + o(1).
Hence, under Condition (22), we have

I 1 = δ -δ exp d(1 -R) -p - b(R) 2 θ 2 -C(ρ; J) + c + o(1) dθ ∼ 2π b(R) exp(C(Rρ) -C(ρ; J)).
We now show that I 2 is negligible compared with I 1 . From (27), we have

|I 2 | = O exp(C(Rρ) -Am p 6(p+1) + C(ρ; J)) = o exp(C(Rρ) -C(ρ; J)) b(R) ,
where we used the fact

C(ρ; J) = O   j≤ ĵ j p-1   = O(( ĵ) p ) = o m p 6(p+1)
. Now Theorem 4.1 follows from (24) and (25).

When

n -m = o n 1 p+1 , it follows from (26) that (R(m)) m ∼ (R(n)) n since (R(m)) m = exp m - pd m 1 p+1 + O m -2 p+1 = exp n + o n 1 p+1 -(pd) 1 p+1 n -1 p+1 1 + o n -p p+1 -1 p+1 +O n + o(n 1 p+1 ) -2 p+1 ∼ (R(n)) n .
Hence we also have exp(C(R(m)ρ)) ∼ exp(C(R(n)ρ)), and the following corollary holds. Then, as n → ∞,

P (S, n) ∼ j∈J P j S(j) , n ∼ j∈J 1 S(j)!
C j ρ j /j! S(j) exp -C j ρ j /j! .

Unlabeled case

As before we assume ρ < 1 for the unlabeled case. Using essentially the same argument as for the labeled case, we obtain the following theorem and corollary. Then, as n → ∞,

P (S, n) ∼ j∈J P j S(j) , n ∼ j∈J C j + S(j) -1 S(j) ρ jS(j) 1 -ρ j Cj .

Examples

We now give some examples.

Example 5.1 (Cayley Trees) A Cayley tree is a non-planar rooted labeled tree. Let C(z) be the exponential generating function of Cayley trees. It is well known [START_REF] Flajolet | Analytic combinatorics[END_REF] that

C(z) = z exp(C(z)), C n = n n-1 , C(z) = 1 -2(1 -ez) + O(1 -ez).
Thus C(z) is of alg-log type with ρ = 1/e, α = 1/2, β = 0, d = -√ 2 and c = 1. First, let us consider a restricted pattern S = 2 s t 3 , where s = √ n , t = ln n .

By Corollary 3.2, we have

P (S, n) ∼ 1 3! C t e -t /t! 3 exp -C t e -t /t! 1 s! C 2 e -2 /2! s exp -C 2 e -2 /2! .
Noting that

C 2 /2! = 1 and C t e -t /t! ∼ 1 √ 2π t -3/2 as t → ∞,
we obtain that the probability of a Cayley forest having s = √ n trees of size 2 and 3 trees of size t = ln n is given by

P (S, n) ∼ 1 6 (2π) -3/2 (ln n) -9/2 1 s! e -2s exp -e -2 .
If in addition to the restricted pattern S we want information related to the 5th (r = 5) smallest component size, we get by Theorems 3.3 P (X [5] n (S) > k) ∼ P (S, n) exp(-C(ρ; N k \ J))

4-d(k) j=0 (C(ρ; N k \ J)) j j! , for k = o n(ln n) -2 .
We note here d(k) = 0 when k < 2 and d(k) ≥ s when k ≥ 2. Thus P (X [START_REF] Flajolet | Analytic combinatorics[END_REF] n (S) > k) = 0 when k ≥ 2, and P X [5] n (S) > 1 ∼ P (S, n) exp(-1/e) 4 j=0 e -j j! .

Finally, by Corollary 3.7, the expected size of the smallest subtree is

E(X [1] n ) ∼ n e .
Example 5.2 (Fragmented permutations) Fragmented permutations are defined in Section II.4.2 of [START_REF] Flajolet | Analytic combinatorics[END_REF] as the combinatorial class F = SET(SEQ ≥1 (Z )). They correspond to unordered collections of permutations. The generating function of fragmented permutations is given by F (z) = exp z 1-z . The coefficients in this exponential generating function form the sequence A000262 in Sloane's Encyclopedia of Integer Sequences that counts sets of lists.

The component generating function for fragmented permutations is then

C(z) = z 1 -z = 1 1 -z -1,
and so it is of alg-log type with α = -1, ρ = 1, d = 1 and c = -1. It follows from Theorem 4.1 (also see Example VIII.7 of [START_REF] Flajolet | Analytic combinatorics[END_REF]) that

[z n ]F (z) = F n n! ∼ e -1/2 e 2 √ n 2 √ πn 3/4 ,
and that the saddle point is

R = 1 - 1 √ n + 1 2n + O(n -3/2 ).
Let us consider fragmented permutations with the restricted pattern S = 2 s t 3 , where s = n 1/4 , t = ln n .

Then Corollary 4.1 gives that the probability a random fragmented permutation has this restricted pattern S is

P (S, n) ∼ 1 3! (C t /t!) 3 exp (-C t /t!) 1 s! (C 2 /2!) s exp (-C 2 /2!) .
Noting C j = j!, we obtain

P (S, n) ∼ 1 6 1 s! e -2 .
We also have, using Corollary 4.3, E(X [1] n ) ∼ k≥0 e -k = e e -1 .

Extensions to integer partitions

Although our theorems do not cover unlabeled structures with ρ = 1, similar arguments lead to the same type of results for some unlabeled structures with ρ = 1. We illustrate this with integer partitions.

Let A = {a 1 , a 2 , . . .} be a set of positive integers. We suppose that if any finite subset of A is deleted then the remaining sequence has gcd equal to one. We let p A (n) be the number of solutions of n = l 1 a 1 + l 2 a 2 + • • • + l m a m , l i ≥ 0.

Call each such representation a partition of n. There are l 1 + l 2 + • • • + l m components of this partition. We require that the following limit exists lim j→∞ ln a j ln j .

The asymptotic behaviour of p A (n) has been studied by Richmond [START_REF] Richmond | Asymptotic relations for partitions[END_REF] under the above assumptions. Define r = r(n) to be the unique solution (the saddle point condition) to n = where |J| denotes the number of elements in the set J.

As in previous sections, let m = n -j∈J jS j . Let A = {1, 2, ...} \ J. Then p A (m) is the number of partitions of n with the pattern S.

We require now the following formulas about inverse Mellin transform (see, for example, Appendix B of [START_REF] Flajolet | Analytic combinatorics[END_REF]. We also note that the last two formulas can be obtained from the first one by integration and differentiation, respectively, with respect to r. )

Fig. 1 :

 1 Fig. 1: ∆1(ν, θ)

  Case I.b: Estimation of γ z -(m+1) g(z, J)dz on γ 3 : Let z = (1 + 3 ln m/m)e it where θ < t < 2π -θ. Using (8) and the definition of alg-log type, we obtain |g(z, J)| = O(1).

Corollary 3 . 1

 31 Consider labeled decomposable combinatorial structures whose component generating function is of alg-log type with an algebraic exponent 0 < α < 1. Suppose ĵ = max{j; j ∈ J} = O(m/ ln m), and j∈J (ln j) β j α = o m 1-α (ln m) β-1 .

Corollary 3 . 3

 33 Consider unlabeled decomposable combinatorial structures whose component generating function is of the alg-log type with an algebraic exponent 0 < α < 1. For ĵ = max{j; j ∈ J}, suppose ĵ = O(m/ ln m) and j∈J (ln j) β j α = o m 1-α (ln m) β-1 .

Corollary 3 . 4

 34 Suppose, in addition to the conditions in Corollary 3.3, the restricted pattern j∈J jS(j) = o(n), that is, m ∼ n. We have, as n → ∞, P (S, n) ∼ j∈J P j S(j) , n ∼ j∈J C j + S(j) -1 S(j) ρ jS(j) 1 -ρ j Cj .

  [r]n (S) denote the size of the rth smallest component in a random structure of size n having a restricted pattern S.

  ) > k) and P (X [r] n > k). For convenience, we define the set N k = {1, 2, . . . , k} where k is a positive integer and d(k) = j∈J∩N k S(j). We only need to consider d(k) < r since P (X [r]

Theorem 3 . 3 1 . 1 α- 1

 33111 Let S : J → N be a restricted pattern with ĵ = O(m/ ln m) and j∈J j -α (ln j) β = o m 1-α (ln m) β-Assume r -d(k) = O(ln m) and k = o(m(ln m)

  j∈N k \J S (j) ≤ r -1 -d(k) = O(ln m),we have m ∼ m. Hence,

Theorem 3 . 4 1 .

 341 Let S : J → N be a restricted pattern with ĵ = O(m/ ln m) and j∈J (ln j) β j α = o m 1-α (ln m) β-Assume r -d(k) = O(ln m) and k = o m(ln m)

Theorem 3 . 5 1 .Corollary 3 . 7

 35137 Let S : J → N be a restricted pattern satisfying ĵ = o m(ln m) j) β j α = o m 1-α (ln m) β-When r = d + 1, we have in the labeled case E(X[r] n (S)) ∼ P (S, n)m exp(-c + C(ρ; J)); We have in the labeled case

dθ, and I 2 =

 2 |θ|≥δ exp h(Re iθ ) -C(Rρe iθ ; J) -imθ + c + o(1) dθ.

Corollary 4 . 1

 41 Suppose, in addition to the condition (22), the restricted pattern ) = o n 1/(p+1) .

Theorem 4 . 2 1 2πp

 421 Suppose the pattern S satisfies Condition (22) and let R be defined in (23). Then as m → ∞, [z n ]F (z; S) ∼ Rρ)+r0 , where r 0 = k≥2 C(ρ k )/k. Corollary 4.2 Suppose, in addition to Condition (22), the restricted pattern ) = o n 1/(p+1) .

  (e raj -1) 2 .The following result is contained in Theorem 1.1 of[START_REF] Richmond | Asymptotic relations for partitions[END_REF] p A (n) = (2πA 2 )

1 =( 1 + 2 .

 112 r -t Γ(t)ζ(t -1)ζ(t -2)dtIt follows from the residue theorem (or use correspondence (47) in Appendix B of[START_REF] Flajolet | Analytic combinatorics[END_REF]) thatj≥1 j e rj -1 = r -2 ζ(2) + ζ(0)r -1 + O(r -ε ), -j≥1 ln 1 -e -rj = r -1 ζ(2) + ζ(0) ln(1/r) + ζ (0) + o(1), j≥1 j 2 e rj (e rj -1) 2 = 2ζ(2)r -3 + O r -2 . r -2 ζ(2) + ζ(0)r -1 + O(r -ε ) -O(rj)),and (30), we obtainn = ζ(2)r -2 + r -1 o n -1/4 .Finally, substituting the above expressions into Equation (29) and notingm = n + o(n 1/2 ), ζ(2) = π 2 /6, ζ(0) = -1/2,and ζ (0) = -ln √ 2π, we obtain p A (m) ∼ p(n) number of partitions of n. Hence the probability that a random partition of n has the restricted pattern S is p A

and in the unlabeled case we get, for r 0 = k≥2 C(ρ k )/k, E(X [r] n (S)) ∼ P (S, n)m exp(-c -r 0 ) j∈J (1 -ρ j ) -Cj .

Proof: To estimate the first moment, we use the well-known expression E(X [r] n (S)) = k≥0 P (X [r] n (S) > k).

We only prove our theorem in the labeled case since the proof is very similar in the unlabeled case.

Let us begin with a special case: there is only one component in addition to the components of the pattern. Namely, we have d + 1 components in total. Thus, the size of the only component not in the pattern is m. The probability that an object has exactly d + 1 components is

Let us now consider small k. Setting t = max ĵ + 1, m(ln m)

Clearly, for any k < m, we always have

Thus, uniformly for t ≤ k ≤ m, we have

Hence, noting that t = o m(ln m)

In the empty pattern case, let X

[r] n be the size of the rth smallest component of a random decomposable combinatorial structure of size n. The expectation of X [START_REF] Arratia | Random combinatorial structures and prime factorizations[END_REF] n immediately follows from Theorem 3.5.

Smallest component size

Let X

[r]

n denote the size of the rth smallest component in a random structure of size n. The following theorem is analogous to Theorem 3.3 and Theorem 3.4. Its proof is identical to the proofs of Theorem 3.3 and Theorem 3.4, and is omitted. Theorem 4.3 Let r be a constant, k < n for some small positive constant < 1/(p + 1) such that J = N k satisfies Condition (22). Let R = R(n) be defined by

Then, for labeled case

and for unlabeled case

where the asymptotics is uniform for all k satisfying the given condition, as n → ∞.

The above expressions for P (X

[r]

n > k) are the same as the ones in Corollaries 3.5 and 3.6. We note that

)) for k → ∞ and k < n . With a similar argument in the unlabeled case, this immediately implies the following.

Corollary 4.3 Let r be any fixed positive integer. For labeled structures we have

In particular, E(X [1] n ) ∼ k≥0 exp(-C(ρ; N k )).

For unlabeled structures we have

In particular,

The product on j in the above formula shows the contribution of each part in the restricted pattern is asymptotically independent of each other. This is in agreement with Corollary 4.2 by noting here ρ = 1 and C j = 1 for all j.

Although we consider here in detail only the case a j = j, our results extend, for any positive integer k, to a j = j k , to a j = F k j where F j is the jth Fibonacci number (where one needs an alternate condition stated in [START_REF] Richmond | Asymptotic relations for partitions[END_REF]), and to a j = p k j , where p j denotes the jth prime number (these assumptions are satisfied since p j ∼ j ln j by the prime number theorem). Of course, conditions stated in (30) need to be adjusted accordingly.

Conclusions

In this paper, we focus on the multi-set construction of decomposable structures with a given restricted pattern where the component generating function are of special alg-log type. We estimate P (X

[r]

n > k) for labeled and unlabeled structures. We remark that for all ranges of α and β consider in this paper, P (X

[r]

n > k) has the same expression among labeled structures; the same result is true among unlabeled structures.

Let Y n be the number of components in a random structure of size n. When the component generating function C(z) is of logarithmic type, it is well known [START_REF] Flajolet | Gaussian limiting distribution for the number of components in combinatorial structures[END_REF][START_REF] Flajolet | General combinatorial schemas: Gaussian limiting distributions and exponential tails[END_REF] that Y n is asymptotically normal with mean and variance proportional to ln n. Also E(X [START_REF] Panario | Smallest components in decomposable structures: exp-log class[END_REF]. We note that, for the labeled case,

When C(z) is of alg-log type with algebraic exponent 0 < α < 1, we have, from (3) and Flajolet-Odlyzko's transfer theorem, that

which is a shifted Poisson distribution with constant mean and variance. Similar results hold for unlabeled structures. We have also shown in this case E(X [START_REF] Arratia | Random combinatorial structures and prime factorizations[END_REF] n ) is proportional to n. When C(z) is of alg-log type with algebraic exponent α = -p < 0, it follows from [START_REF] Wright | The coefficients of a certain power series[END_REF][START_REF] Wright | On the coefficients of power series having exponential singularities[END_REF] that E(Y n ) is proportional to n p/(p+1) . We have also shown in this paper that for this algebraic exponent E(X

[r]

n ) is a constant. For integer partitions, it is also known that the expected number of parts in a random partition of n is proportional to n 1/2 [START_REF] Richmond | The moments of partitions, II[END_REF]. Although integer partitions do not fit into our general framework for unlabeled structures because the radius of convergence is not less than 1, we have shown, using the result of [START_REF] Richmond | Asymptotic relations for partitions[END_REF], that similar results also hold for integer partitions with a restricted pattern.

Further work. So far we have covered the cases 0 < α < 1 and any β; α = 0 and β = 1; and α < 0 and β = 0. It seems possible to extend these results to other ranges of α and β. In addition, it may be possible to relax the conditions on the restricted pattern S.


Kh Hessami Pilehrood

T Hessami Pilehrood

Series acceleration formulas for beta values

Keywords: Dirichlet's beta function, Catalan's constant, Apéry-like series, generating function, convergence acceleration, Markov-Wilf-Zeilberger method, Markov-WZ pair

We prove generating function identities producing fast convergent series for the sequences β(2n + 1), β(2n + 2) and β(2n+3), where β is Dirichlet's beta function. In particular, we obtain a new accelerated series for Catalan's constant convergent at a geometric rate with ratio 2 -10 , which can be considered as an analog of Amdeberhan-Zeilberger's series for ζ(3).

Introduction

In this paper we continue our study on finding generalized identities [START_REF] Kh | Generating function identities for ζ(2n+2), ζ(2n+3) via the WZ-method[END_REF][START_REF] Kh | Simultaneous generation for zeta values by the Markov-WZ method[END_REF] that produce fast convergent series for some classical constants. In 1978, R. Apéry used the fast convergent series

ζ(3) = 5 2 ∞ k=1 (-1) k-1 k 3 2k k (1)
first obtained by A. A. Markov [START_REF] Markoff | Mémoiré sur la transformation de séries peu convergentes en séries tres convergentes[END_REF] to derive the irrationality of ζ(3) [START_REF] Van Der Poorten | Apéry's proof of the irrationality of ζ(3). An informal report[END_REF]. This series converges at a geometric rate with ratio 1/4. A general formula giving analogous series for all ζ(2n + 3), n ≥ 0, was proved by Koecher [START_REF] Koecher | [END_REF] (and independently in an expanded form by Leshchiner [START_REF] Leshchiner | Some new identities for ζ(k)[END_REF]). For |a| < 1, it has the form

∞ n=0 ζ(2n + 3)a 2n = ∞ k=1 1 k(k 2 -a 2 ) = 1 2 ∞ k=1 (-1) k-1 k 3 2k k 5k 2 -a 2 k 2 -a 2 k-1 m=1 1 - a 2 m 2 . ( 2
)
Expanding the right-hand side of (2) by powers of a 2 and comparing coefficients of a 2n on both sides leads to the Apéry-like series for ζ(2n + 3). In particular, comparing constant terms (n = 0) recovers 1365-8050 c 2010 Discrete Mathematics and Theoretical Computer Science (DMTCS), Nancy, France Markov's formula [START_REF] Almkvist | Borwein and Bradley's Apéry-like formulae for ζ(4n + 3)[END_REF] and comparing coefficients of a 2 and a 4 gives the following two formulas:

ζ(5) = 2 ∞ k=1 (-1) k+1 k 5 2k k - 5 2 ∞ k=1 (-1) k+1 k 3 2k k k-1 j=1 1 j 2 , ζ(7) = 2 ∞ k=1 (-1) k+1 k 7 2k k -2 ∞ k=1 (-1) k+1 k 5 2k k k-1 j=1 1 j 2 + 5 2 ∞ k=1 (-1) k+1 k 3 2k k k-1 m=1 1 m 2 m-1 j=1 1 j 2 ,
respectively. In 1996, inspired by this result, J. Borwein and D. Bradley [START_REF] Borwein | Searching symbolically for Apéry-like formulae for values of the Riemann zeta function[END_REF] applied extensive computer searches on the base of integer relations algorithms looking for additional zeta identities of this sort. This led to the discovery of the new identity

ζ(7) = 5 2 ∞ k=1 (-1) k+1 k 7 2k k + 25 2 ∞ k=1 (-1) k+1 k 3 2k k k-1 j=1 1 j 4 , (3)
which is simpler than Koecher's formula for ζ(7), and similar identities for ζ(9), ζ [START_REF] Koecher | [END_REF], ζ [START_REF] Lupas | Formulae for some classical constants[END_REF], etc. This allowed them to conjecture that certain of these identities, namely those for ζ(4n + 3) are given by the following generating function formula [START_REF] Borwein | Empirically determined Apéry-like formulae for ζ(4n + 3)[END_REF]:

∞ n=0 ζ(4n + 3)a 4n = ∞ k=1 k k 4 -a 4 = 5 2 ∞ k=1 (-1) k+1 k 2k k (k 4 -a 4 ) k-1 m=1 m 4 + 4a 4 m 4 -a 4 , |a| < 1. (4)
The validity of (4) was proved later by G. Almkvist and A. Granville [START_REF] Almkvist | Borwein and Bradley's Apéry-like formulae for ζ(4n + 3)[END_REF] in 1999. Expanding the right-hand side of (4) in powers of a 4 gives a formula for ζ(4n + 3), which for n ≥ 1 contains fewer summations the the corresponding formula generated by [START_REF] Amdeberhan | Hypergeometric series acceleration via the WZ method[END_REF]. In particular, comparing constant terms gives (1) and comparing coefficients of a 4 yields (3). There exists a bivariate unifying formula for identities (2) and ( 4)

∞ k=1 k k 4 -x 2 k 2 -y 4 = 1 2 ∞ k=1 (-1) k+1 k 2k k 5k 2 -x 2 k 4 -x 2 k 2 -y 4 k-1 m=1 (m 2 -x 2 ) 2 + 4y 4 m 4 -x 2 m 2 -y 4 .
(

) 5
It was originally conjectured by H. Cohen and then proved by D. Bradley [START_REF] Bradley | Hypergeometric functions related to series acceleration formulas[END_REF] and, independently, by T. Rivoal [START_REF]Simultaneous generation of Koecher and Almkvist-Granville's Apéry-like formulae[END_REF]. Their proof consists of reduction of (5) to a finite non-trivial combinatorial identity which can be proved on the basis of Almkvist and Granville's work [START_REF] Almkvist | Borwein and Bradley's Apéry-like formulae for ζ(4n + 3)[END_REF]. Another proof of (5) based on application of WZ-pairs was given by the authors in [START_REF] Kh | Simultaneous generation for zeta values by the Markov-WZ method[END_REF]. Since

∞ k=1 k k 4 -x 2 k 2 -y 4 = ∞ n=0 ∞ m=0 n + m n ζ(2n + 4m + 3)x 2n y 4m , |x| 2 + |y| 4 < 1, (6)
the formula (5) generates Apéry-like series for all ζ(2n + 4m + 3), n, m ≥ 0, convergent at the geometric rate with ratio 1/4 and contains, as particular cases, both identities (2) and (4).

In [START_REF] Kh | Simultaneous generation for zeta values by the Markov-WZ method[END_REF], the authors showed that the generating function ( 6) also has a much more rapidly convergent representation, namely

∞ k=1 k k 4 -x 2 k 2 -y 4 = 1 2 ∞ n=1 (-1) n-1 r(n) n 2n n n-1 m=1 ((m 2 -x 2 ) 2 + 4y 4 ) 2n m=n (m 4 -x 2 m 2 -y 4 ) , (7)
where

r(n) = 205n 6 -160n 5 + (32 -62x 2 )n 4 + 40x 2 n 3 + (x 4 -8x 2 -25y 4 )n 2 + 10y 4 n + y 4 (x 2 -2).
The identity [START_REF] Bradley | Hypergeometric functions related to series acceleration formulas[END_REF] produces accelerated series for all ζ(2n + 4m + 3), n, m ≥, convergent at the geometric rate with ratio 2 -10 . In particular, if x = y = 0 we get Amdeberhan-Zeilberger's series [START_REF] Amdeberhan | Hypergeometric series acceleration via the WZ method[END_REF] for ζ(3),

ζ(3) = 1 2 ∞ n=1 (-1) n-1 (205n 2 -160n + 32) n 5 2n n 5 . (8)
It is worth pointing out that both identities ( 5) and [START_REF] Bradley | Hypergeometric functions related to series acceleration formulas[END_REF] were proved in [START_REF] Kh | Simultaneous generation for zeta values by the Markov-WZ method[END_REF] by using the same Markov-WZ pair (see also [10, p. 3] for the explicit expression), but with the help of different summation formulas.

A more general form of the bivariate identity (5) for the generating function

∞ n=0 ∞ m=0 m + n n (A 0 ζ(2n + 4m + 4) + B 0 ζ(2n + 4m + 3) + C 0 ζ(2n + 4m + 2))x 2n y 4m = ∞ k=1 A 0 + B 0 k + C 0 k 2 k 4 -x 2 k 2 -y 4 , |x| 2 + |y| 4 < 1,
where A 0 , B 0 , C 0 are arbitrary complex numbers, was proved in [START_REF] Kh | Simultaneous generation for zeta values by the Markov-WZ method[END_REF] by means of the Markov-Wilf-Zelberger theory. More precisely, one has

∞ k=1 A 0 + B 0 k + C 0 k 2 k 4 -x 2 k 2 -y 4 = ∞ n=1 d n n m=1 (m 4 -x 2 m 2 -y 4 ) , (9)
where

d n = (-1) n-1 B 0 (5n 2 -x 2 ) 2n 2n n n-1 m=1 ((m 2 -x 2 ) 2 + 4y 4 ) + (40n + 10)L n + (35n 5 -35n 3 x 2 + 4n(3x 4 + 10y 4 ))L n-1 4(5n 2 -2x 2 )
and L n is a solution of a certain second order linear difference equation with polynomial coefficients in n and x, y with the initial values

L 0 = C 0 , L 1 = (5 -2x 2 )A 0 /15 + (5x 2 -1 -4(x 4 + 6y 4 ))C 0 /30. If we take A 0 = C 0 = 0, B 0 = 1 in (9)
, then L n = 0 for all n ≥ 0 and we get the bivariate identity [START_REF] Bailey | Experimental determination of Apéry-like identities for ζ(2n + 2)[END_REF]. If

B 0 = C 0 = 0, A 0 = 1, then we obtain ∞ n=0 ∞ m=0 m + n n ζ(2n + 4m + 4)x 2n y 4m = 1 4 ∞ n=1 (40n + 10)L n + (35n 5 -35x 2 n 3 + 4n(3x 4 + 10y 4 ))L n-1 (5n 2 -2x 2 ) n m=1 (m 4 -x 2 m 2 -y 4 )
, where the sequence L n is defined recursively as above. A similar formula is valid for the sequence ζ(2n + 4m + 2).

First results related to generating function identities for even zeta values belong to Leshchiner [START_REF] Leshchiner | Some new identities for ζ(k)[END_REF] who proved (in an expanded form) that for |a| < 1,

∞ n=0 1 - 1 2 2n+1 ζ(2n + 2)a 2n = ∞ n=1 (-1) n-1 n 2 -a 2 = 1 2 ∞ k=1 1 k 2 2k k 3k 2 + a 2 k 2 -a 2 k-1 m=1 1 - a 2 m 2 . ( 10
)
Comparing constant terms on both sides of (10) yields

ζ(2) = 3 ∞ k=1 1 k 2 2k k . Since ζ(2n) = (-1) n-1 (2π) 2n 2 • (2n)! B 2n ,
where B 2n ∈ Q are the Bernoulli numbers generated by the exponential generating function

x e x -1 = ∞ n=0 B n x n n! ,
formula [START_REF] Kh | A q-analog of the Bailey-Borwein-Bradley identity[END_REF] gives Apéry-like series for even powers π 2n , n = 1, 2, . . . . In 2006, D. Bailey, J. Borwein and D. Bradley [START_REF] Bailey | Experimental determination of Apéry-like identities for ζ(2n + 2)[END_REF] proved another identity

∞ n=0 ζ(2n + 2)a 2n = ∞ k=1 1 k 2 -a 2 = 3 ∞ k=1 1 2k k (k 2 -a 2 ) k-1 m=1 m 2 -4a 2 m 2 -a 2 .
It generates similar Apéry-like series for the numbers ζ(2n + 2), which are not covered by Leshchiner's result [START_REF] Kh | A q-analog of the Bailey-Borwein-Bradley identity[END_REF]. In the same paper [START_REF] Bailey | Experimental determination of Apéry-like identities for ζ(2n + 2)[END_REF], a generating function producing fast convergent series for the sequence π 2n+4 , n = 0, 1, 2, . . . , was found, which for |a| < 1, has the form

∞ n=0 (-1) n (3 -2n-3 -2B 2n+4 (2 2n+3 -1))π 2n+4 4(2n + 4)! a 2n = ∞ k=1 1 k 2 2k k (k 2 -a 2 ) k-1 m=1 1 - a 2 m 2 . ( 11
)
Here the left-hand side of ( 11) is a Maclaurin expansion of the function πa csc(πa) + 3 cos(πa/3) -4 4a 4 .

Comparing constant terms in [START_REF] Koecher | [END_REF] implies that

ζ(4) = 36 17 ∞ k=1 1 k 4 2k k .
The identity [START_REF] Koecher | [END_REF] gives a formula for π 2n+4 which for n ≥ 0 involves fewer summations then the corresponding formula generated by [START_REF] Kh | A q-analog of the Bailey-Borwein-Bradley identity[END_REF].

In this paper, we consider values of Dirichlet's beta function, which for s > 0 is defined by the series

β(s) = ∞ k=0 (-1) k (2k + 1) s .
It is well-known due to Euler that for odd s, β(s) is a rational multiple of π s

β(2n + 1) = (-1) n E 2n 2 2n+2 (2n)! π 2n+1 , n = 0, 1, 2, . . . , (12)
where the integer coefficients E 2n are the even indexed Euler numbers defined by the exponential generating function

1 cosh(z) = 2e z e 2z + 1 = ∞ n=0 E n n! z n = 1 - z 2 2! + 5z 4 4! - 61z 6 6! + . . . .
For even s, no Euler-type formula is known, and β(2) defines the well-known Catalan's constant

G := ∞ n=0 (-1) n (2n + 1) 2 = 0.915965594 . . . .
In Sections 2, 3 we prove generating function identities producing fast convergent series for the sequences β(2n + 1) and β(2n + 2). In particular, we establish some analogs of identities [START_REF] Kh | A q-analog of the Bailey-Borwein-Bradley identity[END_REF] and [START_REF] Koecher | [END_REF] for the odd powers of π : π 2n+1 , n ≥ 0, and π 2n+3 , n ≥ 0. As a consequence of our results on even beta values, we derive the following nice formula for Catalan's constant:

G = 1 64 ∞ n=1 (-1) n-1 256 n q(n) 8n 4n 2 2n n n 3 (2n -1)(4n -1) 2 (4n -3) 2 , ( 13
)
where q(n) = 419840n 6 -915456n 5 + 782848n 4 -332800n 3 + 73256n 2 -7800n + 315.

It can be considered as an analog of Amdeberhan-Zeilberger's series [START_REF] Kh | Generating function identities for ζ(2n+2), ζ(2n+3) via the WZ-method[END_REF] for ζ(3), since the series on the right-hand side of (13) converges exponentially with ratio 2 -10 .

2 Ap éry-like series for β(2n + 1) and β(2n + 3).

We start by recalling several definitions and known facts related to the Markov-Wilf-Zeilberger theory (see [START_REF] Markoff | Mémoiré sur la transformation de séries peu convergentes en séries tres convergentes[END_REF][START_REF] Mohammed | Infinite families of accelerated series for some classical constants by the Markov-WZ method[END_REF][START_REF] Mohammed | The Markov-WZ method[END_REF]). A function H(n, k), in the integer variables n and k, is called hypergeometric or closed form (CF) if the quotients

H(n + 1, k) H(n, k) and H(n, k + 1) H(n, k)
are both rational functions of n and k. A hypergeometric function that can be written as a ratio of products of factorials is called pure-hypergeometric. A pair of CF functions F (n, k) and G(n, k) is called a WZpair if

F (n + 1, k) -F (n, k) = G(n, k + 1) -G(n, k). (14)
A P-recursive function is a function that satisfies a linear recurrence relation with polynomial coefficients. If for a given hypergeometric function H(n, k), there exists a polynomial P (n, k) in k of the form

P (n, k) = a 0 (n) + a 1 (n)k + • • • + a L (n)k L ,
for some non-negative integer L, and P-recursive functions a 0 (n), . . . , a L (n) such that

F (n, k) := H(n, k)P (n, k)
satisfies ( 14) with some function G, then a pair (F, G) is called a Markov-WZ pair associated with the kernel H(n, k) (MWZ-pair for short). We call G(n, k) an MWZ mate of F (n, k). If L = 0, then (F, G) is simply a WZ-pair.

In 2005, M. Mohammed [START_REF] Mohammed | Infinite families of accelerated series for some classical constants by the Markov-WZ method[END_REF] showed that for any pure-hypergeometric kernel H(n, k), there exists a non-negative integer L and a polynomial P (n, k) as above such that F (n, k) = H(n, k)P (n, k) has an MWZ mate G(n, k) = F (n, k)Q(n, k), where Q(n, k) is a ratio of two P-recursive functions. Paper [START_REF] Mohammed | The Markov-WZ method[END_REF] is accompanied by the Maple package MarkovWZ which, for a given H(n, k) outputs the polynomial P (n, k) and the G(n, k) as above.

From relation [START_REF] Markoff | Mémoiré sur la transformation de séries peu convergentes en séries tres convergentes[END_REF] we get the following summation formulas.

Proposition A. [15, Theorem 2(b)] Let (F, G) be an MWZ-pair. If lim n→∞ F (n, k) = 0 for every k ≥ 0, then ∞ k=0 F (0, k) -lim k→∞ ∞ n=0 G(n, k) = ∞ n=0 G(n, 0), (15)
whenever both sides converge.

Proposition B. [15, Cor. 2] Let (F, G) be an MWZ-pair. If lim k→∞ ∞ n=0 G(n, k) = 0, then ∞ k=0 F (0, k) = ∞ n=0 (F (n, n) + G(n, n + 1)), (16)
whenever both sides converge. Formulas ( 15), ( 16) with an appropriate choice of MWZ-pairs can be used to convert a given hypergeometric series into a different rapidly converging one.

As usual, let (λ) ν be the Pochhammer symbol (or the shifted factorial) defined by

(λ) ν = Γ(λ + ν) Γ(λ) = 1, ν = 0; λ(λ + 1) . . . (λ + ν -1), ν ∈ N.
In 1979, D. Leshchiner [START_REF] Leshchiner | Some new identities for ζ(k)[END_REF] proved accelerated series for the values β(2n + 1) in the spirit of Apéry's series [START_REF] Almkvist | Borwein and Bradley's Apéry-like formulae for ζ(4n + 3)[END_REF]. Namely, he showed that

β(2n + 1) = ∞ k=0 2k k 16 k n ν=0 (-1) n-ν A ν (2k + 1) 2ν+1 f n-ν k+1 , n = 0, 1, 2, . . . ( 17
)
where

f 0 k = 1, f r k = 0 if r < 0 or r ≥ k, f r k = 0<l1<...<lr<k r j=1 1 (2l j -1) 2 , 1 ≤ r ≤ k -1,
and

A ν = 3/4 if ν = 0 1 if ν > 0.
Formulas ( 12), [START_REF] Van Der Poorten | Apéry's proof of the irrationality of ζ(3). An informal report[END_REF] give the following Apéry-like series for odd powers of π :

π = 3 ∞ k=0 2k k 16 k (2k + 1) , π 3 = 32 ∞ k=0 2k k 16 k (2k + 1) 3 -24 ∞ k=0 2k k 16 k (2k + 1) k-1 m=0 1 (2m + 1) 2 , π 5 = 1536 5 ∞ k=0 2k k 16 k (2k + 1) 5 - 1536 5 ∞ k=0 2k k 16 k (2k + 1) 3 k-1 m=0 1 (2m + 1) 2 + 1152 5 ∞ k=0 2k k 16 k (2k + 1) k-1 m=0 k-1 l=0 1 (2m + 1) 2 (2l + 1) 2 .

Using the generating function for odd beta values

∞ n=0 β(2n + 1)a 2n = 1 2 ∞ k=0 (-1) k (k + 1/2) (k + 1/2) 2 -a 2 /4 (18)
it is easily seen that formulas [START_REF] Van Der Poorten | Apéry's proof of the irrationality of ζ(3). An informal report[END_REF] are generated by the following identity.

Proposition 1 For any complex a with |a| < 1 we have

∞ n=0 β(2n + 1)a 2n = ∞ n=0 2n n 4 2n+1 (2n + 1) 3(2n + 1) 2 + a 2 (2n + 1) 2 -a 2 n-1 m=0 1 - a 2 (2m + 1) 2 . ( 19
)
Proof. Identity (19) can easily be proved by the Markov-Wilf-Zeilberger method. Taking the kernel

H(n, k) = (-1) k k!(n + k + 1/2) (k + 2n)!((n + k + 1/2) 2 -a 2 /4)
and applying the Maple package MarkovWZ we get that

F (n, k) = 2(-1) k k!(2n + 2k + 1) (k + 2n)!((2n + 2k + 1) 2 -a 2 ) 1 + a 2 n 1 -a 2 n and G(n, k) = (-1) k k!(3(2n + 1) 2 + a 2 + 4k(2 + 4n + k)) 2(k + 2n + 1)!((2n + 2k + 1) 2 -a 2 ) 1 + a 2 n 1 -a 2 n
give a WZ-pair, i.e.,

F (n + 1, k) -F (n, k) = G(n, k + 1) -G(n, k).
Now by Proposition A, we get

∞ k=0 F (0, k) = ∞ n=0 G(n, 0), which implies (19). 2
Lemma 1 For any complex a,

sin πa 6 = a 2 ∞ n=0 2n n 16 n (2n + 1) n-1 m=0 1 - a 2 (2m + 1) 2 . ( 20
)
Proof. Applying the transformation (see [6, §2.8]) in terms of the Gauss hypergeometric function

sin az = a sin z • 2 F 1 1 + a 2 , 1 -a 2 ; 3 2
; sin 2 z with z = π/6 we get the desired representation. 2 Remark. Formula (20) can be considered as an expansion of the function sin(πa/6) into Newton's interpolation series with interpolation points at zero and odd integers.

Theorem 1 Let a be a complex number, distinct from an odd integer. Then On the other hand, by [START_REF]Simultaneous generation of Koecher and Almkvist-Granville's Apéry-like formulae[END_REF], we have

4 • ∞ n=0 β(2n + 1)a 2n = g 1 -a 2 + g 1 + a 2 ,
where g(z) = ∞ k=0 (-1) k /(k + z). Using the reflection formula (see [6, §1.8])

g(z) + g(1 -z) = π sin(πz) we get ∞ n=0 β(2n + 1)a 2n = π 4 cos(πa/2)
, from which formula (21) follows. Expanding the left-hand side of (21), by [START_REF] Leshchiner | Some new identities for ζ(k)[END_REF], we get the required expansion. 2 Comparing (21) and ( 19) we can easily see that these identities produce different series for the odd powers of π. The series generated by (21) are simpler in that sense they involve fewer summations then the corresponding series generated by (19). Moreover, the formulas obtained here lead to some non-trivial redundancy relations that can be written down explicitly by comparing [START_REF] Van Der Poorten | Apéry's proof of the irrationality of ζ(3). An informal report[END_REF] and the corresponding series for β(2n + 1), n ≥ 1, given by (21). As an example, comparing series for π 3 yields the following redundancy formula: 3 Generating function identities for even beta values.

In this section we derive series acceleration formulae for even beta values by application of the Markov-WZ method.

Theorem 2 Let a and d be complex numbers such that a 2 = (d + n) 2 , n = 0, 1, 2, . . . , and d distinct from zero and negative integers. Then

∞ k=0 (-1) k (k + d) 2 -a 2 = 1 2 ∞ n=0 (1 + a) n (1 -a) n (3n 2 + 2n(2d + 1) + d 2 + 2d + a 2 ) (d) 2n+2 ((n + d) 2 -a 2 ) . ( 22
)
and applying the Maple package MarkovWZ [START_REF] Mohammed | The Markov-WZ method[END_REF], we see that

F (n, k) = (-1) n+k 1+a 2 k 1-a 2 k 1 + a 2 n 1 -a 2 n (2n)! 1-a 2 2n+k+1 1+a 2 2n+k+1
and

G(n, k) = (-1) n+k 1+a 2 k 1-a 2 k 1 + a 2 n 1 -a 2 n (2n)! 8 1-a 2 2n+k+2 1+a 2 2n+k+2
× × (40n 2 + 56n + 19 -a 2 + 24nk + 16k + 4k 2 ) is a Markov-WZ pair. By using Proposition A, we get

∞ k=0 F (0, k) = ∞ n=0
G(n, 0), which implies the required statement. 2 The generalized identities of Corollary 1 and Theorem 3 generate fast convergent series for β(2n + 2) convergent at a geometric rate with ratio 1/4. Formula (23) was earlier found by Lupas in [START_REF] Lupas | Formulae for some classical constants[END_REF]. The next corollary gives much faster convergent series at the geometric rate with ratio 2 2 /3 6 = 4/729 = 0.005 . . . . , where p(n, a) is defined as above. After simplifying and replacing Pochhammer's symbols by binomial coefficients we get the desired identity. 2 The next theorem gives even much faster convergent series at the geometric rate with ratio 2 -10 .

π 4a 2 16 n

 216 cos(πa/2) (2n + 1)((2n + 1) 2 -a 2 ) 1) 2 . (21)If |a| < 1, then the left-hand side of (21) has the following series expansion:∞ n=0 (-1) n+1 ((2n + 3)9 n+1 E 2n+2 -1)π 2n+34 n+2 9 n+1 (2n + 3

16 n

 16 (2n + 1) 3 .

Corollary 2 m=1 ( 1 -F 2 n 1 + a 2 n 1 -a 2 n

 21212 Let a be a complex number with |a| < 1. Then a 2 /(4m 2 ))3n m=n (1 -a 2 /(2m -1) 2 ), where p(n, a) = 580n 4 -764n 3 + 344n 2 -61n + 15/4 -a 2 (18n 2 -15n + 4 -a 2 /4). In particular, By applying Proposition B to the MWZ pair from the proof of Theorem 3 we get ∞ k=0 (2n)! p(n + 1, a)

Acknowledgements

Both authors thank the Institut de Hautes Études Scientifiques, Bures-sur-Yvette, France, where this research was carried out for hospitality and excellent working conditions.

Proof. Considering the kernel

we get that

and

give a WZ-pair, and by Proposition A, we obtain

In particular, from (22) if d = 1 we get Leshchiner's identity [START_REF] Kh | A q-analog of the Bailey-Borwein-Bradley identity[END_REF]. If d = 1/2 we get the following identity generating accelerated series for even beta values.

Corollary 1 Let a be a complex number with |a| < 1.

In particular, if a = 0 we get

16 n (6n -1)

.

Theorem 3 Let a be a complex number with |a| < 1.

.

In particular,

Proof. Starting with the kernel

Theorem 4 Let a be a complex number with |a| < 1. Then

, where q(n, a) = 419840n 6 -915456n 5 + n 4 (782848 -15872a 2 ) -n 3 (332800 -25600a 2 )

+ n 2 (73256 -14992a 2 + 232a 4 ) -n(7800 -3760a 2 + 184a 4 ) + 315 -359a 2 + 45a 4 -a 6 .

In particular,

, where q(n) = 419840n 6 -915456n 5 + 782848n 4 -332800n 3 + 73256n 2 -7800n + 315.

Proof. We first observe that the generating function of even beta values can be written in the form

) .

Define the function

3-a 4 n+k+1

.

Then using the Maple package MarkovWZ we obtain that

is a Markov-WZ pair corresponding to the kernel H(n, k). Now by Proposition B, we have q(n + 1, a), where q(n, a) is defined as above. After simplifying and replacing Pochhammer's symbols by binomial coefficients we get the required identity. Note that application of Proposition A to the Markov-WZ pair found above recovers Theorem 3.

2 In conclusion we note that the different approaches described in the introduction for studying and finding various Apéry-like series for zeta values are applicable to the Dirichlet beta function as well. Hence, it would be of interest to find more general identities for beta values by means of bivariate generating functions as it was done in the case of the zeta function (see for instance identities ( 5), ( 7)).