\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}