Counting vectors in $\mathbb{Z}_n^n$ with $0$ as a most common coordinate value

How can we count the number of vectors in $\mathbb{Z}_n^n$ that have $0$ as their strictly most common coordinate value appearing exactly $k$ times ? More precisely, if we denote by $$\alpha(\mathbf{x},m)=\sum_{k=1}^n \mathbb{1}\{ x_k=m \} $$ the number of times the value $m$ appears as a coordinate in a vector $\mathbf{x}=(x_1,x_2,...,x_n)$, then the numbers I am looking for are

$$ \beta(n,k) = \big| \big\{ (x_1, x_2,...,x_n) \in \mathbb{Z}_n^n: \alpha(0) = k, \alpha(\mathbf{x},0)>\alpha(\mathbf{x},m) \quad \mbox{for} \quad m=1,2,...,n-1 \big \}\big|$$

I would also like to count the vectors that have $0$ as the most common coordinate value appearing exactly $k$ times which is the same number of times another coordinate value appears. In this latter case, I would also like to know how many values are tied and the formal definition would be

$$ \hat{\beta}(n,k) = \big| \big\{ (x_1, x_2,...,x_n) \in \mathbb{Z}_n^n: \alpha(\mathbf{x},0) = k, \exists m \in \{1,2,..., n-1\} \quad \mbox{s.t.} \quad \alpha(\mathbf{x},0)=\alpha(\mathbf{x},m) \big \}\big|$$

For example, if $n=3$, then all $27$ vectors are $(0,0,0), (0,0,1),..., (2,2,2)$, of which there is $1$ that has $0$ as strictly most common coordinate value appearing $3$ times (the vector $(0,0,0)$), there are $6$ that have $0$ as strictly most common coordinate value appearing $2$ times (those are the vectors $(0,0,1), (0,1,0), (1,0,0), (0,0,2), (0,2,0)$ and $(2,0,0)$) and 6 which have $0$ as the most common value appearing once, but it is not the only most common coordinate value (those are the $6$ permutation and $3$ values are tied). So $\beta(3,3)=1, \beta(3,2) = 6$ and $\hat{\beta}(3,1) = 6$)

EDIT When $k>n/2$, calculations are easy as we only need to place the $k$ zeros and fill the remaining places with arbitrary numbers, so $\beta(n,k) = C^k_n \times (n-1)^{(n-k)}$. The problem lies in the case when $k\leq n/2$.

EDIT 2 Here are some precomputed values :

$\beta(3,k) = [0, 0, 6, 1]$ for $k=0,1,2,3$

$\beta(4,k) = [0, 0, 36, 12, 1]$ for $k=0,1,...,4$

$\beta(5,k) = [0, 0, 240, 160, 20, 1]$ for $k=0,1,...,5$

$\beta(6,k) = [0, 0, 1800, 2400, 375, 30, 1]$ for $k=0,1,...,6$

$\beta(7,k) = [0, 0, 15120, 40950, 7560, 756, 42, 1]$ for $k=0,1,...,7$

and for $n=6$ the $A[i][j]$ entry in the matrix below stores the number of times that $0$ appears a maximal number of times equal to $i$ together with $j$ other values.

[[ 0. 0. 0. 0. 720. 0.]

[ 5400. 900. 0. 0. 0. 0.]

[ 100. 0. 0. 0. 0. 0.]

[ 0. 0. 0. 0. 0. 0.]

[ 0. 0. 0. 0. 0. 0.]

[ 0. 0. 0. 0. 0. 0.]]

The same matrix for $n=5$:

[[ 0. 0. 0. 120. 0.]

[ 360. 0. 0. 0. 0.]

[ 0. 0. 0. 0. 0.]

[ 0. 0. 0. 0. 0.]

[ 0. 0. 0. 0. 0.]]

Solution 1:

Given an alphabet of $n$ (distinct) characters, which may assumed to be the set $\{1,2,\cdots,n\}$, the number of words, i.e. lists where order and labeling counts, of length $m$ in which the character $j$ is repeated $k_j$times is given by the multinomial $$ \bbox[lightyellow] { {{m!} \over {k_{\,1} !k_{\,2} !\; \cdots \;k_{\,n} !}}\quad \left| {\;k_{\,1} + k_{\,2} + \; \cdots + \;k_{\,n} \, = \,m} \right. } $$

Let us consider $W(n,m,r)$ as the number of words
- from alphabet $\{1,2,\cdots,n\}$
- of length $m$
- with each character repeated at most $r$ times
It can be clearly expressed as $$ \bbox[lightyellow] { W(n,m,r) = \sum\limits_{\left\{ \begin{subarray}{l} 0\, \leqslant \,k_{\,j} \; \leqslant \,r \\ k_{\,1} + k_{\,2} + \; \cdots + \;k_{\,n} \, = \,m \end{subarray} \right.\;} {\frac{{m!}} {{k_{\,1} !k_{\,2} !\; \cdots \;k_{\,n} !}}} } \tag {1}$$

Now if one specific character (e.g. $k_n$) is repeated exactly $t$ times, while the others are repeated at most $s$ times, then the number of the words so formed will be $$ \bbox[lightyellow] { \begin{gathered} W^ * (n,m,t,s) = \sum\limits_{\left\{ \begin{subarray}{l} k_{\,n} = t \\ 0\, \leqslant \,k_{\,j} \; \leqslant \,s\quad \left| {\;n\, \ne \,j} \right. \\ k_{\,1} + k_{\,2} + \; \cdots + \;k_{\,n} \, = \,m \end{subarray} \right.\;} {\frac{{m!}} {{k_{\,1} !k_{\,2} !\; \cdots \;k_{\,n} !}}} = \hfill \\ = \sum\limits_{\left\{ \begin{subarray}{l} 0\, \leqslant \,k_{\,j} \; \leqslant \,s\quad \left| {\;0\, \leqslant \,j\, \leqslant \,n - 1} \right. \\ k_{\,1} + k_{\,2} + \; \cdots + \;k_{\,n - 1} \, = \,m - t \end{subarray} \right.\;} {\frac{{\left( {m - t} \right)!}} {{k_{\,1} !k_{\,2} !\; \cdots \;k_{\,n - 1} !}}\frac{{m!}} {{\left( {m - t} \right)!t!}}} = \hfill \\ = \left( \begin{gathered} m \\ t \\ \end{gathered} \right)\;W(n - 1,\,m - t,\,s) \hfill \\ \end{gathered} } \tag {2}$$

Putting $s=t-1$ and summing for $2 \le t \le n$ will give the answer to your problem.

So everything boils down to $W$.
I am not aware of a formulation more "compact" than (1).
However we can compute $W$ also recursively.

In fact, putting $s=r, t=j $ in (2) we get $$ \bbox[lightyellow] { \begin{gathered} W(n,m,r) = \sum\limits_{\left\{ \begin{subarray}{l} 0\, \leqslant \,k_j \; \leqslant \,r \\ k_{\,1} + k_{\,2} + \; \cdots + \;k_{\,n} \, = \,m \end{subarray} \right.\;} {\frac{{m!}} {{k_{\,1} !k_{\,2} !\; \cdots \;k_{\,n} !}}} = \hfill \\ = \sum\limits_{0\, \leqslant \,j\; \leqslant \,r} {\;\sum\limits_{\left\{ \begin{subarray}{l} 0\, \leqslant \,k_{\,l} \; \leqslant \,r\quad \left| {\;0\, \leqslant \,l\, \leqslant \,n - 1} \right. \\ k_{\,1} + k_{\,2} + \; \cdots + \;k_{\,n - 1} \, = \,m - j \end{subarray} \right.\;} {\frac{{\left( {m - j} \right)!}} {{k_{\,1} !k_{\,2} !\; \cdots \;k_{\,n} !}}\frac{{m!}} {{\left( {m - j} \right)!j!}}} } = \hfill \\ = \sum\limits_{0\, \leqslant \,j\; \leqslant \,r} {\left( \begin{gathered} m \\ j \\ \end{gathered} \right)\;W(n - 1,\,m - j,\,r)} \hfill \\ \end{gathered} } \tag {3.a}$$ with starting conditions to be properly established.
In fact, it is sufficient to put $$ \bbox[lightyellow] { \left\{ \begin{gathered} W(n,\,m,\,r) = 0\quad \left| {\;n < 0\; \vee \;m < 0\; \vee \;r < 0} \right. \hfill \\ W(n,\,0,\,r) = 1\;\left( {\text{empty}\;\text{word}} \right) \hfill \\ \end{gathered} \right. } \tag {3.b}$$ since other "obvious" values like $$ \bbox[lightyellow] { \left\{ \begin{gathered} W(n,\,m,\,r) = 0\quad \left| {\;rn < m} \right. \hfill \\ W(n,\,m,\,1) = n^{\,\underline {\,m\,} } \hfill \\ W(1,\,m,\,r) = \left[ {m \leqslant r} \right] = \left( \begin{gathered} m - r \\ m - r \\ \end{gathered} \right) \hfill \\ W(n,\,1,\,r) = n\left[ {1 \leqslant r} \right] \hfill \\ \end{gathered} \right. } \tag {3.c}$$ follow from that. A LU decomposition of $W$ rendered as matrix gives $$ W(n,m,r) = \sum\limits_{0\, \leqslant \,k\; \leqslant \,n\;} {\left( \begin{gathered} n \\ k \\ \end{gathered} \right)k!T(k,m,r)} = \sum\limits_{0\, \leqslant \,k\; \leqslant \,n\;} {T(k,m,r)\,n^{\,\underline {\,k\,} } } $$ where:
$T(n,m,2)$ is OEIS A144331,
$T(n,m,3)$ is OEIS A144385,
$T(n,m,4)$ is OEIS A144643 ....

The above shows a parallelism with the tranformation $n^m\; \to \; n^{\,\underline {\,k\,} }$ through Stirling N. 2nd kind.
If so, $T(n,m,r)$ shall read similar to the transposed of the Stirling N., i.e. as $\left\{ \begin{gathered} m \\ n \\ \end{gathered} \right\}$, and in fact, very interestingly, in OEIS it is defined as
number of partitions of an m-set into n nonempty subsets, each of size at most r.