advertisement

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 7 (2007), #A25 COMPUTATION OF q-PARTIAL FRACTIONS Augustine O. Munagi The John Knopfmacher Centre for Applicable Analysis and Number Theory, University of the Witwatersrand, Johannesburg 2050, South Africa munagi@maths.wits.ac.za Received: 8/2/06, Revised: 1/18/07, Accepted: 4/24/07, Published: 5/14/07 Abstract We study a special partial fraction technique which is designed for rational functions with poles on the unit circle, known as q-fractions. Even though the theory of q-partial fractions has already been applied to the Rademacher Conjecture, no systematic computational development appeared. In this paper we present two algorithms for the computation of q-partial fractions and highlight certain predictable coefficients which arise from the symmetry of the decompositions. We also examine the q-partial fraction content of reciprocals of the cyclotomic polynomials, and indicate how the technique can be used to facilitate the extraction of enumeration formulas from certain power series generating functions. 1. Introduction The methods to be discussed in this paper have their genesis in the work of P.A. MacMahon who views his work as an extension of that of A. Cayley. The motivation was the need to devise efficient closed forms for the numbers p(n, m) of the partitions of a positive integer n into at most m parts for small m, the generating function of which is given by a(m, q) = 1 , m ≥ 0, |q| < 1. (1 − q)(1 − q 2 ) · · · (1 − q m ) In the present context the first complete examples of q-partial fraction decompositions are the following expansions given by Cayley [8] and MacMahon [12, p. 63], respectively: ∞ ! n=0 ∞ ! n=0 p(n, 2)q n = a(2, q) = 1/2 1/2 + 2 (1 − q) 1 − q2 p(n, 3)q n = a(3, q) = 1/4 1/6 1/4 1/3 + + + . (1 − q)2 (1 − q)3 1 − q 2 1 − q 3 (1.1) INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 7 (2007), #A25 2 MacMahon observed that (1.1) resulted in simpler formulas for the functions p(n, 2) and p(n, 3) than the following decompositions recommended by Cayley: 1 (1 − q) 1/4 1/2 4 + + 2 (1 − q) (1 − q) 1 − q2 1 (1 − q) 1/4 17/72 1/6 8 + a(3, q) = + + + 1−q (1 − q)2 (1 − q)3 1 − q2 a(2, q) = 1 2 (q 9 + q − 2) . 1 − q3 (1.2) Indeed, by comparing the coefficients of q n on both sides of each identity, after each summand on the right side is expanded as a power series about q = 0, the identities in (1.1) give 1 1 (n + 1) + (1, 0)cr2n , 2 2 1 1 1 (n + 1)(n + 5) + (1, 0)cr2n + (1, 0, 0)cr3n , p(n, 3) = 12 4 3 p(n, 2) = (1.3) while the identities in (1.2) lead to 1 3 1 n + + (1, −1)pcr2n , 2 " 4 4 # 1 47 1 1 2 n + 6n + + (1, −1)pcr2n + (2, −1, −1)pcr3n , p(n, 3) = 12 6 8 9 p(n, 2) = (1.4) where (A0 , A1 , . . . , AM −1 )crMn is the so-called circulator (or circulant) of period M and represents the general coefficient in the$power series expansion about q = 0 of the periodic function (A0 + A1 q + · · · + AM −1 q M −1 ) (1 − q M ). It is defined by (A0 , A1 , . . . , AM −1 )crMn = Ar if n ≡ r(mod M ), 0 ≤ r ≤ M − 1 Cayley’s formulas (1.4) contain the prime circulator (A0 , A1 , . . . , AM −1 )pcrMn which is a circulator subject to the additional conditions Ac + Ac+s + Ac+2s + · · · + Ac+(b−1)s = 0, 0 ≤ c ≤ s − 1, for every factorization of M into two factors M = sb, with b > 1. The immediate advantage of the circulator notation is the elimination of complex and irrational quantities from partition formulas [2, 10]. The q-partial fraction technique is specially designed for handling rational functions whose poles consist of roots of unity, i.e., functions of the type: A(q) = (1 − q n1 )s1 (1 f (q) , − q n2 )s2 · · · (1 − q nr )sr |q| < 1, where the nj and sj are positive integers, 1 ≤ j ≤ r, r > 0, and degree(f )< %r i=1 n i si . These are the q-fractions. Generally, the q-fractions consist of proper rational functions over the field Q of rational numbers in which the denominators can be factored into products of cyclotomic polynomials. INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 7 (2007), #A25 3 Most rational generating functions encountered in Combinatorics and q-Theory are sums and products of q-fractions [1, 3, 4, 7, 9]. Recall that the nth cyclotomic polynomial [16] for a positive integer n is defined by & Φn (q) = (q d − 1)µ(n/d) , (1.5) d|n where µ(n) denotes the Möbius function. It is well-known that the prime circulators appearing in formulas belonging to the class of those in (1.4) are uniquely determined following the uniqueness of the Cayley-type partial fractions. The algorithm for the latter essentially contains two simple steps: Cayley: Step 1: Obtain the ' (k decomposition of the q-fraction into ordinary partial fractions over Q, say Σfi (q)/ Φi (q) ; ' (k Step 2: Translate each summand fi (q)/ Φi (q) into an equivalent function with denominator of the form (1 − q n )s , by multiplying the numerator and denominator with the com' (k plementary polynomial (1 − q i )s / Φi (q) . On the other hand, Gupta, et al [10, p. xxv] observed that formulas in the class of those in (1.3), which bear the simplest forms of the circulators, could in general only be found by trial-and-error transformations of partial fractions, when possible. Thus they suggested the problem of discovering a systematic method for the prescribed partial fractions. The theory of q-partial fractions, which has already appeared in [13], provides a solution to this problem. The primary motivation for the theory there is demonstrated in the application to the proof of a restricted case of the Rademacher Conjecture [15, p. 302], [2]. While reviewing literature afterwards we found that the technique also addressed the formula problem of Gupta and his collaborators. We show below (Section 4) that q-partial fractions also provide a natural platform for the elimination of the circulators in favour of binomial coefficients. It is then immediate to write down formulas such as ) " " " " # # # #* 25 n + 2 1 n+2 1 n+3 1 n2 + 1 p(n, 4) = + + + ; (1.6) 1 2 3 144 8 24 8 1 # " # " # " # ) " 31 n + 2 1 n+3 1 n+4 11 n + 2 + + + p(n, 5) = 64 1 288 2 24 3 120 4 "n #* 1 2 +1 + , (1.7) 16 1 ' ( where %N & is the nearest integer to N and Nj = 0 if N is not an integer. These formulas should be compared with other representations given in [2, 6, 8, 10]. INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 7 (2007), #A25 4 The aim of this paper is to present certain algorithms for the computation of q-partial fractions together with some special features of the decompositions in order to bring the technique to the knowledge of a broader audience. The rest of the paper is organized as follows. Section 2 recaps the fundamental theory, and Section 3 is devoted to the description of two algorithms for computing q-partial fractions. Section 4 deals with an application of the technique to the extraction of general coefficients of certain power series. In Section 5 we examine the q-partial fraction content of reciprocals of the cyclotomic polynomials. Lastly, Section 6 profiles a few predictable coefficients in the decomposition of certain q-fractions. 2. The Basic Representation Theorem The key departure of q-partial fractions from the Cayley-type partial fractions is the stipulation that for a summand v(q)/(1 − q n )s to be admissible, the degree of v(q) must be less than Euler’s totient function φ(n), rather than the standard requirement that the degree of v(q) be less than ns. Definition 2.1 The q-fraction v(q)/(1 − q n )s is called basic if it satisfies degree(v) < φ(n). Definition 2.2 The q-partial fraction decomposition of the q-fraction A(q) is a representation of A(q) as a finite sum of basic q-fractions with distinct denominators. Theorem 2.3 For any specified q-fraction, the representation asserted in Definition 2.2 exists, and is unique up to the order of the summands. Sketch of Proof. We sketch a constructive proof of the theorem by writing the general qfraction A(q) as a sum of basic q-partial fractions. (A non-constructive proof of Theorem 2.3 is given in [13].) We work throughout in the rational field Q. First obtain the ordinary partial fraction decomposition $' (k A(q) = Σfi (q) Φi (q) i (2.1) where deg(fi ) < φ(i) for each i, ki > 0. $' (k Express each summand fi (q) Φi (q) i as a sum of basic q-fractions, by first multiplying (k $' the numerator and denominator by the factor vi (q) = (1 − q i )ki Φi (q) i to get + , fi (q) 1 vi (q)fi (q) vi (q)fi (q) . ( ki = ( ki = ' ' vi (q) (1 − q i )ki Φi (q) Φi (q) If degree(vi fi ) < φ(i) in the third expression, then we have a single basic q-fraction. Other- INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 7 (2007), #A25 5 wise decompose the parenthesized function in the middle into ordinary partial fractions, + k , ki i ! ! fi (q) 1 rj (q) rj (q) r0 (q) + (2.2) ( ki = (ki −j = ' ( ' ' i k vi (q) j=0 Φi (q) (1 − q ) i j=1 vi (q) Φi (q) ki −j Φi (q) where degree(rj ) < φ(i). But the denominator of the general summand on the right side of (2.2) (except the first), need not be of the required form, and is therefore handled again like A(q), ab initio. This procedure is iteratively continued until we arrive at a single basic q-fraction, preceded by a sum of basic q-fractions with denominators (1 − q c )x such that 1 ≤ c ≤ i and 1 ≤ x ≤ ki . The process will terminate since both i and ki are finite. Thus it follows by mathematical induction on the number of distinct factors of (1 − q i )ki of the form (1 − q n )s that ! rj (q) fi (q) = , degree(rj ) < φ(d), c > 0; (2.3) (k ' d )c (1 − q Φi (q) i j d|i and, substituting (2.3) into (2.1), gives A(q) = % % i $ (1 − q d )c . j, d|i rj (q) Thus both the existence and uniqueness of the q-partial fraction decomposition follow from those of the corresponding ordinary partial fraction decomposition. ! 3. Algorithms for q-Partial Fractions We present two algorithms for computing q-partial fractions. The first (Iteratn) is directly prescribed by the proof of Theorem 2.3. The second (UndetCoef) is an adaptation of the familiar method of undetermined coefficients for obtaining ordinary partial fractions. 3.1 Iteratn Decompose the proper rational function f (q)/h(q) into q-partial fractions: (I) If f (q)/h(q) is not a q-fraction, then FAIL; (generally, test if h(q) factors into a product of cyclotomic polynomials). (II) Obtain the ordinary partial fraction decomposition of f (q)/h(q); (III) Transform each summand into a sum of basic q-fractions as explained in the proof of Theorem 2.3; (IV) Substitute into the original decomposition and combine like terms. Example We derive the second member of (1.1). The ordinary partial fraction decomposition is 1 (q + 2) 1/6 1/8 17/72 1/4 1 9 + + = + + . 2 3 2 3 2 (1 − q)(1 − q )(1 − q ) 1−q (q − 1) (1 − q) q+1 q +q+1 (3.1) INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 7 (2007), #A25 6 Transform each summand on the right into a sum of basic q-fractions (the first three fractions are already basic): " # 1 1 (1 − q) (1 − q) 1/8 1 1 1/4 8 8 = − =− = − + q+1 (1 + q)(1 − q) 1 − q2 1−q 8 1+q = 1/4 −1/8 , + 1 − q 1 − q2 1 (q + 2) 9 2 q +q+1 1 = 1−q " 1 1/3 − + 9 1 + q + q2 (3.2) # = 1/3 −1/9 + . 1 − q 1 − q3 (3.3) Substitute (3.2), (3.3) into (3.1) and add like terms to get the required decomposition: 1/4 1/6 1/4 1/3 1 = + + + . 2 3 2 3 2 (1 − q)(1 − q )(1 − q ) (1 − q) (1 − q) 1−q 1 − q3 3.2 UndetCoef Decompose the proper rational function f (q)/h(q) into q-partial fractions: (I) If f (q)/h(q) is not a q-fraction, then FAIL; (II) Re-write f (q)/h(q) as F (q)/H(q), if necessary, so that H(q) is a product of factors of the form (1 − q n )s only; (III) Obtain the q-factorization G(q) of H(q): the q-factorization of (1−q n1 )s1 (1−q n2 )s2 · · · (1− q nr )sr is obtained by replacing each factor 1 − q ni by (1 − q d ), where d|ni ; (IV) State the theoretical decomposition of f (q)/h(q), i.e., identify the given function with a sum of basic q-fractions with unknown polynomial coefficients fi (q) such that each factor (1 − q d )k of G(q) contributes the sum f1 (q)/(1 − q d ) + · · · + fk (q)/(1 − q d )k , where degree(fj ) < φ(d); (V) Clear fractions and compare coefficients of powers of q on both sides to determine unknown coefficients; (VI) Substitute into the theoretical decomposition in (IV). Example We decompose R(q) into q-partial fractions using UndetCoef . We have R(q) = 3q 8 + 5q 4 + 4q 2 − 2 . (1 − q 4 )(1 − q 5 ) The q-factorization of (1 − q 4 )(1 − q 5 ) is (1 − q)2 (1 − q 2 )(1 − q 4 )(1 − q 5 ). Thus we set C D + Eq F + Gq + Hq 2 + Jq 3 B A + + + . + R(q) = 1 − q (1 − q)2 1 − q 2 1 − q4 1 − q5 (3.4) (Note that each summand v(q)/(1 − q d )k on the right side satisfies degree(v) < φ(d).) It is a routine matter to clear fractions and compare coefficients of powers of q on both sides to obtain A = −3, B = 1/2, C = 5/2, D = 1, E = 1, F = −3, G = 1, H = 3, J = 1. INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 7 (2007), #A25 7 Then substitute for the coefficients in (3.4) to obtain the required decomposition: 5/2 1+q −3 + q + 3q 2 + q 3 −3 1/2 3q 8 + 5q 4 + 4q 2 − 2 + + + . = + (1 − q 4 )(1 − q 5 ) 1 − q (1 − q)2 1 − q 2 1 − q 4 1 − q5 Remarks. Iteratn is the algebraically more complicated of the two algorithms since it subsumes a full classical partial fraction algorithm over Q. Clearly the version of the latter which employs the Euclidean algorithm may not be adapted to q-partial fractions because the concept of relative primeness is irrelevant to q-factorization. The expansion of A(q) into q-partial fractions contains at most s1 τ (n1 ) + · · · + sr τ (nr ) summands, which is the same number as in the ordinary partial fraction algorithm, where τ (N ) is the number of positive divisors of N . In particular . m / the number of unknown coefficients % to be computed by UndetCoef for a(q) is 1≤k≤m k φ(k) = (m + 1)m/2, where 'N ( is the floor function. We deduce that the decomposition of A(q) into q-partial fractions is at worst as computationally costly as the ordinary partial fraction decomposition of A(q) over Q, using the corresponding versions of UndetCoef. The determination of the coefficients of basic q-fractions is much simplified by one or more of the following nice situations: • The q-factorization of the function 1 − q n is obviously easier than the ordinary factorization over the integers. • Certain coefficients are predictable (see Section 6). In particular the coefficient of the basic fraction 1/(1 − q) is mostly 0 (Theorem 6.1). • The denominators of basic q-fractions have larger degrees than those of ordinary partial fraction summands. So the clearing of fractions reduces the magnitude of coefficients of powers of q, thus simplifying the system of equations to be solved. 4. Application to Enumeration Formulas We give an illustration with a typical ordinary power series generating function. In this section and the next, the q-fraction 1/(1 − q n )s is also represented by Fns . Let T (n) denote the number of triangles with integer sides and perimeter n. Hirschhorn [11] derives the formula 0 2 %n /48& , if n is even (4.1) T (n) = %(n + 3)2 /48& , if n is odd where %N & is the nearest integer to N . INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 7 (2007), #A25 8 His method involves a combinatorial argument, followed by the application of the wellknown formula: p(n, 3) = %(n + 3)2 /12&. We give an alternative derivation of (4.1) from the generating function for T (n) ([5, p. 557]) via q-partial fractions. Consider the q-partial fraction expansion ∞ ! T (n)q n = q 3 F2 F3 F4 n=0 1 2 1 1 1 1 1 F1 + F13 + F2 − F22 + F3 − (1 + q)F4 . (4.2) 16 24 16 4 3 4 If we expand each summand on the right as a power series about q = 0, and then equate the coefficients of q n on both sides, we first obtain the exact formula 2 n2 + 6n + 5 1 1 n 1 T (n) = − + 1 (1, 0)cr2n + (1, 0)cr2n 48 4 2 16 1 1 + (1, 0, 0)cr3n − (1, 1, 0, 0)cr4n . (4.3) 3 4 Thus, if n is even we have = T (n) = n2 1 5 1 1 1 + − + + (1, 0, 0)cr3n − (1, 1, 0, 0)cr4n . 48 48 4 16 3 4 (4.4) But noticing that 3 3 3 3 35 3 1 3 35 1 1 1 1 1 1 1 3 − + 3 3 3 3 48 4 16 + 3 (1, 0, 0)cr3n − 4 (1, 1, 0)cr4n 3 ≤ 3 48 − 4 + 16 + 3 3 < 2 , we can subtract the terms before the first inequality from the right side of (4.4) to obtain the first part of (4.1). If n is odd then (4.3) becomes T (n) = and since N 2 + 6n + 5 1 1 + (1, 0, 0)cr3n − (1, 1, 0, 0)cr4n , 48 3 4 3 3 31 3 3 (1, 0, 0)cr3n − 1 (1, 1, 0, 0)cr4n 3 − 1 ≤ 1 − 1 < 1 , 33 3 12 4 3 12 2 we can subtract the terms before the first inequality from the right side to obtain the second part of (4.1). ! The simplicity of the coefficients of basic q-fractions makes it convenient to read off formulas directly from expansions. If the definition of the binomial coefficient is slightly adjusted to read, for a nonnegative integer K, " # 4 N! , if N is an integer and N ≥ K, N K!(N −K)! = 0, otherwise, K INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 7 (2007), #A25 9 then the circulator may be replaced by a sum of binomial coefficients: (A0 , . . . , AM −1 )crMn = M −1 ! k=0 Ak " n−k # M 0 . It is now routine to read off the following formula directly from (4.2): ) " # " # " #* 1 n+1 1 n+2 1 n2 + 1 T (n) = + − . 16 1 24 2 4 1 (4.5) Similarly, beginning with the decompositions, 25 2 1 3 1 1 1 1 1 F1 + F1 + F14 + F2 + F22 + (2 + q)F3 + F4 , 144 8 24 16 8 9 4 11 2 31 3 1 4 1 5 11 1 2 = F + F + F + F + F2 + F2 64 1 288 1 24 1 120 1 64 16 1 1 1 + (2 + q)F3 + (1 + q)F4 + F5 , 9 8 5 F1 F2 F3 F4 = F1 F2 F3 F4 F5 one reads off the formulas (1.6) and (1.7) respectively. Obviously such formulas for p(n, m) continue for larger m. To specify the above formulas, we note, for instance, the following version of (4.3) in which binomial coefficients correspond one-to-one with the summands in (4.2): # # # " " " # " " # 1 n+1 1 n3 1 n+2 1 n2 1 n2 + 1 T (n) = + + + − 1 16 1 24 2 16 0 4 3 0 "n# " n−1 # 1 4 1 4 − . − 4 0 4 0 Then (4.5) follows from the fact that 3 3 "n# " # " # " #3 3 3 31 31 1 n3 1 n4 1 n−1 1 33 1 2 4 3 3 3 3 16 0 + 3 0 − 4 0 − 4 0 3 ≤ 3 16 + 3 3 < 2 . 5. Reciprocals of Cyclotomic Polynomials In this section we find the q-partial fraction decomposition of the reciprocal of the cyclotomic polynomial (1.5) for some values of n. The factorization of q n − 1 over the integers q n − 1 = d|n Φd (q), gives the following recursion for the cyclotomic polynomials: Φ1 (q) = q − 1, Φn (q) = - qn − 1 , n ≥ 2. d|n, d<n Φd (q) INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 7 (2007), #A25 10 This in turn gives − 1 = Φn (q) - d|n, d<n Φd (q) , 1 − qn n ≥ 2. (5.1) ' (−1 Thus Φn (q) is equivalent to a standard q-fraction a single denominator factor. It ' with −1 follows that the q-partial fraction decomposition of Φn (q)) has exactly one summand if n < 2φ(n). Such q-partial fraction decompositions are called trivial and may be obtained by (−1 ' applying Cayley to Φn (q) . ' (−1 Clearly the decomposition of Φn (q) cannot be trivial if n is even. We observe that (−1 ' (−1 ' has nontrivial decompositon if and only if Φm (q) does, where m denotes the Φn (q) largest squarefree divisor of n. ' (−1 The next theorem determines all trivial q-partial fraction decompositions of Φn (q) when n is at most the product of powers of four distinct primes. The straightforward derivation is omitted. mr 1 m2 Theorem 5.1 Let N be an odd number with the factorization N = pm 1 p2 · · · pr into primes p' i , p1 <( p2 < · · · < pr , where mi ≥ 1, r ≥ 1. Then the q-partial fraction decomposition of −1 ΦN (q) is trivial only in the following cases, for 1 ≤ r ≤ 4: (i) r = 1, 2; (ii) r = 3, excluding all N determined by (p1 , p2 , p3 ) = (3, 5, 7), (3, 5, 11), (3, 5, 13); (iii) r = 4, excluding all N determined by members of the sets (a) {(3, 5, 7, p4 ) | p4 > 7}, {(3, 5, 11, p4 ) | p4 > 11}, {(3, 5, 13, p4 ) | p4 > 13}; (b) {(3, 5, 17, p4 ) | 19 ≤ p4 ≤ 251}, (c) {(3, 5, 19, p4 ) | 23 ≤ p4 ≤ 89}, (d) {(3, 5, 23, p4 ) | 29 ≤ p4 ≤ 47}, (e) {(3, 5, 29, 31)}, (f ) {(3, 7, 11, p4 ) | 13 ≤ p4 ≤ 23}, (g) {(3, 7, 13, 17)}. Theorem 5.2 Let k, m, n denote positive integers and let p, p1 , p2 be odd primes, p1 < p2 . The following q-partial fraction decompositions are valid. (i) (ii) ' ' (−1 = −F2k−1 + 2F2k . Φ2k (q) m−1 (−1 Φ2k pm (q) = (−F2k−1 pm + 2F2k pm ) Φ2k pi (q), i=0 p ≥ 5. INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 7 (2007), #A25 (iii) ' (−1 n (q) n + 2F2k pm pn ) Φ2k pm = (−F2k−1 pm 1 p2 1 p2 1 2 p1 ≥ 5. "n−1 i=0 11 , # +m−1 n - i (q) Φ2k pm Φ2k ps pj (q) , 1 p2 s=0 j=0 1 2 Proof. For (i), we apply Iteratn to get + , " # k−1 k−1 1 1 − q2 1 1 − q2 2 1 = = = −1 + . Φ2k (q) 1 − q 2k 1 − q 2k−1 1 + q 2k−1 1 − q 2k−1 1 + q 2k−1 1 2 −1 . = k−1 + 2 Φ2k (q) 1−q 1 − q 2k ' (−1 m−1 ' m (−1 For (ii), write Φ2k pm (q) = Φ2k (q p ) Φ2k (q p ) . Hence using part (i) we obtain (−1 ' m−1 = Φ2k (q p )(−F2k−1 pm + 2F2k pm ), which simplifies to the desired result. For Φ2k pm (q) ' m−1 ( the first summand to be basic, we need degree Φ2k (q p ) < φ(2k−1 pm ), or 2k−1 pm−1 < 2k−2 (p − 1)pm−1 , or p ≥ 5. Hence ! The proof of (iii) is analogous to that of part (ii). Remark The decomposition in Theorem 5.2 (ii) merely fails to hold in general when p = 3. ' (−1 (−1 For instance, it holds for Φ18 (q) , but fails for (Φ12 (q) (= −F2 +qF3 −qF6 +2Φ4 (q)F12 .) An analogous remark applies to Theorem 5.2 (iii). 6. Computation of Special Coefficients We highlight certain predictable coefficients in the q-partial fraction decompositions of A(q) and a(q). In the hope of extending the proof in [13], which is based on the coefficient of (1−q)−1 , we compute the coefficient of (1 − q)−2 in the q-partial fraction decomposition of f (q)/(1 − q n )s , when f (q) is a polynomial function of specified type. We will use the notation {g(q)}F (q) to denote the coefficient of the basic q-fraction g(q) in the q-partial fraction expansion of F (q). The following result is established in [13]. Theorem 6.1(Munagi [13]) r % n i si − 1 (−1)s1 +s2 +···+sr −1 lc(f ), if degree(f ) = −1 i=1 {(1 − q) }A(q) = r % 0, if degree(f ) < n i si − 1 i=1 where lc(f ) is the leading coefficient of f (q). 12 INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 7 (2007), #A25 Theorem 6.2 If r > 1, or r = 1 and n1 = 1, in A(q), then with the notation s = we have {(1 − q)−s }A(q) = f (1) . · · · nsrr %r i=1 si , ns11 ns22 Proof. For r > 0 let the theoretical decomposition of A(q) via UndetCoef be given by C1,s,0 C1,s−1,0 C1,1,0 f (q) ≡ + + ··· + s s 1 h(q) (1 − q) (1 − q) (1 − q) ! ! Cd,j,0 + Cd,j,1 q + · · · + Cd,j,φ(d)−1 q φ(d)−1 + , d )j (1 − q d≥2 j≥1 where h(q) = (1 − q n1 )s1 (1 − q n2 )s2 · · · (1 − q nr )sr . Multiply through with h(q) to obtain f (q) = C1,s,0 (1 + q + · · · + q n1 −1 )s1 (1 + q + · · · + q n2 −1 )s2 · · · (1 + q + · · · + q nr −1 )sr + (terms in (1 − q)). ! Setting q = 1 in the last expression proves the theorem. Corollary 6.3 Some coefficient formulas in the q-partial fraction decomposition of a(m, q): {(1 − q)−m } a(m, q) = 1/m!, m ≥ 1; : 9 (2) For each m > 2 there is a sequence of coefficients (1 − q)−(m−k) a(m, q), 1 ≤ k ≤ (, with the following initial terms. ' m−1 k (1) {(1 − q)−1 } a(m, q) = 1/m, (i) {(1 − q)−(m−1) }a(m, q) = 1 , m ≥ 3, 4(m − 2)! (ii) {(1 − q)−(m−2) }a(m, q) = 26 − 13m + 9m2 , 288(m − 2)! m ≥ 5, (iii) {(1 − q)−(m−3) }a(m, q) = 56 − 42m + 33m2 − 10m3 + 3m4 , 1152(m − 2)! m ≥ 7. Proof. The proofs follow from Theorem 6.2, and Cayley’s formula [4, p.81], given by ! 1 1 = 2 m p p p m 1 2 (1 − q)(1 − q ) · · · (1 − q ) 1 2 · · · m p1 !p2 ! · · · pm ! × 1 (1 − q)p1 (1 − q 2 )p2 · · · (1 − q m )pm (6.1) 13 INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 7 (2007), #A25 where the summation runs over all partitions (1p1 , 2p2 , 3p3 , . . . , mpm ) of m, with pj ≥ 0, 1 ≤ j ≤ m. First, evaluate the right side of (6.1) at the partitions (1m ) and (m1 ) to get, respectively, 1/m 1/m! and , (1 − q)m 1 − qm which, since they are basic q-fractions, prove part (1). For part (2), each {(1 − q)−m+k }a(m, q), k ≥ 1, receives contributions, via (6.1), from a finite set of partitons of m of the form (1−m+j π(j, c)>1 ), j ≥ 2, 1 ≤ c ≤ k (6.2) where π(j, c)>1 is a partition of j into c parts, each > 1. For fixed j, it follows that k = j − c. Hence, the total number of contributing partitions is exactly p(1) + p(2) + · · · + p(k), where p(N ) is the number of all partitions of N . A series of basic fractions generated by a partition can be obtained using (6.1) and Theorem 6.2. For example, evaluating the right side of (6.1) at (1m−2 2) gives Q(1m−2 2) = 1 ; 2(m − 2)!(1 − q)m−2 (1 − q 2 ) on applying Theorem 6.2 to 2(m − 2)!Q(1m−2 2) and subtracting, we obtain " # 1 1/2 1/2 m−2 2) = + . Q(1 2(m − 2)! (1 − q)m−1 (1 − q)m−3 (1 − q 2 ) Iterating this procedure, gives, after four steps, # " 1 1/4 1/8 1/16 1/2 m−2 2) = + + + + ··· Q(1 2(m − 2)! (1 − q)m−1 (1 − q)m−2 (1 − q)m−3 (1 − q)m−4 Similarly, # 1/3 2/9 1/9 1/3 + + + + ··· Q(1 (1 − q)m−2 (1 − q)m−3 (1 − q)m−4 (1 − q)m−5 " # 1/4 1 1/4 3/16 1/8 m−4 2 2 )= + + + + ··· Q(1 8(m − 4)! (1 − q)m−2 (1 − q)m−3 (1 − q)m−4 (1 − q)m−5 " # 1/4 1 3/8 5/16 5/32 m−4 4) = + + + + ··· Q(1 4(m − 4)! (1 − q)m−3 (1 − q)m−4 (1 − q)m−5 (1 − q)m−2 m−3 1 3) = 3(m − 3)! " Thus part 2(i) is given by the first term of Q(1m−2 2), and 2(ii) by the sum of coefficients of terms from Q(1m−2 2), Q(1m−3 3), and Q(1m−4 22 ), that is, 9 : (1 − q)−(m−2) a(m, q) = 1/4 1/3 1/4 26 − 13m + 9m2 + + = , 2(m − 2)! 3(m − 3)! 8(m − 4)! 288(m − 2)! INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 7 (2007), #A25 14 and so forth. Finally, note that (6.2) implies m > j = k + c, which implies that m > 2k, for fixed m. So the degree of the polynomial numerator of each coefficient is (2k − 1) − 2 + 1 = 2(k − 1). ! Theorem 6.4 For m > 0, let b0 + b1 q + b2 q 2 + · · · + b(m+1)(n−1) q (m+1)(n−1) B(q) = . (1 − q n )m+1 Then 1 {(1 − q)−2 }B(q) = m!nm m & (sn + 1) s=1 m ! - (kn − 1) u+1 1≤k≤m−u (−1) u=1 - (pn + 1) bun−1 . u≤p≤m To prove Theorem 6.4 we will need the following lemma. Lemma 6.5 Let n, d, k be positive integers such that d|n, d ≥ 2 and 1 ≤ k ≤ N ; also let F (q) = C0 + C1 q + · · · + Cφ(d)−1 q φ(d)−1 . (1 − q d )k Then the polynomial F (q)(1 − q n )N has no terms in q in−1 , 1 ≤ i ≤ N . Proof. We have C0 + C1 q + · · · + Cφ(d)−1 q φ(d)−1 (1 − q n )N (1 − q d )k ' (' (k = C0 + C1 q + · · · + Cφ(d)−1 q φ(d)−1 1 + q d + q 2d + · · · + q n−d (1 − q n )N −k . F (q)(1 − q n )N = When expanded, the set X of degrees of the terms on the right side is given by 9 : X = s + kdt + (N − k)u | 0 ≤ s ≤ φ(d) − 1, 0 ≤ t ≤ n/d − 1, u = 0, n . If in − 1 belongs to X then s = in − 1 (with t = 0 = u) for some i, ⇒ 0 ≤ in − 1 ≤ φ(d) − 1. But this contradicts: d > 1 and d|n ⇒ in > φ(d). ! Proof of Theorem 6.4 Let {(1 − q)−2 }B(q) be represented by C120 . We employ UndetCoef. The theoretical decomposition of B(q) into q-partial fractions is given by (n−1)(m+1) B(q) = ! r=0 br q r (1 − q n )−m−1 = m+1 ! k=2 m+1 ! ! Pd,k (q) C1,k,0 + (1 − q)k (1 − q d )k k=1 (6.3) d|n d≥2 where Pd,k (q) = Cd,k,0 + Cd,k,1 q + · · · + Cd,k,φ(d)−1 q φ(d)−1 . Since the degree of the numerator of B(q) exceeds the degree of the denominator by m + 1 ≥ 2 it follows, by Theorem 6.1, that {(1 − q)−1 }B(q) vanishes in the right side of (6.3). INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 7 (2007), #A25 15 Multiplying both sides of (6.3) by (1 − q n )m+1 gives (n−1)(m+1) ! r br q = r=0 where m+1 ! k=2 T (q) = C1,k,0 (1 − q n )m+1 + T (q), (1 − q)k ! Pd,k (q)(1 − q n )m+1 ! m+1 d|n k=1 d≥2 (1 − q d )k (6.4) . By Lemma 6.5, T (q) has no terms in q in−1 , 1 ≤ i ≤ m, and the powers q in−1 on both sides completely determine the coefficients C1,k,0 . We note that m+1 ! "m + 1# ! "c + k − 1# (1 − q n )m+1 n s = (−q ) qc k (1 − q) s c s=0 c≥0 # #" " m+1 ! ! N + k − 1 − sn N s m+1 = q (−1) , s k − 1 s=0 N ≥0 where c + sn = N . Hence (6.4) becomes (n−1)(m+1) ! r=0 br q r #" # m + 1 N + k − 1 − sn = C1,k,0 q (−1) + T (q) s k − 1 s=0 N ≥0 k=2 0m+1 # " #" m+1 ! ! in + k − 2 − sn in−1 r m+1 C1,k,0 (−1) q = s k−1 r=0 k=2 ; m+1 ! ! N m+1 ! s " + (terms in q v , v += in − 1, 1 ≤ i ≤ m) + T (q). ( ' ≥ 0 ⇔ s ≤ i−1. Observe that s can be restricted to the range 1 ≤ s ≤ i−1 since in+k−2−sn k−1 0 i−1 " #" # (n−1)(m+1) m+1 ! ! ! (i − s)n + k − 2 in−1 r s m+1 br q = C1,k,0 (−1) q s k − 1 r=0 s=0 k=2 ; + (terms in q v , v += in − 1, 1 ≤ i ≤ m) + T (q). To determine the C1,k,0 , equate the coefficients of the q in−1 on both sides to obtain the system of m equations m+1 ' ( % C1,k,0 n+k−2 = bn−1 k−1 k=2 m+1 % k=2 C1,k,0 %1 ' s m+1 s=0 (−1) s ('(2−s)n+k−2( k−1 = b2n−1 .. . m+1 m−1 ' ('(m−s)n+k−2( % % = bnm−1 C1,k,0 (−1)s m+1 s k−1 k=2 s=0 . 16 INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 7 (2007), #A25 That is, Ac̄ = b̄, where (j ≡ k − 1) (A)ij = i−1 ! (−1)s s=0 " #" # m + 1 (i − s)n + j − 1 , c̄ = s j C1,2,0 .. . C1,m+1,0 bn−1 . , b̄ = .. . bmn−1 Let the matrix obtained by replacing the first column of A with b̄ be A1 . Then, according to Cramer’s Rule, {(1 − q)−2 }B(q) = C1,2,0 = det(A1 ) . det(A) (6.5) Let Λu1 denote the matrix obtained from A after deleting the uth row and first column. Then det(A1 ) = m ! (−1)u+1 det(Λu1 )bun−1 . u=1 Thus (6.5) becomes m 1 ! (−1)u+1 det(Λu1 )bun−1 . {(1 − q) }B(q) = det(A) u=1 −2 (6.6) Claim. det(A) = nm(m+1)/2 We use elementary row operations to evaluate det(A). Since (A)ij = " # ! " #" # " # i−2 in + j − 1 (i − s)n + j − 1 n+j−1 s m+1 + (−1) + , j s j j s=1 it follows that det(A) = det(C), where C is the matrix defined by " # in + j − 1 , 1 ≤ i ≤ m, 1 ≤ j ≤ m, (C)ij = j and is obtained on applying the following operations successively to the rows of A: Ri -→ Ri − i−1 ! k (−1) k=1 " # m+1 Ri−k , k 2 ≤ i ≤ j, (6.7) where Ri denotes the ith row and the other symbols have their usual meanings. The result then follows from the fact that det(C) is a special “combinatorial determinant” [17] corresponding to the case f = 1 + x (see [17, p. 3]). But our row operations approach yields det(A) = det(C) = nn2 · · · nm V (1, 2, . . . , m) 1!2! · · · (m − 1)! INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 7 (2007), #A25 17 where V (x1 , x2 , . . . , xN ) = 1≤j≤i≤N (xi − xj ) is the N th order Vandermonde determinant. Since V (1, 2, . . . , m) = 1!2! · · · (m − 1)!, we obtain det(A) = nm(m+1)/2 as claimed. Substituting for det(A) in (6.6) gives −2 {(1 − q) }B(q) = m ! 1 nm(m+1)/2 (−1)u+1 det(Λu1 )bun−1 . (6.8) u=1 It remains to evaluate det(Λu1 ). We prove the following Lemma, from which Theorem 6.4 clearly follows. ! Lemma 6.6 det(Λu1 ) = nm(m−1)/2 m! - (sn + 1) (kn − 1) 1≤s≤m 1≤k≤m−u . (pn + 1) u≤p≤m Proof. We apply the following modified form of the row operations (6.7) successively to the rows of Λu1 , in order: Ri Ri # m+1 -→ Ri − (−1) Rk , i − k k=1 " # i−1 ! i−k m + 1 → Ri − (−1) Rk , i−k k=u s ! i−k " 2 ≤ i ≤ j − 1, s = min(u − 1, i − 1); u + 1 ≤ i ≤ j − 1. The resulting (m − 1)-square matrix Y1u is given by 0 'in+j−1( , 1≤i<u j . (Y1u )ij = '(u+t)n+j−1( 'un+j−1( − E(m, t) , 1 ≤ t ≤ m − u j j (6.9) (6.10) (6.11) We claim that E(m, t) = " # m+t . t (6.12) The proof is by induction on the number t of rows u, u + 1, . . . in which every entry has exactly two summands following applications of the row operations (6.9) 'in+j−1 ( to all the rows, and (6.10) down to the (u + t)th row. For brevity denote Ψ(i) = . j By the definition of the matrix A the effect of the row operations (6.9) down to the uth row is the general uth-row entry Ψ(u + 1) − E(m, 1)Ψ(u). Hence (6.12) holds for t = 1. Assume that (6.12) is true for all positive integers up to t − 1, i.e., the rows from number u through u + t − 2 all have the required form. Then application of the row operations (6.10) INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 7 (2007), #A25 to the (u + t − 1)st row gives Ru+t−1 -→ Ru+t−1 − u+t−2 ! u+t−1−k (−1) k=u " " 18 # m+1 Rk u+t−1−k # m+1 = (−1) Ψ(u + t − s) s s=0 " # u+t−2 ! ' ( m+1 u+t−1−k (−1) − Ψ(k + 1) − E(m, k − u + 1)Ψ(u) u+t−1−k k=u " " # # t−1 ! t m+1 s m+1 (−1) Ψ(u) + E(m, t − s)Ψ(u) = Ψ(u + t) + (−1) t s s=1 " # t ! m+1 = Ψ(u + t) + (−1)s E(m, t − s)Ψ(u). s s=1 t ! s The last step in the proof is to establish the Vandermonde-convolution-type identity # " # #" " t ! m+t m+t−k k m+1 (−1) . (6.13) =− t k t − k k=1 Let St denote the left side: St = t−1 ! k=0 k+1 (−1) " #" # ! m+1 m+t−k−1 = ak , k+1 m k ' ( . Then we obtain where a0 = −(m + 1) m+t−1 m (k − m)(k − t + 1) (k + 1) ak+1 = , ak (k + 2)(k − m − t + 1) (k + 1) after routine simplification. Thus St can be written in hypergeometric notation as follows −m, −t + 1, 1 ,1 . St = a0 3 F2 2, −m − t + 1 By setting a = −m, b = 1, n = t − 1, c = 2 and noting that −m − t + 1 = 1 + a + b − c − n, we see that the 3 F2 -term satisfies the Pfaff-Saalschutz Theorem [5, p. 69], namely 1, −n , b (c − a)n (c − b)n ,1 = , 3 F2 (c)n (c − a − b)n c, 1 + a + b − c − n where the Pochhammer symbol (x)k is defined by (x)k = x(x + 1) · · · (x + k − 1), k ≥ 1, (x)0 = 1. Hence " # (2 + m)t−1 (1)t−1 m+t−1 (2 + m)t−1 (1)t−1 = −(m + 1) · S t = a0 · m (2)t−1 (1 + m)t−1 (2)t−1 (1 + m)t−1 19 INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 7 (2007), #A25 ' ( which gives, after simplification, St = − m+t = −E(m, t). Hence the claim follows. t ! Remark Call (6.13) an identity of order 0. If we concentrate on retaining exactly three summands per entry from the (u + 1)st row downward, the coefficients of Ψ(u) will lead, as above, to the analogous identity of order 1: t ! k+1 (−1) k=1 " #" # " # m+1 m+t−k m+t =t . k+1 t−k t+1 By a similar argument it can be shown that the identity of order 2 is t ! k+1 (−1) k=1 " #" # " #" # m+t m+t−k t+1 m+t = . k+2 t−k 2 t+2 The general form of such identities of fixed order d, 0 ≤ d ≤ m − t + 1, with 1 ≤ t ≤ m, is given by t ! k+1 (−1) k=1 " #" # # " #" t+d−1 m+t m+1 m+t−k . = t+d d t−k k+d Remark We recall an important property of determinants [14, p. 2]. Let D, U, V be determinants of order n with ij-entries given by (D)ij , (U )ij , (V )ij , such that for a fixed index k, 1 ≤ k ≤ n, we have (D)ik = αxik + βyik , (U )ik = αxik , (V )ik = βyik , and (D)ij = (U )ij = (V )ij , if j += k. Then D = αU + βV , where α and β are real numbers. Since det(Λu1 ) = det(Y1u ), we can use the above remark repeatedly to write det(Λu1 ) as a linear combination of the determinants det(C1v ), where each C1v is the matrix obtained from C, after deleting the vth row and first column. Then it follows from (6.11) that det(Λu1 ) = m−u ! t (−1) E(m, t) det(C1u+t ) t=0 = m+t ! t (−1) t=0 " # m+t det(C1u+t ). t (6.14) Each determinant det(C1v ) can be evaluated by reduction to a Vandermonde determinant. det(C1v ) = n(m−1)(m−2)/2 2!3! · · · m! & 1≤s≤m, s%=v sn(sn + 1)V (1, 2, . . . , v − 1, v + 1, . . . , m). Now use the relation V (1, 2, . . . , v − 1, v + 1, . . . , m) = det(C1v ) 1!2! · · · (m − 1)! , to obtain (v − 1)!(m − v)! " # & nm(m−1)/2 m = (sn + 1). m! v 1≤s≤m, s%=v (6.15) 20 INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 7 (2007), #A25 Substituting for (6.15) in (6.14) gives 'm( " # m m−u m(m−1)/2 & ! n m + t u+t ' (. det(Λv1 ) = (sn + 1) (−1)t m! t (u + t)n + 1 s=1 t=0 (6.16) Lastly we eliminate the summation symbol by transformation into hypergeometric notation. As before we have 'm( 'm( " # m−u m + 1, −m + u, n1 (nu + 1) ! m+t u+t u ' (= ,1 . (−1)t 3 F2 t un + 1 (u + t)n + 1 1 t=0 u + 1, n (nu + n + 1) The Pfaff-Saalschultz Theorem applies again and we obtain, after routine simplifications, 'm( " # m−u ! m + t u+t ' ( (−1)t t (u + t)n + 1 t=0 'm( ' n−1 ( m−u - (kn − 1) (−m + u)m−u n m−u k=1 ' ( = . = · m un + 1 (u + 1)m−u −nm−1 b m−u (pn + 1) u p=u Substituting the last result into (6.16) gives the Lemma. ! Acknowledgement The author is grateful to his advisor, George E. Andrews, who is responsible for inventing q-partial fractions. References [1] G.E. Andrews. Applications of basic hypergeometric functions. SIAM Review, 16:441–484, 1974. [2] G.E. Andrews. Partitions: At the interface of q-Series and Modular Forms. Ramanujan Journal 7 (1, 2, 3):385–400, 2003. [3] G.E. Andrews. q-Series: Their Development and Application in Analysis, Number Theory, Combinatorics, Physics, and Computer Algebra. Volume 66 of CBMS Regional Conference Series in Mathematics, Published for the Conference Board of the Mathematical Sciences, Washington, D. C., 1986. [4] G.E. Andrews. The Theory of Partitions. Addison-Wesley, Reading, 1976; reprinted by Cambridge University Press, Cambridge in 1984, 1998. [5] G.E. Andrews, R. Askey and R. Roy. Special Functions. Cambridge University Press 1999. [6] J. Arkin. Researches on Partitions. Duke Math. J., 38:403–409, 1970. [7] A. Bjorner and R.P. Stanley. A Combinatorial Miscellany. L’Enseignement Math. (to appear). [8] A. Cayley. Researches in the Partition of Numbers. Collected Math. Papers, 2:2 35–249, 506–512, 1898. INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 7 (2007), #A25 21 [9] G. Gasper and M. Rahman. Basic Hypergeometric Series. Cambridge University Press 1990. [10] H. Gupter, M.M. Gwyther and J.C.P. Miller. Tables of Partitions. Royal Soc. Math. Tables, Vol. 4, Cambridge Univ Press, Cambridge, 1958. [11] M.D. Hirschhorn, Triangles with Integer Sides Revisited. Math. Mag., 73:53-56, 2000. [12] P.A. MacMahon. Combinatory Analysis. Vol. 2, Cambridge Univ. Press, Cambridge 1916; reprinted by Chelsea, New York in 1960. [13] A.O. Munagi. The Rademacher Conjecture and q-Partial Fractions. Ramanujan Journal (to appear). [14] V.V. Prasolov. Problems and Theorems in Linear Algebra. Translations of Mathematical Monographs, Vol. 134, AMS, Providence, 1994. [15] H. Rademacher. Topics in Analytic Number Theory. Springer, New York, 1973. [16] E.W. Weisstein. “Cyclotomic Polynomial” From MathWorld–A ¡http://mathworld.wolfram.com/ CyclotomicPolynomial.html¿. Wolfram [17] H. Wilf. A Combinatorial Determinant. Eprint arXiv:math.CO/9809120, 09/1998. Web Resource.