2
$\begingroup$

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<k$. $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.

$\endgroup$
  • 1
    $\begingroup$ 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$. $\endgroup$ – Mike Earnest Feb 8 at 19:20
  • $\begingroup$ 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? $\endgroup$ – Mike Earnest Feb 8 at 19:34
  • $\begingroup$ @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. $\endgroup$ – Evan Bailey Feb 11 at 5:18
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Evan Bailey Feb 11 at 19:49
  • $\begingroup$ 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. $\endgroup$ – Evan Bailey Feb 11 at 19:56
  • $\begingroup$ @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. $\endgroup$ – Mike Earnest Feb 11 at 20:00
  • $\begingroup$ Thank you. I will be sure to check it out. $\endgroup$ – Evan Bailey Feb 11 at 20:44
  • $\begingroup$ 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!$? $\endgroup$ – Evan Bailey Feb 19 at 20:23

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.