\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}
\newtheorem{claim}[theorem]{Claim}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{notation}[theorem]{Notation}


\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{note}[theorem]{Note}
\newtheorem{strategy}[theorem]{Strategy}

\begin{center}
\vskip 1cm{\LARGE\bf
Digit Sums Generalizing\\
\vskip .05in
Binomial Coefficients\\
}
\vskip 1cm
\large
Ji Young Choi\\
Department of Mathematics\\
Shippensburg University of Pennsylvania\\
1871 Old Main Drive\\
Shippensburg, PA 17257 \\
USA\\
\href{mailto:jychoi@ship.edu}{\tt jychoi@ship.edu} \\
\end{center}

\vskip .2 in

\begin{abstract}
We define four different generalizations of binomial coefficients, using the digit sum of a string with digits in $\{0, 1, 2,  \dots, g\}$ for any positive integer $g$.
We identify one generalization with the extended binomial coefficients, and we express every other generalization in terms of the extended binomial coefficients.
We also express every  generalization in terms of the binomial coefficients and find the explicit formula for each generalization.
\end{abstract}


\def\modd#1 #2{#1\ \mbox{\rm (mod}\ #2\mbox{\rm )}}


\section{Introduction}
For any nonnegative integers $n$ and $k$, the $(n,k)$-th binomial coefficient, denoted by $\binom{n}{k}$, is the coefficient of $x^k$ in the expansion of $(x+1)^n$, i.e.,
$$
(x+1)^n=\sum_{k=0}^{n}\binom{n}{k}x^k,
$$
and it satisfies the following recurrence relation:
\begin{equation}\label{E:binom recurrence}
  \binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}.
\end{equation}
Using the recurrence relation, we construct Pascal's triangle (\seqnum{A007318}) as follows:
$$
\begin{array}{|r|rrrrrrrrrrrr}
\hline
\binom{n}{k} & k=0 & 1 & 2  &3 &4 &5 \\
\hline
  n=0 & 1 &  &  & & &  \\
  1 & 1 & 1 &   & & & \\
  2 & 1& 2 & 1 & & &  &&&&\\
  3 & 1 &3 & 3 &1& & \\
  4 & 1 & 4 & 6 &4&1 \\
  5 & 1 & 5 & 10&10&5&1\\
\hline
\end{array}
$$

To generalize the binomial coefficients, we let $b$ be an integer greater than $1$ and $g=b-1$ throughout this paper.
Then we can express the \emph{extended binomial coefficients} or \emph{polynomial coefficients} as follows.
\begin{definition} \label{D:bnomial coef}  \cite{Eger}
For any nonnegative integer $n$ and any integer $k$, the $(n,k)$-th $b$-nomial coefficient (or $b$-nomial number of type 1) is denoted by $\binom n k _b$ and satisfies
\begin{equation}\label{E:bnomial def}
  (x^g+x^{g-1}+\cdots+x+1)^n=\sum_k \binom{n}{k}_b x^k.
\end{equation}
\end{definition}
Then the $b$-nomial coefficients satisfy the following recurrence relation \cite{Freund}:
\begin{equation}\label{E:bnomial recurrence}
  \binom{n}{k}_b=\sum_{i=0}^{g} \binom{n-1}{k-i}_b.
\end{equation}
Using this recurrence relation, we construct a triangle and call it the \textit{$b$-nomial triangle}.
Then the $2$-nomial triangle is Pascal's triangle, and $b$-nomial triangles for $b=3$ and $4$ (\seqnum{A027907} and \seqnum{A008287}, respectively) are as follows \cite{FA}:
$$
\begin{array}{l}
\begin{array}{|r|rrrrrrrrrrrr}
\hline
\binom{n}{k}_3 & k=0 & 1 & 2  &3 &4 &5 &6&7&8&9&10&\\
\hline
  n=0 & 1 &  &  & & &  &&&&\\
  1 & 1 & 1 & 1  & & & &&&&\\
  2 & 1& 2 & 3 & 2& 1&  &&&&\\
  3 & 1 &3 & 6 &7& 6& 3&1&&&\\
  4 & 1 & 4 & 10 &16&19& 16&10&4&1& \\
  5 & 1 & 5 & 15&30&45&51&45&30&15&5&1 &\\
\end{array}
\\
\begin{array}{|r|rrrrrrrrrrrrrrrrrrrrrr}
\hline
\hline
\binom{n}{k}_4 & k=0 & 1 & 2  &3 &4 &5 &6&7&8&9&10&11&12&13&14&15\\
\hline
  n=0 & 1 &  &  & & &  &&&&\\
  1 & 1 & 1 & 1  & 1& & &&&&\\
  2 & 1& 2 & 3 & 4& 3&2  &1&&&\\
  3 & 1 &3 & 6 &10& 12& 12&10&6&3&1\\
  4 & 1 & 4 & 10 &20&31& 40&44&40&31&20&10&4&1 \\
  5 & 1 & 5 & 15&35&65&101&135&155&155&135&101&65&35&15&5&1\\
  \hline
\end{array}\\
\end{array}
$$
Notice that Pascal's triangle is a lower triangular matrix but the $b$-nomial triangle for $b>2$ is not.  In this paper, we find two new generalizations of binomial coefficients, whose corresponding matrix is a lower triangular matrix.  Out of these two matrices, one is symmetric just like Pascal's triangle, and the other is not.

To simplify the discussion below, we denote $l_b(m)$ and $s_b(m)$ as the length and the digit sum of the base-$b$ representation of a nonnegative integer $m$, respectively.  Since $s_b(m)\equiv m \text{ }(\text{mod }g)$ for any integer $m$ \cite{Wei}, there exists an integer $k$ satisfying
$$
s_b(g\cdot m)=g\cdot k.
$$
Hence, we can ask the following questions for any positive integers $n$ and $k$:
\begin{description}
   \item[Question 1:] How many nonnegative integers $m$ satisfy $l_b(m)\leq n$ and $s_b(m)=k$?
   \item[Question 2:] How many nonnegative integers $m$ satisfy $l_b(m)=n$ and $s_b(m)=k$?
   \item[Question 3:] How many nonnegative integers $m$ satisfy $l_b(m)\leq n$ and $s_b(g\cdot m)=g\cdot k$?
   \item[Question 4:] How many nonnegative integers $m$ satisfy $l_b(m)= n$ and $s_b(g\cdot m)=g\cdot k$?
 \end{description}
When $b=2$, the answer to Questions 1 and 3 is the $(n,k)$-th binomial coefficient $\binom{n}{k}$ and the answer to Questions 2 and 4 is the $(n-1,k-1)$-th binomial coefficient $\binom{n-1}{k-1}$.  Hence, by answering all these questions for any integer $b\geq 2$ and modifying the indices $n$ and $k$, we can find four different generalizations of the binomial coefficients.  Two of the generalizations are completely new, and both construct a lower triangular matrix for all $b$.

In Section \ref{S:notation}, we clarify notation for this paper.
Section 3 answers Questions 1 and 2, and Section 4 answers Questions 3 and 4 by defining new generalizations of binomial coefficients.
In Section \ref{S:ABCD}, we express each generalization in terms of the extended binomial coefficients.
In Section \ref{S:Explicit}, we express each generalization in terms of the binomial coefficients, and find the explicit formulas.
In Section \ref{S:Symmetry}, we discuss the symmetry in each generalization and the sequences closely related to the generalizations.



\section{Notation} \label{S:notation}

We let $\Sigma_b$ be the set $\{0, 1, 2, \dots, g\}$ and $\Sigma_b^*$ be the set of all  finite strings consisting of digits in $\Sigma_b$.
Every base-$b$ representation of an integer is a finite string in $\Sigma_b^*$,
and the set $\Sigma_b^*$ also includes the \textit{empty string}, which contains no digits, denoted by $\epsilon$ \cite{Sha}.

The notation for the number of digits in a string is as follows.
\begin{notation} \cite{Sha}
For any finite string $x$ and a digit $a$, let $|x|$ denote the number of digits in $x$, and $|x|_a$ denote the number of occurrences of digit $a$ in $x$.
\end{notation}
\begin{lemma}\label{L:sharp}
For any string $x$ in $\Sigma_b^*$,
$$
|x|=\sum_{i=0}^{g}|x|_i.
$$
\end{lemma}
For example, $|01011|=5$, $|01011|_0=2$, $|01011|_1=3$, and $5=2+3$.  We consider $|\epsilon|=0$.

The following operation shows how to create a new string from given ones \cite{Sha}.
\begin{definition}
For any strings $x$ and $y$ and any positive integer $n$, the \textit{concatenation} of $x$ and $y$, denoted by $xy$, is the string obtained by joining $x$ and $y$ end-to-end,
and $x^n$ denotes the concatenation of $n$ copies of $x$.
That is, if $x=a_1a_2\cdots a_{|x|}$ and $y=b_1b_2\cdots b_{|y|}$ for some $a_i, b_i \in \Sigma_b$,
$$
xy=a_1a_2\cdots a_{|x|} b_1b_2\cdots b_{|y|}
\text{, and } x^n=xx\cdots x \text{ ($n$ times)}.
$$
By convention, $x^{0}$ is defined to be $\epsilon$.
\end{definition}

\begin{lemma}
  For any strings $x$ and $y$ and a nonnegative integer $n$, we have
    $|xy|=|x|+|y|$ and $|x^n|=n|x|$.
\end{lemma}
For example, $101\text{ }00=10100$, $(10)^{ 3} =101010$, and $1=1\text{ } (10)^{ 0}$.
Then $|101\text{  }00|=|101|+|00|=3+2=5$, $|(10)^{ 3}|=3|10|=3\cdot 2 =6$, and $|\epsilon|=|(10)^0|=0$.

Since the base-$b$ representation of an integer is a string in $\{0, 1, 2, \ldots, g\}^*$, we call the base-$b$ representation of an integer as a \textit{$b$-ary string} throughout this paper.
When we have to distinguish an integer and its $b$-ary string, we use the following notation.
\begin{notation}
  For any integer $m$ with its base-$b$ representation $x$, we write $m=[x]_b$ or $(m)_b=x$.
\end{notation}
For example, $5=[12]_3$ and $(5)_3=12$.  Then $([x]_b)_b=x$ for any $b$-ary string $x$ and $[(m)_b]_b=m$ for any integer $m$.
Throughout this paper, we use the convention that $m$ is an integer and $x$ is its $b$-ary string.


\begin{notation}
For any nonempty string $x$ with $x=a_n a_{n-1}\cdots a_2 a_1$ for
some digits $a_i$ and any nonnegative integer $m$, we let $s(x)$
and $s_b(m)$ denote the digit sum of $x$ and the digit sum of the
$b$-ary string $(m)_b$, respectively, i.e., $$ s(x)=\sum_{i=1}^{n}a_i
\phantom{mm}\text{ and }\phantom{mm} s_b(m)=s\left((m)_b\right).  $$
By convention, we define $s(\epsilon)=0$.  \end{notation} For example,
$s(16)=1+6=7$ and $s_3(16)=s(121)=4$.

\begin{definition}\cite{Choi}
For any string $x$ with $x=a_n a_{n-1}\cdots a_1 $ for some digits $a_i$,
the digit $a_i$ is called \emph{indispensable} in $x$, if $a_i=a_{i-1}=a_{i-2}=\cdots=a_{i-k+1}>a_{i-k}$ for some positive integer $k\leq i+1$, considering $a_{0}=0$, and \emph{dispensable}, otherwise.  We will follow this convention of dotting indispensable digits.

We let $\iota(x)$ denote the number of indispensable digits in $x$, and we let $\iota_b(m)=\iota((m)_b)$ for any nonnegative integer $m$.  By convention, we define $\iota(\epsilon)=0$.
\end{definition}
For example, if $x=\dot213345\dot7\dot7\dot4$, the digits $2$, $7$, $7$, and  $4$ are indispensable in $x$ and the digits $1$,  $3$,  $3$,  $4$. and $5$ are dispensable in $x$.  Hence, $\iota(x)=4$.  If $m=16$, the ternary string $(m)_3=121$ so $\iota_3(16)=\iota(1\dot2\dot1)=2$.

To simplify arguments, we use the following notation as well.
\begin{notation}
For any positive integer $n$, we let $\Sigma_b^n$ and $\sigma_b^n$ denote as follows:
$$
\Sigma_b^n=\{x\in \Sigma_b^*: |x|=n\}\text{ and }\sigma_b^n=\{x\in \Sigma_b^n: x\neq 0y\text{ for any string }y \}.
$$
By convention, we let $\Sigma_b^0=\sigma_b^0=\{\epsilon\}$.
\end{notation}
For example, $\Sigma_3^{2}=\{00, 01, 02, 10, 11,  12, 20, 21, 22\}$ and $\sigma_3^2=\{10, 11, 12, 20, 21, 22\}$.

\begin{notation}
For any set $X$ of strings, and any nonnegative integer $k$, we have
$$
X[k]=\{x\in X: s(x)=k\} \text{ and } X\langle k \rangle =\{x\in X: \iota(x)=k\}.
$$
\end{notation}
For example, $\Sigma_3^2[2]=\{02, 11, 20\}$ and $\Sigma_3^2\langle 1 \rangle=\{0\dot1, 0\dot2, \dot1 0, 1\dot2, \dot20\}$.


\section{Addressing Questions 1 and 2}\label{S:D}


First, we find a combinatorial interpretations for the extended binomial coefficients as follows.
\begin{theorem}\label{T:bnomial}
For any nonnegative integer $n$ and any integer $k$,
the number of $b$-ary strings of length $n$ with digit sum $k$ is the $(n,k)$-th $b$-nomial coefficient $\binom{n}{k}_b$, i.e.,
\begin{equation}\label{E:bnomial Def Theorem}
  \binom{n}{k}_b=|\Sigma_b^n[k]|=|\{x\in\Sigma_b^n: s(x)=k\}|.
\end{equation}
\end{theorem}
\begin{proof}
Since the empty string $\epsilon$ is the only string of length $0$ and $s(\epsilon)=0$,
$$
|\Sigma_b^0[0]|=|\{\epsilon\}|=1\text{ and } |\Sigma_b^0[k]|=|\phi|=0 \text{ for nonzero }k.
$$
Since the string $0^n$ is the only string of length $n$ with digit sum $0$,
$$
|\Sigma_b^n[0]|=|\{0^n\}|=1 \text{ for any nonzero }n.
$$
Hence, the sequence $\left(|\Sigma_b^n[k]|\right)_{n,k\geq0}$  has the same initial conditions as the $b$-nomial coefficients.
We just need to show the sequences $\left(|\Sigma_b^n[k]|\right)_{n,k\geq0}$ has the same recurrence relation as (\ref{E:bnomial recurrence}).
For any digit $a\in \{0, 1, 2, \dots, g\}$, we let
  $$
  B_a=\{x\in \Sigma_b^n[k]: x=ya \text{ for any string } y\}.
  $$
  Then the set $\Sigma_b^n[k]$ is partitioned by the $B_a$, i.e.,
  \begin{equation}\label{E:partition}
     \Sigma_b^n[k]=\bigcup_{a=0}^g B_a \text{ and } B_a \cap B_{a'}=\phi \text{ for } a\neq a'.
  \end{equation}
   Consider a function $f_a: B_a \rightarrow \Sigma_b^{n-1}[k-a]$ with $f_a(ya)=y$ for any $y\in \Sigma_b^{n-1}$.
  Since $s(ya)=k$ iff $s(y)=k-a$, and $y_1a=y_2a$ iff $y_1=y_2$, the function $f_a$ is bijective.
  Hence, $|B_a|=|\Sigma_b^{n-1}[k-a]|$ so by (\ref{E:partition}),
  $$
  |\Sigma_b^n[k]|=\sum_{a=0}^{g}|B_a|=\sum_{a=0}^{g}|\Sigma_b^{n-1}[k-a]|.
  $$
Therefore, the sequence $\left(|\Sigma_b^n[k]|\right)_{n,k\geq0}$ has the same recurrence relation as (\ref{E:bnomial recurrence}).
\end{proof}

Hence, the $(n,k)$-th $b$-nomial coefficient is the answer to Question 1.
\begin{lemma}
For any positive integers $n$ and $k$,
$$
\binom{n}{k}_b=|\{m\in \mathbb{N}: l_b(m)\leq n \text{ and } s_b(m)=k\}|.
$$
\end{lemma}

Using the combinatorial interpretation, we can also generalize the hockey stick identity for the binomial coefficients\cite{Jones}:
\begin{equation}\label{E:hockey}
  \binom{n}{k}=\sum_{i=1}^{n} \binom{n-i}{k-1}.
\end{equation}
\begin{theorem}\label{T:Hockey bnomial}
For any positive integers $n$ and $k$,
$$
  \binom{n}{k}_b=\sum_{j=1}^{g}\sum_{i=1}^{n}\binom{n-i}{k-j}_b.
$$
\end{theorem}
\begin{proof}
For any nonzero digit $a\in\Sigma_b$ and nonnegative integer $i<n$, we let
$$
B_{a0^i}=\{x\in\Sigma_b^n [k] : x=ya0^i \text{ for any string } y\}=\{ya0^i : y\in\Sigma_b^{n-i-1}[k-a]\}.
$$
Since $k>0$, the string $0^n\not\in \Sigma_b^n[k]$.
Thus, the set $\Sigma_b^n[k]$ is partitioned by the set $B_{a0^i}$.
That is,
$$
\Sigma_b^n[k]= \bigcup_{a=1}^{g}\bigcup_{i=0}^{n-1} B_{a0^i} \text{, and } B_{a0^i}\cap B_{a'0^{i'}}=\phi \text{ for } a\neq a' \text{ or } i\neq i'.
$$
Hence,
$$
\binom{n}{k}_b=|\Sigma_b^n[k]|=\sum_{a=1}^{g}\sum_{i=0}^{n-1}|B_{a0^i}|.
$$
Since $|\{ya0^i: y\in\Sigma_b^{n-i-1}[k-a]\}|=|\Sigma_b^{n-i-1}[k-a]|$,
the size $|B_{a0^i}|=|\Sigma_b^{n-i-1}[k-a]|=\binom{n-i-1}{k-a}_b$.
By adjusting indices $i$ and $a$, we have the relation.
\end{proof}


Now we consider strings with a nonzero leading digit.
For any positive integer $n$ and any integer $k$, we consider
$$
|\sigma_b^n[k]|=|\{x\in \sigma_b^n: s(x)=k\}|.
$$
Since $\sigma_b^0=\{\epsilon\}$ and $s(\epsilon)=0$, we have $|\sigma_b^o[k]|=1$ if $k=0$ and $|\sigma_b^o[k]|=0$ otherwise.
Then it is obvious that the size $|\sigma_b^n[k]|$ is the answer to Question 2.
\begin{lemma} For any positive integers $n$ and $k$,
$$
|\sigma_b^n[k]|=|\{m\in \mathbb{N}: l_b(m)=n \text{ and }s_b(m)=k\}|.
$$
\end{lemma}
When $b=2$, since digit $1$ is the only nonzero digit, the leading digit
for every string in $\sigma_2^n$ is $1$, and the digit sum is the same
as the number of $1$ digits.  Thus,
$$
\begin{aligned}
|\sigma_2^n[k]|=|\{1x\in \sigma_2^n:  s(1x)=k\}|&=|\{x\in \Sigma_2^{n-1}: s(x)=k-1\}|\\
&=|\{x\in \Sigma_2^{n-1}: |x|_1=k-1\}|=\binom{n-1}{k-1}.
\end{aligned}$$
When $b>2$, we sort the strings in $\sigma_b^{n}$ according to digit sums to calculate the number $|\sigma_b^n[k]|$.
For example, since $\sigma_3^2=\{10\} \cup \{11, 20\}\cup\{12, 21\}\cup\{22\}$,
$$
\begin{aligned}
|\sigma_3^2[1]|=|\{10\}|=1\text{; } \phantom{mmm}& |\sigma_3^2[2]|=|\{11, 20\}|=2\text{; }\\
|\sigma_3^2[3]|=|\{12, 21\}|=2\text{; }\phantom{m.}& |\sigma_3^2[4]|=|\{22\}|=1.
\end{aligned}
$$
Then the first few numbers for $|\sigma_b^n[k]|$ when $b=2$, $3$, and $4$ are as follows:
$$
\begin{array}{l}
\begin{array}{|r|rrrrrrr}
\hline
|\sigma_2^n[k]| & k=0 & 1 & 2  &3 &4 &5 &6\\
\hline
  n=0 & 1 &  &  & & \\
  1 &  & 1 &  & & \\
  2 & & 1 & 1 & & \\
  3 &  &1 & 2 &1& & \\
  4 &  & 1 &3 &3&1&  \\
  5 &  & 1 & 4&6&4&1&\\
  \hline
\end{array}
\\
\begin{array}{|r|rrrrrrrrrrrr}
\hline
|\sigma_3^n[k]| & k=0 & 1 & 2  &3 &4 &5 &6&7&8&9&10&\\
\hline
  n=0 & 1 &  &  & & &  &&&&\\
  1 &  & 1 &1   & & & &&&&\\
  2 & & 1 & 2 & 2& 1&  &&&&\\
  3 &  &1 & 3 &5& 5& 3&1&&&\\
  4 &  & 1 &4 &9&13& 13&9&4&1& \\
  5 &  & 1 & 5&14&26&35&35&26&14&5&1 &\\
\hline
\end{array}
\\
\begin{array}{|r|rrrrrrrrrrrrrrrrrrrrrr}
\hline
|\sigma_4^n[k]| & k=0 & 1 & 2  &3 &4 &5 &6&7&8&9&10&11&12&13&14&15\\
\hline
  n=0 & 1 &  &  & & &  &&&&\\
  1 &  & 1 & 1  & 1& & &&&&\\
  2 & & 1 & 2 & 3& 3&2  &1&&&\\
  3 &  &1 & 3 &6& 9& 10&9&6&3&1\\
  4 &  & 1 & 4 &10&19& 28&34&34&28&19&10&4&1 \\
  5 &  & 1 & 5&15&34&61&91&115&124&115&91&61&34&15&5&1\\
  \hline
\end{array}
\end{array}
$$

The sequences $\left(|\sigma_b^n[k]|\right)_{n,k\geq 0}$ for $b=3$ and $10$ are identified with \seqnum{A005773} and \seqnum{A071976}, respectively, but in general, the numbers are not studied much.
In this paper, we adjust the indices $n$ and $k$ to study the numbers as a new generalization of the binomial coefficients as follows.
\begin{definition}\label{D:type2}
For any nonnegative integer $n$ and any integer $k$, the $(n,k)$-th $b$-nomial number of type $2$, denoted by $\binom{n}{k}_{b2}$, is defined as
$$
\binom{n}{k}_{b2}=|\sigma_b^{n+1}[k+1]|=|\{x\in \sigma_b^{n+1}: s(x)=k+1\}|.
$$
By convention, we define $\binom{-1}{k}=1$ if $k=-1$ and $\binom{-1}{k}=0$ otherwise.
\end{definition}
Then the number $\binom{n}{k}_{22}=\binom{n}{k}$, and the first few numbers for $\binom{n}{k}_{b2}$ for nonnegative integers $n$ and $k$ when $b=3$ and $4$ are as follows:
$$
\begin{array}{l}
\begin{array}{|r|rrrrrrrrrrrr}
\hline
\binom{n}{k}_{32} & k=0 & 1 & 2  &3 &4 &5 &6&7&8&9&10&\\
\hline
  n=0 &   1 &1   & & & &&&&\\
  1 &  1 & 2 & 2& 1&  &&&&\\
  2 &  1 & 3 &5& 5& 3&1&&&\\
  3 &   1 &4 &9&13& 13&9&4&1& \\
  4 &   1 & 5&14&26&35&35&26&14&5&1 &\\
  5&1 &6&20&45&75&96& 96&75&45&20&6&1\\
\hline
\end{array}
\\
\begin{array}{|r|rrrrrrrrrrrrrrrrrrrrrr}
\hline
\binom{n}{k}_{42} & k=0 & 1 & 2  &3 &4 &5 &6&7&8&9&10&11&12&13&14&15\\
\hline
 n= 0 &  1 & 1  & 1& & &&&&\\
  1 &  1 & 2 & 3& 3&2  &1&&&\\
  2 &  1 & 3 &6& 9& 10&9&6&3&1\\
  3 &   1 & 4 &10&19& 28&34&34&28&19&10&4&1 \\
  4 &   1 & 5&15&34&61&91&115&124&115&91&61&34&15&5&1\\
  5 &1&6&21&55&115&201&301&391&445&445&391&301&201&115&55&21\\
  \hline
\end{array}
\end{array}
$$

By the definitions, we find the following basic properties for the $b$-nomial numbers of type $1$ and $2$.
\begin{lemma}\label{L:D and bnomial}
For any nonnegative integers $n$ and $k$:
\begin{description}
  \item[(i)] $\binom{n}{k}_b=\sum_{i=0}^{n}\binom{i-1}{k-1}_{b2}$;
  \item[(ii)] $\binom{n}{k}_{b2}=\binom{n+1}{k+1}_b-\binom{n}{k+1}_b$;
  \item[(iii)] $\binom{n}{k}_{b2}\neq 0$  iff $0\leq k< g(n+1)$;
  \item[(iv)] $\sum_{k\geq 0} \binom{n}{k}_{b}=b^{n}$ and $\sum_{k\geq 0} \binom{n}{k}_{b2}=g\cdot b^{n}$;
  \item[(v)] $\binom{n}{k}_{b}=\binom{n-1}{k}_{b2}$ if $k=0, 1, 2, \dots, g-1$;
  \item[(vi)] $\binom{0}{k}_{b2}=1$ if $k=0, 1, 2, \dots, g-1$ and $\binom{0}{k}_{b2}=0$ otherwise.
\end{description}
\end{lemma}
\begin{proof}
Since $\sigma_b^0=\{\epsilon\}$, the set $\Sigma_b^n[k]$ can be partitioned as follows:
$$
\Sigma_b^n[k]=\bigcup_{i=0}^n \{0^{n-i}x: x\in \sigma_b^{i}[k]\}.
$$
Since $\binom{i-1}{k-1}_{b2}=|\sigma_b^i[k]|=|\{0^{n-i}x: x\in \sigma_b^{i}[k]\}|$, we have (i) by Theorem \ref{T:bnomial} and Definition \ref{D:type2}.  Then (i) provides (ii).
For any string $x$ in $\sigma_b^{n+1}$, $1\leq s(x)\leq g(n+1)$, so we have (iii).
Since $\Sigma_b^n=\bigcup_{k\geq 0}\Sigma_b^n[k]$ and $\sigma_b^n=\bigcup_{k\geq 0}\sigma_b^n[k]$, we have (iv).
For (v), we consider $f: \Sigma_b^n[k]\rightarrow \sigma_b^n[k+1]$ by $f(a_1a_2\dots a_n)=(a_1+1)a_2\dots a_n$ for any digit $a_i$ in $\Sigma_b$.  Since $k\leq g-1$, the digit $a_1\leq g-1$ so $a_1+1$ is a nonzero leading digit.  Then $f$ is a well-defined one-to-one mapping, so $|\Sigma_b^n[k]|=|\sigma_b^n[k+1]|$.  Hence, (v) holds.
Since $\sigma_b^1=\{1, 2, \dots, g\}$ and $s(a)=a$ for any $a=1, 2, \dots, g$, (vi) holds.
\end{proof}

Even if the $b$-nomial numbers of type $1$ and $2$ have different initial conditions, they have the same recurrence relations.  We can also find a generalization of the hockey stick identity for the $b$-nomial numbers of type 2.
\begin{corollary}
For any positive integer $n$ and any integer $k$,
$$
\binom{n}{k}_{b2}=\sum_{i=0}^{g} \binom{n-1}{k-i}_{b2}=\sum_{j=1}^{g}\sum_{i=1}^{n+1}\binom{n-i}{k-j}_{b2}.
$$
\end{corollary}
\begin{proof}
By Lemma \ref{L:D and bnomial} (ii) and the recurrence relation (\ref{E:bnomial recurrence}), we have the first recurrence relation for the $b$-nomial numbers of type 2:
$$
\begin{aligned}
\binom{n}{k}_{b2}=\binom{n+1}{k+1}_b-\binom{n}{k+1}_b&=\sum_{i=0}^{g}\binom{n}{k+1-i}_b-\sum_{i=0}^{g}\binom{n-1}{k+1-i}_b\\
&=\sum_{i=0}^{g}\left(\binom{n}{k+1-i}_b-\binom{n-1}{k+1-i}_b \right)=\sum_{i=0}^{g}\binom{n-1}{k-i}_{b2}.
\end{aligned}
$$

By Lemma \ref{L:D and bnomial} (ii) and Theorem \ref{T:Hockey bnomial}, we have the second relation for the $b$-nomial numbers of type $2$.
  $$
  \begin{aligned}
  \binom{n}{k}_{b2}
  &=\binom{n+1}{k+1}_b - \binom{n}{k+1}_b\\
  &=\sum_{j=1}^{g}\sum_{i=1}^{n+1}\binom{n+1-i}{k+1-j}_b-\sum_{j=1}^{g}\sum_{i=1}^{n}\binom{n-i}{k+1-j}_b\\
  &=\sum_{i=1}^g\binom{0}{k+1-j}_b+\sum_{j=1}^{g}\sum_{i=1}^{n}\left(\binom{n+1-i}{k+1-j}_b-\binom{n-i}{k+1-j}_b\right)\\
  &=\sum_{i=1}^g\binom{-1}{k-j}_{b2}+\sum_{j=1}^{g}\sum_{i=1}^{n}\binom{n-i}{k-j}_{b2}=\sum_{j=1}^{g}\sum_{i=1}^{n+1}\binom{n-i}{k-j}_{b2},
  \end{aligned}
  $$
  since
 $$
\binom{0}{k}_b=\begin{cases}
                 1, & \mbox{if $k=0$;} \\
                 0, & \mbox{otherwise},
               \end{cases}
\phantom{m}\text{ and }\phantom{m}
\binom{-1}{k}_{b2}=\begin{cases}
                 1, & \mbox{if $k=-1$;} \\
                 0, & \mbox{otherwise}.
               \end{cases}
$$
\end{proof}





\section{Addressing Questions 3 and 4}\label{S:AB}

First, we define a new sequence to answer Question 3.
\begin{definition}\label{D:Bnk}
   For any positive integer $n$ and any integer $k$, the $(n,k)$-th $b$-nomial number of type $3$, denoted by $\binom{n}{k}_{b3}$, is the number of $b$-ary strings of length $n$ with $k$ indispensable digits, i.e.,
$$
\binom{n}{k}_{b3}=|\Sigma_b^n\langle k \rangle|=|\{x\in \Sigma_b^n: \iota(x)=k\}|.
$$
By convention, we define $\binom{0}{k}_{b3}=1$ if $k=0$ and $\binom{0}{k}_{b3}=0$ otherwise.
\end{definition}
When $b=2$, digit $1$ is the only nonzero digit, so every digit 1 in a binary string is indispensable.  Thus,
$$
|\Sigma_2^n\langle k \rangle|=|\{x\in \Sigma_2^n: |x|_1=k\}|=\binom{n}{k}.
$$
Hence, the number $\binom{n}{k}_{23}=\binom{n}{k}$.
When $b>2$, we can sort the strings in $\Sigma_b^n$ to calculate $\binom{n}{k}_{b3}$.  For example, since
$$
\Sigma_3^2=\{00\}\bigcup\{0\dot{1}, 0\dot2, \dot10, 1\dot2, \dot20\}\bigcup\{\dot1\dot1, \dot2\dot1, \dot2\dot2\},
$$
we have $\binom{2}{k}_{33}=0$ for any $k\neq 0, 1, 2$, and
$$
  \binom{2}{0}_{33}=|\{00\}|=1\text{; } \binom{2}{1}_{33}=|\{0\dot{1}, 0\dot2, \dot10, \dot20, 1\dot2\}|=5\text{; }  \binom{2}{2}_{33}=|\{\dot1\dot1, \dot2\dot1, \dot2\dot2\}|=3.
$$
Then the first few numbers for $\binom{n}{k}_{b3}$ when $b=3$ and $4$ are as follows:
$$
\begin{array}{r|rccccc}
  \binom{n}{k}_{33} & k=0 & 1 & 2 & 3 & 4 & 5 \\
  \hline
  n=0 & 1 & 0 & 0 & 0 & 0 & 0 \\
  1 & 1 & 2 & 0 & 0 & 0 & 0 \\
  2 & 1 & 5 & 3 & 0 & 0 & 0 \\
  3 & 1 & 9 & 13 & 4 & 0 & 0 \\
  4 & 1 & 14 & 35 & 26 & 5 & 0 \\
  5 & 1 & 20 & 75 & 96 & 45 & 6
\end{array}
\phantom{mm}
\begin{array}{r|rccccc}
  \binom{n}{k}_{43} & k=0 & 1 & 2 & 3 & 4 & 5 \\
  \hline
  n=0 & 1 & 0 & 0 & 0 & 0 & 0 \\
  1 & 1 & 3 & 0 & 0 & 0 & 0 \\
  2 & 1 & 9 & 6 & 0 & 0 & 0 \\
  3 & 1 & 19 & 34 & 10 & 0 & 0 \\
  4 & 1 & 34 & 115 & 91 & 15 & 0 \\
  5 & 1 & 55 & 301 & 445 & 201 & 21
\end{array}
$$
Since $s_b(g\cdot m)=g\cdot \iota_b(m)$ \cite{Choi}, the number $\binom{n}{k}_{b3}$ is the answer to Question 3.
\begin{lemma}
For any positive integers $n$ and $k$,
$$
\binom{n}{k}_{b3}=|\{m\in \mathbb{N}: l_b(m)\leq n \text{ and } s_b(g\cdot m)=g\cdot k\}|.
$$
\end{lemma}

Now, we consider strings with a nonzero leading digit to answer Question 4.
For any positive integer $n$ and any integer $k$, we consider the number of strings in the set $\sigma_b^n$ with $k$ indispensable digits, i.e.,
  $$
  |\sigma_b^n\langle k \rangle|=|\{x\in \sigma_b^n: \iota(x)=k\}|.
  $$
Since $\sigma_b^0=\{\epsilon\}$ and $\iota(\epsilon)=0$, we have
$$
|\sigma_b^0\langle k\rangle|=\begin{cases}
                               1, & \mbox{if $k=0$;}  \\
                               0, & \mbox{otherwise}.
                             \end{cases}
$$
Since $s_b(g\cdot m)=g\cdot \iota_b(m)$ \cite{Choi}, the number $|\sigma_b^n\langle k \rangle|$ is the answer to Question 3.
\begin{lemma}
For any positive integers $n$ and $k$,
$$
|\sigma_b^n\langle k \rangle|=|\{m\in \mathbb{N}: l_b(m)= n \text{ and } s_b(g\cdot m)=g\cdot k\}|.
$$
\end{lemma}
When $b=2$, since digit $1$ is the only nonzero digit, the leading digit for every string in $\sigma_2^n$ is $1$ and every digit 1 is indispensable.  Thus, for any positive integers $n$ and $k$,
$$
|\sigma_2^n\langle k \rangle|=|\{1x\in \sigma_2^{n}: \iota(1x)=k\}|=|\{x\in \Sigma_2^{n-1}: \iota(x)=k-1\}=\binom{n-1}{k-1}.
$$
When $b>2$, we can sort the strings in $\sigma_b^n$ to calculate the number $|\sigma_b^n\langle k \rangle|$.  For example, since
$$
\sigma_3^2=\{\dot10, \dot20, 1\dot2\}\bigcup\{\dot1\dot1, \dot2\dot1, \dot2\dot2\},
$$
we have $|\sigma_3^2\langle k \rangle|=0$ for $k\neq 1, 2$, and
$$
  |\sigma_3^2\langle 1 \rangle|=|\{\dot10, \dot20, 1\dot2\}|=3\text{; }  |\sigma_3^2\langle 2 \rangle|=|\{\dot1\dot1, \dot2\dot1, \dot2\dot2\}|=3.
$$
Hence, the first few numbers for $|\sigma_b^n\langle k \rangle|$ when $b=2$ and $3$ are as follows:
$$
\begin{array}{r|rccccc}
  |\sigma_2^n\langle k \rangle| & k=0 & 1 & 2 & 3 & 4 & 5 \\
  \hline
  n=0 & 1 & 0 & 0 & 0 & 0 & 0 \\
  1 & 0 & 1 & 0 & 0 & 0 & 0 \\
  2 & 0 & 1 & 1 & 0 & 0 & 0 \\
  3 & 0 & 1 & 2 & 1 & 0 & 0 \\
  4 & 0 & 1 & 3 & 3 & 1 & 0 \\
  5 & 0 & 1 & 4 & 6 & 4 & 1
\end{array}
\phantom{mm}
\begin{array}{r|rccccc}
  |\sigma_3^n\langle k \rangle| & k=0 & 1 & 2 & 3 & 4 & 5 \\
  \hline
  n=0 & 1 & 0 & 0 & 0 & 0 & 0 \\
  1 & 0 & 2 & 0 & 0 & 0 & 0 \\
  2 & 0 & 3 & 3 & 0 & 0 & 0 \\
  3 & 0 & 4 & 10 & 4 & 0 & 0 \\
  4 & 0 & 5 & 22 & 22 & 5 & 0 \\
  5 & 0 & 6 & 40 & 70 & 40 & 6
\end{array}
$$

Since $|\sigma_b^{n+1}\langle k+1 \rangle|=\binom{n}{k}$ for any nonnegative integers $n$ and $k$, we modify the indices $n$ and $k$ to find another generalization of the binomial coefficients.
\begin{definition}\label{D:bnomial4}
For any nonnegative integer $n$ and any integer $k$, the $(n,k)$-th $b$-nomial number of type $4$, denoted by $\binom{n}{k}_{b4}$, satisfies
$$
\binom{n}{k}_{b4}=|\sigma_b^{n+1}\langle k+1\rangle |=|\{x\in \sigma_b^{n+1}: \iota(x)=k+1\}|.
$$
By convention, we define $\binom{-1}{k}_{4b}=1$ if $k=-1$ and $\binom{-1}{k}_{4b}=0$ otherwise.
\end{definition}
Obviously, the number $\binom{n}{k}_{24}=\binom{n}{k}$, and the first few $b$-nomial numbers of type $4$ for any nonnegative integers $n$ and $k$ when $b=3$ and $4$ are as follows:
$$
\begin{array}{r|rccccc}
  \binom{n}{k}_{34} & k=0 & 1 & 2 & 3 & 4 & 5 \\
  \hline
  n=0 &  2 & 0 & 0 & 0 & 0& 0 \\
  1 &  3 & 3 & 0 & 0 & 0 & 0\\
  2 &  4 & 10 & 4 & 0 & 0 & 0\\
  3 &  5 & 22 & 22 & 5 & 0 & 0\\
  4 &  6 & 40 & 70 & 40 & 6& 0\\
  5& 7&65&171&171&65&7
\end{array}
\phantom{mm}
 \begin{array}{r|rccccc}
 \binom{n}{k}_{44} & k=0 & 1 & 2 & 3 & 4 & 5 \\
  \hline
  n=0 &  3 & 0 & 0 & 0 & 0 & 0\\
  1 &  6 & 6 & 0 & 0 & 0 & 0\\
  2 &  10 & 28 & 10 & 0 & 0 & 0\\
  3 &  15 & 81 & 81 & 15 & 0 & 0\\
  4 &  21 & 186 & 354 &186  &21& 0\\
  5& 28&371&1137&1137&371&28
\end{array}
$$

By the definitions, we find the following basic properties for the $b$-nomial numbers of type 3 and type 4.
\begin{lemma}\label{L:basicA}
For any nonnegative integers $n$ and $k$:
\begin{description}
  \item[(i)] $\binom{n}{k}_{b3}=\sum_{i=0}^{n} \binom{i-1}{k-1}_{b4} $;
  \item[(ii)] $\binom{n}{k}_{b4}=\binom{n+1}{k+1}_{b3}-\binom{n}{k+1}_{b3}$;
  \item[(iii)] $\binom{n}{k}_{b3}=0=\binom{n}{k}_{b4}$  if $k>n$;
  \item[(iv)] $\sum_{k\geq 0} \binom{n}{k}_{b3}=b^{n}$ and $\sum_{k\geq 0} \binom{n}{k}_{b4}=g\cdot b^{n}$;
  \item[(v)] $\binom{n}{n}_{b3}=\binom{n-1}{n-1}_{b4}$;
  \item[(vi)] $\binom{1}{1}_{b3}=g=\binom{0}{0}_{b4}$.
\end{description}
\end{lemma}
\begin{proof}
Equations (i) and (ii) are obtained by Definitions \ref{D:Bnk} and \ref{D:bnomial4}.
(iii) holds, because there cannot be more indispensable digits than the total number of digits.
(iv) holds, because the sum of $\binom{n}{k}_{b3}$ for fixed $n$ is the total number of $b$-ary strings of length $n$, and the sum of $\binom{n}{k}_{b4}$ for fixed $n$ is the total number of $b$-ary strings of length $n+1$ with a nonzero leading digit.
(v) holds, because  $\binom{n-1}{n-1}_{b4}=\binom{n}{n}_{b3}-\binom{n-1}{n}_{b3}=\binom{n}{n}_{b3}$ by (ii) and $\binom{n-1}{n}_{b3}=0$ by (iii).
(vi) is obtained by $|\Sigma_b^1 \langle 1 \rangle|=|\{1, 2, \dots, g\}|=|\sigma_b^1\langle 1\rangle|$.
\end{proof}



\section{In terms of extended binomial coefficients}\label{S:ABCD}

Section \ref{S:D} shows that the $b$-nomial numbers of type 2 are expressed in terms of the extended binomial coefficients.
In this section, we express the $b$-nomial numbers of type 3 and type 4 in terms of the extended binomial coefficients as well.

First, we define the following sequence to help the further calculations.
\begin{definition}\label{D:Cba}
For any digit $a\in\{0, 1, 2,  \dots, g-1\}$, any positive integer $n$, and any integer $k$,
we let $Z_{ba}^n$ denote the set of $b$-ary strings of length $n+1$ with a dispensable leading digit $a$.
That is,
$$
Z_{ba}^n=\begin{cases}
           \{x\in \Sigma_b^{n+1}: [0^{n+1}]_b\leq [x]_b\leq [0g^n]_b\}, & \mbox{if } a=0 ;\\
           \{x\in  \Sigma_b^{n+1}: [a^n(a+1)]_b\leq [x]_b\leq [a g^n]_b \}, & \mbox{if } a=1, 2, \dots, g-1.\\
         \end{cases}
$$
We let $C_{ba}(n,k)$ denote the number of strings in $Z_{ba}^n$ with $k$ indispensable digits, i.e.,
$$
C_{ba}(n,k)=|Z_{ba}^n \langle k\rangle|.
$$
\end{definition}
For example, since
$$
Z_{41}^2=\{11\dot2, 11\dot3, 1\dot20, 12\dot3, 1\dot30\}\cup\{1\dot2\dot1, 1\dot2\dot2, 1\dot3\dot1, 1\dot3\dot2, 1\dot3\dot3\}\text{; }
Z_{42}^2=\{22\dot3, 2\dot30\}\cup\{2\dot3\dot1, 2\dot3\dot2, 2\dot3\dot3\},
$$
we have
 $$
C_{41}(2,1)=5=C_{41}(2,2)\text{; }\phantom{m} C_{42}(2,1)=2\text{; }\phantom{m} C_{42}(2,2)=3.
$$
The following shows the first few numbers for $C_{41}(n,k)$ and $C_{42}(n,k)$:
$$
\begin{array}{r|rccccc}
  C_{41}(n,k)  & 1 & 2 & 3 & 4 & 5 \\
  \hline
  n=1  & 2 & 0 & 0 & 0 & 0 \\
  2  & 5 & 5 & 0 & 0 & 0 \\
  3 & 9 & 24 & 9 & 0 & 0 \\
  4 & 14 & 71 & 71 & 14 & 0 \\
  5 & 20 & 166 & 310 & 166 & 20
\end{array}
\phantom{mm}
\begin{array}{r|rccccc}
  C_{42}(n,k) & 1 & 2 & 3 & 4 & 5 \\
  \hline
  n=1& 1 & 0 & 0 & 0 & 0 \\
  2 & 2 & 3 & 0 & 0 & 0 \\
  3 & 3 & 12 & 6 & 0 & 0 \\
  4 & 4 & 31 & 40 & 10 & 0 \\
  5 & 5 & 65 & 155 &101  &15
\end{array}
$$

Since $Z_{b0}^n=\{0x: x\in\Sigma_b^n\}$ and digit $0$ is always dispensable,
$$
|Z_{b0}^n\langle k \rangle |= |\{0x: x\in \Sigma_b^n \text{ and }\iota(0x)=k\}|=|\{x\in \Sigma_b^n: \iota(x)=k\}|=|\Sigma_b^n\langle k \rangle|.
$$
Hence, we identify the number $C_{b0}(n,k)$ with the $(n,k)$-th $b$-nomial number of type 3.
\begin{lemma}\label{L:Cb0}
For any positive $n$ and $k$,
$$
C_{b0}(n,k)=\binom{n}{k}_{b3}.
$$
\end{lemma}


To calculate $C_{ba}(n,k)$ for any digit $a\in\{0, 1, 2, \dots, g-1\}$, we define a set $Y_a$ as follows:
\begin{equation}\label{E:Ya}
Y_a=\begin{cases}
      \{x\in\Sigma_b^m: [0^n]_b\leq [x]_b\leq [1^n]_b\}, & \mbox{if } a=0; \\
      \left\{x\in \Sigma_b^n : [a^{n-1}(a+1)]_b \leq [x]_b\leq [(a+1)^n]_b \right\}, & \mbox{if } a=1, 2, \dots, g-1.
    \end{cases}
\end{equation}
Then the set $\Sigma_b^n$ is partitioned by the $Y_a$, i.e.,
\begin{equation}\label{E:partion w Ya}
\Sigma_b^n=\bigcup_{a=0}^{g-1} Y_a \phantom{m }\text{ and } \phantom{m }Y_a\cap Y_{a'}=\phi.
\end{equation}
We identify the size $|Y_a\langle k\rangle|$ as the $(n,gk-a)$-th $b$-nomial coefficient as follows.
\begin{lemma}\label{L:recognize}
For any digit $a\in \{ 0,1, 2, \dots, g-1\}$ and any positive integers $n$ and $k$,
$$
\left|Y_a \langle k \rangle\right|
=\binom{n}{gk-a}_b.
$$
\end{lemma}
\begin{proof}
 We define a function
 $$
 f:Y_a\langle k \rangle\rightarrow \Sigma_b^n[gk-a]\text{ with } f(x)=\left(g\cdot [x]_b-[a0^n]_b\right)_b,
 $$
 for any $x\in Y_a\langle k \rangle$.
If $a=1, 2, \dots, g-1$, we have
\begin{equation}\label{E:bound by g}
g\cdot a=[a-1, b-a]_b\text{ and }g\cdot (a+1)=[a, g-a]_b.
\end{equation}
Hence, we can calculate the bounds of the products of $g$ by the numbers represented by the strings in $Y_a$ as follows:
$$
\begin{aligned}
\text{if } x\in Y_0,\phantom{(a\neq 0)mm} & \phantom{m}[00^n]_b=[0^n]_b\leq g\cdot [x]_b\leq [g^n]_b=[0g^n]_b;\\
\text{if } x\in Y_a (a\neq 0), \phantom{mm}& [a0^{n-1}(g-a)]_b \leq g\cdot [x]_b\leq [ag^{n-1}(g-a)]_b.
\end{aligned}
$$
Thus, there exists $y\in \Sigma_{b}^n$ such that $g\cdot [x]_b=[ay]_b$ for every $a=0, 1, 2, \dots, g-1$,  so
$$
g\cdot [x]_b - [a0^n]_b=[0y]_b=[y]_b \text{ for some string }y\in \Sigma_{b}^n.
$$
  Since $\iota(x)=k$, $s_b(g\cdot [x]_b)=g\cdot \iota(x)=g\cdot k$, so
  $$
  s_b(g\cdot [x]_b - [a0^n]_b)=s_b([y]_b)=s_b([ay]_b)-a=s_b(g\cdot [x]_b)-a=g\cdot k - a.
  $$
 Thus, $f$ is well-defined.  We just need to show $f$ is bijective so that
$$
|Y_a\langle k \rangle|=|\Sigma_b^n[gk-a]|=\binom{n}{gk-a}_b.
$$
It is obvious that $f$ is injective, since if $f(x_1)=f(x_2)$, $g\cdot [x_1]_b=g\cdot [x_2]_b$ so $x_1=x_2$.
To prove $f$ is surjective, we consider a string $y\in \Sigma_b^n[gk-a]$.
 Then $s(y)=g\cdot k-a$ so $s(ay)=s(y)+a=g\cdot k$.  Thus, the number $[ay]_b$ is divisible by $g$, so
 $$
 g\cdot \iota_b\left( \frac{[ay]_b}{g}\right)=s_b\left(g\cdot \frac{[ay]_b}{g}\right)=s_b([ay]_b)=g\cdot k \text{, so }\iota_b\left( \frac{[ay]_b}{g}\right)=k.
 $$
 Since $[0^{n}]_b\leq [y]_b\leq [g^n]_b$,
\begin{equation}\label{E:interval}
[a0^{n}]_b\leq [ay]_b\leq [ag^n]_b.
\end{equation}
If $a\neq 0$, the number $[a0^{n-1}(g-1)]_b$ is the least multiple of $g$, and the number $[ag^{n-1}(g-a)]_b$ is the greatest multiple of $g$ in the interval (\ref{E:interval}).
Since the number $[ay]_b$ is a multiple of $g$,
$$
\begin{aligned}
\text{if } a=0,     &\phantom{mm}[0^n]_b=[00^n]_b\leq [ay]_b\leq[0g^n]_b=[g^n]_b\text{; }\\
\text{if } a\neq 0, &\phantom{m}[a0^{n-1}(g-a)]_b\leq [ay]_b\leq [ag^{n-1}(g-a)]_b.
\end{aligned}
$$
Hence,  by (\ref{E:bound by g}), we have
 $$
\begin{aligned}
\text{if } a=0,     &\phantom{mmmmm}[0^n]_b\leq \frac{[ay]_b}{g}\leq[1^n]_b\text{; }\\
\text{if } a\neq 0, &\phantom{m}[a^{n-1}(a+1)]\leq \frac{[ay]_b}{g}\leq [(a+1)^n]_b.
\end{aligned}
$$
Therefore, $\left(\frac{[ay]_b}{g}\right)_b\in Y_a\langle k \rangle$ and
 $$
 f\left(\left(\frac{[ay]_b}{g}\right)_b\right)=\left( g\cdot \frac{[ay]_b}{g}-[a0^n]_b\right )_b=([0y]_b)_b=y.
 $$
\end{proof}

Now we express $C_{ba}(n,k)$ in terms of extended binomial coefficients.
\begin{lemma}\label{L:Cba}
For any digit $a\in \{0,  1, 2, \dots, g-1\}$ and any positive integers $n$ and $k$,
\begin{equation}\label{E:Cba}
  C_{ba}(n,k)=\sum_{i=a}^{g-1}\binom{n}{gk-i}_b.
\end{equation}
\end{lemma}
\begin{proof}
 We define
 $$
 f:  Z_{ba}^n\langle k \rangle\rightarrow \bigcup_{i=a}^{g-1} Y_{i}\langle k \rangle\text{ with }f(ax)=x.
 $$
 Since the leading digit $a$ is always dispensable, $\iota(ax)=\iota(x)$.
 Hence, $f$ is a well-defined one-to-one mapping, so $|Z_{ba}^n\langle k \rangle|=|\cup_{i=a}^{g-1} Y_i\langle k \rangle|$.
By (\ref{E:partion w Ya}),
 $$
 |Z_{ba}^n\langle k \rangle|= \sum_{i=a}^{g-1}|Y_i\langle k \rangle|.
 $$
 By Definition \ref{D:Cba} and Lemma \ref{L:recognize}, we obtain (\ref{E:Cba}).
\end{proof}

Therefore, we can express the $b$-nomial numbers of type 3 and 4 in terms of the $b$-nomial numbers of type 1 and 2, respectively, as follows.
\begin{theorem}\label{T:AB in DE}
For any positive integers $n$ and $k$:
$$
\begin{aligned}
&\mathbf{(i)} \phantom{i,}\binom{n}{k}_{b3}=\sum_{i=0}^{g-1}\binom{n}{gk-i}_b=\binom{n+1}{gk+1}_b-\binom{n}{gk+1}_b=\binom{n+1}{gk}_b-\binom{n}{gk-g}_b;\\
&\mathbf{(ii)} \phantom{,}\binom{n}{k}_{b4}=\sum_{i=1}^{g}\binom{n}{gk-i}_{b2}=\binom{n+1}{gk+g}_{b2}-\binom{n}{gk+g}_{b2} =\binom{n+1}{gk+g-1}_{b2}-\binom{n}{gk-1}_{b2}.
\end{aligned}
$$
\end{theorem}
\begin{proof}
By Lemma \ref{L:Cb0} and \ref{L:Cba}, we have the first expression for $\binom{n}{k}_{b3}$ in (i).  By (\ref{E:bnomial recurrence}), we have the last two expressions in (i).

Since $\binom{n}{k}_{b4}=\binom{n+1}{k+1}_{b3}-\binom{n}{k+1}_{b3}$ and $\binom{n}{k}_{b2}=\binom{n+1}{k+1}_b-\binom{n}{k+1}_b$ by Lemma \ref{L:basicA} (ii) and Lemma \ref{L:D and bnomial} (ii), we apply the first expression for $\binom{n}{k}_{b3}$ in (i) to have
\begin{equation}\label{E:proof1}
\begin{aligned}
\binom{n+1}{k+1}_{b3}-\binom{n}{k+1}_{b3}&=\sum_{i=0}^{g-1}\binom{n+1}{g(k+1)-i}_b-\sum_{i=0}^{g-1}\binom{n}{g(k+1)-i}_b\\
&=\sum_{i=1}^{g}\binom{n}{g(k+1)-i}_{b2},
\end{aligned}
\end{equation}
which provides the first expression for $\binom{n}{k}_{b4}$ in (ii).  Similarly, we apply the second expression for $\binom{n}{k}_{b3}$ in (i).  Since $g(k+1)+1=gk+b$, we have
\begin{equation}\label{E:proof2}
\begin{aligned}
\binom{n+1}{k+1}_{b3}-\binom{n}{k+1}_{b3}
&=\left(\binom{n+2}{gk+b}_b- \binom{n+1}{gk+b}_b\right)-\left(\binom{n+1}{gk+b}_b- \binom{n}{gk+b}_b\right)\\
&=\binom{n+1}{gk+b-1}_{b2}-\binom{n}{gk+b-1}_{b2},
\end{aligned}
\end{equation}
which provides the second expression for $\binom{n}{k}_{b4}$ in (ii).  Similarly, we apply the last expression for $\binom{n}{k}_{b3}$ in (i).
Since $g(k+1)-g=gk$, we have
\begin{equation}\label{E:proof3}
\begin{aligned}
\binom{n+1}{k+1}_{b3}-\binom{n}{k+1}_{b3}
&=\left(\binom{n+2}{gk+g}_b- \binom{n+1}{gk}_b\right)-\left(\binom{n+1}{gk+g}_b- \binom{n}{gk}_b\right)\\
&=\left(\binom{n+2}{gk+g}_b- \binom{n+1}{gk+g}_b\right)-\left(\binom{n+1}{gk}_b- \binom{n}{gk}_b\right)\\
&=\binom{n+1}{gk+g-1}_{b2}-\binom{n}{gk-1}_{b2},
\end{aligned}
\end{equation}
which provides the last expression in (ii).
\end{proof}

Applying Theorem \ref{T:AB in DE} (i) to Lemma \ref{L:basicA} (ii), we express the $b$-nomial numbers of type 4 in terms of the extended binomial coefficients as follows.
\begin{corollary}\label{C:A in D}
For any positive $n$ and $k$,
$$
\begin{aligned}
\binom{n}{k}_{b4}
&=\binom{n+2}{gk+b}_b-2\binom{n+1}{gk+b}_b+\binom{n}{gk+b}_b\\
&=\binom{n}{gk}_b+\sum_{i=1}^{g-1}\binom{n+1}{gk+i}_b\\
&= g\cdot\binom{n}{gk}_b+\sum_{i=1}^{g-1}(g-i)\cdot\left(\binom{n}{gk+i}_b+\binom{n}{gk-i}_b\right).
\end{aligned}
$$
\end{corollary}
\begin{proof}
Since $\binom{n}{k}_{b4}=\binom{n+1}{k+1}_{b3}-\binom{n}{k+1}_{b3}$,
the first identity in (\ref{E:proof2}) provides the first expression.
By the first identity in (\ref{E:proof3}), we have
$$
\binom{n}{k}_{b4} =\left(\binom{n+2}{gk+g}_b-\binom{n+1}{gk}_b-\binom{n+1}{gk+g}_b\right)+\binom{n}{gk}_b.
$$
Since $\binom{n+2}{gk+g}_b=\sum_{i=0}^{g}\binom{n+1}{gk+i}_b$ by (\ref{E:bnomial recurrence}), we have the second expression.
By the first identity in (\ref{E:proof1}) and (\ref{E:bnomial recurrence}),  we have
$$
\binom{n}{k}_{b4}= \sum_{i=1}^{g}\left(\binom{n+1}{gk+i}_b-\binom{n}{gk+i}_b\right)= \sum_{i=1}^{g}\sum_{j=1}^{g}\binom{n}{gk+i-j}_b.
$$
The number $i-j$ for $1\leq i, j \leq g$ is as follows:
$$
\begin{array}{r|rccccccc}
 i-j &j=1&2&3&\cdots &g-2&g-1&g\\
 \hline
 i=1 & 0& -1 &-2 &\cdots &3-g&2-g&1-g\\
   2 & 1& 0 &-1 &\cdots &4-g&3-g&2-g\\
   3 & 2& 1 &0 &\cdots &5-g&4-g&3-g\\
 \vdots& & & &\ddots \\
g-2 & g-3& g-4 &g-5 &\cdots &0&-1&-2\\
g-1 & g-2& g-3 &g-4 &\cdots &1&0&-1\\
  g & g-1& g-2 &g-3 &\cdots &2&1&0\\
\end{array}
$$
Hence, we have
$$
\begin{aligned}
\binom{n}{k}_{b4}&=g\cdot\binom{n}{gk}_b\\
&+(g-1)\cdot\binom{n}{gk+1}_b+(g-2)\cdot\binom{n}{gk+2}_b+\cdots+1\cdot\binom{n}{gk+g-1}_b\\
&+(g-1)\cdot\binom{n}{gk-1}_b+(g-2)\cdot\binom{n}{gk-2}_b+\cdots+1\cdot\binom{n}{gk-(g-1)}_b.
\end{aligned}
$$
Therefore, we have the last expression for $\binom{n}{k}_{b4}$.
\end{proof}




\section{Explicit formulas}\label{S:Explicit}

Neuschel showed that the extended binomial coefficients can be expressed as a sum of Hermite polynomials and Bernoulli numbers \cite{Neuschel}.
In this section, we express the $b$-nomial numbers of each type, including extended binomial coefficients, in terms of the binomial coefficients.
\begin{theorem}\label{T:bnomial bnom}
For any nonnegative integers $n$ and $k$:
$$
\begin{aligned}
&(i)\phantom{iimm}  \binom{n}{k}_b    \phantom{.} =\sum_{i_1+i_2+\cdots+i_g=k\phantom{a+1}} \phantom{m}\binom{n}{i_1}\binom{i_1}{i_2}\binom{i_2}{i_3}\cdots \binom{i_{g-1}}{i_g};\\
&(ii)\phantom{imm}  \binom{n}{k}_{b2} =\sum_{i_1+i_2+\cdots+i_g=k+1\phantom{m}} \binom{n}{i_1-1}\binom{i_1}{i_2}\binom{i_2}{i_3}\cdots \binom{i_{g-1}}{i_g}\text{; }\\
&(iii)\phantom{mm}  \binom{n}{k}_{b3} =\sum_{i_1+i_2+\cdots+i_g=gk+1} \binom{n}{i_1-1}\binom{i_1}{i_2}\binom{i_2}{i_3}\cdots \binom{i_{g-1}}{i_g}\text{; }\\
&(iv)\phantom{mm}  \binom{n}{k}_{b4} =\sum_{i_1+i_2+\cdots+i_g=gk+b} \binom{n}{i_1-2}\binom{i_1}{i_2}\binom{i_2}{i_3}\cdots \binom{i_{g-1}}{i_g}\text{. }\\
\end{aligned}
$$
\end{theorem}
\begin{proof}
\noindent (i) For any string $x=a_{1}a_{2}\cdots a_n$ with a digit $a_i \in \Sigma_b$, we can find the unique string $x_j$ for each $j=0, 1, 2, \dots, g$ as follows:
$$
x_j=a'_{1}a'_{2}\cdots a'_n \text{, where } a'_i=\left\{
                                                   \begin{array}{ll}
                                                     a_i, & \hbox{if $a_i<j$;} \\
                                                     j, & \hbox{if $a_i\geq j$.}
                                                   \end{array}
                                                 \right.
$$
Hence, every string in $\Sigma_b^n[k]$ can be uniquely constructed as follows:
For any positive integer $i_j$ satisfying $\sum_{j=1}^{g}i_j =k$:
\begin{itemize}
  \item Let $x_0=0^n$;
  \item For $j= 1, 2,  \dots, g$, construct string $x_{j}$, by choosing $i_{j}$ digits $(j-1)$ in the string $x_{j-1}$ and replacing each chosen digit $j-1$ with digit $j$;
  \item Let $x=x_g$.
\end{itemize}
Then each string $x_j\in\{0,  1,  2, \dots, j\}^n$ for all $j=0, 1, 2, \dots, g$, so the string $x\in \Sigma_b^n$.  Since there is no change in the occurrences of digit $j$ after constructing the string $x_{j+1}$,
$$
|x|_j=|x_{j+1}|_{j}=i_j-i_{j+1} \text{ for all }j=1, 2, \dots, g-1 \text{, and } |x|_g=|x_g|_g=i_g.
$$
Hence, the digit sum of the string $x$ is
  $$
  s(x)=\sum_{j=1}^g j\cdot|x|_j=\sum_{j=1}^{g-1} j\cdot \left(i_{j}-i_{j+1}\right)+ g\cdot i_g=\sum_{j=1}^{g}i_j=k.
  $$
Since the string $x \in \Sigma_b^n$, the string $x \in \Sigma_b^n[k]$.

Since there are $\binom{n}{i_1}$ ways to construct $x_1$ from $x_0$ and $\binom{i_{j-1}}{i_j}$ ways to construct $x_j$ from $x_{j-1}$ for each $j=2, 3, \dots, g$,
there are $\binom{n}{i_1}\binom{i_1}{i_2}\binom{i_2}{i_3}\cdots \binom{i_{g-1}}{i_g}$ distinct strings in $\Sigma_b^n[k]$.
Therefore, the right-hand side of the equation (i) counts the number of strings in $\Sigma_b^n[k]$.  Since the size $|\Sigma_b^n[k]|=\binom{n}{k}_b$, the equation (i) holds.

\medskip\noindent(ii)
To construct a string in $\sigma_b^{n+1}[k+1]$, we start with the string $x_0=10^{n}$ and we construct $x_1$ by choosing $i_1-1$ copies of the
digit $0$ in $x_0$ and replacing each chosen digit $0$ with the digit $1$.  Then the string $x_1$ has $i_1$ digits $1$ because of the leading digit.  After that, we have the same procedures to construct $x_j$ for all $j=2, 3, \dots, g$ as (i).  Since we want the digit sum to be $k+1$, the sum $\sum i_j = k+1$.
Therefore, we have the equation (ii).

\medskip\noindent(iii)
By (i) and Theorem \ref{T:AB in DE} (i), we have
$$
\begin{aligned}
\binom{n}{k}_{b3}&=\binom{n+1}{gk+1}_b-\binom{n}{gk+1}_b\\
&=\sum_{\sum i_j=gk+1} \binom{n+1}{i_1}\binom{i_1}{i_2}\cdots \binom{i_{g-1}}{i_g}-\sum_{\sum{i'_j}=gk+1} \binom{n}{i'_1}\binom{i'_1}{i'_2}\cdots \binom{i'_{g-1}}{i'_g}.
\end{aligned}
$$
We assume $i_g\leq i_{g-1}\leq \cdots \leq i_2 \leq i_1\leq n+1$ and $i'_g\leq i'_{g-1}\leq \cdots \leq i'_2 \leq i'_1\leq n$.
However, since $\binom{n}{n+1}=0$, we can let $i'_1\leq n+1$ so we set $i_j=i'_j$.  Hence,
$$
\binom{n}{k}_{b3}=\sum\binom{n+1}{i_1}\binom{i_1}{i_2}\cdots \binom{i_{g-1}}{i_g}-\sum\binom{n}{i_1}\binom{i_1}{i_2}\cdots \binom{i_{g-1}}{i_g},
$$
where $\sum_{j=1}^{g} i_j=gk+1$.  Since $\binom{n+1}{i_1}-\binom{n}{i_1}=\binom{n}{i_1-1}$, we have the equation (iii).

\medskip\noindent(iv)
Similarly, by (ii) and Theorem \ref{T:AB in DE} (ii), we have
$$
\begin{aligned}
\binom{n}{k}_{b4}&=\binom{n+1}{gk+g}_{b2}-\binom{n}{gk+g}_{b2}\\
&=\sum\binom{n+1}{i_1-1}\binom{i_1}{i_2}\cdots \binom{i_{g-1}}{i_g}-\sum\binom{n}{i_1-1}\binom{i_1}{i_2}\cdots \binom{i_{g-1}}{i_g}
\end{aligned}
$$
where $\sum_{j=1}^{g} i_j=gk+g+1=gk+b$.  Since $\binom{n+1}{i_1-1}-\binom{n}{i_1-1}=\binom{n}{i_1-2}$, we have (iv).
\end{proof}
Note that we can assume the indices $i_j$ in Theorem \ref{T:bnomial bnom} satisfy the following:
$$
\begin{aligned}
&(i)\phantom{iimm}   i_g\leq i_{g-1}\leq \cdots \leq i_2 \leq i_1\leq n;\\
&(ii)\phantom{imm}  i_g\leq i_{g-1}\leq \cdots \leq i_2 \leq i_1\leq n+1;\\
&(iii)\phantom{mm} i_g\leq i_{g-1}\leq \cdots \leq i_2 \leq i_1\leq n+1;\\
&(iv)\phantom{mm}  i_g\leq i_{g-1}\leq \cdots \leq i_2 \leq i_1\leq n+2,
\end{aligned}
$$
because otherwise, we have $\binom{i_1}{i_2}\binom{i_2}{i_3}\cdots \binom{i_{g-1}}{i_g}=0$, $\binom{n}{i_1}=0$, $\binom{n}{i_1-1}=0$, or $\binom{n}{i_1-2}=0$.

Using the explicit formula for the binomial coefficients:
$$
\binom{n}{k}=\frac{n!}{k!(n-k)!},
$$
we find the following explicit formulas for the $b$-nomial numbers of each type.
\begin{theorem}\label{T:bnomial explicit}
For any nonnegative integers $n$ and $k$:
$$
\begin{aligned}
&(i)\phantom{iimm}   \binom{n}{k}_b \phantom{.} =\phantom{}\sum_{i_1+i_2+\cdots+i_g=k}&\frac{n!}{(n-i_1)!(i_1-i_{2})!(i_2-i_3)!\cdots(i_{g-1}-i_{g})! i_g!};\\
&(ii)\phantom{imm}     \binom{n}{k}_{b2}=\sum_{i_1+i_2+\cdots+i_g=k+1} &\frac{i_1\cdot n!}{(1+n-i_1)!(i_1-i_{2})!(i_2-i_3)!\cdots(i_{g-1}-i_{g})! i_g!};\\
&(iii)\phantom{mm}     \binom{n}{k}_{b3}=\sum_{i_1+i_2+\cdots+i_g=gk+1}&\frac{ i_1\cdot n!}{(1+n-i_1)!(i_1-i_2)!(i_2-i_3)!\cdots (i_{g-1}-i_{g})! i_g!};\\
&(iv)\phantom{mm}     \binom{n}{k}_{b4}=\sum_{i_1+i_2+\cdots+i_g=gk+b}& \frac{i_1(i_1-1)\cdot n!}{(2+n-i_1)!(i_1-i_2)!(i_2-i_3)!\cdots (i_{g-1}-i_{g})! i_g!},
\end{aligned}
$$
where the indices $i_j$ satisfy
$$
\begin{aligned}
 0\leq i_g\leq i_{g-1}\leq \cdots \leq i_2 \leq i_1&\leq n\phantom{+1.. } \text{ for } (i);\\
 0\leq i_g\leq i_{g-1}\leq \cdots \leq i_2 \leq i_1&\leq n+1 \text{ for }(ii);\\
 0\leq i_g\leq i_{g-1}\leq \cdots \leq i_2 \leq i_1&\leq n+1 \text{ for }(iii);\\
 0\leq i_g\leq i_{g-1}\leq \cdots \leq i_2 \leq i_1&\leq n+2 \text{ for }(iv).
\end{aligned}
$$
\end{theorem}



\section{Symmetry}\label{S:Symmetry}

In this section, we discuss symmetry of the sequences defined in Sections \ref{S:D}, \ref{S:AB}, and \ref{S:ABCD}.
By the definitions, the binomial coefficients and extended binomial coefficients have symmetry: for any nonnegative integer $n$,
\begin{equation}\label{E:bnomial symmetry}
\binom{n}{k}=\binom{n}{n-k} \text{ and } \binom{n}{k}_b=\binom{n}{gn-k}_b.
\end{equation}
The $b$-nomial numbers of type 2 and 4 and the sequence $\left(C_{b1}(n,k)\right)_{n,k>0}$ also have symmetry as follows.
\begin{lemma}\label{L:symmetry}
For any nonnegative integers $n$ and $k$:
$$
\begin{aligned}
 &(i) \phantom{m} \binom{n}{k}_{b2}=\binom{n}{g(n+1)-(k+1)}_{b2};\phantom{mmmmmmmmmmmmmmmmmmmmmmm}\\
 &(ii) \phantom{m} \binom{n}{k}_{b4}=\binom{n}{n-k}_{b4};\\
 &(iii) \phantom{m} C_{b1}(n,k)=C_{b1}(n,n-k+1).
\end{aligned}
$$
\end{lemma}
\begin{proof}
\noindent (i)
Let $x$ be a string in $\sigma_b^{n+1}[k+1]$.  Then there exist digits $a_i\in\Sigma_b$ satisfying $x=a_1a_2\cdots a_na_{n+1}$ with $a_1\neq 0$ and $\sum a_i =k+1$.  Then we define a string $x'$ such that
$$
x'=a'_{1}a'_{2}\cdots a'_na'_{n+1}
\text{, where }
  a'_i=\begin{cases}
         b-a_i, & \mbox{if } i=1; \\
         g-a_i, & \mbox{otherwise}.
       \end{cases}
$$
Since $a_1\neq 0$, the digit $a_1'\in \Sigma_b$ so every digit $a_i'\in \Sigma_b$ for all $i$.
Since $a_1\neq b$, the digit $a_1\neq 0$.
Since the sum $\sum a_i =k+1$,
$$
s(x')=gn+b-\sum a_i=gn+g+1-(k+1)=g(n+1)-k.
$$
Thus, the string $x'\in \sigma_b^{n+1}[g(n+1)-k]$.  Hence, the function
$$
f: \sigma_b^{n+1}[k+1]\rightarrow \sigma_b^{n+1}[g(n+1)-k] \text{ with } f(x)=f(x')
$$
is well-defined.  Since $a_i\neq c_{i}$ iff $a'_i\neq c'_i$, the function $f$ is injective.

To prove $f$ is surjective, we consider a string $y\in\sigma_b^{n+1}[g(n+1)-k]$ with digits $c_i$ such that $y=c_1c_2\cdots c_n c_{n+1}$.  Then the string
$$
y'=c'_{1}c'_{2}\cdots c'_nc'_{n+1} \text{, where }
  c_{i'}=\begin{cases}
         b-c_i, & \mbox{if } i=1; \\
         g-c_i, & \mbox{otherwise,}
       \end{cases}
$$
satisfies $f(y')=y$ and $y'\in \sigma_b^{n+1}[k+1]$, since  $s(y')=gn+b-\sum c_i=gn+b-(gn+g-k)=k+1$.
Therefore, $f$ is bijective, so $|\sigma_b^{n+1}[k+1]|=|\sigma_b^{n+1}[g(n+1)-k]|$.

\medskip\noindent(ii)
Applying (\ref{E:bnomial symmetry}) to the second identity in Corollary \ref{C:A in D},
  $$
  \begin{aligned}
   \binom{n}{k}_{b4}&=\binom{n}{gk}_b+\sum_{i=1}^{g-1}\binom{n+1}{gk+i}_b\\
                    &=\binom{n}{gn-gk}_b+\sum_{i=1}^{g-1}\binom{n+1}{g(n+1)-gk-i}_b\\
                    &=\binom{n}{g(n-k)}_b+\sum_{i=1}^{g-1}\binom{n+1}{g(n-k)+g-i}_b\\
                    &=\binom{n}{g(n-k)}_b+\sum_{i=1}^{g-1}\binom{n+1}{g(n-k)+i}_b=\binom{n}{n-k}_{b4}.
  \end{aligned}
  $$

\medskip\noindent(iii)
Similarly, by Lemma \ref{L:Cba} and (\ref{E:bnomial symmetry}),
$$
\begin{aligned}
C_{b1}(n,k)&=\sum_{i=1}^{g-1}\binom{n}{gk-i}_b=\sum_{i=1}^{g-1}\binom{n}{gn-gk+i}_b\\
&=\sum_{i=1}^{g-1}\binom{n}{gn-gk+g-i}_b=\sum_{i=1}^{g-1}\binom{n}{g(n-k+1)-i}_b=C_{b1}(n, n-k+1).
\end{aligned}
$$
\end{proof}


Even if $\binom{n}{k}_{23}=\binom{n}{n-k}_{23}$ and $C_{b1}(n,k)=C_{b1}(n,n-k+1)$, the $b$-nomial numbers of type 3  and the sequence $[C_{ba}(n,k)]_{n,k\geq 0}$ are  not symmetric in general.  That is,
$$
\binom{n}{k}_{b3}\neq \binom{n}{n-k}_{b3}\text{ for any }b>2 \text{ and } C_{ba}(n,k)\neq C_{ba}(n, n-k+1) \text{ for any } a>1.
$$
However, we can find the following relations for symmetric entries.
\begin{lemma}For any positive integer $n$, any integer $k$, and any digit $a=2, 3, \dots, g-1$:
$$
\begin{aligned}
  &(i) \phantom{m} \binom{n}{n-k+1}_{b3}-\binom{n}{k}_{b3}=\binom{n-1}{n-k+1}_{b3}-\binom{n-1}{k}_{b3};\\
  &(ii) \phantom{m} C_{ba}(n, n-k+1)-C_{ba}(n,k)=C_{b, b-a}(n, n-k+1)-C_{b, b-a}(n, k).\phantom{mmmmmmmmm}
\end{aligned}
$$
\end{lemma}
\begin{proof}
\noindent(i)
By (\ref{E:bnomial symmetry}) and Theorem \ref{T:AB in DE} (i),
\begin{equation}\label{E:symmetry B}
\begin{aligned}
\binom{n}{n-k+1}_{b3}&= \sum_{i=0}^{g-1} \binom{n}{g(n-k+1)-i}_b =\sum_{i=0}^{g-1}\binom{n}{gn-(gk-g+i)}_b\\
&=\sum_{i=0}^{g-1}\binom{n}{gk-(g-i)}_b=\sum_{i=1}^{g}\binom{n}{gk-i}_b\\
&=\sum_{i=0}^{g-1}\binom{n}{gk-i}_b-\binom{n}{gk}_b+\binom{n}{g(k-1)}_b\\
&=\binom{n}{k}_{b3}-\binom{n}{gk}_b+\binom{n}{g(k-1)}_b.
\end{aligned}
\end{equation}
By adjusting the indices $n$ and $k$ in (\ref{E:symmetry B}), we have
\begin{equation}\label{E:symmetryC}
  \binom{n-1}{n-k+1}_{b3}=\binom{n-1}{n-1-(k-1)+1}_{b3}=\binom{n-1}{k-1}_{b3}-\binom{n-1}{g(k-1)}_b+\binom{n-1}{g(k-2)}_b.
\end{equation}
By subtracting (\ref{E:symmetryC}) from (\ref{E:symmetry B}) and applying Theorem \ref{T:AB in DE} (i),
we have
$$
\begin{aligned}
&\binom{n}{n-k+1}_{b3}-\binom{n-1}{n-k+1}_{b3}\\
&=\binom{n}{k}_{b3}- \binom{n-1}{k-1}_{b3}-\left(\binom{n}{gk}_b-\binom{n-1}{g(k-1)}_b\right)+\left(\binom{n}{g(k-1)}_b -\binom{n-1}{g(k-2)}_b\right)\\
&=\binom{n}{k}_{b3}- \binom{n-1}{k-1}_{b3}-\binom{n-1}{k}_{b3}+\binom{n-1}{k-1}_{b3}=\binom{n}{k}_{b3}-\binom{n-1}{k}_{b3}, \\
\end{aligned}
$$
which provides the relation in (i).

\medskip\noindent(ii)
By (\ref{E:bnomial symmetry}) and Lemma \ref{L:Cba}, we have
\begin{equation}\label{E:symmetry Cba}
\begin{aligned}
C_{ba}(n,n-k+1)&=\sum_{i=a}^{g-1}\binom{n}{gn-gk+g-i}_b=\sum_{i=a}^{g-1}\binom{n}{gk-g+i}_b=\sum_{i=1}^{g-a}\binom{n}{gk-i}_b\\
&=\sum_{i=1}^{g-1}\binom{n}{gk-i}_b-\sum_{i=g-a+1}^{g-1}\binom{n}{gk-i}_b=C_{b1}(n,k)-C_{b, g-a+1}(n,k).
\end{aligned}
\end{equation}
By adjusting the index $k$, we have
\begin{equation}\label{E:symmetry Cba 2}
C_{ba}(n,k)=C_{b1}(n,n-k+1)-C_{b, g-a+1}(n,n-k+1).
\end{equation}
By subtracting (\ref{E:symmetry Cba 2}) from (\ref{E:symmetry Cba}) and applying Lemma \ref{L:symmetry} (iii), we have
$$
C_{ba}(n,n-k+1)-C_{ba}(n, k)=C_{b, g-a+1}(n,n-k+1)-C_{b, g-a+1}(n, k).
$$
Since $g-a+1=b-a$, we have the relation in (ii).
\end{proof}

\section{Acknowledgments}

I would like to thank the reviewer for his/her suggestions and references, which helped to improve this paper and expand my understanding.

\begin{thebibliography}{99}

\bibitem{BEJ}
T. Ball, T. Edgar, and D. Juda, Dominance orders, generalized binomial
coefficients, and Kummer's theorem, \textit{Math. Mag.} \textbf{87}
(2014), 135--143.

\bibitem{Choi}
J. Choi, Indispensable digits for digit sums, 
\textit{Notes Number Theory Discrete Math.}
\textbf{25} (2019) 40--48.

\bibitem{Freund}
J. E. Freund,
Restricted occupancy theory --- a generalization of Pascal's triangle, \textit{Amer. Math. Monthly} \textbf{63} (1956) 20--27.

\bibitem{FA}
D. C. Fielder and C. O. Alford,
Pascal's triangle: top gun or just one of the gang?, \textit{Applications of Fibonacci Numbers} \textbf{4} (1991) 77--90.

\bibitem{Eger}
S. Eger, Restricted weighted integer compositions and extended binomial coefficients, \textit{J. Integer Sequences} \textbf{16} (2013) 
\href{https://cs.uwaterloo.ca/journals/JIS/VOL16/Eger/eger6.html}{Article 13.1.3}.

\bibitem{Jones}
C. H. Jones, Generalized hockey stick identities and $n$-dimensional block walking, \textit{Fibonacci Quart.} \textbf{34} (1996), 280--288.

\bibitem{Neuschel}
T. Neuschel, A note on extended binomial coefficients, \textit{J. Integer Sequences} \textbf{17} (2014) 
\href{https://cs.uwaterloo.ca/journals/JIS/VOL17/Neuschel/neuschel4.html}{Article 14.10.4}.

\bibitem{Nguyen}
H. D. Nguyen, A generalization of the digital binomial theorem,
\textit{J. Integer Sequences} \textbf{18} (2015) 
\href{https://cs.uwaterloo.ca/journals/JIS/VOL18/Nguyen/nguyen6.html}{Article 15.5.7}.

\bibitem{Sha}
J. Shallit, \textit{A Second Course in Formal Languages and Automata Theory}, Cambridge University Press, 2009.

\bibitem{Sl}
N. J. A. Sloane et al., On-line Encyclopedia of Integer Sequences,
\url{https://oeis.org}, 2019.

\bibitem{Wei}
E. W. Weisstein, MathWorld-A Wolfram Web Resource, 
\url{http://mathworld.wolfram.com/Concatenation.html}.

\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2010 {\it Mathematics Subject Classification}: Primary 11A63; Secondary 05A10.

\noindent {\it Keywords}: digit sum, indispensable digit, binomial coefficient, extended binomial coefficient, polynomial coefficient, generation of binomial coefficient.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A005773},
\seqnum{A007318},
\seqnum{A008287},
\seqnum{A027907}, and
\seqnum{A071976}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received July 7 2019;
revised version received December 9 2019.
Published in {\it Journal of Integer Sequences}, December 11 2019.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{https://cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}

                                                                                



.
