Polynomial Analogues of Restricted b-ary Partition Functions

Karl Dilcher^{1} Department of Mathematics and Statistics Dalhousie University Halifax, Nova Scotia B3H 4R2 Canada

                dilcher@mathstat.dal.ca

Larry Ericksen P. O. Box 172 Millville, NJ 08332-0172 USA

                   LE22@cornell.edu

Abstract

Given an integer b ≥ 2, a well studied concept of a b-ary partition function of a positive integer n counts the number of representations of n as sums of powers of b, with each power occurring up to λ times, for a fixed λ ≥ 1. In this paper we introduce and study a multivariable polynomial sequence that reduces to the restricted b-ary partition function when all variables are taken to be 1. In particular, we show that this polynomial sequence characterizes all restricted b-ary partitions for each n, generalizing previous results on hyperbinary and hyper b-ary representations. All this follows from considering more general concepts of restricted b-ary partition functions.

1Research supported in part by the Natural Sciences and Engineering Research Council of Canada, Grant # 145628481.

1 Introduction

The (unrestricted) binary partition function, which we shall denote by S_{2}(n), counts the number of representations of a positive integer n as a sum of powers of 2. This function was apparently first considered by Euler [14, pp. 162ff.] and later by other authors, including Churchhouse [4] who studied congruence properties of S_{2}(n). Reznick [20] later investigated the following restricted binary partition function. Given an integer λ ≥ 1, let S_{2}^{λ}(n) denote the number of representations

n = ∑_{j≥0} c_{j}2^{j},  c_{j} ∈ {0, 1, …, λ}.  (1)

In particular, we have S_{2}^{1}(n) = 1 since λ = 1 corresponds to the unique binary representation of n, and S_{2}^{2}(n) = s(n + 1), where {s(n)} is the well-known Stern sequence; see [20, p. 470].

As an easy example, we consider n = 6. Then the binary partitions are

4 + 2, 4 + 1 + 1, 2 + 2 + 2, 2 + 2 + 1 + 1, 2 + 1 + 1 + 1 + 1, 1 + 1 + 1 + 1 + 1 + 1.

Hence S_{2}(6) = 6, and S_{2}^{2}(6) = 3 = s(7), this latter number counting the hyperbinary representations 4 + 2, 4 + 1 + 1, and 2 + 2 + 1 + 1.

We can generalize (1) to an arbitrary integer base b ≥ 2 and consider the number of representations

n = ∑_{j≥0} c_{j}b^{j},  c_{j} ∈ {0, 1, …, λ},  (2)

which we denote by S_{b}^{λ}(n). Analogously, S_{b}(n) denotes the number of unrestricted b-ary partitions, and we can write S_{b}(n) = lim_{λ→∞} S_{b}^{λ}(n).

It appears that the function S_{b}(n) was first studied by Mahler [15] who derived an asymptotic formula, then later by other authors, including Churchhouse [4], Rödseth [21], and Andrews [1], who were mainly interested in congruence properties of the function S_{b}(n). The restricted b-ary partition function S_{b}^{λ}(n) was apparently first studied by Dumont et al. [13, Section 6].

As in the case b = 2, the function S_{b}^{b−1}(n) counts the unique b-adic representation of n, and is therefore always equal to 1, and S_{b}^{b}(n) counts the number of hyper b-ary expansions of n, also known as base b over-expansions of n. Defant [6] showed that S_{b}^{b}(n) = s_{b}(n+1), where {s_{b}(n)} is the base-b generalized Stern sequence; this is therefore a direct generalization of Reznick’s result cited after (1). It should also be noted that for b ≥ 3 and 1 ≤ λ < b − 1, we have S_{b}^{λ}(n) = 0 for infinitely many n; see Section 6 for some examples.

In a different direction, the present authors studied the special case λ = b, first for b = 2, i.e., the case of hyperbinary representations. Results of Bates and Mansour [2] and of Stanley and Wilf [22], which are refinements of the Stern identity S_{2}^{2}(n) = s(n + 1), were further refined in [9] by the introduction of a two-variable (generalized Stern) polynomial sequence that characterizes all hyperbinary representations of n counted by S_{2}^{2}(n). This was subsequently extended in [10] to hyper b-ary expansions, i.e., those expansions of the type (1) that are counted by S_{b}^{b}(n) for an arbitrary integer base b ≥ 2. Further properties of these b-variable polynomials were then derived in [11].

It is the purpose of the present paper to use the methods developed in [9]–[11] to define and investigate polynomial analogues of the restricted b-ary partition function S_{b}^{λ}(n) for any integer b ≥ 2 and primarily for λ ≥ b − 1. In the process we investigate a more generalized restricted b-ary partition function and its polynomial analogue.

There is no established notation in the literature for binary and b-ary restricted or unrestricted partition functions. We chose the notation S_{b}^{λ}(n), resp. S_{b}(n), in order to avoid clashes with notations of other objects. It should also be noted that many authors used the letter m to denote a general integer base, while we are using b and “b-ary”.

This paper is structured as follows. In Section 2 we define our principal objects of study, namely the polynomial analogues to the restricted b-ary partition function, and state the main representation theorem. In Section 3 we prove recurrence relations for the polynomials in question and consider a number of special cases. The proof of our main theorem is then given in Section 4, and in Section 5 we derive explicit formulas for our polynomials. We conclude this paper with some further remarks in Section 6.

2 Generating functions and main theorem

It is a well-known fact that partitions, including binary and b-ary partitions, are closely related to generating functions which are usually expressed in the form of infinite products. Indeed, it follows from (2) and the definition of S_{b}^{λ}(n) that

∑_{n=0}^{∞} S_{b}^{λ}(n)ζ^{n} = ∏_{j=0}^{∞} (1 + ζ^{b^{j}} + ζ^{2·b^{j}} + ⋯ + ζ^{λ·b^{j}}) .  (3)

This can be seen by expanding the right-hand side of (3) and equating coefficients of ζ^{n}; see also [13, p. 381], or [20, p. 454] for b = 2. A special case of (3) is the case λ = b, where S_{b}^{b}(n) counts the number of hyper b-ary expansions; see [5]. Since S_{b}^{b}(n) = s_{b}(n + 1), as noted in the Introduction, the generating function (3) immediately gives

∑_{n=0}^{∞} s_{b}(n)ζ^{n} = ζ ∏_{j=0}^{∞} (1 + ζ^{b^{j}} + ζ^{2·b^{j}} + ⋯ + ζ^{b·b^{j}}) ,  (4)

where s_{b}(n) is the b-ary Stern sequence; see also [6]. More recently the current authors introduced a b-variable polynomial analogue of the sequence s_{b}(n) in [10] and showed that it characterizes all s_{b}(n + 1) hyper b-ary representations of n. These polynomials can be seen as b-ary generalized Stern polynomials; they were defined by way of recurrence relations generalizing those in [5] and [6], and the corresponding generating function was obtained in the subsequent paper [11]. These polynomials, written here in the slightly different notation ω_{b,T} (n, Z), have integer parameters T = (t_{1}, …, t_{b}) and variables Z = (z_{1}, …, z_{b}), and satisfy

∑_{n=1}^{∞} ω_{b,T} (n; Z)ζ^{n} = ζ ∏_{j=0}^{∞} (1 + z_{1}^{t_{1}^{j}}ζ^{b^{j}} + z_{2}^{t_{2}^{j}}ζ^{2·b^{j}} + ⋯ + z_{b}^{t_{b}^{j}}ζ^{b·b^{j}}) .  (5)

When we compare (4) and (5), it is clear that ω_{b,T} (n; 1, …, 1) = s_{b}(n), independent of the b-tuple T.

We now use (5) as the basis for the definitions of the main objects of study in this paper.

Definition 1. Let b ≥ 2 and λ ≥ 1 be integers, T = (t_{1}, …, t_{λ}) be a λ-tuple of positive integer parameters, and Z = (z_{1}, …, z_{λ}) a λ-tuple of variables. Then we define the sequence of λ-variable polynomials ω_{b,T}^{λ} (n; Z) by the generating function

∑_{n=1}^{∞} ω_{b,T}^{λ} (n; Z)ζ^{n} = ζ ∏_{j=0}^{∞} (1 + z_{1}^{t_{1}^{j}}ζ^{b^{j}} + z_{2}^{t_{2}^{j}}ζ^{2·b^{j}} + ⋯ + z_{λ}^{t_{λ}^{j}}ζ^{λ·b^{j}}) .  (6)

We immediately see that for λ = b this last identity reduces to (5), and for Z = (1, …, 1) it reduces to (4). Therefore we have for any b ≥ 2, λ ≥ 1 and for any T and indices n ≥ 0 that

ω_{b,T}^{b} (n; Z) = ω_{b,T} (n; Z),  (7)
ω_{b,T}^{λ} (n; 1, …, 1) = S_{b}^{λ}(n − 1).  (8)

By expanding the right-hand side of (6) for a given b ≥ 2 and λ ≥ 1, one can easily write down the first few polynomials ω_{b,T}^{λ} (n; Z). For instance, those for b = 3 and λ = 4 are shown in Table 1, where for greater ease of writing we have set Z = (w, x, y, z) and T = (q, r, s, t).

We recall that the partition function S_{b}^{λ}(n) counts the number of b-ary partitions with each power of b occurring at most λ times, and we will see that ω_{b,T}^{λ} (n; Z) characterizes all these partitions. It turns out that without too much additional effort we can do the same with b-ary partitions whose powers of b, if they occur, can only have multiplicities v from an ordered set of λ integers, V = (v_{1}, v_{2}, …, v_{λ}), where λ ≥ 1 and 1 ≤ v_{1} < v_{2} < ⋯ < v_{λ}. As a consequence we can give a more general definition.

\begin{matrix}n & ω_{3,T}^{4} (n; w, x, y, z) & n & ω_{3,T}^{4} (n; w, x, y, z) \\ 0 & 0 & 10 & w^{q^{2}} + x^{r}y + y^{s} \\ 1 & 1 & 11 & w^{1+q^{2}} + wy^{s} + x^{r}z \\ 2 & w & 12 & w^{q^{2}}x + xy^{s} \\ 3 & x & 13 & w^{q+q^{2}} + w^{q^{2}}y + y^{1+s} + z^{t} \\ 4 & w^{q} + y & 14 & w^{1+q+q^{2}} + w^{q^{2}}z + y^{s}z + wz^{t} \\ 5 & w^{1+q} + z & 15 & w^{q+q^{2}}x + xz^{t} \\ 6 & w^{q}x & 16 & w^{q^{2}}x^{r} + w^{q+q^{2}}y + yz^{t} \\ 7 & x^{r} + w^{q}y & 17 & w^{1+q^{2}}x^{r} + w^{q+q^{2}}z + z^{1+t} \\ 8 & wx^{r} + w^{q}z & 18 & w^{q^{2}}x^{1+r} \\ 9 & x^{1+r} & 19 & x^{r^{2}} + w^{q^{2}}x^{r}y + w^{q^{2}}y^{s} \end{matrix} ; Table 1: ω_{3,T}^{4} (n; w, x, y, z), T = (q, r, s, t), 0 ≤ n ≤ 19.

Definition 2. Let b, λ, T and Z be as in Definition 1, and let V = (v_{1}, …, v_{λ}) be a strictly increasing finite sequence of positive integers. Then we define the sequence of λ-variable polynomials ω_{b,T}^{V} (n; Z) by the generating function

∑_{n=1}^{∞} ω_{b,T}^{V} (n; Z)ζ^{n} = ζ ∏_{j=0}^{∞} (1 + z_{1}^{t_{1}^{j}}ζ^{v_{1}b^{j}} + z_{2}^{t_{2}^{j}}ζ^{v_{2}b^{j}} + ⋯ + z_{λ}^{t_{λ}^{j}}ζ^{v_{λ}b^{j}}) .  (9)

Obviously, when V = (1, 2, …, λ), then ω_{b,T}^{V} (n; Z) = ω_{b,T}^{λ} (n; Z). Also, in analogy to S_{b}^{λ}(m), we define S_{b}^{V} (m) below. As before, let V = (v_{1}, v_{2}, …, v_{λ}) be an ordered set of integers with 1 ≤ v_{1} < ⋯ < v_{λ}, and define

ℍ_{b}^{V} (m) := {m = ∑_{j≥0} c_{j}b^{j} |c_{j} ∈ {0, v_{1}, …, v_{λ}} = {0} ∪ V } ,  (10)

i.e., the set of restricted b-ary partitions of m, where a power of b either does not occur, or occurs v_{1} times, or v_{2} times, …, or v_{λ} times. If we then define its cardinality as

S_{b}^{V} (m) := #ℍ_{b}^{V} (m),  (11)

then we have, in analogy to (8),

ω_{b,T}^{V} (n; 1, …, 1) = S_{b}^{V} (n − 1),  n = 1, 2, …  (12)

We illustrate the objects defined in (9) and (10) with an example.

Example 3. Let b = 2, V = (1, 3, 4), and n = 10. Then the representations of m = n−1 = 9 given by (10) are

8 + 1, 4 + 2 + 1 + 1 + 1, 2 + 2 + 2 + 1 + 1 + 1, 2 + 2 + 2 + 2 + 1.  (13)

Meanwhile, expansion of the right-hand side of (9) gives, with T = (r, s, t) and Z = (x, y, z), the λ = 3 variable polynomial

ω_{2,T}^{V} (10; Z) = x^{1+r^{3}} + x^{r+r^{2}}y + y^{1+s} + xz^{t}.  (14)

We juxtapose the S_{2}^{V} (9) = 4 representations in (13) and the four monomials in (14) as follows:

\begin{aligned}x^{1+r^{3}} & ⟷ & 1 · 2^{0} + 1 · 2^{3}, \\ x^{r+r^{2}}y & ⟷ & 1 · 2^{1} + 1 · 2^{2} + 3 · 2^{0}, \\ y^{1+s} & ⟷ & 3 · 2^{0} + 3 · 2^{1}, \\ xz^{t} & ⟷ & 1 · 2^{0} + 4 · 2^{1}. \end{aligned}

This one-to-one correspondence is a special case of the following theorem, which is the main result of this paper.

Theorem 4. Let b ≥ 2 and λ ≥ 1 be integers, T = (t_{1}, …, t_{λ}) a λ-tuple of positive integer parameters, and V = (v_{1}, …, v_{λ}) an ordered set of strictly increasing positive integers. Then for any integer m ≥ 1 we have

ω_{b,T}^{V} (m + 1; z_{1}, …, z_{λ}) = ∑_{h∈ℍ_{b}^{V} (m)} z_{1}^{p_{h,1}(t_{1})} ⋯ z_{λ}^{p_{h,λ}(t_{λ})},  (15)

where, for each h ∈ ℍ_{b}^{V} (m), the exponents p_{h,1}(t_{1}), …, p_{h,λ}(t_{λ}) are polynomials with only 0 and 1 as coefficients. Furthermore, if for 1 ≤ i ≤ λ we write

p_{h,i}(t_{i}) = t_{i}^{τ_{i}(1)} + t_{i}^{τ_{i}(2)} + ⋯ + t_{i}^{τ_{i}(μ_{i})}, 0 ≤ τ_{i}(1) < ⋯ < τ_{i}(μ_{i}), μ_{i} ≥ 0,  (16)

then the powers that are used exactly v_{i} times in the b-ary partition h are

b^{τ_{i}(1)}, b^{τ_{i}(2)}, …, b^{τ_{i}(μ_{i})}.  (17)

If μ_{i} = 0 in (16), we set p_{h,i}(t_{i}) = 0 by convention, and accordingly (17) is the empty set.

In the special case λ = b and V = (1, 2, …, b), Theorem 4 reduces to Theorem 11 in [10], which characterizes all hyper b-ary representations of m. In the case b = 2, λ = 3, and V = (1, 3, 4), Theorem 4 explains the correspondence given at the end of Example 3.

For the proof of Theorem 4 we need recurrence relations for the polynomials ω_{b,T}^{V} (n; Z), which are established in the next section.

3 Recurrence relations

As we saw in Section 2, the restricted b-ary partition functions S_{b}^{λ}(n − 1) and S_{b}^{V} (n − 1) can be seen as generalizations of the b-ary Stern sequence s_{b}(n) in (4), and the polynomials ω_{b,T}^{λ} (n; Z) and ω_{b,T}^{V} (n; Z) can be seen as further generalizations of the b-ary generalized Stern polynomials ω_{b,T} (n; Z). In order to put the results in this section into perspective, we quote the recurrence relation s_{b}(0) = 0, s_{b}(1) = 1, and for n ≥ 1,

s_{b}(bn − j) = s_{b}(n) (j = 0, 1, …, b − 2),  (18)
s_{b}(bn + 1) = s_{b}(n) + s_{b}(n + 1);  (19)

see [10] (or [5], where the sequence is shifted by 1). The case b = 2 in (18), (19) gives the recurrence for the well-known Stern (diatomic) sequence.

The polynomials ω_{b,T} (n; Z), where T = (t_{1}, …, t_{b}) and Z = (z_{1}, …, z_{b}), were shown in [10] to satisfy the recurrence relations ω_{b,T} (0; Z) = 0, ω_{b,T} (1; Z) = 1, and for n ≥ 1,

ω_{b,T} (b(n − 1) + j + 1; z_{1}, …, z_{b}) = z_{j} ω_{b,T} (n; z_{1}^{t_{1}}, …, z_{b}^{t_{b}}) (1 ≤ j ≤ b − 1),  (20)
ω_{b,T} (bn + 1; z_{1}, …, z_{b}) = z_{b} ω_{b,T} (n; z_{1}^{t_{1}}, …, z_{b}^{t_{b}}) + ω_{b,T} (n + 1; z_{1}^{t_{1}}, …, z_{b}^{t_{b}}).  (21)

For z_{1} = ⋯ = z_{b} = 1, the identities (20), (21) obviously reduce to (18) and (19).

In the case of general λ, especially when λ > b, the right-hand sides of (20) and (21) usually have more than just one or two terms. To state and prove the next result in a concise way, we use the following notation. If

Z = (z_{1}, …, z_{λ}),  T = (t_{1}, …, t_{λ})  (22)

are λ-tuples of variables, resp. positive integers, then we denote

Z^{T} := (z_{1}^{t_{1}}, z_{2}^{t_{2}}, …, z_{λ}^{t_{λ}}).  (23)

We can now state and prove the main result of this section.

Theorem 5. Let b ≥ 2 and λ ≥ 1 be integers, denote ℓ := ⌊λ/b⌋, and let Z and T be given by (22). Then we have the recurrence relation ω_{b,T}^{λ} (0; Z) = 0, ω_{b,T}^{λ} (1; Z) = 1, and for each integer n ≥ 0,

ω_{b,T}^{λ} (bn + j + 1; Z) = ∑_{k=0}^{ℓ} z_{kb+j}ω_{b,T}^{λ} (n − k + 1; Z^{T})  (j = 0, 1, …, b − 1), (24)

with the conventions that z_{0} = 1, z_{μ} = 0 for μ > λ, and ω_{b,T}^{λ} (m; Z) = 0 if m ≤ 0.

Proof. For ease of notation we write ω(n; Z) for ω_{b,T}^{λ} (n; Z). Dividing both sides of (6) by ζ and then manipulating the infinite product, we get

∑_{m=0}^{∞}ω(m + 1; Z)ζ^{m} = ∏_{j=0}^{∞} (1 + z_{1}^{t_{1}^{j}}ζ^{b^{j}} + z_{2}^{t_{2}^{j}}ζ^{2·b^{j}} + ⋯ + z_{λ}^{t_{λ}^{j}}ζ^{λ·b^{j}})

= (1 + z_{1}ζ + ⋯ + z_{λ}ζ^{λ}) ∏_{j=0}^{∞} (1 + z_{1}^{t_{1}^{j+1}}ζ^{b^{j+1}} + ⋯ + z_{λ}^{t_{λ}^{j+1}}ζ^{λ·b^{j+1}})

= (1 + z_{1}ζ + ⋯ + z_{λ}ζ^{λ}) ∏_{j=0}^{∞} (1 + (z_{1}^{t_{1}})^{t_{1}^{j}}(ζ^{b})^{b^{j}} + ⋯ + (z_{λ}^{t_{λ}})^{t_{λ}^{j}}(ζ^{b})^{λ·b^{j}}) .

Using the notation (23) and again the generating function (6), we then obtain

∑_{m=0}^{∞} ω(m + 1; Z)ζ^{m} = (1 + z_{1}ζ + ⋯ + z_{λ}ζ^{λ}) ∑_{ν=0}^{∞} ω(ν + 1; Z^{T})ζ^{νb}.  (25)

With the conventions z_{0} = 1 and z_{μ} = 0 for μ > λ, and with λ = ℓb + r, 0 ≤ r ≤ b − 1, we get

(1 + z_{1}ζ + ⋯ + z_{λ}ζ^{λ}) = ∑_{k=0}^{ℓ} ∑_{j=0}^{b−1} z_{kb+j}ζ^{kb+j} = ∑_{k=0}^{ℓ} ζ^{kb} ∑_{j=0}^{b−1} z_{kb+j}ζ^{j}.  (26)

Next we write m = bn + j, 0 ≤ j ≤ b − 1, in (25) and substitute (26) into (25). Then (25) becomes

∑_{n=0}^{∞} ∑_{j=0}^{b−1}ω(bn + j + 1; Z)ζ^{bn+j}  (27)

= ( ∑_{k=0}^{ℓ} ζ^{kb} ∑_{j=0}^{b−1} z_{bk+j}ζ^{j}) · ∑_{ν=0}^{∞} ω(ν + 1; Z^{T})ζ^{νb}

= ∑_{n=0}^{∞} ∑_{j=0}^{b−1} ( ∑_{k=0}^{ℓ} z_{bk+j}ω(n − k + 1; Z^{T}))ζ^{nb+j},

where we have used a Cauchy product, with k + ν = n. Finally, by equating coefficients of ζ^{nb+j} in the first and the third line of (27), we immediately get (24).

Before considering other consequences and special cases of Theorem 5, we illustrate this result with n = 0 and n = 1.

Corollary 6. Let b ≥ 2 and λ ≥ 2b be integers, and Z and T as in (22). Then

ω_{b,T}^{λ} (j; Z) = z_{j−1}  (j = 2, 3, …, b),  (28)
ω_{b,T}^{λ} (b + 1; Z) = z_{1}^{t_{1}} + z_{b},  (29)
ω_{b,T}^{λ} (b + j; Z) = z_{1}^{t_{1}}z_{j−1} + z_{b+j−1}  (j = 2, 3, …, b).  (30)

Proof. As in the proof of Theorem 5 we suppress the subscripts and superscript of ω. The identity (24) with n = 0 gives, for j = 0, 1, …, b − 1,

ω(j + 1; Z) = z_{j}ω(1; Z^{T}) = z_{j}.

For j = 0 this is consistent with the convention z_{0} = 1, while the cases j = 1, 2, …, b − 1 give (28) when shifted by 1. Next we take (24) with n = 1, and again for j = 0, 1, …, b − 1 we obtain

ω(b + j + 1; Z) = z_{j}ω(2; Z^{T}) + z_{b+j}ω(1; Z^{T}) = z_{j}z_{1}^{t_{1}} + z_{b+j},  (31)

where we have used (23) and (28) for j = 2. Now (24) with j = 0 gives (29), and for j = 1, 2, …, b − 1 we get (30) when j is again shifted by 1.

As a specific (partial) example of Corollary 6 we consider the case b = 3 and λ = 4 in Table 1. Then (28) and (29) correspond to the entries for n = 2, 3, 4. The identity (30) corresponds only to n = 5 since we don’t have λ ≥ 2b. However, we see that Corollary 6 could easily be extended to give further explicit partial sequences of polynomials when λ is large enough compared with b.

We now consider several special cases of Theorem 5. As a first such case, we let λ = b and use the identity (7). Then ℓ = 1, and (24) reduces to

ω_{b,T} (bn + j + 1; Z) = z_{j}ω_{b,T} (n + 1; Z^{T}) + z_{b+j}ω_{b,T} (n; Z^{T})  (32)

for j = 0, 1, …, b − 1. But we have z_{0} = 1 and z_{b+j} = 0 for j ≥ 1, which leads to the following result.

Corollary 7. Let b ≥ 2, Z = (z_{1}, …, z_{b}), and T = (t_{1}, …, t_{b}). Then we have ω_{b,T} (0; Z) = 0, ω_{b,T} (1; Z) = 1, and for n ≥ 0,

ω_{b,T} (bn + 1; Z) = ω_{b,T} (n + 1; Z^{T}) + z_{b}ω_{b,T} (n; Z^{T}),
ω_{b,T} (bn + j + 1; Z) = z_{j}ω_{b,T} (n + 1; Z^{T}) (j = 1, 2, …, b − 1).

We have thus recovered (20) and (21). As our next special case we consider b = 2, with general λ ≥ 1. We separate the two cases j = 0 and j = b − 1 = 1 in (24) and note again that z_{0} = 1. Then we get the following corollary.

Corollary 8. Let λ ≥ 1 and Z = (z_{1}, …, z_{λ}), T = (t_{1}, …, t_{λ}). Then we have ω_{2,T}^{λ} (0; Z) = 0, ω_{2,T}^{λ} (1; Z) = 1, and for n ≥ 0,

ω_{2,T}^{λ} (2n + 1; Z) = ω_{2,T}^{λ} (n + 1; Z^{T}) + ∑_{k=1}^{⌊λ/2⌋} z_{2k}ω_{2,T}^{λ} (n − k + 1; Z^{T}),  (33)

ω_{2,T}^{λ} (2n + 2; Z) = ∑_{k=0}^{⌊λ/2⌋} z_{2k+1}ω_{2,T}^{λ} (n − k + 1; Z^{T}),  (34)

where z_{λ+1} = 0 and ω_{2,T}^{λ} (m; Z) = 0 when m ≤ 0.

When Z = (1, …, 1), then T is irrelevant and by (8) we have ω_{2,T}^{λ} (n + 1; Z) = S_{2}^{λ}(n), the restricted binary partition function defined by (1). Since z_{λ+1} = 0, the identity (34) needs to be split into two cases according to the parity of λ, as indicated in the following corollary.

Corollary 9. Let λ ≥ 1 be an integer. Then we have the recurrence relation S_{2}^{λ}(0) = 1, and for n ≥ 0,

S_{2}^{λ}(2n) = ∑_{k=0}^{⌊λ/2⌋} S_{2}^{λ}(n − k),  (35)

S_{2}^{λ}(2n + 1) = ∑_{k=0}^{λ/2−1} S_{2}^{λ}(n − k)  (λ even),  (36)

S_{2}^{λ}(2n + 1) = ∑_{k=0}^{(λ−1)/2} S_{2}^{λ}(n − k)  (λ odd),  (37)

where S_{2}^{λ}(m) = 0 when m < 0.

The three identities in Corollary 9 can be found in Theorem 2.4 of [20], with different notation.

More generally, we can consider arbitrary bases b ≥ 2, while still setting Z = (1, 1, …, 1) and using (8), namely ω_{b,T}^{λ} (n + 1; Z) = S_{b}^{λ}(n). Since z_{μ} = 0 for μ > λ, we also have to split (24) into two cases.

Corollary 10. Let b ≥ 2 and λ ≥ 1 be integers with λ = ℓb + r, 0 ≤ r ≤ b − 1. Then we have the recurrence relation S_{b}^{λ}(0) = 1, and for n ≥ 0,

S_{b}^{λ}(bn + j) = ∑_{k=0}^{ℓ} S_{b}^{λ}(n − k)  (0 ≤ j ≤ r),  (38)

S_{b}^{λ}(bn + j) = ∑_{k=0}^{ℓ−1} S_{b}^{λ}(n − k)  (r + 1 ≤ j ≤ b − 1),  (39)

where S_{b}^{λ}(m) = 0 for m < 0.

The identities (38) and (39) were previously obtained by Dumont et al. as Equation (6.2) in [13].

The last corollary of Theorem 5 in this section is a special case that is somewhat similar to Corollary 7 and is related to the unique b-ary representation of a positive integer. If we take λ = b − 1 for any b ≥ 2, then we have ℓ = 0, and with (24) and the fact that z_{0} = 1 we get the following recurrence relation.

Corollary 11. Let b ≥ 2 be an integer, and Z = (z_{1}, …, z_{b−1}), T = (t_{1}, …, t_{b−1}) be ordered sets of variables, resp. positive integers. Then we have ω_{b,T}^{b−1}(0; Z) = 0, ω_{b,T}^{b−1}(1; Z) = 1, and for n ≥ 0,

ω_{b,T}^{b−1}(bn + 1; Z) = ω_{b,T}^{b−1}(n + 1; Z^{T}),  (40)
ω_{b,T}^{b−1}(bn + j + 1; Z) = z_{j}ω_{b,T}^{b−1}(n + 1; Z^{T})  (1 ≤ j ≤ b − 1).  (41)

Example 12. We use Corollary 11 with b = 3, Z = (y, z), and T = (s, t). Then (40) and (41) can be written as

ω_{3,T}^{2} (3n + 1; Z) = ω_{3,T}^{2} (n + 1; y^{s}, z^{t}),
ω_{3,T}^{2} (3n + 2; Z) = y · ω_{3,T}^{2} (n + 1; y^{s}, z^{t}),
ω_{3,T}^{2} (3n + 3; Z) = z · ω_{3,T}^{2} (n + 1; y^{s}, z^{t}).

The first 14 nontrivial polynomials, evaluated using these recurrences, are listed in Table 2. They are obviously all monomials.

m ternary ω_{3,T}^{2} (m + 1; Z) m ternary ω_{3,T}^{2} (m + 1; Z)
1 (1)  y  8 (22)  z^{1+t}
2 (2)  z  9 (100)  y^{s^{2}}
3 (10)  y^{s}  10 (101)  y^{1+s^{2}}
4 (11)  y^{1+s}  11 (102)  y^{s^{2}}z
5 (12)  y^{s}z  12 (110)  y^{s+s^{2}}
6 (20)  z^{t}  13 (111)  y^{1+s+s^{2}}
7 (21)  yz^{t}  14 (112)  y^{s+s^{2}}z
Table 2: ω_{3,T}^{2} (m + 1; y, z), T = (s, t), 1 ≤ m ≤ 14.

Table 2 can also be seen as another illustration of Theorem 4 for V = (1, 2). Consider, for example, the last entry in Table 2. The polynomial y^{s+s^{2}}z indicates that the ternary representation of m = 14 is unique, and the powers 3^{1} and 3^{2} each occur once, while 3^{0} occurs twice. This is consistent with 14 = (112) in ternary representation.

To conclude this section, we state and prove a recurrence relation for the more general polynomials ω_{b,T}^{V} (n; Z) that were introduced in Definition 2.

Theorem 13. Let b ≥ 2 and λ ≥ 1 be integers, and V = (v_{1}, …, v_{λ}) a strictly increasing sequence of positive integers. Furthermore, let Z and T be as specified in (22), and define the v_{λ}-tuple Z̃ = (z̃_{1}, z̃_{2}, …, z̃_{v_{λ}}) by

z̃_{j} = \begin{cases}z_{k}, & when j = v_{k}, k = 1, 2, …, λ; \\ 0, & when j ∉ V. \end{cases}  (42)

Then we have the recurrence relation ω_{b,T}^{V} (0; Z) = 0, ω_{b,T}^{V} (1; Z) = 1, and for each integer n ≥ 0,

ω_{b,T}^{V} (bn + j + 1; Z) = ∑_{k=0}^{⌊v_{λ}/b⌋} z̃_{kb+j}ω_{b,T}^{V} (n − k + 1; Z^{T})  (j = 0, 1, …, b − 1),  (43)

with the conventions that z̃_{0} = 1, z̃_{μ} = 0 for μ > λ, and ω_{b,T}^{V} (m; Z) = 0 when m ≤ 0.

Proof. In analogy to (42) we set

t̃_{j} = \begin{cases}t_{k}, & when j = v_{k}, k = 1, 2, …, λ; \\ 1, & when j ∉ V. \end{cases}

Then with this definition and with (42) we see that we can write

ω_{b,T}^{V} (n; Z) = ω_{b,T̃}^{v_{λ}}(n; Z̃),  (44)

where the right-hand side of (44) is a polynomial of the type in Definition 1, with v_{λ} used in place of λ. We can therefore apply Theorem 5, which immediately gives Theorem 13, with ⌊v_{λ}/b⌋ in place of ℓ.

Example 14. Let b = 2 and V = (1, 3, 4). Then ⌊v_{λ}/b⌋ = 2, Z = (x, y, z), T = (r, s, t), and Z̃ = (x, 0, y, z). Therefore

z̃_{0} = 1, z̃_{1} = x, z̃_{2} = 0, z̃_{3} = y, z̃_{4} = z, z̃_{5} = 0,

and thus (43), written separately for j = 0 and j = 1, gives

ω_{2,T}^{V} (2n + 1; x, y, z) = ω_{2,T}^{V} (n + 1; x^{r}, y^{s}, z^{t}) + z · ω_{2,T}^{V} (n − 1; x^{r}, y^{s}, z^{t}),
ω_{2,T}^{V} (2n + 2; x, y, z) = x · ω_{2,T}^{V} (n + 1; x^{r}, y^{s}, z^{t}) + y · ω_{2,T}^{V} (n; x^{r}, y^{s}, z^{t}).

These last two identities, together with the initial conditions ω_{2,T}^{V} (0; Z) = 0 and ω_{2,T}^{V} (1; Z) = 1, can be used to easily compute the polynomials in question; see Table 3. We note that the entry for m = 10 agrees with (14) in Example 3.

\begin{matrix}m & ω_{2,T}^{V} (m; x, y, z) & m & ω_{2,T}^{V} (m; x, y, z) \\ 1 & 1 & 6 & x^{1+r^{2}} + x^{r}y \\ 2 & x & 7 & x^{r+r^{2}} + y^{s} + x^{r}z \\ 3 & x^{r} & 8 & x^{1+r+r^{2}} + xy^{s} + x^{r^{2}}y \\ 4 & x^{1+r} + y & 9 & x^{r^{3}} + z^{t} + x^{r^{2}}z \\ 5 & x^{r^{2}} + z & 10 & x^{1+r^{3}} + xz^{t} + x^{r+r^{2}}y + y^{1+s} \end{matrix}

Table 3: ω_{2,T}^{V} (m; x, y, z), T = (r, s, t), V = (1, 3, 4), 1 ≤ m ≤ 10.

4 Proof of Theorem 4

In this relatively brief section we use the general recurrence relation, Theorem 13, to prove our main representation theorem, namely Theorem 4. In what follows, in order to simplify terminology, we refer to a restricted b-ary partition of m in the sense of (10) simply as a “representation of m”.

We fix the integers b ≥ 2, λ ≥ 1, and the λ-tuples T, V, and Z as in Theorems 4 and 13. As we did in earlier proofs, we suppress the subscripts and superscript of ω. We now proceed by induction on m.

1. For the induction beginning we consider (43) with n = 0. Since ω(0; Z) = 0 and ω(1; Z) = 1, we find for j = 0, 1, …, b − 1 that

ω(j + 1; Z) = z̃_{j} = \begin{cases}z_{k}, & when j = v_{k}, k = 1, 2, …, λ; \\ 0, & when j ∉ V, j ≥ 1; \\ 1, & when j = 0. \end{cases}  (45)

Here we have used (42) and the convention z̃_{0} = 1.

On the other hand, the only representation of j = 1, 2, …, b−1 is v_{k} = v_{k}b^{0} when j = v_{k}, while j has no representation when j ∉ V. This is consistent with (15) and (16), namely

ω(j + 1; Z) = z_{k}^{1}, p_{h,k}(t_{k}) = 1 = t_{k}^{0},

as the power b^{0} is used exactly v_{k} times in the representation of j. Hence Theorem 4 holds for m = j, 1 ≤ j ≤ b − 1. This concludes the induction beginning.

2. Now we assume that Theorem 4 is true for all m ≤ nb − 1, for some n ≥ 1. We wish to show that it is then also true for m = nb + j, for all j = 0, 1, …, b − 1. To do so, we fix j, 0 ≤ j ≤ b − 1, and consider all representations of nb + j. They can be obtained recursively as follows. We fix an integer k ≥ 0 and

(a) take all representations of n − k and multiply them by b,

(b) add to each such representation kb + j times the part b^{0},

(c) ignore (a) and (b) when kb + j ∉ V,

(d) do (a) and (b) for all k ≥ 0 that satisfy kb + j ≤ v_{λ}. This procedure gives all representations of nb + j since (n − k)b + (kb + j) = nb + j. Also note that the maximal k given by (d) is ⌊v_{λ}/b⌋.

3. Using the induction hypothesis and (15), we have

ω(n − k + 1; Z) = ∑_{h∈ℍ_{b}^{V} (n−k)} z_{1}^{p_{h,1}(t_{1})} ⋯ z_{λ}^{p_{h,λ}(t_{λ})},  (46)

with exponents p_{h,1}(t_{1}), …, p_{h,λ}(t_{λ}) as in (16). In order to lift the representations of n − k to those of (n − k)b, which corresponds to step (a), all powers of t_{i}, 1 ≤ i ≤ λ, are augmented by 1. In addition, for each k with 0 ≤ k ≤ ⌊v_{λ}/b⌋ and satisfying kb + j ∈ V (say kb + j = v_{r}, 1 ≤ r ≤ λ) we add t_{r}^{0}, corresponding to b^{0} being used exactly v_{r} times; this, in turn, corresponds to step (b). If kb + j ∉ V, there is no contribution to the representations of nb + j, which corresponds to step (c).

Altogether, then, carrying out the procedure of the previous paragraph for each k for 0 ≤ k ≤ ⌊v_{λ}/b⌋ (step (d)), we get the polynomials

P_{k} := ∑_{h′∈ℍ_{b}^{V} (nb+j)} z_{1}^{p_{h′,1}(t_{1})} ⋯ z_{λ}^{p_{h′,λ}(t_{λ})},  (47)

where h′ ranges over all those representations of nb + j that have exactly v_{r} = kb + j times the part b^{0}, and

p_{h′,r}(t_{r}) = 1 + t_{r}p_{h,r}(t_{r}),  p_{h′,i}(t_{i}) = t_{i}p_{h,i}(t_{i}) (1 ≤ i ≤ λ, i ≠ r).  (48)

Now with (46) and (48), the sum in (47) becomes

P_{k} = z_{r} ∑_{h∈ℍ_{b}^{V} (n−k)}(z_{1}^{t_{1}})^{p_{h,1}(t_{1})} ⋯ (z_{λ}^{t_{λ}})^{p_{h,λ}(t_{λ})}  (49)
= z_{r}ω(n − k + 1; Z^{T}),

where we have used the notation (23).

Finally we sum (49) over all k, 0 ≤ k ≤ ⌊v_{λ}/b⌋, and use the fact that by (42) we have z̃_{kb+j} = z_{r} when kb + j ∈ V, and z̃_{kb+j} = 0 otherwise. Then the representations of nb + j are characterized by

∑_{k=0}^{⌊v_{λ}/b⌋} z̃_{kb+j}ω(n − k + 1; Z^{T}) = ω(bn + j + 1; Z),  (50)

where the right-hand side of (50) comes from (43). Therefore all the representations of nb+j are characterized by ω(bn + j + 1; Z); and since this holds for any j, 0 ≤ j ≤ b − 1, the proof by induction of the main statement of Theorem 4 is now complete.

It only remains to show that for each h ∈ ℍ_{b}^{V} (m) the polynomials p_{h,i}(t_{i}), i = 1, …, λ, have only 0 and 1 as coefficients. But this follows from (48), again by induction.

5 Explicit Formulas

In [3] Carlitz proved, in a different notation, that the number of odd binomial coefficients \binom{n−k}{k} is given by s(n+1), where \{s(n)\} is the Stern sequence mentioned in the Introduction. If we set \binom{n}{k}^{∗} = \binom{n}{k} (mod 2) with \binom{n}{k}^{∗} ∈ \{0, 1\}, then Carlitz’s result can be written as

s(n + 1) = ∑_{k=0}^{⌊ \frac{n}{2} ⌋} \binom{n − k}{k}^{∗} (n ≥ 0).  (51)

In [9] we extended the identity (51) to 2-variable Stern polynomials, again in base b = 2. To state this and further results, we need the following definition from [9].

For an integer k ≥ 0, let k = ∑_{j≥0} c_{j}2^{j}, c_{j} ∈ {0, 1}, be the binary expansion of k. Then for an integer base t ≥ 1 we define

d_{t}(k) := ∑_{j≥0} c_{j}t^{j}.  (52)

Various small values of d_{t}(k) can be found in Table 2 of [8], with references to the OEIS [19].

With the definition (52) and notation from (6), the polynomial extension of (51) in [9] can be stated as

ω_{2,T}^{2} (n + 1; y, z) = ∑_{k=0}^{⌊ \frac{n}{2} ⌋} \binom{n − k}{k}^{∗}y^{d_{s}(n−2k)}z^{d_{t}(k)},  (53)

where T = (s, t). As indicated in [18], the identity (51) can be rewritten as

∑_{k=0}^{⌊ \frac{n}{2} ⌋} \binom{n − k}{k}^{∗} = ∑_{j+2k=n} \binom{j + k}{k}^{∗},  (54)

and similarly, we can rewrite (53) as

ω_{2,T}^{2} (n + 1; y, z) = ∑_{k_{1}+2k_{2}=n} \binom{k_{1} + k_{2}}{k_{2}}^{∗}y^{d_{s}(k_{1})}z^{d_{t}(k_{2})}.  (55)

This last identity may serve as motivation for the following main result of this section. In analogy to \binom{n}{k}^{∗} we define \binom{k_{1}+···+k_{λ}}{k_{1},...,k_{λ}}^{∗} to be the least nonnegative residue of the multinomial coefficient \binom{k_{1}+···+k_{λ}}{k_{1},...,k_{λ}} modulo 2.

Theorem 15. Let λ ≥ 1 be an integer, V = (v_{1}, …, v_{λ}) a strictly increasing sequence of positive integers, and Z and T as in (22). Then for n ≥ 0 we have

ω_{2,T}^{V} (n + 1; Z) = ∑_{v_{1}k_{1}+v_{2}k_{2}+···+v_{λ}k_{λ}=n} \binom{k_{1} + ⋯ + k_{λ}}{k_{1}, …, k_{λ}}^{∗}z_{1}^{d_{t_{1}}(k_{1})} ⋯ z_{λ}^{d_{t_{λ}}(k_{λ})}.  (56)

Example 16. With λ = 3, V = (1, 3, 4), Z = (x, y, z), and T = (r, s, t), the identity (56) becomes

ω_{2,T}^{V} (n + 1; Z) = ∑_{k_{1}+3k_{2}+4k_{3}=n} \binom{k_{1} + k_{2} + k_{3}}{k_{1}, k_{2}, k_{3}}^{∗}x^{d_{r}(k_{1})}y^{d_{s}(k_{2})}z^{d_{t}(k_{3})}.  (57)

For n = 9, the conditions k_{1} + 3k_{2} + 4k_{3} = n and \binom{k_{1}+k_{2}+k_{3}}{k_{1},k_{2},k_{3}}^{∗} = 1 are satisfied by the triples (k_{1}, k_{2}, k_{3}) = (9, 0, 0), (6, 1, 0), (0, 3, 0), (1, 0, 2), so that (57) becomes

ω_{2,T}^{V} (10; Z) = x^{d_{r}(9)} + x^{d_{r}(6)}y^{d_{s}(1)} + y^{d_{s}(3)} + x^{d_{r}(1)}z^{d_{t}(2)}
= x^{1+r^{3}} + x^{r+r^{2}}y + y^{1+s} + xz^{t}.

This is consistent with (14) in Example 3; see also Table 3.

We note that the sum in (56) is taken over all partitions of n with parts in V. In the special case V = (1, 2, …, λ), we get the following immediate consequence of Theorem 15.

Corollary 17. Let λ ≥ 1 be an integer, and Z and T as in (22). Then for n ≥ 0 we have

ω_{2,T}^{λ} (n + 1; Z) = ∑_{k_{1}+2k_{2}+···+λk_{λ}=n} \binom{k_{1} + ⋯ + k_{λ}}{k_{1}, …, k_{λ}}^{∗}z_{1}^{d_{t_{1}}(k_{1})} ⋯ z_{λ}^{d_{t_{λ}}(k_{λ})}.  (58)

We now see that the identity (55) is the case λ = 2 of Corollary 17. If we set Z = (1, …, 1) in (56) and use (12), we get the following extension of (51) and (54).

Corollary 18. Let λ ≥ 1 be an integer and V = (v_{1}, …, v_{λ}) a strictly increasing sequence of positive integers. Then for n ≥ 0 we have

S_{2}^{V} (n) = ∑_{v_{1}k_{1}+v_{2}k_{2}+···+v_{λ}k_{λ}=n} \binom{k_{1} + ⋯ + k_{λ}}{k_{1}, …, k_{λ}}^{∗},  (59)

where S_{2}^{V} (n) is the number of restricted binary partitions of n, as defined in (11).

Theorem 15 is a special case of a more general result, which in turn is a consequence of the following lemma.

Lemma 19. Let b ≥ 2 and λ ≥ 1 be integers, V = (v_{1}, …, v_{λ}) a strictly increasing sequence of positive integers, and Z and T as in (22). Then for n ≥ 0 we have

ω_{b,T}^{V} (n + 1; Z) = ∑ ∏_{j≥0}(z_{i_{j}})^{t_{i_{j}}^{j}} ,  (60)

where the sum is taken over all representations v_{i_{0}} +v_{i_{1}}b+v_{i_{2}}b^{2} +⋯ = n in ℍ_{b}^{V} (n) as defined in (10), and where we set z_{0} = 1 and v_{0} = 0 by convention.

Example 20. Let b = 3, V = {1, 2, 3, 4, 5}, Z = (v, w, x, y, z), and T = (p, q, r, s, t). The representations of n = 15 and the corresponding monomials, according to Lemma 19, are then given as follows:

\begin{aligned}2 · 3 + 1 · 3^{2} & ⟷ & z_{2}^{t_{2}}z_{1}^{t_{1}^{2}} & = & w^{q}v^{p^{2}}, \\ 3 · 1 + 1 · 3 + 1 · 3^{2} & ⟷ & z_{3}^{t_{3}^{0}}z_{1}^{t_{1}}z_{1}^{t_{1}^{2}} & = & xv^{p+p^{2}}, \\ 5 · 3 & ⟷ & z_{5}^{t_{5}} & = & z^{t}, \\ 3 · 1 + 4 · 3 & ⟷ & z_{3}^{t_{3}^{0}}z_{4}^{t_{4}} & = & xy^{s}. \end{aligned}

In accordance with (60) these monomials are the terms of the polynomial

ω_{3,T}^{5} (16; Z) = w^{q}v^{p^{2}} + xv^{p+p^{2}} + z^{t} + xy^{s}.

Proof of Lemma 19. If we divide both sides of (9) by ζ, we see that the infinite product on the right-hand side of (9) is the generating function of the polynomial sequence ω_{b,T}^{V} (n+1; Z) for n ≥ 0.

On the other hand, for a fixed n the product in (9) shows that all powers of ζ^{n} are of the form

ζ^{n} = ∏_{j≥0} ζ^{v_{i_{j}} b^{j}},

or, in terms of the exponents,

n = ∑_{j≥0} v_{i_{j}}b^{j},  0 ≤ i_{j} ≤ λ,  v_{0} = 0, v_{i} ∈ V (1 ≤ i ≤ λ).  (61)

The structure of the factors on the right-hand side of (9) also shows that the monomial z_{1}, …, z_{λ} corresponding to the exponent n in (61) is

∏_{j≥0}(z_{i_{j}})^{t_{i_{j}}^{j}} .  (62)

Summing over all representations of n as in (61), we obtain the identity (60).

In order to state and prove our next result, we need some additional definitions with corresponding notations. For the remainder of this section, let b ≥ 2 be a fixed integer.

First we define the set

M_{b} := {∑_{j≥0} c_{j}b^{j} | c_{j} ∈ {0, 1}} ,  (63)

i.e., the set of all nonnegative integers whose b-ary digits are only 0 or 1. Clearly we have M_{2} = ℕ ∪ {0}.

Next we extend (52) as follows. Let k ∈ M_{b} with k = ∑_{j≥0} c_{j}b^{j}, c_{j} ∈ {0, 1}. Then for an integer base t ≥ 1 we define

d_{t}^{b}(k) := ∑_{j≥0} c_{j}t^{j}.  (64)

It is clear that d_{t}^{2}(k) = d_{t}(k) and d_{b}^{b}(k) = k for all integers b ≥ 2 and k ∈ M_{b}.

Finally, we extend the multinomial coefficient modulo 2, as used in Theorem 15. If k_{1}, …, k_{λ} ∈ M_{b}, we set

\binom{k_{1} + ⋯ + k_{λ}}{k_{1}, …, k_{λ}}_{b}^{∗} := \binom{d_{2}^{b}(k_{1}) + ⋯ + d_{2}^{b}(k_{λ})}{d_{2}^{b}(k_{1}), …, d_{2}^{b}(k_{λ})}^{∗},  (65)

with the right-hand side of (65) as defined earlier, just before Theorem 15. We are now ready to state a result that generalizes Theorem 15.

Theorem 21. Let b ≥ 2 and λ ≥ 1 be integers, V = (v_{1}, …, v_{λ}) a strictly increasing sequence of positive integers, and Z and T as in (22). Then for n ≥ 0 we have

ω_{b,T}^{V} (n + 1; Z) = ∑_{\begin{matrix}v_{1}k_{1}+v_{2}k_{2}+···+v_{λ}k_{λ}=n \\ k_{1},...,k_{λ}∈M_{b} \end{matrix}} \binom{k_{1} + ⋯ + k_{λ}}{k_{1}, …, k_{λ}}_{b}^{∗}z_{1}^{d_{t_{1}}^{b}(k_{1})} ⋯ z_{λ}^{d_{t_{λ}}^{b}(k_{λ})}.  (66)

Before proving this result, we note that it immediately implies Theorem 15. Indeed, when b = 2, the multinomial coefficient defined in (65) reduces to the one in (56) since d_{2}^{2}(k_{i}) = k_{i}. Then in the b = 2 case we also have d_{t_{i}}^{b}(k_{i}) = d_{t_{i}}(k_{i}), and the conditions concerning M_{b} become irrelevant.

For the proof of Theorem 21 we require the following result due to Dickson [7], which we state as a lemma. See also the more recent paper [17].

Lemma 22 (Dickson). Let p be a prime and λ ≥ 2 an integer, and suppose that the positive integers k_{1}, …, k_{λ} and k := k_{1} + ⋯ + k_{λ} are given in base-p representation as

k_{i} = a_{0}^{i} + a_{1}^{i}p + ⋯ + a_{m}^{i}p^{m},  i = 1, …, λ,
k = a_{0} + a_{1}p + ⋯ + a_{m}p^{m}.

Then we have

\binom{k}{k_{1}, …, k_{λ}} ≢ 0 (mod p),  (67)

if and only if

a_{j} = a_{j}^{1} + ⋯ + a_{j}^{λ}  (68)

holds for all j = 1, …, m.

Proof of Theorem 21. We begin with Lemma 19 and its proof. The representation of n in (61) can be rewritten as

n = v_{1}k_{1} + v_{2}k_{2} + ⋯ + v_{λ}k_{λ},  (69)

where for each r = 1, 2, …, λ we have

k_{r} := ∑_{i_{j}=r} b^{j},

for integers i_{j} with 0 ≤ i_{j} ≤ λ. This means that each power b^{0}, b^{1}, b^{2}, … occurs in the base-b representation of at most one of the integers k_{1}, k_{2}, …, k_{λ}, which in turn implies that

(i) k_{i} ∈ M_{b} for all i = 1, 2, …, λ, and

(ii) the powers b^{0}, b^{1}, b^{2}, … do not “overlap” in the sum k_{1} + ⋯ + k_{λ}.

Furthermore, as n is rewritten in the form (69), the corresponding monomial in (62) can be rewritten as

∏_{i=1}^{λ} z_{i}^{d_{t_{i}}^{b}(k_{i})},  (70)

where we have used the definition (64).

We are now going to characterize condition (ii), noting that condition (i) is taken care of by the summation in (66). If for each i = 1, 2, …, λ we replace

k_{i} = c_{0}^{i} + c_{1}^{i}b + ⋯ + c_{j_{i}}b^{j_{i}} ∈ M_{b}

by

d_{2}^{b}(k_{i}) = c_{0}^{i} + c_{1}^{i}2 + ⋯ + c_{j_{i}}2^{j_{i}},

then condition (ii) means that there is no “carry” as we take the sum S := d_{2}^{b}(k_{1})+⋯+d_{2}^{b}(k_{λ}). This, in turn, means that for each power of 2, say 2^{ν}, the sum of the coefficients of 2^{ν} in d_{2}^{b}(k_{1}), …, d_{2}^{b}(k_{λ}), namely 0 or 1, is exactly the coefficient of 2^{ν} in S. Hence the condition (68) in Lemma 22 with p = 2 is satisfied, and by (67) and (65) the modified multinomial coefficient in (66) is 1. Therefore the product (70) is included, as required.

On the other hand, if condition (ii) is not satisfied, then there is a carry in the sum S. This means that there is at least one index ν ≥ 0 such that

c_{ν}^{1} + c_{ν}^{2} + ⋯ + c_{ν}^{λ} ≥ 2,

while the coefficient of 2^{ν} in S is only 0 or 1. Therefore the condition (68) in Lemma 22 (again with p = 2) is not satisfied, and by (67) and (65) the modified multinomial coefficient in (66) is 0. This completes the proof of Theorem 21.

Example 23. As in Example 20, we choose again b = 3, V = {1, 2, 3, 4, 5}, and n = 15. Of the 84 partitions of n = 15 with parts in V, 25 satisfy the second summation condition in (66), namely k_{i} ∈ M_{3} = {0, 1, 3, 4, 9, 10, 12, 27, …}, 1 ≤ i ≤ 5. For only four of these partitions the modified multinomial coefficient in (66) is 1, namely for

(k_{1}, …, k_{5}) = (9, 3, 0, 0, 0), (12, 0, 1, 0, 0), (0, 0, 1, 3, 0), (0, 0, 0, 0, 3).  (71)

Hence (66) with Z = (v, w, x, y, z) and T = (p, q, r, s, t) gives

ω_{3,T}^{5} (16; Z) = v^{d_{p}^{3}(9)}w^{d_{q}^{3}(3)} + v^{d_{p}^{3}(12)}x^{d_{r}^{3}(1)} + x^{d_{r}^{3}(1)}y^{d_{s}^{3}(3)} + z^{d_{t}^{3}(3)}
= v^{p^{2}}w^{q} + v^{p+p^{2}}x + xy^{s} + z^{t},

which is consistent with the result of Example 20.

Remark. A necessary condition for the product (70) to be included in (66) is k_{1} +⋯+k_{λ} ∈ M_{b}, since otherwise condition (ii) in the proof of Theorem 21 is obviously not satisfied. However, this condition is not sufficient, as the following example shows.

On the other hand, we conjecture that a necessary and sufficient condition for the product (70) to be included in (66) is that all possible partial sums of elements of {k_{1}, …, k_{λ}} be in M_{b}. A further analysis would go beyond the scope of this paper; we leave this to the interested reader.

Example 24. Continuing with Example 23, we note that of the 25 partitions that satisfy k_{i} ∈ M_{3}, 1 ≤ i ≤ 5, there are 19 such that k_{1} + ⋯ + k_{5} ∉ M_{3}. The remaining six partitions obviously include the four in (71), while (k_{1}, …, k_{5}) = (10, 1, 1, 0, 0) and (4, 4, 1, 0, 0) are excluded by way of the modified multinomial coefficients as in (66), or by the fact that, for instance, 1 + 1 ∉ M_{3} and 4 + 1 ∉ M_{3}.

6 Further Remarks

We recall that Definition 1 and most of the results that follow are valid for all λ ≥ 1, regardless of the base b ≥ 2. While in most of this paper we were interested in the case λ ≥ b − 1 (or even λ ≥ b), we are now going to consider the case λ ≤ b − 2 when b ≥ 3. We begin with a consequence of Theorem 5.

Corollary 25. Let b ≥ 3 and 1 ≤ λ ≤ b − 2 be integers, and let Z and T be given by (22). Then we have ω_{b,T}^{λ} (0; Z) = 0, ω_{b,T}^{λ} (1; Z) = 1, and for each n ≥ 0 we have

ω_{b,T}^{λ} (bn + j; Z) = \begin{cases}ω_{b,T}^{λ} (n + 1; Z^{T}), & when λ = 1; \\ z_{j}ω_{b,T}^{λ} (n + 1; Z^{T}), & when 2 ≤ j ≤ λ; \\ 0, & when λ + 1 ≤ j ≤ b − 1. \end{cases}  (72)

This follows immediately from Theorem 5 since ℓ = ⌊λ/b⌋ = 0, z_{0} = 1, and z_{λ+1} = ⋯ = z_{b−1} = 0. Corollary 25 can also be seen as an extension of Corollary 11.

By iterating (72), we immediately get the following result which characterizes the cases in which the polynomials are zero when λ ≤ b − 2.

Corollary 26. Let b ≥ 3 and 1 ≤ λ ≤ b − 2 be integers, and Z and T as in (22). If the integer m ≥ 0 has the base-b representation m = ∑_{i=0}^{r} c_{i}b^{i}, 0 ≤ c_{i} ≤ b − 1 for 0 ≤ i ≤ r, then

ω_{b,T}^{λ} (m + 1; Z) = 0 if and only if λ ≤ c_{i} ≤ b − 2

for at least one index i, 0 ≤ i ≤ r.

Example 27. Let b = 4 and λ = 2, with Z = (y, z) and T = (s, t). Then Corollary 25 leads to the entries of Table 4, which also illustrates Corollary 26.

\begin{matrix}m & ω(m + 1; Z) & m & ω(m + 1; Z) & m & ω(m + 1; Z) & m & ω(m + 1; Z) \\ 0 & 1 & 5 & y^{1+s} & 10 & z^{1+t} & 15 & 0 \\ 1 & y & 6 & y^{s}z & 11 & 0 & 16 & y^{s^{2}} \\ 2 & z & 7 & 0 & 12 & 0 & 17 & y^{1+s^{2}} \\ 3 & 0 & 8 & z^{t} & 13 & 0 & 18 & y^{s^{2}}z \\ 4 & y^{s} & 9 & yz^{t} & 14 & 0 & 19 & 0 \end{matrix}

Table 4: ω(m + 1; Z) = ω_{4,T}^{2} (m + 1; Z), T = (s, t), Z = (y, z), 0 ≤ m ≤ 19.

Using (8), we get the following result for the integers S_{b}^{λ}(m) defined by (2).

Corollary 28. Let b ≥ 3 and 1 ≤ λ ≤ b − 2 be integers, and suppose that m ≥ 0 has the base-b representation m = ∑_{i=0}^{r} c_{i}b^{i}, 0 ≤ c_{i} ≤ b − 1 for 0 ≤ i ≤ r. Then

S_{b}^{λ}(m) = \begin{cases}1, & when 0 ≤ c_{i} ≤ λ − 1 for all 0 ≤ i ≤ r; \\ 0, & otherwise. \end{cases}

This last result is not difficult to obtain directly. The special case where b is a prime in Corollary 28 was mentioned in [12] in connection with a study of products of cyclotomic polynomials.

As a second remark, we note that Mansour and Shattuck [16] defined the following concept.

Fix m ≥ 2 and 0 ≤ c ≤ m − 1. By a c-hyper m-expansion of a positive integer n, we mean a partition of n into powers of m in which a given power can appear exactly j times, where j ∈ {0, 1, …, m − 1, m + c}. See [16, Def. 1.1].

If we compare this definition with (10), we see that the set of c-hyper m-expansions is, in our notation,

ℍ_{m}^{V}(n), where V = (1, 2, …, m − 1, m + c).

Furthermore, again for m ≥ 2 and 0 ≤ c ≤ m − 1, Mansour and Shattuck define the sequence of polynomials f_{m,c}(d; q) for d ≥ 0 by

f_{m,c}(mn + j; q) = f_{m,c}(n; q),  0 ≤ j ≤ m − 1, j ≠ c,  (73)
f_{m,c}(mn + c; q) = f_{m,c}(n; q) + q f_{m,c}(n − 1; q),  (74)

with f_{m,c}(0; q) = 1 and f_{m,c}(d; q) = 0 for d < 0. See [16, Def. 1.2].

If we compare (73), (74) with Theorem 13, where b = λ = m and V = (1, 2, …, m − 1, m + c), then we find

f_{m,c}(d; q) = ω_{m,T}^{V} (d + 1, Z),  (75)

with the m-tuples T = (1, …, 1) and Z = (1, …, 1, q). Also, a special case of our Theorem 4 for the polynomials in (75) was obtained in [16]. Apart from these connections, however, the paper [16] has a different emphasis from ours and deals mainly with generalizations of the well-known Calkin-Wilf tree.

References

[1] G. E. Andrews, Congruence properties of the m-ary partition function, J. Number Theory 3 (1971), 104–110.

[2] B. Bates and T. Mansour, The q-Calkin-Wilf tree, J. Combin. Theory Ser. A 118 (2011), 1143–1151.

[3] L. Carlitz, Single variable Bell polynomials, Collect. Math. 14 (1960), 13–25.

[4] R. F. Churchhouse, Congruence properties of the binary partition function, Proc. Cambridge Philos. Soc. 66 (1969), 371–376.

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

[6] C. Defant, Upper bounds for Stern’s diatomic sequence and related sequences, Electron. J. Combin. 23 (2016), Paper 4.8.

[7] L. E. Dickson, Theorems on the residues of multinomial coefficients with respect to a prime modulus, Quart. J. Pure Appl. Math. 33 (1902), 378–384.

[8] K. Dilcher and L. Ericksen, Hyperbinary expansions and Stern polynomials, Electron. J. Combin. 22 (2015), Paper 2.24.

[9] K. Dilcher and L. Ericksen, Generalized Stern polynomials and hyperbinary representations, Bull. Pol. Acad. Sci. Math. 65 (2017), 11–28.

[10] K. Dilcher and L. Ericksen, Polynomials characterizing hyper b-ary representations, J. Integer Seq. 21 (2018), Article 18.4.3.

[11] K. Dilcher and L. Ericksen, Properties of multivariate b-ary Stern polynomials, Ann. Comb., to appear.

[12] W. Duke and H. N. Nguyen, Infinite products of cyclotomic polynomials, Bull. Aust. Math. Soc. 91 (2015), 400–411.

[13] J. M. Dumont, N. Sidorov, and A. Thomas, Number of representations related to a linear recurrent basis, Acta Arith. 88 (1999), 371–396.

[14] L. Euler, De partitione numerorum, Novi Commentarii academiae scientiarum Petropolitanae 3 (1753), 125–169. In Opera Omnia, Ser. 1, Vol. 2, pp. 254–294. Also available from The Euler Archive, http://eulerarchive.maa.org, Paper E191.

[15] K. Mahler, On a special functional equation, J. London Math. Soc. 15 (1940), 115–123.

[16] T. Mansour and M. Shattuck, Generalized q-Calkin-Wilf trees and c-hyper m-expansions of integers, J. Comb. Number Theory 7 (2015), 1–12.

[17] R. J. Martin and G. L. Mullen, Reducing multinomial coefficients modulo a prime power, Comput. Math. Appl. 10 (1984), 37–41.

[18] S. Northshield, Sums across Pascal’s triangle mod 2, Congr. Numer. 200 (2010), 35–52.

[19] OEIS Foundation Inc. (2011), The On-Line Encyclopedia of Integer Sequences,

    https://oeis.org.

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

[21] Ö. Rödseth, Some arithmetical properties of m-ary partitions, Proc. Cambridge Philos. Soc. 68 (1970), 447–453.

[22] R. P. Stanley and H. S. Wilf, Refining the Stern diatomic sequence, Preprint, 2010.

    Available at http://www-math.mit.edu/~rstan/papers/stern.pdf.

2010 Mathematics Subject Classification: Primary 11P81; Secondary 11B37, 11B83. Keywords: binary partition, b-ary partition, restricted partition, polynomial analogue, generating function, recurrence relation, multinomial coefficient.

(Concerned with sequences \underline{A002487} and \underline{A018819}.)

Received December 2 2018; revised version received May 8 2019. Published in Journal of Integer Sequences, May 17 2019.

Return to Journal of Integer Sequences home page.