# 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.]]

• You would expect the answer to your first question to be less than $n^{n-1}$ and the sum of the two to be greater than $n^{n-1}$: in your example $7 \lt 3^2 \lt 7+6$ Nov 2, 2017 at 14:46
• and the first count should be $\leq \frac{n^n - n!}{n}.$ Nov 3, 2017 at 0:35
• Some consecutive desired vals: 7, 49, 421, 4606, 64429 with no OEIS! Nov 3, 2017 at 1:47
• If you are going as $\{0,1,\cdots,n-1\}$ instead as in your previous formulation with $\{1,2,\cdots,n\}$, then change also the title accordingly ! . BUT avoid to sensibly change a post after you publish it: it is much annoying and confusing for either for those trying to reply and for any reader !! Nov 3, 2017 at 12:31
• @GCab Relax man, I forgot to update the title; there you have it ! I only wanted to formalise the problem better, as people seem to have shown interest by upvoting and starring. Do you have any ideas of a solution ? I thought of using a dynamic programming approach to get the values, but that would not give a general formula. Nov 3, 2017 at 13:19

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.

• Interesting, indeed and a nice approach. I'm curious to see this story going on ... (+1) Nov 3, 2017 at 16:00
• @MarkusScheuer: thanks, initial conditions are now established. Do you (or every other reader) know some existing works about "Number of words with given max repetition" ? Nov 3, 2017 at 16:42