\documentclass[12pt,reqno]{article}
\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amscd}
\usepackage{graphicx}
\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}
\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}
\usepackage{color}
\usepackage{fullpage}
\usepackage{float}
\usepackage{psfig}
\usepackage{graphics}
\usepackage{latexsym}
\usepackage{epsf}
\usepackage{breakurl}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}
\newcommand{\seqnum}[1]{\href{https://oeis.org/#1}{\underline{#1}}}
\begin{document}
\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\begin{center}
\vskip 1cm{\LARGE\bf
Polynomial Analogues of Restricted \\
\vskip .1in
$b$-ary Partition Functions}
\vskip 1cm
\large
Karl Dilcher\footnote{Research supported in part by the Natural Sciences and
Engineering Research Council of Canada, Grant \# 145628481.}\\
Department of Mathematics and Statistics\\
Dalhousie University\\
Halifax, Nova Scotia B3H 4R2\\
Canada\\
\href{mailto:dilcher@mathstat.dal.ca}{\tt dilcher@mathstat.dal.ca}\\
\ \\
Larry Ericksen\\
P. O. Box 172\\
Millville, NJ 08332-0172\\
USA\\
\href{mailto:LE22@cornell.edu}{\tt LE22@cornell.edu}\\
\end{center}
\vskip .2in
\begin{abstract}
Given an integer $b\geq 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 $\lambda$ times, for
a fixed $\lambda\geq 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.
\end{abstract}
\section{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 \cite[pp.~162ff.]{Eu} and
later by other authors,
including Churchhouse \cite{Ch} who studied congruence properties of $S_2(n)$.
Reznick \cite{Re} later investigated the following restricted binary partition
function. Given an integer $\lambda\geq 1$, let $S_2^\lambda(n)$ denote
the number of representations
\begin{equation}\label{1.1}
n = \sum_{j\geq 0}c_j2^j,\qquad c_j\in\{0,1,\ldots,\lambda\}.
\end{equation}
In particular, we have $S_2^1(n)=1$ since $\lambda=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 \cite[p.~470]{Re}.
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 \eqref{1.1} to an arbitrary integer
base $b\geq 2$ and consider the number of representations
\begin{equation}\label{1.2}
n = \sum_{j\geq 0}c_jb^j,\qquad c_j\in\{0,1,\ldots,\lambda\},
\end{equation}
which we denote by $S_b^\lambda(n)$. Analogously, $S_b(n)$ denotes the number
of unrestricted $b$-ary partitions, and we can write
$S_b(n)=\lim_{\lambda\to\infty}S_b^\lambda(n)$.
It appears that the function $S_b(n)$ was
first studied by Mahler \cite{Ma} who derived an asymptotic formula, then later
by other authors, including Churchhouse \cite{Ch}, R\"odseth \cite{Ro}, and
Andrews \cite{An}, who were mainly interested in congruence properties of the
function $S_b(n)$. The restricted $b$-ary partition function $S_b^\lambda(n)$
was apparently first studied by Dumont et al. \cite[Section~6]{DST}.
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
\cite{De} 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 \eqref{1.1}. It should also be noted that
for $b\geq 3$ and $1\leq\lambda< b-1$, we have $S_b^\lambda(n)=0$ for
infinitely many $n$; see Section~6 for some examples.
In a different direction, the present authors studied the special case
$\lambda=b$, first for $b=2$, i.e., the case of hyperbinary representations.
Results of Bates and Mansour \cite{BM} and of Stanley and Wilf \cite{SW}, which
are refinements of the Stern identity $S_2^2(n)=s(n+1)$, were further refined
in \cite{DE7} 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 \cite{DE9} to
hyper $b$-ary expansions, i.e., those expansions of the type \eqref{1.1} that
are counted by $S_b^b(n)$ for an arbitrary integer base $b\geq 2$. Further
properties of these $b$-variable polynomials were then derived in \cite{DE10}.
It is the purpose of the present paper to use the methods developed in
\cite{DE7}--\cite{DE10} to define and investigate polynomial analogues of the
restricted $b$-ary partition function $S_b^\lambda(n)$ for any integer
$b\geq 2$ and primarily for $\lambda\geq 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^\lambda(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.
\section{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
\eqref{1.2} and the definition of $S_b^\lambda(n)$ that
\begin{equation}\label{2.1}
\sum_{n=0}^\infty S_b^\lambda(n)\zeta^n
=\prod_{j=0}^\infty\left(1+\zeta^{b^j}+\zeta^{2\cdot b^j}+\dots
+\zeta^{\lambda\cdot b^j}\right).
\end{equation}
This can be seen by expanding the right-hand side of \eqref{2.1} and equating
coefficients of $\zeta^n$; see also \cite[p.~381]{DST}, or \cite[p.~454]{Re} for
$b=2$. A special case of \eqref{2.1} is the case $\lambda=b$, where $S_b^b(n)$
counts the number of hyper $b$-ary expansions; see \cite{CSe}. Since
$S_b^b(n)=s_b(n+1)$, as noted in the Introduction, the generating function
\eqref{2.1} immediately gives
\begin{equation}\label{2.2}
\sum_{n=0}^\infty s_{b}(n)\zeta^n
=\zeta\prod_{j=0}^\infty\left(1+\zeta^{b^j}+\zeta^{2\cdot b^j}+\dots
+\zeta^{b\cdot b^j}\right),
\end{equation}
where $s_b(n)$ is the $b$-ary Stern sequence; see also \cite{De}. More recently
the current authors introduced a $b$-variable polynomial analogue of the
sequence $s_b(n)$ in \cite{DE9} 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 \cite{CSe} and \cite{De},
and the corresponding generating function was obtained in the subsequent paper
\cite{DE10}. These polynomials, written here in the slightly different notation
$\omega_{b,T}(n,Z)$, have integer parameters $T=(t_1,\ldots,t_b)$ and variables
$Z=(z_1,\ldots,z_b)$, and satisfy
\begin{equation}\label{2.3}
\sum_{n=1}^\infty \omega_{b,T}(n;Z)\zeta^n
=\zeta\prod_{j=0}^\infty\left(1+z_1^{t_1^j}\zeta^{b^j}+
z_2^{t_2^j}\zeta^{2\cdot b^j}+\dots+z_b^{t_b^j}\zeta^{b\cdot b^j}\right).
\end{equation}
When we compare \eqref{2.2} and \eqref{2.3}, it is clear that
$\omega_{b,T}(n;1,\ldots,1)=s_b(n)$, independent of the $b$-tuple $T$.
We now use \eqref{2.3} as the basis for the definitions of the main
objects of study in this paper.
\begin{definition}\label{def:2.1}
Let $b\geq 2$ and $\lambda\geq 1$ be integers, $T=(t_1,\ldots,t_\lambda)$ be
a $\lambda$-tuple of positive integer parameters, and $Z=(z_1,\ldots,z_\lambda)$
a $\lambda$-tuple of variables. Then we define the sequence of
$\lambda$-variable polynomials $\omega_{b,T}^\lambda(n;Z)$ by the generating
function
\begin{equation}\label{2.4}
\sum_{n=1}^\infty \omega_{b,T}^\lambda(n;Z)\zeta^n
=\zeta\prod_{j=0}^\infty\left(1+z_1^{t_1^j}\zeta^{b^j}+
z_2^{t_2^j}\zeta^{2\cdot b^j}+\dots
+z_\lambda^{t_\lambda^j}\zeta^{\lambda\cdot b^j}\right).
\end{equation}
\end{definition}
We immediately see that for $\lambda=b$ this last identity reduces to
\eqref{2.3}, and for $Z=(1,\ldots,1)$ it reduces to \eqref{2.2}. Therefore we
have for any $b\geq 2$, $\lambda\geq 1$ and for any $T$ and indices $n\geq 0$
that
\begin{align}
\omega_{b,T}^b(n;Z) &= \omega_{b,T}(n;Z),\label{2.5}\\
\omega_{b,T}^\lambda(n;1,\ldots,1) &= S_b^\lambda(n-1).\label{2.6}
\end{align}
By expanding the right-hand side of \eqref{2.4} for a given $b\geq 2$ and
$\lambda\geq 1$, one can easily write down the first few polynomials
$\omega_{b,T}^\lambda(n;Z)$. For instance, those for $b=3$ and $\lambda=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^\lambda(n)$ counts the number of
$b$-ary partitions with each power of $b$ occurring at most $\lambda$ times, and
we will see that $\omega_{b,T}^\lambda(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 $\lambda$ integers,
$V=(v_1,v_2,\ldots,v_\lambda)$, where $\lambda\geq 1$ and
$1\leq v_1b$, the right-hand
sides of \eqref{3.3} and \eqref{3.4} 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
\begin{equation}\label{3.4a}
Z=(z_1,\ldots,z_\lambda),\qquad T=(t_1,\ldots,t_\lambda)
\end{equation}
are $\lambda$-tuples of variables, resp.\ positive integers, then we denote
\begin{equation}\label{3.5}
Z^T := (z_1^{t_1}, z_2^{t_2},\ldots, z_\lambda^{t_\lambda}).
\end{equation}
We can now state and prove the main result of this section.
\begin{theorem}\label{thm:3.1}
Let $b\geq 2$ and $\lambda\geq 1$ be integers, denote
$\ell:=\lfloor\lambda/b\rfloor$, and let $Z$ and $T$ be given by \eqref{3.4a}.
Then we have the recurrence relation $\omega_{b,T}^\lambda(0;Z)=0$,
$\omega_{b,T}^\lambda(1;Z)=1$, and for each integer $n\geq 0$,
\begin{equation}\label{3.6}
\omega_{b,T}^\lambda(bn+j+1;Z)
= \sum_{k=0}^\ell z_{kb+j}\omega_{b,T}^\lambda(n-k+1;Z^T)\qquad
(j=0,1,\ldots,b-1),
\end{equation}
with the conventions that $z_0=1$, $z_\mu=0$ for $\mu > \lambda$, and
$\omega_{b,T}^\lambda(m;Z)=0$ if $m\leq 0$.
\end{theorem}
\begin{proof}
For ease of notation we write $\omega(n;Z)$ for $\omega_{b,T}^\lambda(n;Z)$.
Dividing both sides of \eqref{2.4} by $\zeta$ and then manipulating the
infinite product, we get
\begin{align*}
\sum_{m=0}^\infty &\omega(m+1;Z)\zeta^m
=\prod_{j=0}^\infty\left(1+z_1^{t_1^j}\zeta^{b^j}+
z_2^{t_2^j}\zeta^{2\cdot b^j}+\cdots
+z_\lambda^{t_\lambda^j}\zeta^{\lambda\cdot b^j}\right)\\
&=(1+z_1\zeta+\cdots+z_\lambda\zeta^\lambda)
\prod_{j=0}^\infty\left(1+z_1^{t_1^{j+1}}\zeta^{b^{j+1}}+\cdots
+z_\lambda^{t_\lambda^{j+1}}\zeta^{\lambda\cdot b^{j+1}}\right)\\
&=(1+z_1\zeta+\cdots+z_\lambda\zeta^\lambda)
\prod_{j=0}^\infty\left(1+(z_1^{t_1})^{t_1^j}(\zeta^b)^{b^j}+\cdots
+(z_\lambda^{t_\lambda})^{t_\lambda^j}(\zeta^b)^{\lambda\cdot b^j}\right).
\end{align*}
Using the notation \eqref{3.5} and again the generating function \eqref{2.4},
we then obtain
\begin{equation}\label{3.7}
\sum_{m=0}^\infty\omega(m+1;Z)\zeta^m
=(1+z_1\zeta+\cdots+z_\lambda\zeta^\lambda)
\sum_{\nu=0}^\infty\omega(\nu+1;Z^T)\zeta^{\nu b}.
\end{equation}
With the conventions $z_0=1$ and $z_\mu=0$ for $\mu>\lambda$, and with
$\lambda=\ell b+r$, $0\leq r\leq b-1$, we get
\begin{equation}\label{3.8}
(1+z_1\zeta+\cdots+z_\lambda\zeta^\lambda)
= \sum_{k=0}^\ell\sum_{j=0}^{b-1}z_{kb+j}\zeta^{kb+j}
= \sum_{k=0}^\ell\zeta^{kb}\sum_{j=0}^{b-1}z_{kb+j}\zeta^j.
\end{equation}
Next we write $m=bn+j$, $0\leq j\leq b-1$, in \eqref{3.7} and substitute
\eqref{3.8} into \eqref{3.7}. Then \eqref{3.7} becomes
\begin{align}
\sum_{n=0}^\infty\sum_{j=0}^{b-1}&\omega(bn+j+1;Z)\zeta^{bn+j}\label{3.9}\\
&=\bigg(\sum_{k=0}^\ell\zeta^{kb}\sum_{j=0}^{b-1}z_{bk+j}\zeta^j\bigg)
\cdot\sum_{\nu=0}^\infty\omega(\nu+1;Z^T)\zeta^{\nu b}\nonumber \\
&=\sum_{n=0}^\infty\sum_{j=0}^{b-1}
\bigg(\sum_{k=0}^\ell z_{bk+j}\omega(n-k+1;Z^T)\bigg)\zeta^{nb+j},\nonumber
\end{align}
where we have used a Cauchy product, with $k+\nu=n$. Finally, by equating
coefficients of $\zeta^{nb+j}$ in the first and the third line of \eqref{3.9},
we immediately get \eqref{3.6}.
\end{proof}
Before considering other consequences and special cases of
Theorem~\ref{thm:3.1}, we illustrate this result with $n=0$ and $n=1$.
\begin{corollary}\label{cor:3.2}
Let $b\geq 2$ and $\lambda\geq 2b$ be integers, and $Z$ and $T$ as in
\eqref{3.4a}. Then
\begin{align}
\omega_{b,T}^\lambda(j;Z) &= z_{j-1}\qquad(j=2,3,\ldots,b),\label{3.6a}\\
\omega_{b,T}^\lambda(b+1;Z) &= z_1^{t_1}+z_b,\label{3.6b}\\
\omega_{b,T}^\lambda(b+j;Z) &= z_1^{t_1}z_{j-1}+z_{b+j-1}\qquad(j=2,3,\ldots,b).\label{3.6c}
\end{align}
\end{corollary}
\begin{proof}
As in the proof of Theorem~\ref{thm:3.1} we suppress the subscripts and
superscript of $\omega$. The identity \eqref{3.6} with $n=0$ gives, for
$j=0,1,\ldots,b-1$,
\[
\omega(j+1;Z) = z_j\omega(1;Z^T) = z_j.
\]
For $j=0$ this is consistent with the convention $z_0=1$, while the cases
$j=1,2,\ldots,b-1$ give \eqref{3.6a} when shifted by 1. Next we take \eqref{3.6}
with $n=1$, and again for $j=0,1,\ldots,b-1$ we obtain
\begin{equation}\label{3.6d}
\omega(b+j+1;Z) = z_j\omega(2;Z^T)+z_{b+j}\omega(1;Z^T) = z_jz_1^{t_1}+z_{b+j},
\end{equation}
where we have used \eqref{3.5} and \eqref{3.6a} for $j=2$. Now \eqref{3.6} with
$j=0$ gives \eqref{3.6b}, and for $j=1,2,\ldots,b-1$ we get \eqref{3.6c} when
$j$ is again shifted by 1.
\end{proof}
As a specific (partial) example of Corollary~\ref{cor:3.2} we consider the case
$b=3$ and $\lambda=4$ in Table~1. Then \eqref{3.6a} and \eqref{3.6b}
correspond to the entries for $n=2, 3, 4$. The identity \eqref{3.6c}
corresponds only to $n=5$ since we don't have $\lambda\geq 2b$. However, we see
that Corollary~\ref{cor:3.2} could easily be extended to give further explicit
partial sequences of polynomials when $\lambda$ is large enough compared with
$b$.
We now consider several special cases of Theorem~\ref{thm:3.1}.
As a first such case, we let $\lambda=b$ and use the identity \eqref{2.5}.
Then $\ell=1$, and \eqref{3.6} reduces to
\begin{equation}\label{3.10}
\omega_{b,T}(bn+j+1;Z) = z_j\omega_{b,T}(n+1;Z^T) + z_{b+j}\omega_{b,T}(n;Z^T)
\end{equation}
for $j=0, 1, \ldots, b-1$. But we have $z_0=1$ and $z_{b+j}=0$ for $j\geq 1$,
which leads to the following result.
\begin{corollary}\label{cor:3.3}
Let $b\geq 2$, $Z=(z_1,\ldots,z_b)$, and $T=(t_1,\ldots,t_b)$. Then we have
$\omega_{b,T}(0;Z)=0$, $\omega_{b,T}(1;Z)=1$, and for $n\geq 0$,
\begin{align*}
\omega_{b,T}(bn+1;Z) &= \omega_{b,T}(n+1;Z^T) + z_b\omega_{b,T}(n;Z^T),\\
\omega_{b,T}(bn+j+1;Z) &= z_j\omega_{b,T}(n+1;Z^T)\quad (j=1, 2, \ldots, b-1).
\end{align*}
\end{corollary}
We have thus recovered \eqref{3.3} and \eqref{3.4}. As our next special case
we consider $b=2$, with general $\lambda\geq 1$. We separate the two cases
$j=0$ and $j=b-1=1$ in \eqref{3.6} and note again that $z_0=1$. Then we get the
following corollary.
\begin{corollary}\label{cor:3.4}
Let $\lambda\geq 1$ and $Z=(z_1,\ldots,z_\lambda)$, $T=(t_1,\ldots,t_\lambda)$.
Then we have $\omega_{2,T}^\lambda(0;Z)=0$, $\omega_{2,T}^\lambda(1;Z)=1$, and
for $n\geq 0$,
\begin{align}
\omega_{2,T}^\lambda(2n+1;Z) &= \omega_{2,T}^\lambda(n+1;Z^T)
+\sum_{k=1}^{\lfloor\lambda/2\rfloor}z_{2k}\omega_{2,T}^\lambda(n-k+1;Z^T),\label{3.11}\\
\omega_{2,T}^\lambda(2n+2;Z)
&=\sum_{k=0}^{\lfloor\lambda/2\rfloor}z_{2k+1}\omega_{2,T}^\lambda(n-k+1;Z^T),\label{3.12}
\end{align}
where $z_{\lambda+1}=0$ and $\omega_{2,T}^\lambda(m;Z)=0$ when $m\leq 0$.
\end{corollary}
When $Z=(1,\ldots,1)$, then $T$ is irrelevant and by \eqref{2.6} we have
$\omega_{2,T}^\lambda(n+1;Z)=S_2^\lambda(n)$, the restricted binary partition
function defined by \eqref{1.1}. Since $z_{\lambda+1}=0$, the identity
\eqref{3.12} needs to be split into two cases according to the parity of
$\lambda$, as indicated in the following corollary.
\begin{corollary}\label{cor:3.5}
Let $\lambda\geq 1$ be an integer. Then we have the recurrence relation
$S_2^\lambda(0)=1$, and for $n\geq 0$,
\begin{align}
S_2^\lambda(2n) &= \sum_{k=0}^{\lfloor\lambda/2\rfloor}S_2^\lambda(n-k),\label{3.13}\\
S_2^\lambda(2n+1) &= \sum_{k=0}^{\lambda/2-1}S_2^\lambda(n-k)\qquad(\lambda\;\hbox{even}),\label{3.14}\\
S_2^\lambda(2n+1) &= \sum_{k=0}^{(\lambda-1)/2}S_2^\lambda(n-k)\qquad(\lambda\;\hbox{odd}),\label{3.15}
\end{align}
where $S_2^\lambda(m)=0$ when $m<0$.
\end{corollary}
The three identities in Corollary~\ref{cor:3.5} can be found in
Theorem~2.4 of \cite{Re}, with different notation.
More generally, we can consider arbitrary bases $b\geq 2$, while still setting
$Z=(1,1,\ldots,1)$ and using \eqref{2.6}, namely
$\omega_{b,T}^\lambda(n+1;Z)=S_b^\lambda(n)$. Since $z_\mu=0$ for $\mu>\lambda$,
we also have to split \eqref{3.6} into two cases.
\begin{corollary}\label{cor:3.6}
Let $b\geq 2$ and $\lambda\geq 1$ be integers with $\lambda=\ell b+r$,
$0\leq r\leq b-1$. Then we have the recurrence relation $S_b^\lambda(0)=1$, and
for $n\geq 0$,
\begin{align}
S_b^\lambda(bn+j) &= \sum_{k=0}^\ell S_b^\lambda(n-k)\qquad(0\leq j\leq r),\label{3.16}\\
S_b^\lambda(bn+j) &= \sum_{k=0}^{\ell-1}S_b^\lambda(n-k)\qquad(r+1\leq j\leq b-1),\label{3.17}
\end{align}
where $S_b^\lambda(m)=0$ for $m<0$.
\end{corollary}
The identities \eqref{3.16} and \eqref{3.17} were previously obtained by
Dumont et al.\ as Equation (6.2) in \cite{DST}.
The last corollary of Theorem~\ref{thm:3.1} in this section is a special case
that is somewhat similar to Corollary~\ref{cor:3.3} and is related to the unique
$b$-ary representation of a positive integer. If we take $\lambda=b-1$ for any
$b\geq 2$, then we have $\ell=0$, and with \eqref{3.6} and the fact that $z_0=1$
we get the following recurrence relation.
\begin{corollary}\label{cor:3.7}
Let $b\geq 2$ be an integer, and $Z=(z_1,\ldots,z_{b-1})$,
$T=(t_1,\ldots,t_{b-1})$ be ordered sets of variables, resp.\ positive integers.
Then we have $\omega_{b,T}^{b-1}(0;Z)=0$, $\omega_{b,T}^{b-1}(1;Z)=1$, and for
$n\geq 0$,
\begin{align}
\omega_{b,T}^{b-1}(bn+1;Z) &= \omega_{b,T}^{b-1}(n+1;Z^T),\label{3.18}\\
\omega_{b,T}^{b-1}(bn+j+1;Z) &= z_j\omega_{b,T}^{b-1}(n+1;Z^T)\qquad
(1\leq j\leq b-1).\label{3.19}
\end{align}
\end{corollary}
\noindent
\begin{example}\label{ex:2nd}
We use Corollary~\ref{cor:3.7} with $b=3$, $Z=(y,z)$, and
$T=(s,t)$. Then \eqref{3.18} and \eqref{3.19} can be written as
\begin{align*}
\omega_{3,T}^2(3n+1;Z) &= \omega_{3,T}^2(n+1;y^s,z^t),\\
\omega_{3,T}^2(3n+2;Z) &= y\cdot\omega_{3,T}^2(n+1;y^s,z^t),\\
\omega_{3,T}^2(3n+3;Z) &= z\cdot\omega_{3,T}^2(n+1;y^s,z^t).
\end{align*}
The first 14 nontrivial polynomials, evaluated using these recurrences, are
listed in Table~2. They are obviously all monomials.
\end{example}
\bigskip
\begin{center}
\begin{tabular}{|r|c|c||r|c|c|}
\hline
$m$ & ternary & $\omega_{3,T}^2(m+1;Z)$ & $m$ & ternary & $\omega_{3,T}^2(m+1;Z)$ \\
\hline
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^sz$ & 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$\\
\hline
\end{tabular}
\medskip
{\bf Table~2}: $\omega_{3,T}^2(m+1;y,z)$, $T=(s,t)$, $1\leq m\leq 14$.
\end{center}
\bigskip
Table~2 can also be seen as another illustration of Theorem~\ref{thm:2.3} 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.
\medskip
To conclude this section, we state and prove a recurrence relation for the more
general polynomials $\omega_{b,T}^V(n;Z)$ that were introduced in
Definition~\ref{def:2.2}.
\begin{theorem}\label{thm:3.8}
Let $b\geq 2$ and $\lambda\geq 1$ be integers, and $V=(v_1,\ldots,v_\lambda)$
a strictly increasing sequence of positive integers. Furthermore, let
$Z$ and $T$ be as specified in \eqref{3.4a}, and define the $v_\lambda$-tuple
$\widetilde{Z}=(\widetilde{z}_1,\widetilde{z}_2,\ldots,\widetilde{z}_{v_\lambda})$ by
\begin{equation}\label{3.20}
\widetilde{z}_j=\begin{cases}
z_k, &\hbox{when}\quad j=v_k,\;k=1,2,\ldots,\lambda;\\
0, &\hbox{when}\quad j\not\in V.
\end{cases}
\end{equation}
Then we have the recurrence relation $\omega_{b,T}^V(0;Z)=0$,
$\omega_{b,T}^V(1;Z)=1$, and for each integer $n\geq 0$,
\begin{equation}\label{3.21}
\omega_{b,T}^V(bn+j+1;Z)
= \sum_{k=0}^{\lfloor v_\lambda/b\rfloor}\widetilde{z}_{kb+j}\omega_{b,T}^V(n-k+1;Z^T)
\qquad (j=0,1,\ldots,b-1),
\end{equation}
with the conventions that $\widetilde{z}_0=1$, $\widetilde{z}_\mu=0$ for
$\mu > \lambda$, and $\omega_{b,T}^V(m;Z)=0$ when $m\leq 0$.
\end{theorem}
\begin{proof}
In analogy to \eqref{3.20} we set
\[
\widetilde{t}_j=\begin{cases}
t_k, &\hbox{when}\quad j=v_k,\;k=1,2,\ldots,\lambda;\\
1, &\hbox{when}\quad j\not\in V.
\end{cases}
\]
Then with this definition and with \eqref{3.20} we see that we can write
\begin{equation}\label{3.22}
\omega_{b,T}^V(n;Z) = \omega_{b,\widetilde{T}}^{v_\lambda}(n;\widetilde{Z}),
\end{equation}
where the right-hand side of \eqref{3.22} is a polynomial of the type in
Definition~\ref{def:2.1}, with $v_\lambda$ used in place of $\lambda$. We can
therefore apply Theorem~\ref{thm:3.1}, which immediately gives
Theorem~\ref{thm:3.8}, with $\lfloor v_\lambda/b\rfloor$ in place of $\ell$.
\end{proof}
\noindent
\begin{example}\label{ex:3rd}
Let $b=2$ and $V=(1,3,4)$. Then $\lfloor v_\lambda/b\rfloor=2$,
$Z=(x,y,z)$, $T=(r,s,t)$, and $\widetilde{Z}=(x,0,y,z)$. Therefore
\[
\widetilde{z}_0=1,\quad \widetilde{z}_1=x,\quad \widetilde{z}_2=0,\quad
\widetilde{z}_3=y,\quad \widetilde{z}_4=z,\quad \widetilde{z}_5=0,
\]
and thus \eqref{3.21}, written separately for $j=0$ and $j=1$, gives
\begin{align*}
\omega_{2,T}^V(2n+1;x,y,z) &= \omega_{2,T}^V(n+1;x^r,y^s,z^t)
+ z\cdot\omega_{2,T}^V(n-1;x^r,y^s,z^t),\\
\omega_{2,T}^V(2n+2;x,y,z) &= x\cdot\omega_{2,T}^V(n+1;x^r,y^s,z^t)
+ y\cdot\omega_{2,T}^V(n;x^r,y^s,z^t).
\end{align*}
These last two identities, together with the initial conditions
$\omega_{2,T}^V(0;Z)=0$ and $\omega_{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 \eqref{2.12} in Example~\ref{ex:1st}.
\end{example}
\bigskip
\begin{center}
\begin{tabular}{|r|l||r|l|}
\hline
$m$ & $\omega_{2,T}^V(m;x,y,z)$ & $m$ & $\omega_{2,T}^V(m;x,y,z)$ \\
\hline
1 & $1$ & 6 & $x^{1+r^2}+x^ry$ \\
2 & $x$ & 7 & $x^{r+r^2}+y^s+x^rz$ \\
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}$ \\
\hline
\end{tabular}
\medskip
{\bf Table~3}: $\omega_{2,T}^V(m;x,y,z)$, $T=(r,s,t)$, $V=(1,3,4)$,
$1\leq m\leq 10$.
\end{center}
\section{Proof of Theorem~\ref{thm:2.3}}
In this relatively brief section we use the general recurrence relation,
Theorem~\ref{thm:3.8}, to prove our main representation theorem, namely
Theorem~\ref{thm:2.3}. In what follows, in order to simplify terminology, we
refer to a restricted $b$-ary partition of $m$ in the sense of \eqref{2.8}
simply as a ``representation of $m$".
We fix the integers $b\geq 2$, $\lambda\geq 1$, and the $\lambda$-tuples $T$,
$V$, and $Z$ as in Theorems~\ref{thm:2.3} and~\ref{thm:3.8}. As we did in
earlier proofs, we suppress the subscripts and superscript of $\omega$. We now
proceed by induction on $m$.
\medskip
{\bf 1.} For the induction beginning we consider \eqref{3.21} with $n=0$. Since
$\omega(0;Z)=0$ and $\omega(1;Z)=1$, we find for $j=0,1,\ldots,b-1$ that
\begin{equation}
\omega(j+1;Z) = \widetilde{z}_j
= \begin{cases}
z_k, &\hbox{when}\; j=v_k,\; k=1, 2,\ldots,\lambda;\\
0, &\hbox{when}\; j\not\in V,\; j\geq 1;\\
1, &\hbox{when}\; j=0.
\end{cases}
\end{equation}
Here we have used \eqref{3.20} and the convention $\widetilde{z}_0=1$.
On the other hand, the only representation of $j=1,2,\ldots,b-1$ is
$v_k=v_kb^0$ when $j=v_k$, while $j$ has no representation when $j\not\in V$.
This is consistent with \eqref{2.13} and \eqref{2.14}, namely
\[
\omega(j+1;Z) = z_k^1,\qquad 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~\ref{thm:2.3} holds for $m=j$, $1\leq j\leq b-1$. This concludes
the induction beginning.
\medskip
{\bf 2.} Now we assume that Theorem~\ref{thm:2.3} is true for all $m\leq nb-1$,
for some $n\geq 1$. We wish to show that it is then also true for $m=nb+j$,
for all $j=0,1,\ldots,b-1$.
To do so, we fix $j$, $0\leq j\leq b-1$, and consider all representations of
$nb+j$. They can be obtained recursively as follows. We fix an integer
$k\geq 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\not\in V$,
(d) do (a) and (b) for all $k\geq 0$ that satisfy $kb+j\leq v_\lambda$.
\noindent
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 $\lfloor v_\lambda/b\rfloor$.
\medskip
{\bf 3.} Using the induction hypothesis and \eqref{2.13}, we have
\begin{equation}\label{4.2}
\omega(n-k+1;Z)=\sum_{h\in{\mathbb H}_b^V(n-k)}
z_1^{p_{h,1}(t_1)}\cdots z_\lambda^{p_{h,\lambda}(t_\lambda)},
\end{equation}
with exponents $p_{h,1}(t_1),\ldots,p_{h,\lambda}(t_\lambda)$ as in
\eqref{2.14}. 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\leq i\leq\lambda$, are augmented by 1. In addition, for each $k$ with
$0\leq k\leq\lfloor v_\lambda/b\rfloor$ and satisfying $kb+j\in V$ (say
$kb+j=v_r$, $1\leq r\leq\lambda$) 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\not\in 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\leq k\leq\lfloor v_\lambda/b\rfloor$ (step (d)), we get the
polynomials
\begin{equation}\label{4.3}
P_k := \sum_{h'\in{\mathbb H}_b^V(nb+j)}
z_1^{p_{h',1}(t_1)}\cdots z_\lambda^{p_{h',\lambda}(t_\lambda)},
\end{equation}
where $h'$ ranges over all those representations of $nb+j$ that have exactly
$v_r=kb+j$ times the part $b^0$, and
\begin{equation}\label{4.4}
p_{h',r}(t_r)=1+t_rp_{h,r}(t_r),\qquad
p_{h',i}(t_i)=t_ip_{h,i}(t_i)\quad(1\leq i\leq\lambda, i\neq r).
\end{equation}
Now with \eqref{4.2} and \eqref{4.4}, the sum in \eqref{4.3} becomes
\begin{align}
P_k &= z_r\sum_{h\in{\mathbb H}_b^V(n-k)}(z_1^{t_1})^{p_{h,1}(t_1)}\cdots
(z_\lambda^{t_\lambda})^{p_{h,\lambda}(t_\lambda)}\label{4.5} \\
&= z_r\omega(n-k+1;Z^T),\nonumber
\end{align}
where we have used the notation \eqref{3.5}.
Finally we sum \eqref{4.5} over all $k$,
$0\leq k\leq\lfloor v_\lambda/b\rfloor$, and use the fact that by \eqref{3.20}
we have $\widetilde{z}_{kb+j}=z_r$ when $kb+j\in V$, and
$\widetilde{z}_{kb+j}=0$ otherwise. Then the representations of $nb+j$ are
characterized by
\begin{equation}\label{4.6}
\sum_{k=0}^{\lfloor v_\lambda/b\rfloor}\widetilde{z}_{kb+j}\omega(n-k+1;Z^T)
= \omega(bn+j+1;Z),
\end{equation}
where the right-hand side of \eqref{4.6} comes from \eqref{3.21}.
Therefore all the representations of $nb+j$ are
characterized by $\omega(bn+j+1;Z)$; and since this holds for any $j$,
$0\leq j\leq b-1$, the proof by induction of the main statement of
Theorem~\ref{thm:2.3} is now complete.
It only remains to show that for each $h\in{\mathbb H}_b^V(m)$ the polynomials
$p_{h,i}(t_i)$, $i=1,\ldots,\lambda$, have only 0 and 1 as coefficients. But
this follows from \eqref{4.4}, again by induction.
\section{Explicit Formulas}
In \cite{Ca} 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}^*\in\{0,1\}$, then
Carlitz's result can be written as
\begin{equation}\label{5.1}
s(n+1) = \sum_{k=0}^{\lfloor\frac{n}{2}\rfloor}\binom{n-k}{k}^*\qquad(n\geq 0).
\end{equation}
In \cite{DE7} we extended the identity \eqref{5.1} to 2-variable Stern
polynomials, again in base $b=2$. To state this and further results, we need the
following definition from \cite{DE7}.
For an integer $k\geq 0$, let $k=\sum_{j\geq 0}c_j2^j$, $c_j\in\{0,1\}$, be the
binary expansion of $k$. Then for an integer base $t\geq 1$ we define
\begin{equation}\label{5.2}
d_t(k):=\sum_{j\geq 0}c_jt^j.
\end{equation}
Various small values of $d_t(k)$ can be found in Table~2 of \cite{DE2}, with
references to the OEIS \cite{OEIS}.
With the definition \eqref{5.2} and notation from \eqref{2.4}, the
polynomial extension of \eqref{5.1} in \cite{DE7} can be stated as
\begin{equation}\label{5.3}
\omega_{2,T}^2(n+1;y,z) =\sum_{k=0}^{\lfloor\frac{n}{2}\rfloor}\binom{n-k}{k}^* y^{d_s(n-2k)}z^{d_t(k)},
\end{equation}
where $T=(s,t)$. As indicated in \cite{No}, the identity \eqref{5.1} can be
rewritten as
\begin{equation}\label{5.4}
\sum_{k=0}^{\lfloor\frac{n}{2}\rfloor}\binom{n-k}{k}^*
= \sum_{j+ 2k=n} \binom{j+k}{k}^*,
\end{equation}
and similarly, we can rewrite \eqref{5.3} as
\begin{equation}\label{5.5}
\omega_{2,T}^2(n+1;y,z) = \sum_{k_1+2k_2=n}\binom{k_1+k_2}{k_2}^*
y^{d_s(k_1)}z^{d_t(k_2)}.
\end{equation}
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+\cdots+k_\lambda}{k_1,\ldots,k_\lambda}^*$ to be the least
nonnegative residue of the multinomial coefficient
$\binom{k_1+\cdots+k_\lambda}{k_1,\ldots,k_\lambda}$ modulo 2.
\begin{theorem}\label{thm:5.1}
Let $\lambda\geq 1$ be an integer, $V=(v_1,\ldots,v_\lambda)$ a strictly
increasing sequence of positive integers, and $Z$ and $T$ as in \eqref{3.4a}.
Then for $n\geq 0$ we have
\begin{equation}\label{5.6}
\omega_{2,T}^V(n+1;Z) = \sum_{v_1k_1+v_2k_2+\cdots+v_{\lambda}k_{\lambda}=n}
\binom{k_1+\cdots+k_\lambda}{k_1,\ldots,k_\lambda}^*
z_1^{d_{t_1}(k_1)}\cdots z_\lambda^{d_{t_\lambda}(k_\lambda)}.
\end{equation}
%where the sum is taken over all partitions of $n$ with parts in $V$.
\end{theorem}
\begin{example}\label{ex:4th}
With $\lambda=3$, $V=(1,3,4)$, $Z=( x,y,z)$, and $T=(r,s,t)$,
the identity \eqref{5.6} becomes
\begin{equation}\label{5.7}
\omega_{2,T}^V(n+1;Z) = \sum_{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)}.
\end{equation}
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 \eqref{5.7}
becomes
\begin{align*}
\omega_{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.
\end{align*}
This is consistent with \eqref{2.12} in Example~\ref{ex:1st}; see also Table~3.
\end{example}
\medskip
We note that the sum in \eqref{5.6} is taken over all partitions of $n$ with
parts in $V$. In the special case $V=(1,2,\ldots,\lambda)$, we get the
following immediate consequence of Theorem~\ref{thm:5.1}.
\begin{corollary}\label{cor:5.2}
Let $\lambda\geq 1$ be an integer, and $Z$ and $T$ as in \eqref{3.4a}.
Then for $n\geq 0$ we have
\begin{equation}\label{5.8}
\omega_{2,T}^\lambda(n+1;Z) = \sum_{k_1+2k_2+\cdots+\lambda k_{\lambda}=n}
\binom{k_1+\cdots+k_\lambda}{k_1,\ldots,k_\lambda}^*
z_1^{d_{t_1}(k_1)}\cdots z_\lambda^{d_{t_\lambda}(k_\lambda)}.
\end{equation}
\end{corollary}
We now see that the identity \eqref{5.5} is the case $\lambda=2$ of
Corollary~\ref{cor:5.2}. If we set $Z=(1,\ldots,1)$ in \eqref{5.6} and use
\eqref{2.10}, we get the following extension of \eqref{5.1} and \eqref{5.4}.
\begin{corollary}\label{cor:5.3}
Let $\lambda\geq 1$ be an integer and $V=(v_1,\ldots,v_\lambda)$ a strictly
increasing sequence of positive integers. Then for $n\geq 0$ we have
\begin{equation}\label{5.9}
S_2^V(n) = \sum_{v_1k_1+v_2k_2+\cdots+v_{\lambda}k_{\lambda}=n}
\binom{k_1+\cdots+k_\lambda}{k_1,\ldots,k_\lambda}^*,
\end{equation}
where $S_2^V(n)$ is the number of restricted binary partitions of $n$, as
defined in \eqref{2.9}.
\end{corollary}
Theorem~\ref{thm:5.1} is a special case of a more general result, which in
turn is a consequence of the following lemma.
\begin{lemma}\label{lem:5.4}
Let $b\geq 2$ and $\lambda\geq 1$ be integers, $V=(v_1,\ldots,v_\lambda)$ a
strictly increasing sequence of positive integers, and $Z$ and $T$ as in
\eqref{3.4a}. Then for $n\geq 0$ we have
\begin{equation}\label{5.10}
\omega_{b,T}^V(n+1;Z) = \sum
\prod_{j\geq 0}(z_{i_j})^{t_{i_j}^j},
\end{equation}
where the sum is taken over all representations
$v_{i_0}+v_{i_1}b+v_{i_2}b^2+\cdots=n$ in ${\mathbb H}_b^V(n)$ as defined in
\eqref{2.8}, and where we set $z_0=1$ and $v_0=0$ by convention.
\end{lemma}
\begin{example}\label{ex:5th}
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~\ref{lem:5.4}, are then given as
follows:
\begin{center}
%\medskip
\begin{tabular}{rcrcl}
$2\cdot 3+1\cdot 3^2$ & $\longleftrightarrow$ & $z_2^{t_2}z_1^{t_1^2}$ & $=$ & $ w^qv^{p^2}$, \\
$3\cdot 1+1\cdot 3+1\cdot 3^2$ & $\longleftrightarrow$ &$z_3^{t_3^0}z_1^{t_1}z_1^{t_1^2}$ & $=$ & $xv^{p+p^2}$, \\
$5\cdot 3$ & $\longleftrightarrow$ & $z_5^{t_5}$ & $=$ & $ z^t$, \\
$3\cdot 1+4\cdot 3$ & $\longleftrightarrow$ & $z_3^{t_3^0}z_4^{t_4}$ & $=$ & $ xy^s$.\\
\end{tabular}
\end{center}
\medskip
\noindent
In accordance with \eqref{5.10} these monomials are the terms of the polynomial
\[
\omega_{3,T}^5(16;Z) = w^qv^{p^2}+xv^{p+p^2}+z^t+xy^s.
\]
\end{example}
\begin{proof}[Proof of Lemma~\ref{lem:5.4}]
If we divide both sides of \eqref{2.7} by $\zeta$, we see that the infinite
product on the right-hand side of \eqref{2.7} is the generating function of the
polynomial sequence $\omega_{b,T}^V(n+1;Z)$ for $n\geq 0$.
On the other hand, for a fixed $n$ the product in \eqref{2.7} shows that all
powers of $\zeta^n$ are of the form
\[
\zeta^n = \prod_{j\geq 0}\zeta^{v_{i_j}b^j},
\]
or, in terms of the exponents,
\begin{equation}\label{5.11}
n = \sum_{j\geq 0}v_{i_j}b^j,\qquad 0\leq i_j\leq\lambda,\qquad
v_0=0,\; v_i\in V\; (1\leq i\leq\lambda).
\end{equation}
The structure of the factors on the right-hand side of \eqref{2.7} also shows
that the monomial $z_1,\ldots,z_\lambda$ corresponding to the exponent $n$ in
\eqref{5.11} is
\begin{equation}\label{5.12}
\prod_{j\geq 0}(z_{i_j})^{t_{i_j}^j}.
\end{equation}
Summing over all representations of $n$ as in \eqref{5.11}, we obtain the
identity \eqref{5.10}.
\end{proof}
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\geq 2$ be a fixed integer.
First we define the set
\begin{equation}\label{5.13}
M_b := \left\{\sum_{j\geq 0}c_jb^j\mid c_j\in\{0,1\}\right\},
\end{equation}
i.e., the set of all nonnegative integers whose $b$-ary digits are only 0 or 1.
Clearly we have $M_2={\mathbb N}\cup\{0\}$.
Next we extend \eqref{5.2} as follows. Let $k\in M_b$ with
$k=\sum_{j\geq 0}c_jb^j$, $c_j\in\{0,1\}$. Then for an integer base $t\geq 1$
we define
\begin{equation}\label{5.14}
d_t^b(k):=\sum_{j\geq 0}c_jt^j.
\end{equation}
It is clear that $d_t^2(k)=d_t(k)$ and $d_b^b(k)=k$ for all integers $b\geq 2$
and $k\in M_b$.
Finally, we extend the multinomial coefficient modulo 2, as used in
Theorem~\ref{thm:5.1}. If $k_1,\ldots,k_\lambda\in M_b$, we set
\begin{equation}\label{5.15}
\binom{k_1+\cdots+k_\lambda}{k_1,\ldots,k_\lambda}_b^*
:=\binom{d_2^b(k_1)+\cdots+d_2^b(k_\lambda)}{d_2^b(k_1),\ldots,d_2^b(k_\lambda)}^*,
\end{equation}
with the right-hand side of \eqref{5.15} as defined earlier, just before
Theorem~\ref{thm:5.1}. We are now ready to state a result that generalizes
Theorem~\ref{thm:5.1}.
\begin{theorem}\label{thm:5.5}
Let $b\geq 2$ and $\lambda\geq 1$ be integers, $V=(v_1,\ldots,v_\lambda)$ a
strictly increasing sequence of positive integers, and $Z$ and $T$ as in
\eqref{3.4a}. Then for $n\geq 0$ we have
\begin{equation}\label{5.16}
\omega_{b,T}^V(n+1;Z)
= \sum_{\substack{v_1k_1+v_2k_2+\cdots+v_{\lambda}k_{\lambda}=n\\k_1,\ldots,k_\lambda\in M_b}}
\binom{k_1+\cdots+k_\lambda}{k_1,\ldots,k_\lambda}_b^*
z_1^{d_{t_1}^b(k_1)}\cdots z_\lambda^{d_{t_\lambda}^b(k_\lambda)}.
\end{equation}
%where the sum is taken over all $(k_1,\ldots,k_\lambda)$ satisfying
%$v_1k_1+v_2k_2+\cdots+v_{\lambda}k_{\lambda}=n$, with the additional
\end{theorem}
Before proving this result, we note that it immediately implies
Theorem~\ref{thm:5.1}. Indeed, when $b=2$, the multinomial coefficient defined
in \eqref{5.15} reduces to the one in \eqref{5.6} since $d^2_2(k_i) = k_i$.
Then in the $b=2$ case we also have $d^b_{t_i}(k_i) = d_{t_i}(k_i)$,
and the conditions concerning $M_b$ become irrelevant.
For the proof of Theorem~\ref{thm:5.5} we require the following result due to
Dickson \cite{Di}, which we state as a lemma. See also the more recent
paper \cite{MM}.
\begin{lemma}[Dickson]\label{lem:5.6}
Let $p$ be a prime and $\lambda\geq 2$ an integer, and suppose that the
positive integers $k_1,\ldots,k_\lambda$ and $k:=k_1+\cdots+k_\lambda$ are
given in base-$p$ representation as
\begin{align*}
k_i &= a_0^i+a_1^ip+\cdots+a_m^ip^m,\qquad i=1,\ldots,\lambda,\\
k &= a_0+a_1p+\cdots+a_mp^m.
\end{align*}
Then we have
\begin{equation}\label{5.17}
\binom{k}{k_1,\ldots,k_\lambda} \not\equiv 0\pmod{p},
\end{equation}
if and only if
\begin{equation}\label{5.18}
a_j = a_j^1 +\cdots+a_j^\lambda
\end{equation}
holds for all $j=1,\ldots,m$.
\end{lemma}
\begin{proof}[Proof of Theorem~\ref{thm:5.5}]
We begin with Lemma~\ref{lem:5.4} and its proof. The representation of $n$ in
\eqref{5.11} can be rewritten as
\begin{equation}\label{5.19}
n = v_1k_1 + v_2k_2 +\cdots+v_\lambda k_\lambda,
\end{equation}
where for each $r=1,2,\ldots,\lambda$ we have
\[
k_r := \sum_{i_j=r}b^j,
\]
for integers $i_j$ with $0\leq i_j\leq\lambda$.
This means that each power $b^0, b^1, b^2,\ldots$ occurs in the base-$b$
representation of at most one of the integers $k_1,k_2,\ldots,k_\lambda$, which
in turn implies that
\begin{enumerate}
\item[(i)] $k_i\in M_b$ for all $i=1,2,\ldots,\lambda$, and
\item[(ii)] the powers $b^0, b^1, b^2,\ldots$ do not ``overlap" in the sum
$k_1+\cdots+k_\lambda$.
\end{enumerate}
Furthermore, as $n$ is rewritten in the form \eqref{5.19}, the corresponding
monomial in \eqref{5.12} can be rewritten as
\begin{equation}\label{5.20}
\prod_{i=1}^\lambda z_i^{d_{t_i}^b(k_i)},
\end{equation}
where we have used the definition \eqref{5.14}.
We are now going to characterize condition (ii), noting that condition (i) is
taken care of by the summation in \eqref{5.16}. If for each
$i=1,2,\ldots,\lambda$ we replace
\[
k_i = c_0^i + c_1^ib + \cdots + c_{j_i}b^{j_i} \in M_b
\]
by
\[
d_2^b(k_i) = c_0^i + c_1^i2 + \cdots + 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)+\cdots+d_2^b(k_\lambda)$. This, in turn, means that for each
power of 2, say $2^\nu$, the sum of the coefficients of $2^\nu$ in
$d_2^b(k_1),\ldots,d_2^b(k_\lambda)$, namely 0 or 1, is exactly the coefficient
of $2^\nu$ in $S$. Hence the condition \eqref{5.18} in Lemma~\ref{lem:5.6} with
$p=2$ is satisfied, and by \eqref{5.17} and \eqref{5.15} the modified
multinomial coefficient in \eqref{5.16} is 1. Therefore the product \eqref{5.20}
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 $\nu\geq 0$
such that
\[
c_\nu^1+c_\nu^2+\cdots+c_\nu^\lambda \geq 2,
\]
while the coefficient of $2^\nu$ in $S$ is only 0 or 1. Therefore the
condition \eqref{5.18} in Lemma~\ref{lem:5.6} (again with $p=2$) is not
satisfied, and by \eqref{5.17} and \eqref{5.15} the modified multinomial
coefficient in \eqref{5.16} is 0. This completes the proof of
Theorem~\ref{thm:5.5}.
\end{proof}
\begin{example}\label{ex:6th}
As in Example~\ref{ex:5th}, 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 \eqref{5.16}, namely
$k_i\in M_3=\{0,1,3,4,9,10,12,27,\ldots\}$, $1\leq i\leq 5$. For
only four of these partitions the modified multinomial coefficient in
\eqref{5.16} is 1, namely for
\begin{equation}\label{5.21}
(k_1,\ldots,k_5)=(9,3,0,0,0),\quad (12,0,1,0,0),\quad (0,0,1,3,0),\quad (0,0,0,0,3).
\end{equation}
Hence \eqref{5.16} with $Z=(v,w,x,y,z)$ and $T=(p,q,r,s,t)$ gives
\begin{align*}
\omega_{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,
\end{align*}
which is consistent with the result of Example~\ref{ex:5th}.
\end{example}
\medskip
\noindent
{\bf Remark.} A necessary condition for the product \eqref{5.20} to be
included in \eqref{5.16} is $k_1+\cdots+k_\lambda\in M_b$, since otherwise
condition (ii) in the proof of Theorem~\ref{thm:5.5} is obviously not
satisfied. However, this condition is not sufficient, as the following example
shows.
On the other hand, we conjecture that a necessary {\it and} sufficient condition
for the product \eqref{5.20} to be included in \eqref{5.16} is that all
possible partial sums of elements of $\{k_1,\ldots,k_\lambda\}$ be in $M_b$.
A further analysis would go beyond the scope of this paper; we leave this to
the interested reader.
\medskip
\begin{example}\label{ex:7th}
Continuing with Example~\ref{ex:6th}, we note that of the 25
partitions that satisfy $k_i\in M_3$, $1\leq i\leq 5$, there are 19 such that
$k_1+\cdots+k_5\not\in M_3$. The remaining six partitions obviously include
the four in \eqref{5.21}, while $(k_1,\ldots,k_5)=(10,1,1,0,0)$ and
$(4,4,1,0,0)$ are excluded by way of the modified multinomial
coefficients as in \eqref{5.16}, or by the fact that, for instance,
$1+1\not\in M_3$ and $4+1\not\in M_3$.
\end{example}
\section{Further Remarks}
We recall that Definition~\ref{def:2.1} and most of the results that
follow are valid for all $\lambda\geq 1$, regardless of the base $b\geq 2$.
While in most of this paper we were interested in the case $\lambda\geq b-1$
(or even $\lambda\geq b$), we are now going to consider the case
$\lambda\leq b-2$ when $b\geq 3$. We begin with a consequence of
Theorem~\ref{thm:3.1}.
\begin{corollary}\label{cor:6.1}
Let $b\geq 3$ and $1\leq\lambda\leq b-2$ be integers, and let $Z$ and $T$ be
given by \eqref{3.4a}. Then we have $\omega_{b,T}^\lambda(0;Z)=0$,
$\omega_{b,T}^\lambda(1;Z)=1$, and for each $n\geq 0$ we have
\begin{equation}\label{6.1}
\omega_{b,T}^\lambda(bn+j;Z) = \begin{cases}
\omega_{b,T}^\lambda(n+1;Z^T), &\hbox{when}\;\;\lambda=1;\\
z_j\omega_{b,T}^\lambda(n+1;Z^T), &\hbox{when}\;\;2\leq j\leq\lambda;\\
0, &\hbox{when}\;\;\lambda+1\leq j\leq b-1.
\end{cases}
\end{equation}
\end{corollary}
This follows immediately from Theorem~\ref{thm:3.1} since
$\ell=\lfloor\lambda/b\rfloor=0$, $z_0=1$, and $z_{\lambda+1}=\cdots=z_{b-1}=0$.
Corollary~\ref{cor:6.1} can also be seen as an extension of
Corollary~\ref{cor:3.7}.
By iterating \eqref{6.1}, we immediately get the following result which
characterizes the cases in which the polynomials are zero when
$\lambda\leq b-2$.
\begin{corollary}\label{cor:6.2}
Let $b\geq 3$ and $1\leq\lambda\leq b-2$ be integers, and $Z$ and $T$ as in
\eqref{3.4a}. If the integer $m\geq 0$ has the base-$b$ representation
$m=\sum_{i=0}^r c_ib^i$, $0\leq c_i\leq b-1$ for $0\leq i\leq r$, then
\[
\omega_{b,T}^\lambda(m+1;Z) = 0\quad\hbox{if and only if}\quad
\lambda\leq c_i\leq b-2
\]
for at least one index $i$, $0\leq i\leq r$.
\end{corollary}
\begin{example}\label{ex:8th}
Let $b=4$ and $\lambda=2$, with $Z=(y,z)$ and $T=(s,t)$. Then
Corollary~\ref{cor:6.1} leads to the entries of Table~4, which also illustrates
Corollary~\ref{cor:6.2}.
\end{example}
\bigskip
\begin{center}
\begin{tabular}{|c|c||c|c||c|c||c|c|}
\hline
$m$ & $\omega(m+1;Z)$ & $m$ & $\omega(m+1;Z)$
& $m$ & $\omega(m+1;Z)$ & $m$ & $\omega(m+1;Z)$ \\
\hline
0 & $1$ & 5 & $y^{1+s}$ & 10 & $z^{1+t}$ & 15 & 0 \\
1 & $y$ & 6 & $y^sz$ & 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 \\
\hline
\end{tabular}
\medskip
{\bf Table~4}: $\omega(m+1;Z)=\omega_{4,T}^2(m+1;Z)$, $T=(s,t)$, $Z=(y,z)$,
$0\leq m\leq 19$.
\end{center}
\bigskip
Using \eqref{2.6}, we get the following result for the integers
$S_b^\lambda(m)$ defined by \eqref{1.2}.
\begin{corollary}\label{cor:6.3}
Let $b\geq 3$ and $1\leq\lambda\leq b-2$ be integers, and suppose that
$m\geq 0$ has the base-$b$ representation $m=\sum_{i=0}^r c_ib^i$,
$0\leq c_i\leq b-1$ for $0\leq i\leq r$. Then
\[
S_b^\lambda(m) = \begin{cases}
1, & \hbox{when}\;\;0\leq c_i\leq\lambda-1\;\;\hbox{for all}\;\;0\leq i\leq r;\\
0, & \hbox{otherwise}.
\end{cases}
\]
\end{corollary}
This last result is not difficult to obtain directly. The special case where
$b$ is a prime in Corollary~\ref{cor:6.3} was mentioned in \cite{DN} in
connection with a study of products of cyclotomic polynomials.
\medskip
As a second remark, we note that Mansour and Shattuck \cite{MS} defined the
following concept.
{\it Fix $m\geq 2$ and $0\leq c\leq 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\in\{0,1,\ldots,m-1,m+c\}$.}
See \cite[Def.~1.1]{MS}.
If we compare this definition with \eqref{2.8}, we see that the set of
$c$-hyper $m$-expansions is, in our notation,
\[
{\mathbb H}_m^V(n),\quad\hbox{where}\quad V=(1,2,\ldots,m-1,m+c).
\]
Furthermore, again for $m\geq 2$ and $0\leq c\leq m-1$, Mansour and Shattuck
define the sequence of polynomials $f_{m,c}(d;q)$ for $d\geq 0$ by
\begin{align}
f_{m,c}(mn+j;q) &= f_{m,c}(n;q),\qquad 0\leq j\leq m-1,\quad j\neq c,\label{6.2}\\
f_{m,c}(mn+c;q) &= f_{m,c}(n;q)+q\,f_{m,c}(n-1;q),\label{6.3}
\end{align}
with $f_{m,c}(0;q)=1$ and $f_{m,c}(d;q)=0$ for $d<0$. See \cite[Def.~1.2]{MS}.
If we compare \eqref{6.2}, \eqref{6.3} with Theorem~\ref{thm:3.8}, where
$b=\lambda=m$ and $V=(1,2,\ldots,m-1,m+c)$, then we find
\begin{equation}\label{6.4}
f_{m,c}(d;q) = \omega_{m,T}^V(d+1,Z),
\end{equation}
with the $m$-tuples $T=(1,\ldots,1)$ and $Z=(1,\ldots,1,q)$. Also, a special
case of our Theorem~\ref{thm:2.3} for the polynomials in \eqref{6.4} was
obtained
in \cite{MS}. Apart from these connections, however, the paper \cite{MS} has a
different emphasis from ours and deals mainly with generalizations of the
well-known Calkin-Wilf tree.
\begin{thebibliography}{25}
\bibitem{An} G.~E.~Andrews, Congruence properties of the $m$-ary partition
function, {\it J. Number Theory} {\bf 3} (1971), 104--110.
\bibitem{BM} B.~Bates and T.~Mansour, The $q$-Calkin-Wilf tree,
{\it J. Combin. Theory Ser. A} {\bf 118} (2011), 1143--1151.
\bibitem{Ca} L.~Carlitz, Single variable Bell polynomials, {\it Collect.
Math.} {\bf 14} (1960), 13--25.
\bibitem{Ch} R.~F.~Churchhouse, Congruence properties of the binary partition
function, {\it Proc. Cambridge Philos. Soc.} {\bf 66} (1969), 371--376.
\bibitem{CSe} K.~M.~Courtright and J.~A.~Sellers, Arithmetic properties for
hyper $m$-ary partition functions, {\it Integers} {\bf 4} (2004), A6, 5 pp.
\bibitem{De} C.~Defant, Upper bounds for Stern's diatomic sequence and related
sequences, {\it Electron. J. Combin.} {\bf 23} (2016), Paper 4.8.
\bibitem{Di} L.~E.~Dickson, Theorems on the residues of multinomial
coefficients with respect to a prime modulus, {\it Quart. J. Pure Appl. Math.}
{\bf 33} (1902), 378--384.
\bibitem{DE2} K.~Dilcher and L.~Ericksen, Hyperbinary expansions and Stern
polynomials, {\it Electron. J. Combin.} {\bf 22} (2015), Paper 2.24.
\bibitem{DE7} K.~Dilcher and L.~Ericksen, Generalized Stern polynomials and
hyperbinary representations, {\it Bull. Pol. Acad. Sci. Math.} {\bf 65} (2017),
11--28.
\bibitem{DE9} K.~Dilcher and L.~Ericksen, Polynomials characterizing hyper
$b$-ary representations, {\it J. Integer Seq.} {\bf 21} (2018),
\href{https://cs.uwaterloo.ca/journals/JIS/VOL21/Dilcher/dilcher7.html}{Article 18.4.3}.
\bibitem{DE10} K.~Dilcher and L.~Ericksen, Properties of multivariate b-ary
Stern polynomials, {\it Ann. Comb.}, to appear.
\bibitem{DN} W.~Duke and H.~N.~Nguyen,
Infinite products of cyclotomic polynomials,
{\it Bull. Aust. Math. Soc.} {\bf 91} (2015), 400--411.
\bibitem{DST} J.~M.~Dumont, N.~Sidorov, and A.~Thomas, Number of representations
related to a linear recurrent basis, {\it Acta Arith.} {\bf 88} (1999),
371--396.
\bibitem{Eu} L.~Euler, De partitione numerorum, {\it Novi Commentarii academiae
scientiarum Petro\-politanae} {\bf 3} (1753), 125--169. In {\it Opera Omnia},
Ser.~1, Vol.~2, pp.~254--294. Also available from The Euler Archive,
\url{http://eulerarchive.maa.org}, Paper E191.
\bibitem{Ma} K.~Mahler, On a special functional equation,
{\it J. London Math. Soc.} {\bf 15} (1940), 115--123.
\bibitem{MS} T.~Mansour and M.~Shattuck, Generalized $q$-Calkin-Wilf trees
and $c$-hyper $m$-expansions of integers, {\it J. Comb. Number Theory} {\bf 7}
(2015), 1--12.
\bibitem{MM} R.~J.~Martin and G.~L.~Mullen, Reducing multinomial coefficients
modulo a prime power, {\it Comput. Math. Appl.} {\bf 10} (1984), 37--41.
\bibitem{No} S.~Northshield, Sums across Pascal's triangle mod 2,
{\it Congr. Numer.} {\bf 200} (2010), 35--52.
\bibitem{OEIS}
OEIS Foundation Inc. (2011), {\it The On-Line Encyclopedia of Integer
Sequences},\\
{\tt https://oeis.org}.
\bibitem{Re} B.~Reznick, Some binary partition functions, in
B. C. Berndt et al., eds., {\it Analytic
Number Theory: Proceedings of a Conference in Honor of Paul T.~Bateman},
Birkh\"auser, 1990, pp.~451--477.
\bibitem{Ro} \"O.~R\"odseth, Some arithmetical properties of $m$-ary
partitions, {\it Proc. Cambridge Philos. Soc.} {\bf 68} (1970), 447--453.
\bibitem{SW} R.~P.~Stanley and H.~S.~Wilf, Refining the Stern diatomic sequence,
{\it Preprint}, 2010. Available at
\url{http://www-math.mit.edu/~rstan/papers/stern.pdf}.
\end{thebibliography}
\bigskip
\hrule
\bigskip
\noindent 2010 {\it Mathematics Subject Classification}:
Primary 11P81; Secondary 11B37, 11B83.
\noindent \emph{Keywords: }
binary partition, $b$-ary partition, restricted partition, polynomial analogue,
generating function, recurrence relation, multinomial coefficient.
\bigskip
\hrule
\bigskip
\noindent (Concerned with sequences
\seqnum{A002487} and
\seqnum{A018819}.)
\bigskip
\hrule
\bigskip
\vspace*{+.1in}
\noindent
Received December 2 2018;
revised version received May 8 2019.
Published in {\it Journal of Integer Sequences},
May 17 2019.
\bigskip
\hrule
\bigskip
\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in
\end{document}