Perfect Compositions of Numbers

Augustine O. Munagi School of Mathematics University of the Witwatersrand Wits 2050, Johannesburg South Africa

                  augustine.munagi@wits.ac.za

Abstract A perfect composition of a positive integer is one whose sequence of parts contains one composition of every smaller positive integer. We obtain explicit formulas based on the observation that perfect compositions are identical with certain restricted permutations of perfect partitions. We also consider n-color perfect compositions.

1 Introduction

A perfect partition of a positive integer n is one whose parts include exactly one partition of every positive integer less than n. For example, (1, 1, 1, 4) = (1^{3}, 4) is a perfect partition of 7 because it contains the following partitions of 1, 2, 3, 4, 5, 6 respectively, and no other: (1), (1^{2}), (1^{3}), (4), (1, 4), (1^{2}, 4).

The definition of perfect partitions goes back to MacMahon [4, 5]. He first considered partitions of numbers of the form n = p^{α} − 1, where p is a prime number, and showed that the number of perfect partitions of n is given by 2^{α−1}. MacMahon also considered the number n = p_{1}^{α_{1}}p_{2}^{α_{2}} ⋯ p_{k}^{α_{k}} − 1, where the p_{i} are distinct primes, and found that it has as many perfect partitions as the number of generalized partitions of the vector (α_{1}, …, α_{k}) (see Andrews [3] for details).

There is a natural bijection between the set of perfect partitions of n and the set of ordered factorizations of N = n + 1, that is, representations of N as ordered products of positive integers without unit factors [3, 5, 8]. Indeed every ordered factorization a_{1}a_{2} ⋯ a_{k} corresponds uniquely to the perfect partition

λ = (1^{a_{1}−1}, a_{1}^{a_{2}−1}, (a_{1}a_{2})^{a_{3}−1}, …, (a_{1}a_{2} ⋯ a_{k−1})^{a_{k}−1}) .  (1)

Notice that (1^{a_{1}−1}) generates partitions of 1, 2, …, a_{1}−1; then (1^{a_{1}−1}, a_{1}^{a_{2}−1}) generates further partitions, of a_{1}, a_{1}+1, …, a_{1}a_{2}−1. Thus by induction λ generates a partition of each number from 1 through a_{1}a_{2} ⋯ a_{k} − 1.

Let f(n, k) denote the number of ordered factorizations of n into k factors, and let the prime-power factorization of n be n = p_{1}^{α_{1}}p_{2}^{α_{2}} ⋯ p_{k}^{α_{k}}. A general formula for f(n, k) was found in 1893 by MacMahon [5] (also [3, p. 59]):

f(n, k) = ∑_{i=0}^{k−1}(−1)^{i}\binom{k}{i} ∏_{j=1}^{r} \binom{α_{j} + k − i − 1}{α_{j}}.

The purpose of this paper is to study perfect compositions in analogy with perfect partitions. This work was partly inspired by a recent extension of perfect partitions to n-color perfect partitions by Agarwal and Sachdeva [2]. An n-color partition is a partition in which a part of size n, n ≥ 1 can come in n colors denoted by subscripts n_{1}, n_{2}, …, n_{n}. Among other results they proved that every ordered factorization a_{1}a_{2} ⋯ a_{k} of ν + 1, with k > 1, gives rise to a_{1}^{k−1}a_{2}^{k−2} ⋯ a_{k−1} n-color perfect partitions of ν.

Compositions or ordered partitions of n are denoted by vectors with positive integer entries that sum to n. We also express the parts of a composition symbolically by writing a^{s} in place of a run of s equal parts a. For example, the composition (8, 8, 8, 1, 1, 6, 3, 3, 1, 4) = (8^{3}, 1^{2}, 6, 3^{2}, 1, 4) has 6 symbolic parts and 10 (actual) parts.

Definition 1. A perfect composition of n is one whose sequence of parts contains exactly one composition of every positive integer less than n.

We emphasize that the order of parts of a composition of each m ∈ {1, 2, …, n − 1}, which is contained in a perfect composition C, is induced by the order of the parts of C.

Thus every perfect partition is a perfect composition. For instance, (6, 1, 2^{2}) is a perfect composition of 11 since it contains one composition of each m ∈ {1, …, 10}:

(1), (2), (1, 2), (2^{2}), (1, 2^{2}), (6), (6, 1), (6, 2), (6, 1, 2), (6, 2^{2}).

In the next section, we give a characterization of perfect compositions, followed by their enumeration in Section 3. Then in section 4, we consider n-color perfect compositions in analogy with n-color perfect partitions.

2 Perfect compositions

Consider a composition C = (c_{1}^{u_{1}}, …, c_{r}^{u_{r}}), where c_{i} ≠ c_{j} for i ≠ j. Replace each c_{i}^{u_{i}} with the set V_{i} = {c_{i}, c_{i}^{2}, …, c_{i}^{u_{i}}}. Then the set of compositions generated by C is determined by the Cartesian product of the V_{i} provided that c_{i}^{x} and c_{i}^{y} are treated as distinct whenever x ≠ y. So denoting by D_{t}(C) the set of compositions with t part-sizes generated by C, 1 ≤ t ≤ r, we obtain

D_{t}(C) = V_{j_{1}} × V_{j_{2}} × ⋯ × V_{j_{t}}, 1 ≤ j_{1} < ⋯ < j_{t} ≤ r.  (2)

Thus, from standard set theory, the cardinality is

|D_{t}(C)| = ∑_{1≤j_{1}<···<j_{t}≤r} u_{j_{1}}u_{j_{2}} ⋯ u_{j_{t}}.

Hence, with D(C) := D_{1}(C) + ⋯ + D_{r}(C),

|D(C)| = ∑_{t=1}^{r} ∑_{1≤j_{1}<···<j_{t}≤r} u_{j_{1}}u_{j_{2}} ⋯ u_{j_{t}}.  (3)

In particular, if C has the form C = (c_{1}^{u}, …, c_{r}^{u}) for a fixed integer u > 0, then

|D_{t}(C)| = \binom{r}{t}u^{t} and |D(C)| = (u + 1)^{r} − 1.

Thus even though any pair of non-empty sets A, B generally satisfies A×B ≠ B ×A, the equality of the product in (3) for any two permutations of the sets on the right-hand-side of (2) is immediate, given that the c_{i} are distinct.

Lemma 2. If a composition C is perfect, then each part-size occupies a unique place in C, that is, all copies of each part-size appear in consecutive positions.

Proof. If C = (c_{1}, c_{2}, …) contains three parts c_{i}, c_{j}, c_{k} with i < j < k such that c_{i} = c_{k}, then C would generate two different compositions of m = c_{i} + c_{j}, namely (c_{i}, c_{j}) and (c_{j}, c_{k}), in contradiction of the perfection of C.

Theorem 3. A composition C of n is perfect if and only if the sequence of symbolic parts of C is a permutation of the sequence of symbolic parts of a perfect partition of n.

Proof. Let C = (c_{1}^{u_{1}}, c_{2}^{u_{2}}, …, c_{r}^{u_{r}}) with c_{j} ≠ c_{j}, i ≠ j and u_{i} > 0 for all i. Let λ be the partition obtained by arranging the parts of C in weakly increasing order.

Then C is perfect ⟺ C generates n − 1 compositions of 1, 2, …, n − 1, say C(1), …, C(n − 1) ⟺ the partitions obtained by arranging the parts of each C(j), 1 ≤ j ≤ n − 1 in increasing order are generated by λ ⟺ λ is a perfect partition of n.

This correspondence is illustrated with the perfect composition (6, 1^{2}, 3) and the underlying partition (1^{2}, 3, 6) below:

(6, 1^{2}, 3) :(1), (1^{2}), (3), (1, 3), (1^{2}, 3), (6), (6, 1), (6, 1^{2}), (6, 3), (6, 1, 3);
(1^{2}, 3, 6) :(1), (1^{2}), (3), (1, 3), (1^{2}, 3), (6), (1, 6), (1^{2}, 6), (3, 6), (1, 3, 6).

3 Enumeration aspects

Since the number of symbolic parts of a perfect partition λ is equal to the number of factors in the corresponding ordered factorization (see Equation (1)), we deduce from Theorem 3 that the number pc_{k}(n) of perfect compositions of n with k symbolic parts is given by

pc_{k}(n) = k!f(n + 1, k).  (4)

Hence the number pc(n) := ∑_{k≥1} pc_{k}(n) of all perfect compositions of n is given by

pc(n) = ∑_{k≥1} k!f(n + 1, k).  (5)

The sequence pc(n), n ≥ 0 appears as \underline{A330773} in the OEIS [9]. The initial terms below were computed using the computer algebra system Maple [6]:

1, 1, 3, 1, 5, 1, 11, 3, 5, 1, 27, 1, 5, 5, 49, 1, 27, 1, 27, 5, 5, 1, 163, 3, 5, 11, …

Note that pc(n) = 1 if and only if n + 1 is prime; the sole perfect composition is (1^{n}). It is clear from (5) that pc(n) is odd for all positive integers n.

Table 1 shows the compositions enumerated by pc(7) = 11, and how they are related to ordered factorizations and perfect partitions. Note that pc_{1}(7) = 1, pc_{2}(7) = 4 and pc_{3}(7) = 6.

Factorization Partition Compositions
8 (1^{7}) (1^{7})
2 · 4  (1, 2^{3}) (1, 2^{3}), (2^{3}, 1)
4 · 2  (1^{3}, 4) (1^{3}, 4), (4, 1^{3})
2 · 2 · 2  (1, 2, 4) (1, 2, 4), (1, 4, 2), (2, 1, 4), (2, 4, 1), (4, 1, 2), (4, 2, 1)

Table 1: Perfect partitions versus perfect compositions of 7

We highlight two interesting cases of (4) and (5), namely (i) when n is 1 less than a prime power, and (ii) when n is 1 less than a squarefree number.

(i) If p is prime, then f(p^{α}, k) equals the number of compositions of α into k parts (see, for example, [7]). Since the latter number is known to be \binom{α−1}{k−1}, we deduce from (5) that

pc(p^{α} − 1) = ∑_{k=1}^{α} k!\binom{α − 1}{k − 1}.

The sequence \{pc(p^{α} − 1)\}_{α≥1} agrees with sequence [9, \underline{A001339}] with offset 1.

(ii) If p_{1}, …, p_{r} are distinct primes, then f(p_{1}p_{2} ⋯ p_{r}, k) = k!S(r, k), where S(N, k) is the Stirling number of the second kind (see, for example, [7]). Hence

pc(p_{1}p_{2} ⋯ p_{r} − 1) = ∑_{k=1}^{r} k!^{2}S(r, k).

This is clearly the Stirling transform of (n!)^{2} and agrees with sequence [9, \underline{A064618}].

3.1 Compositions with a given number of parts

A number n has a perfect composition into k distinct parts if and only if n = 2^{k} − 1. We deduce from (4) that pc_{k}(2^{k} − 1) = k!.

More generally if n has a perfect composition into k part sizes which all appear u times, then n = (u + 1)^{k} − 1. There are k! such compositions, obtained by permuting the unique partition (1^{u}, (u + 1)^{u}, ((u + 1)^{2})^{u}, …, ((u + 1)^{k−1})^{u}). (Note that (4) is not applicable unless u + 1 is prime).

We now extend MacMahon’s result that the number g_{k} of all perfect partitions with k (actual) parts is equal to the number of compositions of k (see [4, p. 188]):

g_{k} = 2^{k−1}.  (6)

MacMahon described the following recurrence, and noted that it is the sequences of exponents of the enumerated partitions that form the compositions of k.

g_{k} = 2g_{k−1}, g_{1} = 1.

Denoting the enumerated set by G_{k}, we see that G_{1} contains the partition (1). A partition λ ∈ G_{k} gives rise to two partitions in G_{k+1} by either appending the largest part of λ or by appending a part which is greater by 1 than the sum of all the parts of λ.

For example, given G_{3} = {(1^{3}), (1^{2}, 3), (1, 2^{2}), (1, 2, 4)}, we use the recursive rule to obtain the members of G_{4}, in pairs:

G_{4} = {(1^{4}), (1^{3}, 4), (1^{2}, 3^{2}), (1^{2}, 3, 6), (1, 2^{3}), (1, 2^{2}, 6), (1, 2, 4^{2}), (1, 2, 4, 8)}.

Observe that in both G_{3} and G_{4} the exponents of the part sizes give the compositions of 3 and 4 respectively. Thus

G_{3} : (1^{3}) ↦ (3), (1^{2}, 3) ↦ (2, 1), (1, 2^{2}) ↦ (1, 2), (1, 2, 4) ↦ (1, 1, 1).

The symbolic parts of each partition fix the positions of the parts of each derived composition. For example, (1, 2, 4^{2}) ∈ G_{4} has three symbolic parts which fix the positions of the parts of (1, 1, 2). So there are as many partitions in G_{k} with j symbolic parts as compositions of k into j parts. Since their number is \binom{k−1}{j−1}, and a perfect partition gives perfect compositions by permutations of symbolic parts, the following result is proved.

Theorem 4. The number h_{k} of all perfect compositions with k parts is given by

h_{k} = ∑_{j=1}^{k} j!\binom{k − 1}{j − 1}.

For example, h_{3} = 11 enumerates the compositions

(1^{3}), (1^{2}, 3), (3, 1^{2}), (1, 2^{2}), (2^{2}, 1), (1, 2, 4), (1, 4, 2), (2, 1, 4), (2, 4, 1), (4, 1, 2), (4, 2, 1).

4 Colored perfect compositions

An n-color perfect partition of ν is one which contains one and only one n-color partition of each lesser number [2]. Thus (1_{1}^{ν}) is an n-color perfect partition for all ν, and ν = 5 has six n-color perfect partitions: (1_{1}^{5}), (1_{1}, 2_{1}^{2}), (1_{1}, 2_{2}^{2}), (1_{1}^{2}, 3_{1}), (1_{1}^{2}, 3_{2}), (1_{1}^{2}, 3_{3}).

We consider two formulas for the number P_{ν} of n-color perfect partitions of ν from Agarwal-Sachdeva [2].

P_{ν} = ∑_{λ}(product of distinct parts of λ),  (7)

where the summation runs over all ordinary perfect partitions of ν. Secondly, if F = a_{1}a_{2} ⋯ a_{k}, k ≥ 1, is an ordered factorization of ν + 1, then

P_{ν} = 1 + ∑_{F} a_{1}^{k−1}a_{2}^{k−2} ⋯ a_{k−1}, (a_{0} = 0).  (8)

We recall that an n-color composition is a composition in which a part of size n, n ≥ 1 can come in n colors denoted by subscripts n_{1}, n_{2}, …, n_{n} [1].

Definition 5. An n-color perfect composition of ν is an n-color composition C whose sequence of parts contain exactly one n-color composition of every positive integer less than ν, where the order of parts of each composition is induced by the order of the parts of C.

We enumerate n-color perfect compositions by permuting the symbolic parts of n-color perfect partitions. Let C_{ν} be the number of n-color perfect compositions of ν. Then we find, for instance, that C_{5} = 11, the enumerated objects being

(1_{1}^{5}), (1_{1}, 2_{1}^{2}), (2_{1}^{2}, 1_{1}), (1_{1}, 2_{2}^{2}), (2_{2}^{2}, 1_{1}), (1_{1}^{2}, 3_{1}), (3_{1}, 1_{1}^{2}), (1_{1}^{2}, 3_{2}), (3_{2}, 1_{1}^{2}), (1_{1}^{2}, 3_{3}), (3_{3}, 1_{1}^{2}).

Straightforward reasoning shows that (7) and (8) adapt to the following formulas. If λ is an ordinary perfect partition of ν with k ≥ 1 distinct parts, then

C_{ν} = ∑_{λ} k!(product of distinct parts of λ).  (9)

Alternatively, if F = a_{1}a_{2} ⋯ a_{k}, k ≥ 1, is an ordered factorization of ν + 1, then

C_{ν} = 1 + ∑_{F} k!a_{1}^{k−1}a_{2}^{k−2} ⋯ a_{k−1}, (a_{0} = 0).  (10)

Of course (9) is equivalent to the more direct version:

C_{ν} = ∑_{C}(product of distinct parts of C),  (11)

where the summation runs over all ordinary perfect compositions of ν.

Thanks to Maple, the sequence C_{ν}, ν ≥ 1, begins as follows (see [9, \underline{A330774}]): 1, 1, 5, 1, 11, 1, 61, 7, 15, 1, 259, 1, 19, 17, 1901, 1, 383, 1, 511, 21, …

References

[1] A. K. Agarwal, n-color compositions, Indian J. Pure Appl. Math. 31 (2000), 1421–1427.

[2] A. K. Agarwal and R. Sachdeva, Combinatorics of n-color perfect partitions, Ars Combinatoria 136 (2018), 29–43

[3] G. E. Andrews, The Theory of Partitions, Cambridge University Press, 1998.

[4] P. A. MacMahon, Combinatory Analysis, Volume 1, Cambridge University Press, 1915 [5] P. A. MacMahon, Memoir on the theory of the compositions of numbers, Philos. Trans.

Roy. Soc. London Ser. A, 184 (1893), 835–901.

[6] Maple 18. Maplesoft, a division of Waterloo Maple Inc., Waterloo, Ontario.

[7] A. O. Munagi, Labeled factorization of integers, Electron. J. Combin. 16 (2009), no. 1, Research Paper 50.

[8] J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958.

[9] N. J. A. Sloane et al., The On-Line Encyclopedia of Integer Sequences. Published electronically at https://oeis.org, 2019.

2000 Mathematics Subject Classification: Primary 05A17; Secondary 11P81, 05A15, 05A19. Keywords: partition, ordered factorization, perfect composition, n-color composition.

(Concerned with sequences: \underline{A001339}, \underline{A002033}, \underline{A064618}, \underline{A074206}, \underline{A165552}, \underline{A330773}, and \underline{A330774}.)

Received December 30 2019; revised version received May 6 2020. Published in Journal of Integer Sequences, May 7 2020.

Return to Journal of Integer Sequences home page.