Lets say I have T total items and out of them n are distinct. So n <= T.
In other words we can have m1 items of item 1 and m2 items of item 2....and so on, and that $m_1 + m_2 +\cdots +m_n = T$.
What are the number of permutations of r items taken out of those T items where r <= T?
If r == T, the answer is : $T!/( m_1! m_2! \cdots m_n!)$
Question is : What if r < T ? What are the number of permutations?
Note I am not looking for number of combinations where order doesn't matter, but number of permutations where order does matter.
I know the combination of r items from n distinct items is C(n+r-1,r).
Consider the the following expansion $$ \eqalign{ & \left( {x_{\,1} + x_{\,2} + \cdots + x_{\,n} } \right)^{\,2} = \cr & \left( {x_{\,1} + x_{\,2} + \cdots + x_{\,n} } \right)\left( {x_{\,1} + x_{\,2} + \cdots + x_{\,n} } \right) = \cr & = x_{\,1} ^{\,2} + x_{\,1} ^{\,1} x_{\,2} ^{\,1} + x_{\,2} ^{\,1} x_{\,1} ^{\,1} + x_{\,2} ^{\,2} + \cdots = \cr & = \sum\limits_{\left\{ {\matrix{ {0\, \le \,j_{\,k} \left( { \le \,2} \right)} \cr {j_{\,1} + \,j_{\,2} + \, \cdots + \,j_{\,n} \, = \,2} \cr } } \right.\;} {\left( \matrix{ 2 \cr j_{\,1} ,\,j_{\,2} ,\, \cdots ,\,j_{\,n} \cr} \right)\;x_{\,1} ^{j_{\,1} } \;x_{\,2} ^{j_{\,2} } \; \cdots \;x_{\,n} ^{j_{\,n} } } \cr} $$ we can see that it counts either $x_1x_2$ and $x_2x_1$, i.e. order is taken into account
Here, each item can appear from $0$ to $2$ times.
You are instead looking for $$ \eqalign{ & \left( {x_{\,1} + x_{\,2} + \cdots + x_{\,n} } \right)^{\,r} \quad \left| {\;rep.\,x_{\,k} \le m_{\,k} } \right.\quad = \cr & = \sum\limits_{\left\{ {\matrix{ {0\, \le \,j_{\,k} \le \,m_{\,k} } \cr {j_{\,1} + \,j_{\,2} + \, \cdots + \,j_{\,n} \, = \,r} \cr } } \right.\;} {\left( \matrix{ r \cr j_{\,1} ,\,j_{\,2} ,\, \cdots ,\,j_{\,n} \cr} \right)\;x_{\,1} ^{j_{\,1} } \;x_{\,2} ^{j_{\,2} } \; \cdots \;x_{\,n} ^{j_{\,n} } } \cr} $$ where each index is limited to a given max repetition $m_k$., and thus for the corresponding number $$ \bbox[lightyellow] { N(r,n,{\bf m}) = \sum\limits_{\left\{ {\matrix{ {0\, \le \,j_{\,k} \le \,m_{\,k} } \cr {j_{\,1} + \,j_{\,2} + \, \cdots + \,j_{\,n} \, = \,r} \cr } } \right.\;} {\left( \matrix{ r \cr j_{\,1} ,\,j_{\,2} ,\, \cdots ,\,j_{\,n} \cr} \right)} } \tag{1}$$
The multinomial in fact, counts the number of permutations of $j_1$ objects of type 1 and $j_2$ objects of type 2 and etc.
In standard combinatorics jargon we are dealing with the number of
Identity (1) can be recasted in various ways, which will result more or less appealing depending on the characteristics of the vector $\bf m$.
Let's note first of all, that wlog $\bf m$ can be permuted , so arranged in (e.g.) non decreasing order.
Let's examine some particular cases.
a) $m_k=1 \quad \to$ words with different characters
Calling $\bf u$ the vector with all components at 1, $$ \begin{array}{l} N(r,n,{\bf u}) = \sum\limits_{\left\{ {\begin{array}{*{20}c} {0\, \le \,j_{\,k} \le \,1} \\ {j_{\,1} + \,j_{\,2} + \, \cdots + \,j_{\,n} \, = \,r} \\ \end{array}} \right.\;} {\left( \begin{array}{c} r \\ j_{\,1} ,\,j_{\,2} ,\, \cdots ,\,j_{\,n} \\ \end{array} \right)} = \\ = \left( \begin{array}{c} n \\ r \\ \end{array} \right)\sum\limits_{\left\{ {\begin{array}{*{20}c} {j_{\,1} = j_{\,2} = \cdots = j_{\,r} = \,1} \\ {j_{\,r + 1} = j_{\,r + 2} = \cdots = j_{\,n} = \,0} \\ {j_{\,1} + \,j_{\,2} + \, \cdots + \,j_{\,r} \, = \,r} \\ \end{array}} \right.\;} {\left( \begin{array}{c} r \\ j_{\,1} ,\,j_{\,2} ,\, \cdots ,\,j_{\,n} \\ \end{array} \right)} = \\ = \left( \begin{array}{c} n \\ r \\ \end{array} \right)\frac{{r!}}{{1! \cdots 1!0! \cdots 0!}} = n^{\,\underline {\,r\,} } \\ \end{array} $$ which is obvious : $n^{\,\underline {\,r\,} } $ denotes the Falling Factorial.
b) $r \le m_k \quad \to$ general words
$$ N(r,\,n,\,r\,{\bf u} \le {\bf m}) = \sum\limits_{\left\{ {\begin{array}{*{20}c} {0\, \le \,j_{\,k} \left( { \le \,r} \right)} \\ {j_{\,1} + \,j_{\,2} + \, \cdots + \,j_{\,n} \, = \,r} \\ \end{array}} \right.\;} {\left( \begin{array}{c} r \\ j_{\,1} ,\,j_{\,2} ,\, \cdots ,\,j_{\,n} \\ \end{array} \right)} = n^{\,r} $$ which is obvious as well.
Therefore in general we will have $$ n^{\,\underline {\,r\,} } \le N(r,\,n,\,{\bf m}) \le n^{\,r} $$
c) composition of words
Let's split the alphabet into two, one with $q$ characters and the other with $n-q$ characters.
We divide the vector $\bf m$ in two, accordingly. We may well put at 0 the max repetition of the characters not included. A word of $r$ characters may be formed by $s$ characters of the first alphabete and $r-s$ of the second one, with $0 \le s \le r$.
We may consider the words from the total alphabet as made by words from the first interspersed with words from the second.
The $s$ characters are dispersed into the $r$ places, maintaining their order in $\binom{r}{s}$ ways.
We obtain in fact the interesting relation
$$ \bbox[lightyellow] { \begin{array}{l} N(r,\,n,\,{\bf m}_{\,q} \oplus {\bf m}_{\,n - q} ) = \sum\limits_{\left\{ {\begin{array}{*{20}c} {0\, \le \,j_{\,k} \le \,m_{\,k} \;\left| {\;1\, \le \,k\, \le \,n} \right.} \\ {j_{\,1} + \,j_{\,2} + \, \cdots + \,j_{\,n} \, = \,r} \\ \end{array}} \right.\;} { \left( \begin{array}{c} r \\ j_{\,1} ,\,j_{\,2} ,\, \cdots ,\,j_{\,n} \\ \end{array} \right)} = \\ = \sum\limits_s {\sum\limits_{\left\{ {\begin{array}{*{20}c} {0\, \le \,j_{\,k} \le \,m_{\,k} \;\left| {\;1\, \le \,k\, \le \,q} \right.} \\ {j_{\,1} + \,j_{\,2} + \, \cdots + \,j_{\,q} \, = \,s} \\ {0\, \le \,j_{\,k} \le \,m_{\,k} \;\left| {\;q + 1\, \le \,k\, \le \,n} \right.} \\ {j_{\,q + 1} + \,j_{\,q + 2} + \, \cdots + \,j_{\,n} \, = \,r - s} \\ \end{array}} \right.\;} {\frac{{r!}}{{s!\left( {r - s} \right)!}}\frac{{s!}}{{j_{\,1} !\,\, \cdots j_{\,q} !}}\frac{{\left( {r - s} \right)!}}{{j_{\,q + 1} !\,\, \cdots j_{\,n} !}}} } = \\ = \sum\limits_s {\left( \begin{array}{c} r \\ s \\ \end{array} \right) \sum\limits_{\left\{ {\begin{array}{*{20}c} {0\, \le \,j_{\,k} \le \,m_{\,k} \;\left| {\;1\, \le \,k\, \le \,q} \right.} \\ {j_{\,1} + \,j_{\,2} + \, \cdots + \,j_{\,q} \, = \,s} \\ \end{array}} \right.\;} {\frac{{s!}}{{j_{\,1} !\,\, \cdots j_{\,q} !}}} } \;\sum\limits_{\left\{ {\begin{array}{*{20}c} {0\, \le \,j_{\,k} \le \,m_{\,k} \;\left| {\;q + 1\, \le \,k\, \le \,n} \right.} \\ {j_{\,q + 1} + \,j_{\,q + 2} + \, \cdots + \,j_{\,n} \, = \,r - s} \\ \end{array}} \right.\;} {\frac{{\left( {r - s} \right)!}}{{j_{\,q + 1} !\,\, \cdots j_{\,n} !}}} = \\ = \sum\limits_{0\, \le \,s\left( { \le \,r} \right)} {\left( \begin{array}{c} r \\ s \\ \end{array} \right)N(s,\,q,\,{\bf m}_{\,q} )N(r - s,\,n - q,\,{\bf m}_{\,n - q} )} =\\ = \sum\limits_{0\, \le \,s\left( { \le \,r} \right)} {\left( \begin{array}{c} r \\ s \\ \end{array} \right)N(s,\,n,\,{\bf m}_{\,q} )N(r - s,\,n,\,{\bf m}_{\,n - q} )} =\\ \end{array} } \tag{2}$$ where the last two lines comes from understanding, equivalently:
- the vectors ${\bf m}_{\,q}$ and ${\bf m}_{\,n-q}$ as two vectors with the dimensions indicated
and then $\oplus$ meaning "join";
- ${\bf m}_{\,q}$ and ${\bf m}_{\,n-q}$ as vectors of dimension $n$ with complementary null components
and then $\oplus$ meaning effectively "plus".
That says that $N$ is given by the binomial convolution of its parts, same as it is for its two limit expressions $$ n^{\,r} = \sum\limits_{0\, \le \,s} {\binom{r}{s} q^{\,s} \left( {n - q} \right)^{\,r - s} } \quad n^{\,\underline {\,r\,} } = \sum\limits_{0\, \le \,s} {\binom{r}{s}q^{\,\underline {\,s\,} } \left( {n - q} \right)^{\,\underline {\,r - s\,} } } $$