2
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ Please read this tutorial on how to typeset mathematics on this site. $\endgroup$ – N. F. Taussig Jun 11 at 19:11
1
$\begingroup$

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

words of length $r$, from alphabet $\{1,2, \cdots , n \}$, with allowed repetitions of each character up to $m_k \; |\, 1 \le k \le n$.

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

So you are right, a recursive approach is well viable.

$\endgroup$
  • $\begingroup$ Thanks for the answer. But I am not able to follow it completely, but I see where you are going with vector m and the expansion. I was looking at more of a readily available formula which I think doesn't exist for the case r < T. It has to be calculated recursively based on the sequence with r = r - 1. $\endgroup$ – SomeDude Jun 12 at 14:18
  • $\begingroup$ @SomeDude Uhm, if you think to approach the problem by recursion, then in general (i.e. excluding simplest cases) you will get into tangles, because the recursion shall be split piecewise depending on the relation of $r$ with the various $m_k$. So, in general I do not see a better way than the sum of multinomials I've indicated. However I will try and expand my answer to be more clear and helpful. $\endgroup$ – G Cab Jun 12 at 16:25
  • $\begingroup$ @SomeDude: beg your pardon ! contrary to my doubts, there is a nice and very interesting recursive relation underneath ! fascinating subject ... $\endgroup$ – G Cab Jun 13 at 11:37
  • $\begingroup$ thanks a lot for your effort. I have to admit that I am not a mathematician and it will take a while to actually go through your answer and try to understand it. Having involved in some other things at present it might take a while to do so. But thanks again for your answer. Upvoting it. $\endgroup$ – SomeDude Jun 13 at 20:53
  • $\begingroup$ @SomeDude: you are welcome, and thanks to you for posing such an interesting subject, which I find much appealing, specially due to the recursive relation. $\endgroup$ – G Cab Jun 13 at 21:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.