ON PARTITIONS AND CYCLOTOMIC POLYNOMIALS

Neville Robbins

Mathematics Department, San Francisco State University, San Francisco, CA 94132

                             robbins@math.sfsu.edu

Received: November 12, 1999, Revised: May 22, 2000, Accepted: June 2, 2000, Published: June 6, 2000

Abstract

Let m denote a squarefree number. Let f_{m}(n) denote the number of partitions of n into parts that are relatively prime to m. Let Φ_{m}(z) denote the m^{th} cyclotomic polynomial. We obtain a generating function for f_{m}(n) that involves factors Φ_{m}(z^{n}).

1. Introduction

If z is a complex variable, let Φ_{m}(z) denote the mth cyclotomic polynomial, that is

Φ_{m}(z) = ∏_{d|m}(z^{d} − 1)^{μ(m/d)}

where μ(n) denotes the Möbius function. If p is prime, let b_{p}(n) denote the number of p-regular partitions of n, that is, the number of partitions of n such that no part occurs p or more times. It is well-known that b_{p}(n) also counts the number of partitions of n into parts, k, such that (k, p) = 1. (See [1],[2], and [3].) Furthermore, b_{p}(n) has a generating function given by

∑_{n=0}^{∞} b_{p}(n)z^{n} = ∏_{n=1}^{∞} \frac{1 − z^{pn}}{1 − z^{n}} = ∏_{n=1}^{∞} Φ_{p}(z^{n})  (1)

where |z| < 1 . In particular, if q(n) denotes the number of partitions of n into distinct parts (or odd parts), so that q(n) = b_{2}(n), then

∑_{n=0}^{∞} q(n)z^{n} = ∑_{n=0}^{∞} b_{2}(n)z^{n} = ∏_{n=1}^{∞}(1 + z^{n}) = ∏_{n=1}^{∞} Φ_{2}(z^{n}).  (2)

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 0 (2000), #A06 2

In this note, we generalize (1) as follows. Let m be the product of r distinct primes. Let f_{m}(n) denote the number of partitions of n into parts, k, such that (k, m) = 1. That is, f_{m}(n) denotes the number of partitions of n into parts that are not divisible by any of the r distinct primes. We obtain a generating function for f_{m}(n) as an infinite product of factors Φ_{m}(z^{n}) or 1/Φ_{m}(z^{n}), accordingly as r is odd or even, respectively.

2. Preliminaries

Theorem 0 If H ⊂ N, let p_{H}(n) denote the number of partitions of n into parts belonging to H; let q_{H}(n) denote the number of partitions of n into distinct parts belonging to H; let q_{H}^{E}(n) denote the number of partitions of n into evenly many distinct parts from H; let q_{H}^{O}(n) denote the number of partitions of n into oddly many distinct parts from H. Further, let q_{H}^{∗}(n) = q_{H}^{E}(n) − q_{H}^{O}(n) and define p_{H}(0) = q_{H}(0) = q_{H}^{E}(0) = q_{H}^{∗}(0) = 1. Let z be a complex variable such that |z| < 1. Then

∑_{n=0}^{∞} p_{H}(n)z^{n} = ∏_{n∈H}(1 − z^{n})^{−1}  (3)

∑_{n=0}^{∞} q_{H}(n)z^{n} = ∏_{n∈H}(1 + z^{n})  (4)

∑_{n=0}^{∞} q_{H}^{∗}(n)z^{n} = ∏_{n∈H}(1 − z^{n}).  (5)

Remarks: Equation (3) is Theorem 1.1, (1.2.4) in [1]; (4) follows from the same theorem; (5) is proven for the case H = N in [1]. The proof extends easily to the case: H ⊂ N.

3. The Main Results

Theorem 1 Let m = ∏_{i=1}^{r} p_{i} , where r ≥ 1 and the p_{i} are distinct primes. Let f_{m}(n) be the number of partitions of n into parts, k, such that (k, m) = 1. Let Φ_{m}(z) denote the mth cyclotomic polynomial, where z is a complex variable, with |z| < 1. Then

∑_{n=0}^{∞} f_{m}(n)z^{n} = ∏_{n=1}^{∞}(Φ_{m}(z^{n}))^{(−1)^{r−1}}.  (6)

Proof. If r = 1, then f_{m}(n) = f_{p}(n) = b_{p}(n) = the number of p-regular partitions of n , so (by (1))

∑_{n=0}^{∞} f_{m}(n)z^{n} = ∑_{n=0}^{∞} b_{p}(n)z^{n} = ∏_{n=1}^{∞} \frac{1 − z^{pn}}{1 − z^{n}} = ∏_{n=1}^{∞} Φ_{p}(z^{n}).

Now suppose that m has r distinct prime factors, and p is a prime such that p |̸m. Then pm has r + 1 distinct prime factors. By induction hypothesis,

∑_{n=0}^{∞} f_{m}(n)z^{n} = ∏_{n=1}^{∞}(Φ_{m}(z^{n}))^{(−1)^{r−1}}.

Now

\begin{aligned}∑_{n=0}^{∞} f_{pm}(n)z^{n} & = ∏_{(p,n)=1}(Φ_{m}(z^{n}))^{(−1)^{r−1}} & = ∏_{n=1}^{∞} (\frac{Φ_{m}(z^{n})}{Φ_{m}(z^{pn})})^{(−1)^{r−1}} \\ & = ∏_{n=1}^{∞}(1/Φ_{pm}(z^{n}))^{(−1)^{r−1}} & = ∏_{n=1}^{∞}(Φ_{pm}(z^{n}))^{(−1)^{r}}, \end{aligned}

so we are done.

Remarks: Let ω(d) denote the number of distinct prime factors of d. Then (6) could be restated as:

∑_{n=0}^{∞} f_{m}(n)z^{n} = ∏_{n=1}^{∞} ∏_{d|m}(1 − z^{dn})^{(−1)^{1+ω(d)}}.  (7)

Since d is squarefree by hypothesis, we have (−1)^{ω(d)} = μ(d). Thus (7) becomes:

∑_{n=0}^{∞} f_{m}(n)z^{n} = ∏_{n=1}^{∞} ∏_{d|m}(1 − z^{dn})^{−μ(d)}.  (8)

A shorter, alternate proof is based on the inclusion-exclusion principle, namely

∑_{n=0}^{∞} f_{m}(n)z^{n} = ∏_{n=1}^{∞}(1 − z^{n})^{−1} ∏_{p|m}(1 − z^{pn}) ∏_{p_{1}p_{2}|m}(1 − z^{p_{1}p_{2}n})^{−1} ∏_{p_{1}p_{2}p_{3}|m}(1 − z^{p_{1}p_{2}p_{3}n}) ⋯ (9)

= ∏_{n=1}^{∞} ∏_{d|m}(1 − z^{dn})^{−μ(d)}.

(In the products above, the p_{i} are distinct prime divisors of m.)

Furthermore, f_{m}(n) may be computed recursively by the repeated use of Theorem 2 below, whose elementary proof is omitted.

Theorem 2 Let m, r, f_{m}(n), z be as in the hypothesis of Theorem 1. Let p be a prime such that p ∤ m. Then

f_{pm}(n) + ∑_{j=1}^{[n/p]} f_{pm}(n − pj)f_{m}(j) = f_{m}(n).

For example, suppose we wish to compute the number of partitions of n into parts that are not divisible by 2, 3, or 5. That is, we wish to compute f_{30}(n). According to Theorem 1, we have:

∑_{n=0}^{∞} f_{30}(n)z^{n} = ∏_{n=1}^{∞} Φ_{30}(z^{n}) = ∏_{n=1}^{∞}(z^{8n} + z^{7n} − z^{5n} − z^{4n} − z^{3n} + z^{n} + 1).

We conclude with the following theorem, which follows easily from Theorems 1 and 0.

Theorem 3 Let m, r, n, z be as in the hypothesis of Theorem 1. Let q_{m}^{E}(n), q_{m}^{O}(n) denote respectively the number of partitions of n into evenly, oddly many distinct parts, k, such that (k, m) = 1. Then

∏_{n=1}^{∞}(Φ_{m}(z^{n}))^{(−1)^{r}} = ∑_{n=0}^{∞}(q_{m}^{E}(n) − q_{m}^{O}(n))z^{n}.

Proof. This follows from the hypothesis, Theorem 1, and Theorem 0, part (iii).

References

1. George E. Andrews, “The Theory of Partitions,” Cambridge University Press (1984).

2. J. W. L. Glaisher, “A theorem in partitions,” Messenger of Math. 12 (1883), 158-170.

3. G. D. James & A. Kerner, “The representation theory of the symmetric group,” Addison-Wesley, Reading, MA (1981).

AMS Classification: 11P83, 11P81