Double Perfect Partitions of Higher Order

#A109 INTEGERS 25 (2025) DOUBLE PERFECT PARTITIONS OF HIGHER ORDER Augustine O. Munagi School of Mathematics, University of the Witwatersrand, Johannesburg, South Africa [email protected] Received: 1/9/25, Accepted: 11/9/25, Published: 11/25/25 Abstract A partition of a positive integer nis called double-perfect if the summands contain two partitions of every integer between 2 and n−2. In this paper we give new derivations of known results on double-perfect partitions. Then we consider generalized double-perfect partitions of nin which the summands contain two partitions of every integer between rand n−r, where 2 ≤r < n/2. Our results include explicit characterizations of double-perfect partitions of all orders and a seemingly new class of pseudo-perfect partitions that produce double-perfect partitions. We also state an inclusive enumeration formula in terms of ordered factorization functions. 1. Introduction Apartition of a positive integer nis any nondecreasing sequence of positive integers whose sum is n. The summands are called parts, and nis the weight, of the partition. Thus, a partition λof n(also expressed as λ⊢n) into kparts will be denoted by λ= (λ1, λ2, . . . , λk),0< λ1≤···≤λk or λ= (λm1 1, λm2 2, . . . , λmr r),0< λ1<· · · < λr,1≤r≤k, where midenotes the multiplicity of λifor all i. The definition of a perfect partition first appeared in the works of P. A. MacMahon [5, 6]. Subsequently other mathematicians studied and found several properties and generalizations of perfect partitions (see for example, [1, 2, 4, 7, 8]). Definition 1. Aperfect partition of nis a partition in which the parts contain exactly one partition of every positive integer less than or equal to n. DOI: 10.5281/zenodo.17711671 INTEGERS: 25 (2025) 2 For example, (13,4) ⊢7 is a perfect partition since it contains the partitions (1), (12), (13), (4),(1,4),(12,4),(13,4) with weights 1,2,...,7, respectively. There is a known bijection between the set of perfect partitions of nand the set of ordered factorizations of N=n+ 1, that is, representations of Nas ordered products of positive integers without unit factors [3, 6, 9]. For example, N= 12 has eight ordered factorizations, namely, 12,2·6,6·2,3·4,4·3,2·2·3,2·3·2,3·2·2. Let n+ 1 = a1a2···ar, ai>1, be an ordered factorization of n+ 1. Then the bijection is given by a1a2···ar−→ 1a1−1, aa2−1 1,(a1a2)a3−1,...,(a1a2···ar−1)ar−1.(1) Let f(n, k) be the number of ordered factorizations of ninto kfactors, and let the prime-power factorization of nbe n=pα1 1pα2 2···pαr r. The formula for f(n, k) is given by (see [6] or [3, p. 59]) f(n, k) = k−1 X i=0 (−1)ik ir Y j=1 αj+k−i−1 αj. We define f(n) := Pkf(n, k), where f(0) = 0 and f(1) = 1. So the formula for the number per(n) of perfect partitions of nis given by per(n) = f(n+ 1). Example 1. Table 1 shows the ordered factorizations of 6 which correspond to the perfect partitions of 5. Ordered Factorization of 6 6 2 ·3 3 ·2 Perfect Partition of 5 (15) (1,22) (12,3) Table 1: Factorizations of 6 and perfect partitions of 5 Park [8] generalized perfect partitions to “complete partitions” by removing the uniqueness condition from subpartitions, that is, contained partitions. Definition 2 (Park).A complete partition of nis a weakly increasing partition λ with λ1= 1, such that each integer m, 1≤m≤n, can be expressed as a sum of parts of λ, that is, each mcan be expressed as Pk j=1 αjλj, where αj∈ {0,1}. For example, of the 7 partitions of n= 5, four are complete partitions, namely, (15), (13,2), (12,3), (1,22). Another extension of perfect partitions was introduced by Lee [4] based on the following observation. INTEGERS: 25 (2025) 3 Lemma 1 (Lee).Let H(n, v)be the set of partitions of nthat contain exactly v partitions of m, v ≤m≤n−v, and exactly one partition of every other positive integer less than n. Then H(n, v)=∅if and only if v= 1 or v= 2. The case v= 1 gives perfect partitions. Naturally, Lee decided to study the seemingly overlooked case of v= 2. Definition 3. Adouble-perfect partition is a partition (λ1, λ2, . . . , λk)⊢nsuch that each integer m, 2≤m≤n−2, can be represented exactly twice as m=Pk i=1 αiλi, where αi∈ {0,1}. For example, (15,2) is a double-perfect partition of 7 because it contains two partitions of 2,3,4,5 and one partition of 1,6,7: (1),(12),(2),(13),(1,2),(14),(12,2),(15),(13,2),(14,2),(15,2).(2) Proposition 1 (Lee [4]).A double-perfect partition has the form (1q1,2q2,(q1+2q2−1)q3,{(q1+2q2−1)(q3+1)}q4,{(q1+2q2−1)(q3+1)(q4+1)}q5, . . .), (3) where q1≥2and q2, q3, . . . are positive integers such that q1= 3 implies q2= 1. Theorem 1 (Lee [4]).Let d(n)be the number of double-perfect partitions of a positive integer n. We have d(n) = (f(n−1) if n≡ 1 (mod 4), f(n−1) −f(n−1 4)if n≡1 (mod 4).(4) In the course of proving Theorem 1, Lee separated (3) into two forms of doubleperfect partitions λby setting q2>1 (with q1= 3) and q2= 1, as follows: λ= (13,2q2,(2(q2+ 1))q3,(2(q2+ 1)(q3+ 1))q4,...,(2(q2+ 1) ···(qk−1+ 1))qk); (5) λ= (1q1,2,(q1+ 1)q3,((q1+ 1)(q3+ 1))q4,...,((q1+ 1)(q3+ 1) ···(qk−1+ 1))qk). (6) These forms were then shown to correspond to the following ordered factorizations: n−1 = 2(q2+ 1)(q3+ 1) ···(qk−1+ 1)(qk+ 1), q2>1; (7) n−1=(q1+ 1)(q3+ 1)(q4+ 1) ···(qk−1+ 1)(qk+ 1), q1>1.(8) Notice that (7) and (8) exclude factorizations of the type n−1=2·2·(q3+ 1) ···. The number of such factorizations, f(n−1 2), is therefore subtracted from the total count in (4). INTEGERS: 25 (2025) 4 The aim of this paper is to study generalized double-perfect partitions of nthat contain two partitions of every integer between r+ 1 and n−r−1, where 1 ≤r≤ ⌊n−2 2⌋. These will be called double-perfect partitions of order r. We will first give new proofs of Theorem 1 and Proposition 1 in Section 2. Then in Section 3 we adapt the new approach to the study of double-perfect partitions of order rand characterize the first sub-class of the partitions followed by an enumeration result (Theorems 2 and 3). In Section 4 we discuss alternative methods of generating the partitions (Theorem 4). Section 5 deals with a special ordered factorization which leads to the second sub-class of double-perfect partitions of order r. Finally, we state an inclusive enumeration formula (Theorem 7). 2. New Proofs of Lee’s Results Let G(λ) be the set of nonempty subpartitions of λ⊢n. Thus, if λis complete, then G(λ) contains at least one partition of every positive integer less than or equal to n. We will show that double-perfect partitions of Narise from perfect partitions of N−2, and hence from ordered factorizations of N−1 by (1). Let Per(n) denote the set of perfect partitions of n, and let D(N) be the set of double-perfect partitions of N. Proposition 2. A double-perfect partition λ⊢N > 3may be obtained from a partition β∈Per(N−2) in two ways: I. If the multiplicity of 1 in βis 1, then insert 12into β. Denote the resulting set by E(12). II. If βdoes not contain 2 as a part, insert 2into β. Denote the resulting set by W(2). Then D(N) = E(12)∪W(2). Proof. Let h(m) be the partition of mcontained in G(β) and write λ∪γfor the partition obtained by combining the parts of two partitions λand γ. Assume that λ⊢Nis obtained from β∈Per(N−2) by insertion of 12or 2 according to I or II respectively. Then from G(β) to G(λ) we find one additional partition of each j∈ {2,3, . . . , N− 2}, namely (12)∪h(j−2) or (2)∪h(j−2). Then one new partition of each of N−1 and Nappears, that is, (12)∪h(N−3) or (2) ∪h(N−3) and (12)∪h(N−2) or (2) ∪h(N−2). INTEGERS: 25 (2025) 5 So the resulting partition λis double-perfect by definition. For example, let β= (12,3). Then from II, λ= (2) ∪β= (12,2,3), and our construction is shown in Table 2. j h(j)∈G(β)γ∈G(λ)\G(β) 1 (1) − 2 (12) ((2), h(0)) = (2) 3 (3) ((2), h(1)) = (1,2) 4 (1,3) ((2), h(2)) = (12,2) 5 (12,3) ((2), h(3)) = (2,3) 6−((2), h(4)) = (1,2,3) 7−((2), h(5)) = (12,2,3). Table 2: The construction in the proof of Proposition 2 for β= (12,3) Example 2. We illustrate Proposition 2 further by extending Table 1 to the corresponding double-perfect partitions (see Table 3). Ordered Factorization of 6 6 2 ·3 3 ·2 Per(5) (15) (1,22) (12,3) Insert Parts 2 122 Double-Perfect Partition of 7 (15,2) (13,22) (12,2,3) Table 3: Factorizations of 6 and double-perfect partitions of 7 The following corollary is equivalent to Proposition 1. Corollary 1. A double-perfect partition has one of the forms in (5) and (6). Proof. Consider an ordered factorization of the form N−1=2a2a3···ak, a2>2. From (1) the corresponding perfect partition is (1,2a2−1,(2a2)a3−1,(2a2a3)a4−1,...,(2a2a3···ak−1)ak−1).(9) Secondly, an ordered factorization of the form N−1=a1a2a3···ak, a1>2, corresponds to the perfect partition (1a1−1, aa2−1 1,(a1a2)a3−1,...,(a1a2a3···ak−1)ak−1).(10) Observe that the partitions in (9) and (10) fulfill the asserted properties of βin parts I and II of Proposition 2. Lastly, insertion of 12and 2 into these partitions restores (5) and (6) respectively (on setting ai=qi+ 1 for all i). INTEGERS: 25 (2025) 6 Proof of Theorem 1. Proposition 2 implies that d(N)=f(N−1) with the exception of certain duplicated partitions. Note that the factorizations N−1 = 2 ·2·mand N−1=4·mproduce the same double-perfect partition: N−1=2·2·m=⇒β= (1,2,4m−1)7−→ (13,2,4m−1)∈E(12) and N−1=4·m=⇒β= (13,4m−1)7−→ (13,2,4m−1)∈W(2). The number of factorizations of the form N−1 = 2·2·mis given by f(N−1 4). Thus, when N−1≡0 (mod 4), we have d(N) = f(N−1) −f(N−1 4). This completes the proof. 3. Double Perfect Partitions of Higher Order We propose the following extension of double-perfect partitions. Definition 4. Adouble-perfect partition of order ris a partition λ= (λ1, . . . , λk)⊢ Nsuch that each integer mwith r+ 1 ≤m≤N−r−1 can be represented exactly twice as m=Pk i=1 αiλi, αi∈ {0,1}, and other integers less than or equal to Ncan be uniquely represented. In particular, double-perfect partitions of order r= 1 are the original double-perfect partitions discussed above. The representation scheme of a double-perfect partition of Nof order ris 1,2, . . . , r | {z } 1 time , r + 1, r + 2, . . . , N −r−1 | {z } 2 times , N −r, N −r+ 1,...,N −1, N | {z } 1 time .(11) Let Ur(N) be the set of double-perfect partitions of Nof order rwith ur(N) = |Ur(N)|. Then (11) implies that Ur(N)=∅⇐⇒N≥2(r+ 1).(12) Let Dr(N) be the subset of Ur(N) containing partitions which may be found by insertions of (1r+1) and (r+1) into perfect partitions (thus extending the construction in Section 2 that corresponds to r= 1). Then define Er(N) := Ur(N)\Dr(N). Partitions in Dr(N) and Er(N) will also be referred to as Type-A and TypeBrespectively. The rest of this section is devoted to the characterization and enumeration of Dr(N). Properties of Er(N) will be explored in detail in Sections 4 and 5. INTEGERS: 25 (2025) 7 Theorem 2. A Type-A double-perfect partition λ⊢Nof order r > 0may be obtained from a partition β∈Per(N−r−1) in two ways: I. If the multiplicity of 1 in βis r, then insert 1r+1 into β, and denote the resulting set by A(1r+1). II. If the multiplicity of 1 in βis different from r, then insert r+ 1 into β, and denote the resulting set by B(r+ 1). Then Dr(N) = A(1r+1)∪B(r+ 1).(13) Proof. Let h(m)∈G(β),1≤m≤N−r−1. We show that any λ⊢Nobtained from I or II is double-perfect of order rby accounting for new partitions arising between G(β) and G(λ). The single partitions of 1,2, . . . , r are not affected by insertion of additional parts into β, but one new partition of each m∈ {r+ 1, r + 2, . . . , N −r−1}appears from A(1r+1) or B(r+ 1), namely, (1r+1) and (1r+1)∪h(m−r−1) or (r+ 1) and (r+1)∪h(m−r−1)), respectively. Finally we obtain one new partition of each m∈ {N−r, . . . , N}by symmetry (since G(λ) already contains partitions of j= 0,1,...,r). This shows that weights of partitions in G(λ) are distributed as in (11), as desired. Remark 1. In the proof of Theorem 2 consider the effect of inserting γ∈P(r+ 1) \ {(1r+1),(r+ 1)}into β, where r > 1. So γhas the form γ= (γ1, . . . , γk), k > 1 and γi>1 for some i. We claim that λ=γ∪βis not a Type-A double-perfect partition of order r. Assume that the multiplicity of 1 in βis x≥r. Then λwould contain at least two partitions of γiinstead of one, namely (1γi) and (γi). The case when the multiplicity of 1 in βis x < r affects only type II. Observe that already x+ 1 ∈βsince βis perfect. Thus, if 1 ∈γ, then λwould contain at least two partitions of x+ 1: (1x+1) and (x+ 1). However, if 1 /∈γwhen x<r, it is possible for λto be double perfect of order r, but not of Type-A. For example, consider N= 23, r = 5 with β= (12,3,62) and γ= (32). Then it may be verified that λ= (12,33,62)∈E5(23). A systematic method of obtaining all members of Er(N) is discussed in Section 5. Corollary 2. A Type-A double-perfect partition λ∈Dr(N)has either of the following forms: λ= (12r+1,(r+ 1)a2−1,((r+ 1)a2)a3−1,...,((r+ 1)a2a3···ak−1)ak−1),(14) λ= (1a1−1,(r+ 1), aa2−1 1,(a1a2)a3−1,(a1a2a3)a4−1,...,(a1a2···ak−1)ak−1),(15) where a1=r+ 1 and the location of r+ 1 in (15) depends on its relative size. INTEGERS: 25 (2025) 8 Proof. The two forms are consequences of converting the following ordered factorizations to perfect partitions by means of the bijection (1), and then inserting 1r+1 and r+ 1 respectively. N−r= (r+ 1)a2a3···ak; (16) N−r=a1a2a3···ak, a1=r+ 1.(17) Note that the two sets on the right-hand-side of (13) are not always disjoint as certain partitions may be obtained twice using the two methods. The following result gives the exact cardinality of Dr(N) after excluding duplicates. Theorem 3. The number dr(N)of Type-A double-perfect partitions of Nof order r, 1≤r≤ ⌊n−2 2⌋, is given by dr(N) =      f(N−r)−f(N−r 2(r+1) )−(f(r+1)−1)f(N−r r+1 )if N≡r(mod 2(r+ 1)), f(N−r)−(f(r+1)−1)f(N−r r+1 )if N≡ −1 (mod 2(r+ 1)), f(N−r)otherwise. (18) In particular when 1 ≤r≤3, we obtain d1(N)=d(N) (same as (4)); d2(N) = (f(N−2) −f(N−2 6) if N≡2 (mod 6), f(N−2) otherwise; (19) d3(N) =      f(N−3) −f(N−3 8)−f(N−3 4) if N≡3 (mod 8), f(N−3) −f(N−3 4) if N≡7 (mod 8), f(N−3) otherwise. (20) Proof. From Theorem 2, λ∈Dr(N) is obtained by inserting 1r+1 or r+ 1 into suitable perfect partitions of n=N−r−1. The latter may be constructed from the ordered factorizations of N−r; see Corollary 2. Thus, dr(N)=f(N−r) subject to the following exceptions. (i) If N−r≡0 (mod 2(r+ 1)), the factorizations N−r= (r+1)·2·mand N−r= (2(r+ 1)) ·mproduce the same λ: (r+1)·2·m=⇒(1r, r + 1,(2(r+ 1))m−1)7→ (12r+1, r + 1,(2(r+ 1))m−1) ∈A(1r+1), and (2(r+1))·m=⇒(12r+1,(2(r+1))m−1)7→ (12r+1, r+1,(2(r+1))m−1)∈B(r+1). INTEGERS: 25 (2025) 9 We remove the first type of such factorizations which is counted by f(N−r 2(r+1) ). (ia) Furthermore, since N−r≡0 (mod 2(r+ 1)) implies N−r≡0 (mod r+ 1) we isolate a set of perfect partitions that do not contribute to discovering additional λ, namely, factorizations of the form a1a2···atm, t > 1, where a1a2···at=r+ 1. Note that a1a2···atmtranslates into the perfect partition β= (1a1−1, aa2−1 1,(a1a2)a3−1,...,(a1a2···at)m−1). However, βcontains 1a1−1 but a1−1=r, so Method I does not apply. Also, βalready contains the part r+1=a1a2···at, so Method II does not apply. The number of such noncontributing perfect partitions of N−r−1 is equal to the number of ordered factorizations of r+ 1 into two or more factors times the number of ordered factorizations of (N−r)/(r+ 1), that is, (f(r+ 1) −1)f(N−r r+1 ). Parts (i) and (ia) together give the first line of the stated formula. (ii) When N−r≡r+ 1 (mod 2(r+ 1)), we obtain part (ia) independently. Hence the second line of the formula follows. There are no other exceptions. The remaining factorizations all yield valid partitions λ. Hence their number is f(N−r). Example 3. Let N= 17 with 1 ≤r≤7. The members of Dr(N) are shown in Table 4. The derivation of members of D2(17) is shown in Table 5. It may be verified that the distribution of weights of members of G(λ), for every λ∈D2(17), corresponds to the scheme (cf. (11)) 1,2 |{z} 1 time ,3,4,...,14 | {z } 2 times ,15,16,17 | {z } 1 time . r Dr(17) dr(17) 1 (13,27),(13,2,43),(13,23,8),(13,2,4,8),(115,2),(17,2,8) 6 2 (114,3),(15,34),(14,3,5) 3 3 (113,4),(1,26,4),(16,4,7) 3 4 (112,5) 1 5 (111,6),(1,25,6),(12,23,6),(13,42,6),(1,2,42,6) 5 6 (110,7) 1 7 (19,8),(1,24,8),(14,5,8) 3 Table 4: Type-A double-perfect partitions of 17 of all orders Remark 2. Note that Dr(17) = Ur(17) when r= 2, that is, Er(17) = ∅; but E2(17) = {(1,22,34)}. Hence d2(17) = 3 but u2(17) = 4 (see Example 4). INTEGERS: 25 (2025) 16 [4] H. Lee, Double perfect partitions, Discrete Math. 306 (5) (2006), 519–525. [5] P. A. MacMahon, Combinatory Analysis, Volume 1, Cambridge University Press, 1915 [6] P. A. MacMahon, The theory of perfect partitions and the compositions of multipartite numbers, Messenger Math. 20 (1891) 103–119. [7] A. O. Munagi, Perfect compositions of numbers, J. Integer Seq. 23 (2020), Article 20.5.1. [8] S. K. Park, Complete partitions, Fibonacci Quart. 36 (1998), 354–360. [9] J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958. [10] OEIS Foundation Inc. (2025), The On-Line Encyclopedia of Integer Sequences, Published electronically at https://oeis.org.