Minimal r-Complete Partitions

Øystein J. Rødseth Department of Mathematics University of Bergen Johs. Brunsgt. 12 N-5008 Bergen Norway

                      rodseth@math.uib.no

Abstract

A minimal r-complete partition of an integer m is a partition of m with as few parts as possible, such that all the numbers 1, …, rm can be written as a sum of parts taken from the partition, each part being used at most r times. This is a generalization of M-partitions (minimal 1-complete partitions). The number of M-partitions of m was recently connected to the binary partition function and two related arithmetic functions. In this paper we study the case r ≥ 2, and connect the number of minimal r-complete partitions to the (r + 1)-ary partition function and a related arithmetic function.

1 Introduction

Let λ = (λ_{0}, λ_{1}, …, λ_{n}) be a partition of the natural number m into n + 1 parts λ_{i} arranged in non-decreasing order,

m = λ_{0} + λ_{1} + ⋯ + λ_{n}, 1 ⩽ λ_{0} ⩽ λ_{1} ⩽ ⋯ ⩽ λ_{n}.

The sum of the parts is called the weight of the partition and is denoted by |λ|, while n + 1 is the length of the partition.

MacMahon [3], [4, pp. 217–223] calls the partition λ of weight m perfect if each positive integer less than m can be written in a unique way as a sum of distinct parts λ_{i}. Park [6] calls λ a complete partition of m if the representation property is maintained, while the uniqueness constraint is dropped. (O’Shea [5] calls this a weak M-partition.) Prior to Park’s paper, infinite complete sequences had been introduced by Hoggatt and King [2], and studied by Brown [1].

Park [7] generalized the notion of a complete partition to r-complete partitions for a positive integer r. The partition λ = (λ_{0}, …, λ_{n}) of m is r-complete if each integer w in the interval 0 ⩽ w ⩽ rm can be written as

w = α_{0}λ_{0} + ⋯ + α_{n}λ_{n} with 0 ⩽ α_{i} ⩽ r.  (1)

Clearly, “complete” is the same as “1-complete”. An r-complete partition is also (r + 1)- complete.

We call an r-complete partition of m of minimal length a minimal r-complete partition of m. O’Shea [5] uses the term M-partition in place of minimal complete partition. He showed that for half the numbers m, the number of M-partitions of m is equal to the number of binary partitions of 2^{n+1} − 1 − m, where n = ⌊log_{2} m⌋. (In a binary partition, all parts are powers of 2.) O’Shea’s partial enumeration formula was completed by us in [8].

In this paper we connect the minimal r-complete partition function (for r ⩾ 2) to the (r + 1)-ary partition function and a related arithmetic function. (In an (r + 1)-ary partition, all parts are powers of r + 1.) In Section 2 we state our results. In Section 3 we consider a characterization of minimal r-partitions, and in Section 4 we prove our main result using (truncated) polynomials and formal power series.

2 Statement of Results

Let f(k) be the (r + 1)-ary partition function, that is, the number of partitions of k into powers of r + 1. For the generating function F (x) we have

F (x) = ∑_{k=0}^{∞} f(k)x^{k} = ∏_{i=0}^{∞} \frac{1}{1 − x^{(r+1)^{i}}} .

We also define the auxiliary arithmetic function g(k) as follows:

G(x) = ∑_{k=0}^{∞} g(k)x^{k} = ∑_{j=0}^{∞} \frac{x^{(r+1)^{j}−1}}{1 − x^{2(r+1)^{j}}} F (x^{(2r+1)(r+1)^{j}}) ∏_{i=0}^{j} \frac{1}{1 − x^{(r+1)^{i}}} .

A straightforward verification shows that the following functional equations hold:

F (x) = \frac{1}{1 − x}F (x^{r+1}),  (2)
G(x) = \frac{x^{r}}{1 − x}G(x^{r+1}) + \frac{1}{(1 − x)(1 − x^{2})}F (x^{2r+1}).  (3)

These functional equations give simple recurring relations for fast computation of f(k) and g(k). We adopt the convention that g(k) = 0 if k is not a non-negative integer.

Theorem 2.1. Let r ⩾ 2, and let a_{r}(m) be the number of minimal r-complete partitions of m. Then

a_{r}(m) = f (\frac{1}{r} ((r + 1)^{n+1} − 1) − m) − g (\frac{1}{r} ((2r + 1)(r + 1)^{n−1} − 1) − 1 − m) ,

where n = ⌊log_{r+1}(rm)⌋.

Corollary 2.1. We have

a_{r}(m) = f (\frac{1}{r} ((r + 1)^{n+1} − 1) − m)

if \frac{1}{r}((2r + 1)(r + 1)^{n−1} − 1) ⩽ m ⩽ \frac{1}{r}((r + 1)^{n+1} − 1).

The case r = 1 is not covered by Theorem 2.1. This case is slightly different from r ⩾ 2, as an additional arithmetic function is required in the description of a_{1}(m); see [8, Theorem 2]. The expression for a_{r}(m) in Theorem 2.1 is, however, valid for r = 1 if 2^{n} + 2^{n−3} − 4 ⩽ m ⩽ 2^{n+1} − 1. In particular, Corollary 2.1 remains valid if r = 1, a result due to O’Shea [5].

Some of the sequences appearing above can be found in Sloane’s On-Line Encyclopedia of Integer Sequences [9]. For perfect partitions, see sequence \underline{A002033}; for a_{1}(m), see \underline{A100529}. The sequences \underline{A000123}, \underline{A018819}, \underline{A0005704}, \underline{A0005705}, \underline{A0005706} give the first several values of f(k) for r = 1, 1, 2, 3, and 4, respectively. In addition, sequence \underline{A117115} gives the 53 first values of g(k) for r = 1, and \underline{A117117} gives the 53 first values of the additional arithmetic function required in the description of a_{1}(m).

3 Completeness

The following lemma is due to Park [7], with partial results by Brown [1] and Park [6].

Lemma 3.1. The partition λ = (λ_{0}, …, λ_{n}) is r-complete if and only if λ_{0} = 1 and

λ_{i} ⩽ 1 + r(λ_{0} + ⋯ + λ_{i−1}) for i = 1, 2, …, n.  (4)

The necessity of the conditions λ_{0} = 1 and (4) is clear, and the sufficiency follows by induction on n; see the proof of Theorem 2.2 in [7].

Suppose that λ = (λ_{0}, …, λ_{n}) is an r-complete partition of m. Then (1) must be solvable for rm + 1 values of w. Since the right hand side attains at most (r + 1)^{n+1} distinct values, we have rm + 1 ⩽ (r + 1)^{n+1}. Alternatively, by Lemma 3.1, λ_{i} ⩽ (r + 1)^{i} for i = 0, 1, …, n, so that rm ⩽ (r + 1)^{n+1} − 1. In any case, we have ⌊log_{r+1}(rm)⌋ ⩽ n, cf. [7, Proposition 2.4].

On the other hand, for a given m, let n = ⌊log_{r+1}(rm)⌋. Order the n+1 positive integers 1, r + 1, (r + 1)^{2}, …, (r + 1)^{n−1}, k = m − \frac{1}{r}((r + 1)^{n} − 1) in increasing order 1 = λ_{0} ⩽ λ_{1} ⩽ ⋯ ⩽ λ_{n}. We have 1 ⩽ k ⩽ (r + 1)^{n}, and it follows that λ is a minimal r-complete partition of m.

Lemma 3.2. Let λ be an r-complete partition of weight m and length n + 1. Then λ is minimal if and only if

n = ⌊log_{r+1}(rm)⌋.  (5)

We have shown that if λ = (λ_{0}, …, λ_{n}) is a partition of weight m with λ_{0} = 1, then λ is a minimal r-complete partition if and only if (4) and (5) hold.

4 Generating functions

In order to determine the number a_{r}(m) of minimal r-complete partitions of weight m, we first consider the number q_{n}(m) of r-complete partitions of weight m and length n + 1. By Lemma 3.2, we know that such an r-complete partition is minimal if and only if \frac{1}{r}((r + 1)^{n} − 1) + 1 ⩽ m ⩽ \frac{1}{r}((r + 1)^{n+1} − 1). Thus

a_{r}(m) = q_{n}(m) if \frac{1}{r} ((r + 1)^{n} − 1) + 1 ⩽ m ⩽ \frac{1}{r} ((r + 1)^{n+1} − 1) .  (6)

For the generating function Q_{n}(x) of q_{n}(m), we have

Q_{n}(x) = ∑_{m=n+1}^{(1/r)((r+1)^{n+1}−1)} q_{n}(m)x^{m} = ∑_{λ} x^{|λ|},  (7)

where we sum over the λ satisfying 1 = λ_{0} ⩽ λ_{1} ⩽ ⋯ ⩽ λ_{n} and (4).

We change parameters by setting μ_{i} = (r + 1)^{i} − λ_{i} for i = 0, 1, …, n. Then the constraints, necessary for λ being r-complete, become μ_{0} = 0, and

r(μ_{0} + ⋯ + μ_{i−1}) ⩽ μ_{i} ⩽ r(r + 1)^{i−1} + μ_{i−1} for i = 1, …, n.  (8)

Moreover,

|λ| = \frac{1}{r}((r + 1)^{n+1} − 1) − |μ|,  (9)

for |μ| = μ_{0} + ⋯ + μ_{n}. For a fixed n, we are interested in the number of solutions λ of |λ| = m for each m in the interval \frac{1}{r}((r + 1)^{n} − 1) + 1 ⩽ m ⩽ \frac{1}{r}((r + 1)^{n+1} − 1), that is, the number of solutions μ of |μ| = k for each k in the interval 0 ⩽ k ⩽ (r + 1)^{n} − 1.

We write

R_{n}(x) = ∑_{k⩾0}r_{n}(k)x^{k} = ∑_{μ} x^{|μ|},  (10)

where we sum over the μ satisfying μ_{0} = 0 and (8). We are interested in the coefficients r_{n}(k) for k < (r + 1)^{n}. Therefore we shall on some occasions truncate polynomials and formal power series under consideration. We shall use the order symbol O(x^{N}) for truncation of order N. Thus, if we write

∑_{k} b(k)x^{k} = ∑_{k} c(k)x^{k} + O(x^{N}),

then b(k) = c(k) for all k < N.

Let n ⩾ 2. It simplifies notations to “sum” over μ_{0} = 0. We have

R_{n}(x) = ∑_{μ_{0}} ⋯ ∑_{μ_{n}} x^{μ_{0}+···+μ_{n}},

where the innermost sum is

∑_{μ_{n}=r(μ_{0}+···+μ_{n−1})}^{r(r+1)^{n−1}+μ_{n−1}} x^{μ_{0}+···+μ_{n}} = x^{(r+1)(μ_{0}+···+μ_{n−1})} \frac{1 − x^{r(r+1)^{n−1}+1−r(μ_{0}+···+μ_{n−1})+μ_{n−1}}}{1 − x} .

Now, we have

R_{n}(x) = \frac{1}{1 − x}R_{n−1}(x^{r+1}) − \frac{x^{r(r+1)^{n−1}+1}}{1 − x} ∑_{μ_{0}} ⋯ ∑_{μ_{n−1}} x^{μ_{0}+···+μ_{n−2}+2μ_{n−1}}.

We repeat this process once, and obtain

R_{n}(x) = \frac{1}{1 − x}R_{n−1}(x^{r+1}) − \frac{x^{r(r+1)^{n−1}+1}}{(1 − x)(1 − x^{2})}R_{n−2}(x^{2r+1})

+ \frac{x^{r(r+3)(r+1)^{n−2}+3}}{(1 − x)(1 − x^{2})} ∑_{μ_{0}} ⋯ ∑_{μ_{n−2}} x^{μ_{0}+···+μ_{n−3}+3μ_{n−2}},

so that

R_{n}(x) = \frac{1}{1 − x}R_{n−1}(x^{r+1}) − \frac{x^{r(r+1)^{n−1}+1}}{(1 − x)(1 − x^{2})}R_{n−2}(x^{2r+1}) + O(x^{(r+1)^{n}})  (11)

for n ⩾ 2.

By (2) and (3), we have

F (x) = \frac{1}{1 − x} + O(x^{r+1}),
G(x) = \frac{1}{(1 − x)(1 − x^{2})} + O(x^{r}).  (12)

Moreover, R_{0}(x) = 1, and

R_{1}(x) = 1 + x + ⋯ + x^{r} = \frac{1 − x^{r+1}}{1 − x} = F (x) + O(x^{r+1}),

so we may write

R_{1}(x) = F (x) − x^{r+1}G(x) + O(x^{r+1}).  (13)

Putting n = 2 in (11), we get

R_{2}(x) = \frac{1}{1 − x}R_{1}(x^{r+1}) − \frac{x^{r(r+1)+1}}{(1 − x)(1 − x^{2})}R_{0}(x^{2r+1}) + O(x^{(r+1)^{2}}),

and using (13), we obtain

R_{2}(x) = \frac{1}{1 − x}F (x^{r+1}) − \frac{x^{r(r+1)+1}}{(1 − x)(1 − x^{2})} + O(x^{(r+1)^{2}}).

Hence, by (2) and (12), we have R_{2}(x) = F (x) − x^{r(r+1)+1}G(x) + O(x^{(r+1)^{2}}).

We claim that if r ⩾ 2 and n ⩾ 1, then

R_{n}(x) = F (x) − x^{r(r+1)^{n−1}+1}G(x) + O(x^{(r+1)^{n}}).  (14)

To prove this, we use induction on n. We have just seen that the claim is valid for n = 1 and n = 2. Suppose that (14) holds for n replaced by n − 1 and by n − 2 for some n ⩾ 3. Using (11) and the induction hypotheses, we obtain

R_{n}(x) = \frac{1}{1 − x} (F (x^{r+1}) − x^{r(r+1)^{n−1}+r+1}G(x^{r+1}) + O(x^{(r+1)^{n}}))

− \frac{x^{r(r+1)^{n−1}+1}}{(1 − x)(1 − x^{2})} (F (x^{2r+1}) − x^{(2r+1)(r(r+1)^{n−3}+1)}G(x^{2r+1}) + O(x^{(2r+1)(r+1)^{n−2}}))

+ O(x^{(r+1)^{n}}).

We find that

R_{n}(x) = \frac{1}{1 − x}F (x^{r+1}) − \frac{x^{r(r+1)^{n−1}+r+1}}{1 − x} G(x^{r+1}) − \frac{x^{r(r+1)^{n−1}+1}}{(1 − x)(1 − x^{2})}F (x^{2r+1}) + O(x^{(r+1)^{n}}),

and, using the functional equations (2) and (3), (14) follows.

We are now ready to conclude the proof of Theorem 2.1. By (10) and (9), we have

R_{n}(x) = ∑_{μ} x^{|μ|} = ∑_{λ} x^{(1/r)((r+1)^{n+1}−1)−|λ|}.

Moreover, by (7),

R_{n}(x) = x^{(1/r)((r+1)^{n+1}−1)}Q_{n}(x^{−1}) = ∑_{m=n+1}^{(1/r)((r+1)^{n+1}−1)} q_{n}(m)x^{(1/r)((r+1)^{n+1}−1)−m}.

Hence,

R_{n}(x) = ∑_{k⩾0}r_{n}(k)x^{k} = ∑_{k=0}^{(1/r)((r+1)^{n+1}−1)−n−1} q_{n} (\frac{1}{r} ((r + 1)^{n+1} − 1) − k) x^{k};

that is,

r_{n}(k) = q_{n} (\frac{1}{r} ((r + 1)^{n+1} − 1) − k) .  (15)

For n ⩾ 1, we have by (14),

r_{n}(k) = f(k) − g(k − r(r + 1)^{n−1} − 1) for 0 ⩽ k ⩽ (r + 1)^{n} − 1.

Setting k = \frac{1}{r} ((r + 1)^{n+1} − 1)−m and using (15) and (6), we get Theorem 2.1. By inspection, the theorem also holds for n = 0.

References

[1] J. L. Brown, Note on complete sequences of integers, Amer. Math. Monthly 68 (1961), 557–560.

[2] V. E. Hoggatt and C. King, Problem E 1424, Amer. Math. Monthly 67 (1960), 593.

[3] P. A. MacMahon, The theory of perfect partitions and the compositions of multipartite numbers, Messenger Math. 20 (1891), 103–119.

[4] P. A. MacMahon, Combinatory Analysis, vols. I and II, Cambridge University Press, 1915, 1916 (reprinted Chelsea 1960).

[5] E. O’Shea, M-partitions: optimal partitions of weight for one scale pan, Discrete Math. 289 (2004), 81–93.

[6] S. K. Park, Complete partitions, Fibonacci Quart. 36 (1998), 354–360.

[7] S. K. Park, The r-complete partitions, Discrete Math. 183 (1998), 293–297.

[8] Ø. J. Rødseth, Enumeration of M-partitions, Discrete Math. 306 (2006), 694–698.

[9] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, published electronically at http://www.research.att.com/˜ njas/sequences/, 2007.

2000 Mathematics Subject Classification: Primary 11P81; Secondary 05A17. Keywords: complete partitions, M-partitions, (r + 1)-ary partitions.

(Concerned with sequences \underline{A000123}, \underline{A002033}, \underline{A0005704}, \underline{A0005705}, \underline{A0005706}, \underline{A018819}, \underline{A100529}, \underline{A117115}, and \underline{A117117}.)

Received May 14 2007; revised version received July 30 2007. Published in Journal of Integer Sequences, August 3 2007.

Return to Journal of Integer Sequences home page.