Printer Friendly

Closed paths whose steps are roots of unity.

1 Introduction

The subject of random walks is classical and appears in many areas of mathematics, physics and computer science (see, for example, http://en.wikipedia.org/wiki/Randomwalks). In this paper we combinatorially analyse a new type of closed random walks in the complex plane--a kind of restricted Brownian motion--whose steps are given by nth-roots of unity. For n [greater than or equal to] 1, let [[OMEGA].sub.n] = {1, [w.sub.n], [w.sup.2.sub.n], ..., [w.sup.n-1.sub.n]} be the set of all n-th roots of unity, where [w.sub.n] = exp(2[pi]i/n) [member of] C. A polygonal path of length N, starting at the origin in the complex plane, whose steps are n-th roots of unity can be encoded by the sequence [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] of its successive steps, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. For v = 0, ..., n - 1, let [m.sub.v] be the number of times that [w.sup.v.sub.n] appears in w. We call the sequence [??] = [[m.sub.0], ..., [m.sub.n-1]] the type of w, and write [??] = type(w). Of course, the path w is closed if and only if [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] if and only if

[m.sub.0] + [m.sub.1][w.sub.n] + [m.sub.2][w.sup.2.sub.n] + ... + [m.sub.n-1][w.sup.n-1.sub.n] = 0. (1.1)

We call a sequence [??] = [[m.sub.0], [m.sub.1], ..., [m.sub.n-1]] [member of] [N.sup.n] admissible if (1.1) is satisfied. Figure 1 shows a closed pentagon made of 18-th roots of unity encoded by [[w.sup.3.sub.18], [w.sup.11.sub.18], [w.sup.5.sub.18], [w.sup.12.sub.18], [w.sup.17.sub.18]] and a closed 11-gon made of 14-th roots of unity encoded by [[w.sup.12.sub.14], [w.sub.14], [w.sup.4.sub.14], [w.sup.5.sub.14], [w.sup.7.sub.14], [w.sup.5.sub.14], [w.sup.11.sub.14], [w.sup.11.sub.14], [w.sup.9.sub.14], [w.sup.3.sub.14], [w.sup.13.sub.14]].

Clearly, the number of closed paths, of length N, with admissible type [??] is given by the multinomial coefficient N!/[m.sub.0]![m.sub.1]! .... [m.sub.n-1]!. This implies that the number [U.sub.n](N) of closed polygonal paths of

length N whose steps are n-th roots of unity is given by the formula

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (1.2)

[FIGURE 1 OMITTED]

In Section 2, we characterize admissibility and express the numbers [U.sub.n](N) as constant term extractions in suitable rational expressions. We also give a formula from which the computation of the numbers [U.sub.n](N) can be reduced to the computation of the numbers [U.sub.q](N'), where N' [less than or equal to] N and q is a suitable divisor of n. Section 3 is devoted to an analysis of recursive and asymptotic properties of the numbers [U.sub.n](N). Finally, some tables are given.

2 Constant term and reduction formulas

To take advantage of formula (1.2) for [U.sub.n](N) on a symbolic algebra system, we state first a simple characterization of admissibility for a sequence [??] [member of] [N.sup.n]. This is done using the classical cyclotomic polynomials [[PHI].sub.n](z) = [PI](z - w), where w runs through the primitive n-th roots of unity. Equivalently, this means that w = exp(2k[pi]i/n), where 1 [less than or equal to] k [less than or equal to] n and GCD(n, k) = 1. Since [z.sup.n] - 1 = [[PI].sub.d|n] [[PHI].sub.d](z), Moebius inversion implies that [[PHI].sub.n](z) = [[PI].sub.d|n][([x.sup.d] - 1).sup.[mu](n/d)], where [mu] denotes the Moebius function. This shows that [[PHI].sub.n](z) is a monic polynomial in Z[z] of degree [PHI](n), the Euler function of n. The following very easy, but basic lemma characterizes admissibility.

Lemma 2.1 (criteria for admissibility). For n [greater than or equal to] 1, the sequence [??] = [[m.sub.0], ..., [m.sub.n-1]] [member of] [N.sup.n] is admissible if and only if the cyclotomic polynomial [[PHI].sub.n](z) divides the polynomial

[P.sub.[??]](z) = [m.sub.0] + [m.sub.1]z + ... + [m.sub.n-1][z.sup.n-1].

Proof: Consider the euclidean division of [P.sub.[??]](z) by [[PHI].sub.n](z) in the ring Z[z]:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (2.1)

where deg [R.sub.[??]](z) < deg [[PHI].sub.n](z) = [phi](n). Since [[PHI].sub.n]([w.sub.n]) = 0 this shows that [??] is admissible if and only if [P.sub.[??]]([w.sub.n]) = 0 if and only if [R.sub.[??]]([w.sub.n]) = 0. But [R.sub.[??]]([w.sub.n]) = 0 if and only if [R.sub.[??]](z) = 0 identically since [[PHI].sub.n](z) is known to be the minimal polynomial of any of its roots and deg [R.sub.[??]] < deg [[PHI].sub.n]. []

Euclidean division shows that the coefficients of [R.sub.[??]](z) are Z-linear combinations [l.sub.k]([m.sub.0], ..., [m.sub.n-1]) of the [m.sub.i]'s. Hence, [??] is admissible if and only if [l.sub.k]([m.sub.0], ..., [m.sub.n-1]) = 0 for k = 0, ..., [phi](n) - 1. Table 1, made using the rem command in Maple gives the values of the [l.sub.k]'s for n = 1, ..., 20. For example, for n = 6, [phi](n) = 2 and using Table 1, formula (1.2) takes the form

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Note that, by the multinomial formula, this is equivalent to the following constant term formula

[U.sub.6](N) = CT([([t.sub.1] + [t.sub.2] + [t.sub.1]/[t.sub.2] + [t.sub.2]/[t.sub.1] + [t.sup.-1.sub.1] + [t.sup.-1.sub.2]).sup.N)],

where CT(L([t.sub.1], [t.sub.2], ...)) denotes the constant term of the full expansion of L as a Laurent series in [t.sub.1], [t.sub.2], .... This is generalized as follows.

Theorem 2.2 There is a Laurent polynomial, [[LAMBDA].sub.n]([t.sub.1], ..., [t.sub.[phi]](n)), such that [U.sub.n](N) = CT[([[LAMBDA].sub.n]([t.sub.1], ..., [t.sub.[phi]](n)).sup.N] Moreover, [[LAMBDA].sub.n]([t.sub.1], ..., [t.sub.[phi]](n)) is computed as follows. Let [m.sub.0] + ... + [m.sub.n- 1][z.sup.n-1] = [[PHI].sub.n](z)Q(z) + R(z), where the remainder is R(z) = [[summation].sup.[phi](n)-1.sub.k=0] [l.sub.k]([m.sub.0], ..., [m.sub.n-1])[z.sup.k], with [l.sub.k]([m.sub.0], ..., [m.sub.n-1]) = [[summation].sup.n-1.sub.i=0] [c.sub.k,i][m.sub.i], [c.sub.k,i] [member of] Z, k = 0,..., [phi](n) - 1. Then,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (2.2)

Proof: By the multinomial theorem,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

The result follows since the constant term is given by taking the sum of the terms corresponding to the exponents [l.sub.k] = 0 for k = 0, ..., [phi](n) - 1. []

Table 2 gives the rational functions [[LAMBDA].sub.n]([t.sub.1], ..., [t.sub.[phi]](n)) for n = 1, ..., 20. Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] be the canonical decomposition of the integer n. By definition, the radical of n is the square-free integer q = rad(n) = [p.sub.1] ... [p.sub.s] consisting of the product of the [p.sub.i]'s. The computation of the cyclotomic polynomial [[PHI].sub.n](z) is greatly simplified by making use of the well-known reduction formula

[[PHI].sub.n](z) = [[PHI].sub.q]([z.sup.n/q]), q = rad(n). (2.3)

This implies that the computation of the exponential generating function of the sequence [([U.sub.n](N)).sub.N[greater than or equal to]0] is reduced to that of [([U.sub.q](N)).sub.N[greater than or equal to]0] as follows.

Proposition 2.3 (reduction formula for [U.sub.n](N)). Let n [greater than or equal to] 1 and q = rad(n). Then,

[summation over (N[greater than or equal to]0)][U.sub.n](N)[X.sup.N]/N! = [([summation over (N[greater than or equal to]0)][U.sub.q](N)[X.sup.N]/N!).sup.n/q]. (2.4)

Proof: Using the remainder function, we have by linearity,

[R.sub.[??]](z) = rem([P.sub.[??]](z), [[PHI].sub.n](z)) = [n-1summation over (k=0)] [m.sub.k]rem([z.sup.k], [[PHI].sub.n](z)). (2.5)

Now, for 0 [less than or equal to] v [less than or equal to] q - 1, consider the euclidean division

[z.sup.v] = [[PHI].sub.q](z)[Q.sub.v](z) + [[rho].sub.v](z), (2.6)

where [[rho].sub.v](z) = rem([z.sup.v], [[PHI].sub.q](z)). The substitution z [right arrow] [z.sup.n/q] in (2.6) followed by a multiplication by [z.sup.r] gives, using (2.3), [z.sup.vn/q+r] = [[PHI].sub.q]([z.sup.n/q])[z.sup.r][Q.sub.v]([z.sup.n/q]) + [z.sup.r][[rho].sub.v]([z.sup.n/q]) = [[PHI].sub.n](z)[z.sup.r][Q.sub.v]([z.sup.n/q]) + [z.sup.r][[rho].sub.v]([z.sup.n/q]). Let k = vn/q + r, where 0 [less than or equal to] r < n/q. Then,

deg [z.sup.r][[rho].sub.v]([z.sup.n/q]) = r + n/q deg[[rho].sub.v](z) [less than or equal to] r + n/q([phi](q) - 1) = r + [phi](n) - n/q < [phi](n).

This implies that rem([z.sup.k], [[PHI].sub.n](z)) = [z.sup.r][[rho].sub.v]([z.sup.n/q]). Substituting this into (2.5) and collecting terms, we find that the [phi](n) conditions for admissibility, [[[l.sub.k]([m.sub.0], [m.sub.1], ..., [m.sub.n-1]) = 0].sub.0[less than or equal to]k[less than or equal to][phi](n)-1], split into n/q blocks of [phi](q) conditions, [[[l.sub.i]([m.sub.j], [m.sub.n/q+j], [m.sub.2n/q+j], [m.sub.(q-1)n/q+j]) = 0].sub.0[less than or equal to]i[less than or equal to][phi](q)-1], 0 [less than or equal to] j [less than or equal to] n/q - 1, from which (2.4) follows. []

Table 3 gives the numerical values of [U.sub.n](N) for 1 [less than or equal to] n [less than or equal to] 20 and 0 [less than or equal to] N [less than or equal to] 20.

3 Analysis of the sequences

Let us say that a path is normalized if its first step is the complex number 1 (i.e. the path starts horizontally along the positive real axis). Each normalized path [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] generates, by rotation, n distinct paths [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. This implies that n divides [U.sub.n](N) for every n [greater than or equal to] 1 and N [greater than or equal to] 1. As Tables 1 and 2 indicate, the structure of the sequence [([U.sub.n](N)).sub.N[greater than or equal to]0] heavily depend on the arithmetical nature of n. For example, let n = p be a prime number. Then for such values of n, admissibility for a vector [??] [member of] [N.sup.p] means that [m.sub.0] = [m.sub.1] = ... = [m.sub.p-1] since, in this case, [[PHI].sub.p](z) = 1 + z + ... + [z.sup.p-1] and [R.sub.[??]](z) = ([m.sub.0] - [m.sub.p-1]) + ([m.sub.1] - [m.sub.p- 1])z + ... + ([m.sub.p-2] - [m.sub.p-1])[z.sup.p-2], (see Table 1, for example). Formula (1.2) then takes the form

[U.sub.p](N) = N!/(N/p)!p if P|N, 0 otherwise. (3.1)

Note that when p = 2, (3.1) corresponds to the classical central binomial coefficients enumerating one-dimensional closed lattice paths of length N. When p = 3, (3.1) corresponds to the De Bruijn numbers (sequence A006480 in Sloane-Plouffe encyclopedia [Sloane(2010)]). For prime powers n = pa, we have by Proposition 2.3,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (3.2)

since, in this case q = p. Note that when n = 8 = [2.sup.3], then Us(N) is the number of 4-dimensional closed lattice paths in [Z.sup.4] of length N starting at the origin (see sequence A039699 in Sloane). The reader can check that, more generally, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is the number of closed lattice paths in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] of length N starting at the origin. Interestingly enough, for any other dimension d [not equal to] [2.sup.[alpha]-1], such a connection betweens lattice paths in [Z.sup.d] and plane paths whose steps are roots of unity does not exist.

When n is not a prime power, the situation is more delicate. For example, if n = 6, then, using the Maple package GFUN [Salvy and Zimmermann(1994)], it can be seen that [([U.sub.n](N)).sub.N[greater than or equal to]0] satisfies the following linear recurrence with polynomial coefficients,

[(N + 3).sup.2][U.sub.6](N + 3) = (N + 2)(N + 3)[U.sub.6](N + 2) + 24[(N + 2).sup.2][U.sub.6](N + 1) + 36(N + 1)(N + 2)[U.sub.6](N) (3.3)

with initial conditions [U.sub.6](0) = 1, [U.sub.6](1) = 0, [U.sub.6](2) = 6. Such sequences are called polynomially recursive (P-recursive for short) and are characterized by the fact that their (ordinary or exponential) generating series are D-finite (i.e. satisfy a linear differential equation with polynomial coefficients). As a consequence, P-recursive sequences are closed under many operations including linear combinations, pointwise and Cauchy products [Stanley(1980)]. Moreover their asymptotic estimates, as N [right arrow] [infinity], are well behaved. In our context, the general situation is summarized by Theorem 3.2. below. We need first the following technical lemma.

Lemma 3.1 Let [??] = ([t.sub.1], ..., [t.sub.[phi]](n)) [member of] [C.sup.[phi](n)]. Then the Laurent polynomial [[LAMBDA].sub.n] satisfies

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (3.4)

Moreover, if n = [p.sup.[alpha]], a prime power, then the maximum value (3.4) is attained precisely at the p distinct points ([e.sup.2[pi]iv/p], ..., [e.sup.2[pi]iv/p]), v = 0, ..., p - 1 and we have [[LAMBDA].sub.n]([e.sup.2[pi]iv/p], ..., [e.sup.2[pi]iv/p]) = [ne.sup.2[pi]iv/p]. If n is not a prime power, then the maximum value (3.4) is attained only at the point (1, ..., 1) and we have [[LAMBDA].sub.n](1, ..., 1) = n.

Proof: By Theorem 2.2, [[LAMBDA].sub.n] can be written as a sum of n terms,

[[LAMBDA].sub.n]([??])= [t.sub.1] + ... + [t.sub.[phi]](n) + [[GAMMA].sub.n]([??]), (3.5)

where [[GAMMA].sub.n] is a sum of n - [phi](n) unitary Laurent monomials in [t.sub.1], ..., [t.sub.[phi]](n). Each of the n terms in [[LAMBDA].sub.n] has modulus 1 when [absolute value of [t.sub.v]] = 1, v = 1, ..., [phi](n). Hence (3.4) follows from the triangular inequality and the fact that [[LAMBDA].sub.n](1, ..., 1) = n. Note that the maximum value in (3.4) is attained only at points [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for which the n monomials take a common value, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], say. In particular, from (3.5), we must have [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. We consider two cases:

(i) if n = [p.sup.[alpha]], then it can be checked that each term in [[GAMMA].sub.n] has total degree - (p - 1). This implies that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is a p-th root of unity: [e.sup.2[pi]iv/p], v = 0, ..., p - 1;

(ii) if n [not equal to] [p.sup.[alpha]], the situation is more delicate. If we can show that at least one of the terms in [[GAMMA].sub.n] has total degree 0, then the maximal value in (3.4) will be attained only at the point (1, ..., 1), since this would imply that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. The existence of such a 0-degree term is proved as follows. By (2.2), the general term [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] has total degree [[summation].sub.[phi](n)-1.sub.k=0] [c.sub.k,j]. When j = [phi](n), this total degree is 0. To see this, note that [[summation].sub.[phi](n)-1.sub.k=0] [c.sub.k,j][z.sup.k] = rem([z.sup.j], [[PHI].sub.n](z)). Taking j = [phi](n), z = 1, this gives [[summation].sub.[phi](n)-1.sub.k=0] [c.sub.k,[phi](n)] = rem([z.sup.[phi](n)], [[PHI].sub.n](z))[|.sub.z=1] = ([z.sup.[phi](n)] - [[PHI].sub.n](z))[|.sub.z=1] = 0, since [[PHI].sub.n](1) = 1 when n [not equal to] [p.sup.[alpha]].

Theorem 3.2 For any n > 1, we have an asymptotic estimate of the form

[U.sub.n](N) ~ [a.sub.n] [n.sup.N]/[N.sup.1/2[phi](n)] (1 + [b.sub.1,n]/N + [b.sub.2,n]/[N.sup.2] + ...), as N [right arrow] [infinity], (3.6)

where [a.sub.n], [b.sub.j,n] are independent of N. When n = [p.sup.[alpha]] is a prime power, then N must be a multiple of p as it goes to infinity in (3.6). More explicitly, the leading coefficient [a.sub.n] is given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

For each n [greater than or equal to] 1, the sequence [([U.sub.n](N)).sub.N[greater than or equal to]0] is P-recursive but is not algebraic when n > 2.

Proof: In order to establish the asymptotic estimate (3.6), first note that the constant term extraction [U.sub.n](N) = CT[([[LAMBDA].sub.n]([t.sub.1], ..., [t.sub.[phi](n)]).sup.N]) can be expressed as the multiple integral

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (3.7)

which is the average value of [[LAMBDA].sup.N.sub.n] over the [phi](n)-dimensional torus {([t.sub.1], ..., [t.sub.[phi](n)]) [member of] [C.sup.[phi](n)]| [absolute value of [t.sub.v]] = 1, v = 1, ..., [phi](n)}. Now by Theorem 2.2,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (3.8)

where [[lambda].sub.j]([??]) = [[summation].sup.[phi](n)-1.sub.k=0] [c.sub.k,j] [u.sub.k+1] is a real-valued linear combination of [u.sub.1], ..., [u.sub.k], 0 [less than or equal to] j [less than or equal to] [phi](n) - 1. By the triangular inequality, [absolute value of [L.sub.n]([??])] [less than or equal to] n for every [??] [member of] [(-[pi], [pi]].sup.[phi](n)]. To obtain the asymptotic estimate of (3.6) it suffices to approximate (3.7) by a gaussian distribution around each point [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for which the maximum value [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is attained. This is Laplace's method [De Bruijn(1981)]. By Lemma 3.1,

(i) if n = [p.sup.[alpha]], then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is the only point in [(-[pi], [pi]].sup.[phi](n)] for which [absolute value of [L.sub.n]([??])] = n. In fact [[theta].sup.*] = 0;

(ii) if n = [p.sup.[alpha]], then there are exactly p possible values of [u.sup.*] for which [absolute value of [L.sub.n]([??])] = n. In fact [[theta].sup.*] = 2v[pi]/p mod 2[pi] [member of] (-[pi], [pi]],v = 0, ..., p - 1.

We conclude by estimating (3.7) by a sum of moments of gaussian distributions in the following way:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

where, for each [??] such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (3.9)

where [Q.sup.*]([??]) is the positive definite quadratic form associated to the symmetric [phi](n) x [phi](n) matrix K = [CC.sup.T] in which C = [[[c.sub.k,j]].sub.0[less than or equal to]k[less than or equal to][phi](n)-1,0[less than or equal to]j[less than or equal to]n-1], where the [c.sub.k,j]'s are defined by (2.2) and [H.sup.*]([??]) = 1 + O([[parallel] [??] [parallel].sup.3]). It turns out that det(K) = [[PI].sub.p|n][p.sup.[phi](n)/(p-1)], which is a consequence of the known fact that the absolute value of the discriminant of [[PHI].sub.n](z) is equal to [n.sup.[phi](n)] [[PI].sub.p|n][p.sup.[phi](n)/(p-1)], for n > 2.

The P-recursivity of [([U.sub.n](N)).sub.N[greater than or equal to]0] is established as follows. Fix n [greater than or equal to] 1 and let k = [phi](n). We shall show that the series

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (3.10)

is D-finite in X where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] means constant term extraction relative to the variables [t.sub.1], ..., [t.sub.k]. First, fix integers [m.sub.1] > 0, ..., [m.sub.k] > 0 in such a way that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is a polynomial in [t.sub.1], ..., [t.sub.k]. The rational function

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (3.11)

is obviously D-finite in the variables [t.sub.1], ..., [t.sub.k], X. By Theorem 2.2, the numbers [U.sub.n](N) can be expressed as the following coefficient extraction in f([t.sub.1], ..., [t.sub.k], X):

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Hence, by (3.10),

[summation over (N[greater than or equal to]0)][U.sub.n](N)[X.sup.N] = [summation over (N[greater than or equal to]0)]a([m.sub.1]N, ..., [m.sub.k]N, N)[X.sup.N]. (3.12)

Consider now the algebraic, hence D-finite, series

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

where b([n.sub.1], ..., [n.sub.k], N) = a([m.sub.1][n.sub.1], ..., [m.sub.k][n.sub.k], N). Formula (3.12) shows that

[summation over (N[greater than or equal to]0)][U.sub.n](N)[X.sup.N] = [summation over (N[greater than or equal to]0)] b(N, ..., N, N)[X.sup.N]

which is a (full) diagonal of g([t.sub.1], ..., [t.sub.k], X). We conclude using the fact that any diagonal of a D- finite series is also D-finite, a result due to Lipshitz [Lipshitz(1988)]. The non algebraicity of [([U.sub.n](N)).sub.N[greater than or equal to]0], for each n > 2, follows from the fact that [phi](n) is even and the dominant term of the asymptotic formula contains [N.sup.-positive integer]. This is incoherent with Puiseux expansion around an algebraic singularity. []

A better control of the coefficients [b.sub.j,n] can be achieved by a smooth local change of variables, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. This is always possible by Morse Lemma [Morse(1925)]. The first terms of the asymptotic estimates of Theorem 3.2 are given in Table 4 for n = 1, ..., 20.

Corollary 3.3 If n is not a prime power, then [there exists][N.sub.0] = [N.sub.0](n) such that [U.sub.n](N) > 0 for N [greater than or equal to] [N.sub.0]. []

The sequences [([U.sub.n](N)).sub.N[greater than or equal to]0], n = 1, 2, ..., can be considered in a dual way: for each fixed N, one can consider the sequence [([U.sub.n](N)).sub.n[greater than or equal to]1] by reading each column of Table 3. The first five of these dual sequences, [([U.sub.n](0)).sub.n[greater than or equal to]1], ..., [([U.sub.n](1)).sub.n[greater than or equal to]1], [([U.sub.n](4)).sub.n[greater than or equal to]1], are P-recursive. The fifth one, [([U.sub.n](4)).sub.n[greater than or equal to]1], can be described as follows: [U.sub.n](4) = 3n(n - 1)[chi](2|n), where [chi](T(n)) = 1 if T(n) is true and 0 otherwise. This can be checked by noting that closed paths of length 4 whose steps are nth roots of unity are (possibly degenerated and non-convex) rhombuses. Following extensive computations we conjecture that [([U.sub.n](5)).sub.n[greater than or equal to]1] is also P-recursive and is of the form [U.sub.n](5) = 24n[chi](5|n) + 20n(n - 3)[chi](6|n). We leave open the problem of determining the values of N for which [([U.sub.n](N)).sub.n[greater than or equal to]1] is P- recursive.

Acknowledgements. The authors wish to thank B. Salvy for his assistance in the proof of the second part of Theorem 3.2, J. Tremblay for his LTeX / Maple help, and a referee for his constructive suggestions.

References

[De Bruijn(1981)] N. G. De Bruijn. Asymptotic methods in analysis. New York Dover Publications, 1981. ISBN 0486642216.

[Lipshitz(1988)] L. Lipshitz. The diagonal of a D-finite power series is D-finite. Journal of Algebra, 113: 373-378, 1988.

[Morse(1925)] M. Morse. Relations between the critical points of a real function of n independent variables. Trans. Amer. Math. Soc., 27:345-396, 1925.

[Salvy and Zimmermann(1994)] B. Salvy and P. Zimmermann. Gfun: a Maple package for the manipulation of generating and holonomic functions in one variable. ACM Transactions on Mathematical Software, 20(2):163-177, 1994.

[Sloane(2010)] N. J. A. Sloane. The On-Line Encyclopedia of Integer Sequences. Enlarged edition, 2010. Published electronically at http://oeis.org/classic/index.html.

[Stanley(1980)] R. P. Stanley. Differentiably finite power series. Europ. J. Combinatorics, 1:175-188, 1980.

Gilbert Labelle (1) and Annie Lacasse (2)

(1) LaCIM et Dep. de Mathematiques, UQAM, Montreal, Quebec, Canada

(2) LIRMM, Montpellier, France
Tab. 1: The linear combinations ([l.sub.k] [([??])).sub.o[less than or
equal to]k[less than or equal to][phi](n)-1] for admissibility, n = 1,
..., 20.

n     Linear combinations for admissibility

1     [[m.sub.0]]

2     [[m.sub.0] - [m.sub.1]]

3     [[m.sub.0] - [m.sub.2], [m.sub.1] - mi]]

4     [[m.sub.0] - [m.sub.2], [m.sub.1] - m3]]

5     [[m.sub.0] - [m.sub.4], [m.sub.1] - [m.sub.4], [m.sub.2] -
      [m.sub.4], [m.sub.3] - [m.sub.4]]

6     [[m.sub.0] - [m.sub.2] - [m.sub.3] + [m.sub.5], [m.sub.1] +
      [m.sub.2] - [m.sub.4] - [m.sub.5]]

7     [[m.sub.0] - [m.sub.6], [m.sub.1] - [m.sub.6], [m.sub.2] -
      [m.sub.6], [m.sub.3] - [m.sub.6], [m.sub.4] - [m.sub.6],
      [m.sub.5] - [m.sub.6]]

8     [[m.sub.0] - [m.sub.4], [m.sub.1] - [m.sub.5], [m.sub.2] -
      [m.sub.6], [m.sub.3] - [m.sub.7]]

9     [[m.sub.0] - [m.sub.6], [m.sub.1] - [m.sub.7], [m.sub.2] -
      [m.sub.6], [m.sub.3] - [m.sub.6], [m.sub.4] - [m.sub.7],
      [m.sub.5] - [m.sub.8]]

10    [[m.sub.0] - [m.sub.4] - [m.sub.5] + [m.sub.9], [m.sub.1] +
      [m.sub.4] - [m.sub.6] - [m.sub.9], [m.sub.2] - [m.sub.4] -
      [m.sub.7] + [m.sub.9], [m.sub.3] + [m.sub.4] - [m.sub.8] -
      [m.sub.9]]

11    [[m.sub.0] - [m.sub.10], [m.sub.1] - [m.sub.10], [m.sub.2] -
      [m.sub.10], [m.sub.3] - [m.sub.10], [m.sub.4] - [m.sub.10],
      [m.sub.5] - [m.sub.10], [m.sub.6] - [m.sub.10], [m.sub.7] -
      [m.sub.10], [m.sub.81] - [m.sub.10], [m.sub.9] - [m.sub.10]]

12    [[m.sub.0] - [m.sub.4] - [m.sub.6] + [m.sub.10], [m.sub.1] -
      [m.sub.5] - [m.sub.7] + [m.sub.11], [m.sub.2] + [m.sub.4] -
      [m.sub.8] - [m.sub.10], [m.sub.3] + [m.sub.5] - [m.sub.9] -
      [m.sub.11]

13    [[m.sub.0] - [m.sub.12], [m.sub.1] - [m.sub.12], [m.sub.2] -
      [m.sub.12], [m.sub.3] - [m.sub.12], [m.sub.4] - [m.sub.12],
      [m.sub.5] - [m.sub.12], [m.sub.6] - [m.sub.12], [m.sub.7] -
      [m.sub.12], [m.sub.8] - [m.sub.12], [m.sub.9] - [m.sub.12],
      [m.sub.10] - [m.sub.12], [m.sub.11] - [m.sub.12]]

14    [[m.sub.0] - [m.sub.6] - [m.sub.7] + [m.sub.13], [m.sub.1] +
      [m.sub.6] - [m.sub.8] - [m.sub.13], [m.sub.2] - [m.sub.6] -
      [m.sub.9] + [m.sub.13], [m.sub.3] + [m.sub.6] - [m.sub.10] -
      [m.sub.13], [m.sub.4] - [m.sub.6] - [m.sub.11] + [m.sub.13],
      [m.sub.5] + [m.sub.6] - [m.sub.12] - [m.sub.13]]

15    [[m.sub.0] - [m.sub.8] - [m.sub.9] - [m.sub.10] + [m.sub.13] +
      [m.sub.14], [m.sub.1] + [m.sub.8] - [m.sub.11] - [m.sub.13],
      [m.sub.2] + [m.sub.9] - [m.sub.12] - [m.sub.14], [m.sub.3] -
      [m.sub.8] - [m.sub.9] + [m.sub.14], [m.sub.4] + [m.sub.8] -
      [m.sub.13] - [m.sub.14], [m.sub.5] - [m.sub.8] - [m.sub.10] +
      [m.sub.13], [m.sub.6] - [m.sub.9] - [m.sub.11] + [m.sub.14],
      [m.sub.7] + [m.sub.8] + [m.sub.9] - [m.sub.12] - [m.sub.13] -
      [m.sub.14]]

16    [[m.sub.0] - [m.sub.8], [m.sub.1] - [m.sub.9], [m.sub.2] -
      [m.sub.10], [m.sub.3] - [m.sub.11], [m.sub.4] - [m.sub.12],
      [m.sub.5] - [m.sub.13], [m.sub.6] - [m.sub.14], [m.sub.7] -
      [m.sub.15]]

17    [[m.sub.0] - [m.sub.16], [m.sub.1] - [m.sub.16], [m.sub.2] -
      [m.sub.16], [m.sub.3] - [m.sub.16], [m.sub.4] - [m.sub.16],
      [m.sub.5] - [m.sub.16], [m.sub.6] - [m.sub.16], [m.sub.7] -
      [m.sub.16], [m.sub.8] - [m.sub.16], [m.sub.9] - [m.sub.16],
      [m.sub.10] - [m.sub.16], [m.sub.11] - [m.sub.16], [m.sub.12] -
      [m.sub.16], [m.sub.13] - [m.sub.16], [m.sub.14] - [m.sub.16],
      [m.sub.15] - [m.sub.16]]

18    [[m.sub.0] - [m.sub.6] - [m.sub.9] + [m.sub.15], [m.sub.1] -
      [m.sub.7] - [m.sub.10] + [m.sub.16], [m.sub.2] - [m.sub.8] -
      [m.sub.11] + [m.sub.17], [m.sub.3] + [m.sub.6] - [m.sub.12] -
      [m.sub.15], [m.sub.4] + [m.sub.7] - [m.sub.13] - [m.sub.16],
      [m.sub.5] + [m.sub.8] - [m.sub.14] - [m.sub.17]]

19    [[m.sub.0] - [m.sub.18], [m.sub.1] - [m.sub.18], [m.sub.2] -
      [m.sub.18], [m.sub.3] - [m.sub.18], [m.sub.4] - [m.sub.18],
      [m.sub.5] - [m.sub.18], [m.sub.6] - [m.sub.18], [m.sub.7] -
      [m.sub.18], [m.sub.8] - [m.sub.18], [m.sub.9] - [m.sub.18],
      [m.sub.10] - [m.sub.18], [m.sub.11] - [m.sub.18], [m.sub.12] -
      [m.sub.18], [m.sub.13] - [m.sub.18], [m.sub.14] - [m.sub.18],
      [m.sub.15] - [m.sub.18], [m.sub.16] - [m.sub.18], [m.sub.17] -
      [m.sub.18]]

20    [[m.sub.0] - [m.sub.8] - [m.sub.10] + [m.sub.18], [m.sub.1] -
      [m.sub.9] - [m.sub.11] + [m.sub.19], [m.sub.2] + [m.sub.8] -
      [m.sub.12] - [m.sub.18], [m.sub.3] + [m.sub.9] - [m.sub.13] -
      [m.sub.19], [m.sub.14] - [m.sub.8] - [m.sub.14] + [m.sub.18],
      [m.sub.5] - [m.sub.9] - [m.sub.15] + [m.sub.19], [m.sub.6] +
      [m.sub.8] - [m.sub.16] - [m.sub.18], [m.sub.7] + [m.sub.9] -
      [m.sub.17] - [m.sub.19]]

Tab. 2: The Laurent polynomials [[LAMBDA].sub.n] for n = 1, ..., 20.

n     [[lambda].sub.n]([t.sub.1], ..., [t.sub.[phi]](n) )

1     [t.sub.1]

2     ([t.sub.1] + [t.sub.1.sup.-1])

3     ([t.sub.1] + [t.sub.2] + 1/[t.sub.1][t.sub.2])

4     ([t.sub.1] + [t.sub.2] + [t.sub.1.sup.-1] + [t.sub.2.sup.-1])

5     [t.sub.1] + [t.sub.2] + [t.sub.3] + [t.sub.4] +
      1/[t.sub.1][t.sub.2][t.sub.3][t.sub.4])

6     ([t.sub.1] + [t.sub.2] + [t.sub.1]/[t.sub.2] +
      [t.sub.2]/[t.sub.1] + [t.sub.1.sup.-1] + [t.sub.2.sup.-1])

7     ([t.sub.1] + [t.sub.2] + [t.sub.3] + [t.sub.4] + [t.sub.5] +
      [t.sub.6] +
      1/[t.sub.1][t.sub.2][t.sub.3][t.sub.4][t.sub.5][t.sub.6])

8     ([t.sub.1] + [t.sub.2] + [t.sub.3] + [t.sub.4] +
      [t.sub.1.sup.-1] + [t.sub.2.sup.-1] + [t.sub.3.sup.-1] +
      [t.sub.4.sup.-1])

9     ([t.sub.1] + [t.sub.2] + [t.sub.3] + [t.sub.4] + [t.sub.5] +
      [t.sub.6] + 1/[t.sub.1][t.sub.4] + 1/[t.sub.2][t.sub.5] +
      1/[t.sub.3][t.sub.6])

10    ([t.sub.1] + [t.sub.2] + [t.sub.3] + [t.sub.4] +
      [t.sub.1][t.sub.3]/[t.sub.2][t.sub.4] +
      [t.sub.2][t.sub.4]/[t.sub.1][t.sub.3] + [t.sub.1.sup.-1] +
      [t.sub.2.sup.-1] + [t.sub.3.sup.-1] + [t.sub.4.sup.-1])

11    ([t.sub.1] + [t.sub.2] + [t.sub.3] + [t.sub.4] + [t.sub.1] +
      [t.sub.6] + [t.sub.7] + [t.sub.8] + [t.sub.9] + [t.sub.10] + 1/
      [t.sub.1][t.sub.2][t.sub.3][t.sub.4][t.sub.5][t.sub.6][t.sub.7]
      [t.sub.8][t.sub.9][t.sub.10])

12    ([t.sub.1] + [t.sub.2] + [t.sub.3] + [t.sub.4] +
      [t.sub.1]/[t.sub.3] + [t.sub.3]/[t.sub.1] + [t.sub.2]/[t.sub.4]
      + [t.sub.4]/[t.sub.2] + [t.sub.1.sup.-1] + [t.sub.2.sup.-1] +
      [t.sub.1.sup.-1] + [t.sub.4.sup.-1)

13    ([t.sub.1] + [t.sub.2] + [t.sub.3] + [t.sub.4] + [t.sub.5] +
      [t.sub.6] + [t.sub.7] + [t.sub.8] + [t.sub.9] + [t.sub.10] +
      [t.sub.11] + [t.sub.12] + 1/[t.sub.1][t.sub.2][t.sub.3][t.sub.4]
      [t.sub.5][t.sub.6][t.sub.7][t.sub.8][t.sub.9][t.sub.10]
      [t.sub.11][t.sub.12])

14    ([t.sub.1] + [t.sub.2] + [t.sub.3] + [t.sub.4] + [t.sub.5] +
      [t.sub.6] + [t.sub.7] + [t.sub.8] +
      [t.sub.1][t.sub.4][t.sub.7]/[t.sub.3][t.sub.6][t.sub.8] +
      [t.sub.2][t.sub.5][t.sub.8]/[t.sub.1][t.sub.4][t.sub.6] +
      [t.sub.1][t.sub.6]/[t.sub.2][t.sub.5][t.sub.8] +
      [t.sub.3][t.sub.8]/[t.sub.1][t.sub.4][t.sub.7] +
      1/[t.sub.1][t.sub.6] + 1[t.sub.2][t.sub.7] +
      1/[t.sub.3][t.sub.8])

15    (+ [t.sub.1] + [t.sub.2] + [t.sub.3] + [t.sub.4] + [t.sub.5] +
      [t.sub.6] + [t.sub.7] + [t.sub.8] + [t.sub.1][t.sub.4][t.sub.7]/
      [t.sub.3][t.sub.5][t.sub.7] + [t.sub.2][t.sub.5][t.sub.8]/
      [t.sub.1][t.sub.4][t.sub.6] + [t.sub.1][t.sub.6]/
      [t.sub.2][t.sub.5][t.sub.8] + [t.sub.3][t.sub.8]/
      [t.sub.1][t.sub.4][t.sub.7] + 1/[t.sub.1][t.sub.6] +
      1[t.sub.2][t.sub.7] + 1/[t.sub.3][t.sub.8])

16    ([t.sub.1] + [t.sub.2] + [t.sub.3] + [t.sub.4] + [t.sub.5] +
      [t.sub.6] + [t.sub.7] + [t.sub.8] + [t.sub.1.sup.-1] +
      [t.sub.2.sup.-1] + [t.sub.3.sup.-1] + [t.sub.4.sup.-1] +
      [t.sub.5.sup.-1] + [t.sub.6.sup.-1] + [t.sub.7.sup.-1] +
      [t.sub.8.sup.-1])

17    ([t.sub.1] + [t.sub.2] + ... + [t.sub.16] 1/[t.sub.1][t.sub.2]
      [t.sub.3][t.sub.4][t.sub.5][t.sub.6][t.sub.7][t.sub.8][t.sub.9]
      [t.sub.10][t.sub.11][t.sub.12][t.sub.13][t.sub.14][t.sub.15]
      [t.sub.16]

18    ([t.sub.1] + [t.sub.2] + [t.sub.3] + [t.sub.4] + [t.sub.5] +
      [t.sub.6] + [t.sub.1]-[t.sub.4] + [t.sub.4]-[t.sub.1] +
      [t.sub.2]-[t.sub.5] + [t.sub.5]-[t.sub.2] + [t.sub.3]-[t.sub.6]
      + [t.sub.6]-[t.sub.3] + [t.sub.1.sup.-1] + [t.sub.2.sup.-1] +
      [t.sub.3.sup.-1] + [t.sub.4.sup.-1] + [t.sub.5.sup.-1] +
      [t.sub.6.sup.-1])

19    ([t.sub.1] + [t.sub.2] + ... + [t.sub.18] + 1/[t.sub.1]
      [t.sub.2][t.sub.3][t.sub.4][t.sub.5][t.sub.6][t.sub.7][t.sub.8]
      [t.sub.9][t.sub.10][t.sub.11][t.sub.12][t.sub.13][t.sub.14]
      [t.sub.15][t.sub.16][t.sub.17][t.sub.18]

20    ([t.sub.1] + [t.sub.2] + ... + [t.sub.8] + [t.sub.1][t.sub.5]-
      [t.sub.3][t.sub.7] + [t.sub.3][t.sub.7]-[t.sub.1][t.sub.5] +
      [t.sub.2][t.sub.6]-[t.sub.4][t.sub.8] + [t.sub.4][t.sub.8]-
      [t.sub.2][t.sub.6] + [t.sub.1.sup.-1] + [t.sub.2.sup.-1] +
      [t.sub.3.sup.-1] + [t.sub.4.sup.-1] + [t.sub.5.sup.-1] +
      [t.sub.6.sup.-1] + [t.sub.7.sup.-1] + [t.sub.8.sup.-1])

Tab. 3: The sequences ([U.sub.n][(N)).sub.0[less than or equal
to]N[less than or equal to]20] for n = 1, ..., 20.

n     Un(N), N = 0, ..., 20

1     1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0

2     1, 0, 2, 0, 6, 0, 20, 0, 70, 0, 252, 0, 924, 0, 3432, 0, 12870,
      0, 48620, 0, 184756

3     1, 0, 0, 6, 0, 0, 90, 0, 0, 1680, 0, 0, 34650, 0, 0, 756756, 0,
      0, 17153136, 0, 0

4     1, 0, 4, 0, 36, 0, 400, 0, 4900, 0, 63504, 0, 853776, 0,
      11778624, 0, 165636900, 0, 2363904400, 0, 34134779536

5     1, 0, 0, 0, 0, 120, 0, 0, 0, 0, 113400, 0, 0, 0, 0, 168168000,
      0, 0, 0, 0, 305540235000

6     1, 0, 6, 12, 90, 360, 2040, 10080, 54810, 290640, 1588356,
      8676360, 47977776, 266378112, 1488801600, 8355739392,
      47104393050, 266482019232, 1512589408044, 8610448069080,
      49144928795820

7     1, 0, 0, 0, 0, 0, 0, 5040, 0, 0, 0, 0, 0, 0, 681080400, 0, 0, 0,
      0, 0, 0

8     1, 0, 8, 0, 168, 0, 5120, 0, 190120, 0, 7939008, 0, 357713664,
      0, 16993726464, 0, 839358285480, 0,  42714450658880, 0,
      2225741588095168

9     1, 0, 0, 18, 0, 0, 2430, 0, 0, 640080, 0, 0, 215488350, 0, 0,
      84569753268, 0, 0, 36905812607664, 0, 0

10    1, 0, 10, 0, 270, 240, 10900, 25200, 551950, 2116800, 32458860,
      169092000, 2120787900, 13427013600 149506414200, 1075081207200,
      11143223412750, 87198375264000, 865743970019500,
      7171730187336000,  69416724049550020

11    1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 39916800, 0, 0, 0, 0, 0, 0, 0,
      0, 0

12    1, 0, 12, 24, 396, 2160, 23160, 186480, 1845900, 17213280,
      171575712, 1703560320, 17365421304,  178323713568,
      1856554560432, 19487791106784, 206411964321420,
      2201711191213248, 23642813637773616 255355132936441824,
      2772650461148938656

13    1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6227020800, 0, 0, 0, 0,
      0, 0, 0

14    1, 0, 14, 0, 546, 0, 32900, 10080, 2570050, 2540160, 238935564,
      465696000, 25142196156, 76886409600,  2900343069624,
      12211317518400, 359067702643650, 1915829643087360,
      47006105030584700,  300455419743198720, 6437718469449262996

15    1, 0, 0, 30, 0, 360, 7650, 0, 302400, 4544400, 11226600,
      324324000, 4310633250, 24324300000, 437404968000,
      5634178329780, 45972927000000, 697866761592000,
      8962716395833200, 88725951057744000,  1258898645656852200

16    1, 0, 16, 0, 720, 0, 50560, 0, 4649680, 0, 514031616, 0,
      64941883776, 0, 9071319628800, 0, 1369263687414480,  0,
      219705672931613440, 0, 37024402443528248320

17    1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
      355687428096000, 0, 0, 0

18    1, 0, 18, 36, 918, 5400, 82800, 801360, 10907190, 132053040,
      1802041668, 24199809480, 340640607384,  4834708246368,
      70229958125184, 1032223723667136, 15391538570569590,
      231935110984687968,  3531542904056225916, 54244559313713885688,
      839979883121036697468

19    1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
      121645100408832000, 0

20    1, 0, 20, 0, 1140, 480, 102800, 151200, 12310900, 38707200,
      1812247920, 9574488000, 313983978000,  2391608419200,
      62051403928800, 611744666332800, 13627749414064500,
      160896284989440000,  3253345101771050000, 43527416858084016000,
      829176006298475046640

Tab. 4: Asymptotic estimates of [U.sub.n](N) as N [right arrow]
[infinity], for n [equivalent to] 1, ..., 20.

 n         Asymptotic estimate of [U.sub.n](N) as N [right arrow]
                                 [infinity]

 1    0

 2    [square root of 2]/[square root of [pi]] x [2.sup.N]/[square
      root of N] (1 - 1/4N + 1/32[N.sup.2] + O(1/[N.sup.3]))

 3    3[square root of 3]/2[pi] x [3.sup.N]/N (1 - 2/3N + 2/9[N.sup.2]
      + O(1/[N.sup.3]))

 4    2/[pi] x [3.sup.N]/N (1 - 1/2N + 1/8[N.sup.2] + O(1/[N.sup.3]))

 5    25[square root of 5]/4[[pi].sup.2] x [4.sup.N]/N (1 - 1/2N + 2/
      9[N.sup.2] + O(1/[N.sup.3]))

 6    [square root of 3]/2[pi] x [6.sup.N]/N (1 - 1/2N + 1/12[N.sup.2]
      + O(1/[N.sup.3]))

 7    343[square root of 7]/8[[pi].sup.3] x [7.sup.N]/[N.sup.3]
      (1 - 4/N + 8/[N.sup.2] + O(1/[N.sup.3]))

 8    8/[[pi].sup.2] x [8.sup.N]/[N.sup.2] (1 - 1/N + 1/[N.sup.2] +
      O(1/[N.sup.3]))

 9    243[square root of 3]/8[[pi].sup.3] x [9.sup.N]/[N.sup.3]
      (1 - 3/N + 4/[N.sup.2] + O(1/[N.sup.3]))

10    5[square root of 5]/4[[pi].sup.2] x [10.sup.N]/[N.sup.2]
      (1 - 1/N + 3/4[N.sup.2] + O(1/[N.sup.3]))

11    161051[square root of 11]/32[[pi].sup.5] x [11.sup.N]/[N.sup.5]
      (1 - 10/N + 50/[N.sup.2] + O(1/[N.sup.3]))

12    3/[[pi].sup.2] x [12.sup.N]/[N.sup.2] (1 - 1/N + 2/3[N.sup.2] +
      O(1/[N.sup.3]))

13    4826809[square root of 13]/64[[pi].sup.6] x [13.sup.N]/
      [N.sup.6] (1 - 14/N + 98/[N.sup.2] + O(1/[N.sup.3]))

14    49[square root of 7]/8[[pi].sup.3] x [14.sup.N]/[N.sup.3]
      (1 - 14/N + 98/[N.sup.2] + O(1/[N.sup.3]))

15    1125/[[pi].sup.4] x [16.sup.N]/[N.sup.4] (1 - 2/N + 9/[N.sup.2]
      + O(1/[N.sup.3]))

16    512/[[pi].sup.4] x [16.sup.N]/[N.sup.4] (1 - 2/N + 9/[N.sup.2]
      + O(1/[N.sup.3]))

17    6975757441[square root of 17]/256[[pi].sup.8] x [17.sup.N]/
      [N.sup.8] (1 - 24/N + 288/[N.sup.2] + O(1/[N.sup.3]))

18    81[square root of 3]/8[[pi].sup.3] x [18.sup.N]/[N.sup.3]
      (1 - 3/2N + 5/2[N.sup.2] + O(1/[N.sup.3]))

19    322687697779[square root of 19]/512[[pi].sup.9] x [19.sup.N]/
      [N.sup.9] (1 - 30/N + 450/[N.sup.2] + O(1/[N.sup.3]))

20    125/[[pi].sup.4] x [20.sup.N]/[N.sup.4] (1 - 2/N + 7/[N.sup.2]
      + O(1/[N.sup.3]))

 n           Extra condition

 1                 NIL

 2     N [equivalent to] 0 (mod 2)

 3     N [equivalent to] 0 (mod 3)

 4     N [equivalent to] 0 (mod 2)

 5     N [equivalent to] 0 (mod 5)

 6                 NIL

 7     N [equivalent to] 0 (mod 7)

 8     N [equivalent to] 0 (mod 2)

 9     N [equivalent to] 0 (mod 3)

10                 NIL

11    N [equivalent to] 0 (mod 11)

12                 NIL

13    N [equivalent to] 0 (mod 13)

14                 NIL

15                 NIL

16     N [equivalent to] 0 (mod 2)

17    N [equivalent to] 0 (mod 17)

18                 NIL

19    N [equivalent to] 0 (mod 19)

20                 NIL
COPYRIGHT 2011 DMTCS
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2011 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Labelle, Gilbert; Lacasse, Annie
Publication:DMTCS Proceedings
Article Type:Report
Geographic Code:1CANA
Date:Jan 1, 2011
Words:7679
Previous Article:Skew quantum Murnaghan-Nakayama rule.
Next Article:Minkowski decompositions of associahedra.
Topics:

Terms of use | Privacy policy | Copyright © 2020 Farlex, Inc. | Feedback | For webmasters