Formula for r-Permutations of a Multiset

Solution 1:

I do not think there is a nice formula, but there is a generating function solution.

Let $E_n(x)=\sum_{j=0}^n\frac{x^j}{j!}$ be the partial exponential series. The number of $r$-permutations is $$ r![x^r]\prod_{i=0}^{k-1} E_{n_i}(x) $$ where $[x^r]f(x)$ is the coefficient of $x^r$ in the polynomial $f(x)$.

On a side note, I disagree with the formula $n!/\prod n_i!$ for the number of $r$-permutations where each object appears at least once (each $t_i>0$). First, this does not involve $r$ at all. Second, in the case where the multiset is $\{A,A,B,B\}$ and $r=2$, the answer should be two, since the valid permutations are $AB$ and $BA$, but your formula gives $4!/(2!\cdot 2!)=6$. Instead, $n!/\prod n_i!$ gives the number of $n$-permutations of a multiset with $n$ elements total (all objects used completely, each $t_i=n_i$).