# Formula for r-Permutations of a Multiset

Suppose we have a multiset $$M$$, which contains $$k$$ distinct elements. Each element $$x_i$$ has multiplicity $$n_i$$ for each $$i\in\Bbb{N}$$ such that $$0\le i. $$n$$, the number of elements in $$M$$ including repetition, is defined as $$n=\underset{i=0}{\overset{k-1}{\sum}}n_i$$.

How would I go about calculating the number of permutations of length $$r$$ of $$M$$, where each element $$x_i$$ is repeated $$t_i$$ times for $$0\le t_i\le n_i$$? (The specific values of each $$t_i$$ may vary for each permutation, so long as they all add up to $$r$$.) I have found this question answered in several places with the additional constraint that $$t_i>0$$ (which gives an answer of $$\frac{n!}{\underset{i=0}{\overset{k-1}{\prod}}t_i!}$$), but never in this general case.

• Are you counting lists of length $r$, where each entry is equal to $x_i$ for some $0\le i<k$, and $x_i$ appears $t_i$ times in the list? If so, the answer should be $r!/(\prod_{i=0}^{k-1}t_i!)$, and this should work even without the assumption $t_i>0$. – Mike Earnest Feb 8 at 19:20
• Or are you not counting permutations with fixed $t_i$, but instead counting permutations where the $t_i$ can be anything except $n_i$? In other words, permutations where no element is completely used? – Mike Earnest Feb 8 at 19:34
• @Mike $t_i$ is not fixed but may vary for each list (such that all of them sum to r). Also, I meant to say that $t_i\le n_i$, not that $t_i<n_i$. I have updated the question accordingly. – Evan Bailey Feb 11 at 5:18

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$$).
• Thank you for this answer. It was exactly what I was looking for. Also, I will correct the formula in my original question to use $t_i$ in the denominator instead of $n_i$. – Evan Bailey Feb 11 at 19:49
• Also, I would assume (although I am no expert when it comes to generating functions) that in this context, it would be equivalent to define $E_n(x)$ as $\frac{x^{n+1}-1}{x^2-x}$. I am just wondering if it would really be simpler in this context to do so. – Evan Bailey Feb 11 at 19:56
• @EvanBailey No, that would not work. It is important you use exponential generating functions, meaning the $i!$ in $\frac{x^i}{i!}$ is important. This ensures that order matters, because you are counting permutations where order matters. You can take a look at the exponential generating function chapter of generatingfunctionology for some more details. – Mike Earnest Feb 11 at 20:00
• So would the generating function for the number of $r$-combinations be the same as that for the number of $r$-permutations sans the $r!$? – Evan Bailey Feb 19 at 20:23