Extending a Recent Result on Hyper m-ary Partition Sequences

Timothy B. Flowers Department of Mathematics Indiana University of Pennsylvania Indiana, PA 15705 USA

                    flowers@iup.edu

Shannon R. Lockard Department of Mathematics Bridgewater State University Bridgewater, MA 02324 USA

              Shannon.Lockard@bridgew.edu

Abstract

A hyper m-ary partition of an integer n is defined to be a partition of n where each part is a power of m and each distinct power of m occurs at most m times. Let h_{m}(n) denote the number of hyper m-ary partitions of n and consider the resulting sequence. We show that the hyper m_{1}-ary partition sequence is a subsequence of the hyper m_{2}-ary partition sequence, for 2 ≤ m_{1} ≤ m_{2}.

1 Introduction

In 2004, Courtright and Sellers [2] defined a hyper m-ary partition of an integer n to be a partition of n for which each part is a power of m and each power of m occurs at most m times. They denote the number of hyper m-ary partitions of n as h_{m}(n) and showed that they satisfy the following recurrence relation:

h_{m}(mq) = h_{m}(q) + h_{m}(q − 1),  (1)
h_{m}(mq + s) = h_{m}(q), for 1 ≤ s ≤ m − 1.  (2)

Several of these hyper m-ary partition sequences can be found in the On-line Encyclopedia of Integer Sequences [7]. In particular, h_{2} is \underline{A002487}, h_{3} is \underline{A054390}, h_{4} is \underline{A277872}, and h_{5} is \underline{A277873}.

The sequence h_{2} \underline{A002487}, the hyperbinary partition sequence, is well known. It is commonly known as the Stern sequence based on Stern’s work [8]. Northshield [5] gives an extensive summary of the many uses and applications of \underline{A002487}. Calkin and Wilf [1] also studied h_{2}, outlining a connection between this sequence and a sequence of fractions they defined and used to give an enumeration of the rationals. Since then, several authors have studied similar restricted binary and m-ary partition functions; see [3, 4, 6] for additional examples.

In this paper, we will be analyzing hyper m-ary partitions of n while also considering the base m representation of n. Thus, it will be convenient to have clear and distinct notation. In particular, for m ≥ 2, let (n_{r}, n_{r−1}, …, n_{1}, n_{0})_{m} be the base m representation of positive integer n where 0 ≤ n_{i} < m, n_{r} ≠ 0, and n = ∑_{i=0}^{r} n_{i}m^{i}. Also, for 2 ≤ m_{1} < m_{2} and n = (n_{r}, n_{r−1}, …, n_{1}, n_{0})_{m_{1}}, we define a change of base function, F_{m_{1},m_{2}}(n) = (n_{r}, n_{r−1}, …, n_{1}, n_{0})_{m_{2}}.

Next, we write a hyper m-ary partition of n as [x_{r}, x_{r−1}, …, x_{1}, x_{0}]_{m} where 0 ≤ x_{i} ≤ m and n = ∑_{i=0}^{r} x_{i}m^{i}. Here, we may allow any of the x_{i} to be 0 so that each hyper m-ary partition of n is the same length r as the base m representation of n. Furthermore, let H_{m}(n) be the set of all distinct hyper m-ary partitions of n. Observe that h_{m}(n) is the cardinality of this set.

Recently, the authors gave an identity relating h_{2} to h_{3} and then generalized this identity to show that h_{2} is a subsequence of h_{m} for any m [4]. This result involved giving a bijection between H_{2}(ℓ) and H_{m}(k), where k = F_{2,m}(ℓ). In this note, the authors will follow a similar process to show that h_{m_{1}} is a subsequence of h_{m_{2}}, for 2 ≤ m_{1} ≤ m_{2}.

2 A preliminary example

Consider the integer 37 = (1, 1, 0, 1)_{3} and use the change of base function to find the integer with the same digits in base 4. In particular, F_{3,4}(37) = (1, 1, 0, 1)_{4} = 81. Now consider the hyper 3-ary partitions of 37 and the hyper 4-ary partitions of 81.

\begin{aligned}37 & = & 1 · 3^{3} + 1 · 3^{2} + 1 · 3^{0} \\ & = & 1 · 3^{3} + 3 · 3^{1} + 1 · 3^{0} \\ & = & 3 · 3^{2} + 3 · 3^{1} + 1 · 3^{0} \end{aligned}  \begin{aligned}81 & = & 1 · 4^{3} + 1 · 4^{2} + 1 · 4^{0} \\ & = & 1 · 4^{3} + 4 · 4^{1} + 1 · 4^{0} \\ & = & 4 · 4^{2} + 4 · 4^{1} + 1 · 4^{0} \end{aligned}

Adopting the notation for hyper m-ary partitions and the sets of these partitions, rewrite these partitions in the following way:

H_{3}(37) = { [1, 1, 0, 1]_{3}, [1, 0, 3, 1]_{3}, [0, 3, 3, 1]_{3} };
H_{4}(81) = { [1, 1, 0, 1]_{4}, [1, 0, 4, 1]_{4}, [0, 4, 4, 1]_{4} } .

Note that the number of hyper 3-ary partitions of 37 is the same as the number of hyper 4-ary partitions of 81. In other words,

h_{3}(37) = h_{4} (F_{3,4}(37)) = h_{4}(81) .

We also observe that the coefficients of the partitions are similar, indicating that there is a relationship between the partitions in each set. This relationship will be further explored in the next section.

3 Bijections between hyper m-ary partitions and hyper (m + 1)-ary partitions

We now verify the result suggested by the example in the prior section by considering hyper m-ary partitions of an integer ℓ and the hyper (m + 1)-ary partitions of k = F_{m,m+1}(ℓ).

Lemma 1. For a positive integer ℓ, let k = F_{m,m+1}(ℓ). Define g_{m} : H_{m+1}(k) → H_{m}(ℓ) by mapping

[c_{r}, c_{r−1}, …, c_{2}, c_{1}, c_{0}]_{m+1} ↦ [b_{r}, b_{r−1}, ⋯, b_{2}, b_{1}, b_{0}]_{m}

according to the following rules:

c_{i} = 0 ⟶ b_{i} = 0
c_{i} = 1 ⟶ b_{i} = 1
⋮
c_{i} = m − 2 ⟶ b_{i} = m − 2
c_{i} = m − 1 ⟶ b_{i} = m − 1
c_{i} = m ⟶ b_{i} = m − 1
c_{i} = m + 1 ⟶ b_{i} = m.

Then g_{m} is a bijection.

Proof. It is clear from the definition that g_{m} is a function. So we first show that g_{m} is oneto-one. Suppose x = [x_{r}, x_{r−1}, … x_{2}, x_{1}, x_{0}]_{m+1} and y = [y_{r}, y_{r−1}, … y_{2}, y_{1}, y_{0}]_{m+1} are two hyper (m + 1)-ary partitions of k such that x ≠ y. Then there must be at least one digit that doesn’t match. Let J = {j_{1}, j_{2}, …, j_{n}} be the set of indices such that x_{j} ≠ y_{j}. Then we have two cases.

First suppose without loss of generality that there is an index j such that x_{j} ∉ {m−1, m}. Then the j^{th} digit of g_{m}(x) will be different than the j^{th} digit of g_{m}(y). Thus g_{m}(x) ≠ g_{m}(y).

Now suppose that x_{j} ∈ {m − 1, m} and y_{j} ∈ {m − 1, m} for all j ∈ J. Let J_{1} = {j ∈ J : x_{j} = m − 1} and J_{2} = {j ∈ J : x_{j} = m}. Note that y_{j} = m for all j ∈ J_{1} and y_{j} = m − 1 for all j ∈ J_{2}. Also observe that

x = ∑_{j∉J} x_{j}m^{j} + ∑_{j∈J_{1}}(m − 1)m^{j} + ∑_{j∈J_{2}} m · m^{j}
y = ∑_{j∉J} y_{j}m^{j} + ∑_{j∈J_{1}} m · m^{j} + ∑_{j∈J_{2}}(m − 1)m^{j}.

Since x_{j} = y_{j} for all j ∉ J,

x − y = ∑_{j∈J_{1}}(m − 1 − m)m^{j} + ∑_{j∈J_{2}}(m − m + 1)m^{j}
= ∑_{j∈J_{2}} m^{j} − ∑_{j∈J_{1}} m^{j}.

Observe that x − y = 0 since x and y are two different hyper (m + 1)-ary partitions of the same number k, implying

∑_{j∈J_{2}} m^{j} − ∑_{j∈J_{1}} m^{j} = 0.

However, since J_{1} and J_{2} are disjoint, this is impossible. Thus it must be the case that when x ≠ y, one of x_{j} or y_{j} must be outside of {m − 1, m} so that g_{m}(x) ≠ g_{m}(y) as seen above. Thus g_{m} is one-to-one.

To show that g_{m} is onto, consider b = [b_{r}, b_{r−1}, ⋯, b_{2}, b_{1}, b_{0}]_{m} ∈ H_{m}(ℓ). We then define c = [c_{r}, c_{r−1}, ⋯, c_{2}, c_{1}, c_{0}]_{m+1} in the following way. If b_{i} ∈ {0, 1, 2, …, m − 3, m − 2}, then set c_{i} = b_{i} and if b_{i} = m, set c_{i} = m + 1. Now suppose b_{i} = m − 1. Let v be the minimal index with v < i such that b_{v} ≠ m − 1. If v does not exist, then set c_{i} = m − 1. If v does exist with b_{v} = m, then set c_{i} = m. If v exists with b_{v} ∈ {0, 1, 2, …, m − 2}, then set c_{i} = m − 1. Notice that we may verify that c ∈ H_{m+1}(k) by converting c into the base m + 1 representation of k. Therefore b is the image of c under g_{m} and thus g_{m} is onto.

This bijection implies that the number of m-ary partitions of any integer ℓ is the same as the number of (m + 1)-ary partitions of F_{m,m+1}(ℓ).

4 Hyper m_{1}-ary partitions and hyper m_{2}-ary partitions

In this section, we use the result of Lemma 1 to define a more general bijection between H_{m_{1}}(n) and H_{m_{2}}(F_{m_{1},m_{2}}(n)) for m_{2} > m_{1} + 1. To do this, we need the following lemma about hyper m_{2}-ary partitions of an integer n.

In the following proof, observe that multiplying a partition [x_{r}, x_{r−1}, ⋯, x_{2}, x_{1}, x_{0}]_{m} by m corresponds to shifting the coefficients to the left one place and adding an additional 0 as the last coefficient.

Lemma 2. Let m_{2} > m_{1} + 1. If the base m_{2} representation of an integer n contains only digits from the set {0, 1, 2, …, m_{1} − 1}, then there are no hyper m_{2}-ary partitions of n which use any of the coefficients m_{1}, m_{1} + 1, …, m_{2} − 2.

Proof. We will prove this by induction on n. Assume that for all q < n, when the base m_{2} representation of q contains only digits from the set {0, 1, 2, …, m_{1} − 1}, then there are no hyper m_{2}-ary partitions of n which use any of the coefficients m_{1}, m_{1} + 1, …, m_{2} − 2.

First, consider when n = m_{2}q and suppose that in base m_{2} the digits of n come from the set {0, 1, 2, …, m_{1} − 1}. This means the digits in the base m_{2} representation of q also come only from this set. Now, apply the recurrence (1) to write h_{m_{2}}(m_{2}q) = h_{m_{2}}(q) + h_{m_{2}}(q − 1). This implies that every hyper m_{2}-ary partition of n is obtained from either a hyper m_{2}-ary partition of q or a hyper m_{2}-ary partition of q − 1.

Observe that a hyper m_{2}-ary partition of n obtained from a hyper m_{2}-ary partition of q is found by multiplying the latter partition by m_{2}, thereby shifting the coefficients of q and appending a 0 at the end. This results in hyper m_{2}-ary partitions of n whose coefficients are the same as the coefficients of hyper m_{2}-ary partitions of q, along with an additional 0. Similarly, a hyper m_{2}-ary partition of n that is obtained from a hyper m_{2}-ary partition of q − 1 is found by shifting the digits of the latter partition and appending an m_{2} to the end. This means we may write

H_{m_{2}}(n) = {[x_{r}, x_{r−1}, ⋯, x_{2}, x_{1}, x_{0}, 0]_{m_{2}} : [x_{r}, x_{r−1}, ⋯, x_{2}, x_{1}, x_{0}]_{m_{2}} ∈ H_{m_{2}}(q)}

∪ {[x_{r}, x_{r−1}, ⋯, x_{2}, x_{1}, x_{0}, m_{2}]_{m_{2}} : [x_{r}, x_{r−1}, ⋯, x_{2}, x_{1}, x_{0}]_{m_{2}} ∈ H_{m_{2}}(q − 1)} .

Since q − 1 and q are less than n, by the induction hypothesis we know the coefficients of all hyper m_{2}-ary partitions of q − 1 and q are from the set {0, 1, 2, …, m_{1} − 1, m_{2} − 1, m_{2}}. Thus, the coefficients of any hyper m_{2}-ary partition of n are also from this set.

Now assume that n = m_{2}q + s, where 1 ≤ s ≤ m_{2} − 1. Observe that since the base m_{2} representation of n contains only digits from the set {0, 1, 2, …, m_{1} − 1}, then we must have 1 ≤ s ≤ m_{1} − 1. Furthermore, when n = m_{2}q + s, apply the recurrence (2) to conclude that a hyper m_{2}-ary partition of n is obtained from a hyper m_{2}-ary partition of q by multiplying the latter partition by m_{2} and appending s to the end, where 1 ≤ s ≤ m_{1} − 1. So,

H_{m_{2}}(n) = {[x_{r}, x_{r−1}, ⋯, x_{2}, x_{1}, x_{0}, s]_{m_{2}} : [x_{r}, x_{r−1}, ⋯, x_{2}, x_{1}, x_{0}]_{m_{2}} ∈ H_{m_{2}}(q)} .

Since q < n, the coefficients of all hyper m_{2}-ary partitions of q are in the set {0, 1, 2, …, m_{1}− 1, m_{2} − 1, m_{2}}. Since s is an element of this set, we conclude that the coefficients of hyper m_{2}-ary partitions of n come from the same set.

Therefore, in all cases, the hyper m_{2}-ary partitions of n never contain any of the coefficients m_{1}, m_{1} + 1, …, m_{2} − 2.

Now we are ready to prove there is a bijection between hyper m_{1}-ary partitions of an integer ℓ and hyper m_{2}-ary partitions of k = F_{m_{1},m_{2}}(ℓ).

Lemma 3. Let ℓ be a positive integer and set k = F_{m_{1},m_{2}}(ℓ). Define ϕ : H_{m_{2}}(k) → H_{m_{1}}(ℓ) by mapping

[c_{r}, c_{r−1}, …, c_{2}, c_{1}, c_{0}]_{m_{2}} ↦ [b_{r}, b_{r−1}, ⋯, b_{2}, b_{1}, b_{0}]_{m_{1}}

according to the following rules:

c_{i} = 0 ⟶ b_{i} = 0
c_{i} = 1 ⟶ b_{i} = 1
⋮
c_{i} = m_{1} − 1 ⟶ b_{i} = m_{1} − 1
c_{i} = m_{2} − 1 ⟶ b_{i} = m_{1} − 1
c_{i} = m_{2} ⟶ b_{i} = m_{1}.

Then, ϕ is a bijection.

Proof. If m_{2} = m_{1} + 1, then the result follows immediately from Lemma 1. So, we assume that m_{2} > m_{1}+1. From the definition of k, we know the base m_{2} representation of k includes only digits less than or equal to m_{1} − 1. So, we apply Lemma 2 to conclude that none of the hyper m_{2}-ary partitions in H_{m_{2}}(k) have any coefficients between m_{1} and m_{2} − 2, inclusive. Thus, ϕ need only specify how to map coefficients from the set {0, 1, …, m_{1} −1, m_{2} −1, m_{2}}.

Now, using the bijection g_{m} given in Lemma 1, define a new function G : H_{m_{2}}(k) → H_{m_{1}}(ℓ) as follows:

G = g_{m_{1}} ∘ g_{m_{1}+1} ∘ g_{m_{1}+2} ∘ ⋯ ∘ g_{m_{2}−2} ∘ g_{m_{2}−1} .

It is clear from Lemma 1 that when we apply G to any m_{2}-ary partition coefficient which is less than or equal to m_{1} − 1, the coefficient maps to itself. When we apply G to a partition coefficient of m_{2} − 1, we see that

m_{2} − 1 ⟼^{g_{m_{2}−1}} m_{2} − 2 ⟼^{g_{m_{2}−2}} m_{2} − 3 ⟼^{g_{m_{2}−3}} ⋯ ⟼^{g_{m_{1}}} m_{1} − 1 .

Finally, when we apply G to a partition coefficient of m_{2}, we see that

m_{2} ⟼^{g_{m_{2}−1}} m_{2} − 1 ⟼^{g_{m_{2}−2}} m_{2} − 2 ⟼^{g_{m_{2}−3}} ⋯ ⟼^{g_{m_{1}}} m_{1} .

Thus, G = ϕ.

We have ϕ equal to a finite composition of bijective functions. Therefore, ϕ is a bijection.

Lemma 3 leads to the following identity between values of h_{m_{1}} and h_{m_{2}}.

Theorem 4. Let 2 ≤ m_{1} < m_{2}. For positive integer ℓ, set k = F_{m_{1},m_{2}}(ℓ). Then

h_{m_{2}}(k) = h_{m_{1}}(ℓ).

Proof. The values ℓ and k given here match Lemma 3 and we know that h_{m_{1}}(ℓ) = |H_{m_{1}}(ℓ)| and h_{m_{2}}(k) = |H_{m_{2}}(k)|. Lemma 3 gives a bijection between these finite sets. Therefore, we conclude that the sets must have the same cardinality.

As an immediate corollary, we now state a final result regarding the relationships between hyper m-ary partition sequences for different values of m.

Corollary 5. Let 2 ≤ m_{1} ≤ m_{2}. Then h_{m_{1}} is a subsequence of h_{m_{2}}.

These theorems extend the results in [4], ultimately showing that the subsequence identity holds for any hyper m_{1}-ary and hyper m_{2}-ary partition sequences.

5 Acknowledgments

The authors wish to thank the referee for insightful comments and suggestions. This feedback helped us clarify the notation and improved the overall quality of the paper.

References

[1] N. Calkin and H. Wilf, Recounting the rationals, Amer. Math. Monthly 107 (2000), 360–363.

[2] K. Courtright and J. Sellers, Arithmetic properties for hyper m-ary partition functions, Integers 4 (2004), A6.

[3] J. Eom, G. Jeong, and J. Sohn, Three different ways to obtain the values of hyper m-ary partition functions, Bull. Korean Math. Soc. 53 (2016), 1857–1868.

[4] T. B. Flowers and S. R. Lockard, Identifying an m-ary partition identity through an m-ary tree, Integers 16 (2016), A10.

[5] S. Northshield, Stern’s diatomic sequence 0, 1, 1, 2, 1, 3, 2, 3, 1, 4, …, Amer. Math. Monthly 117 (2010), 581–598.

[6] B. Reznick, Some binary partition functions, in B. Berndt, ed., Analytic Number Theory: Proceedings of a Conference in Honor of Paul T. Bateman, Birkhäuser, 1990, pp. 451– 477.

[7] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences. Published electronically

   at http://oeis.org, 2017.

[8] M. A. Stern, Über eine zahlentheoretische Funktion, J. Reine Angew. Math. 55 (1858), 193–220.

2010 Mathematics Subject Classification: Primary 05A17. Keywords: integer partition, hyper m-ary partition.

(Concerned with sequences \underline{A002487}, \underline{A054390}, \underline{A277872}, and \underline{A277873}.)

Received June 30 2016; revised versions received February 9 2017; June 13 2017; June 23 2017. Published in Journal of Integer Sequences, July 1 2017. Minor revision, July 30 2017.

Return to Journal of Integer Sequences home page.