# Number of permutations with repeated objects.

I will use letters as objects. In general, suppose we have objects $\underbrace{X_1, \dotsc, X_1}_{n_1}, \underbrace{X_2, \dotsc, X_2}_{n_2}, \dotsc,\dotsc, \dotsc, \underbrace{X_k, \dotsc, X_k}_{n_k}$. Then what is the number of ways we can choose and order $N$ objects $0 \leq N \leq n_1 +\dotsb + n_k$, i.e. the number of permutations? If $n_1 = \dotsb = n_k = 1$, then of course this is just a standard permutation problem. I am just curious if there is a formula for it.

Note: I initially asked about combinations, which was pointed out to be a duplicate of the question here. I have deleted the original post to ask this question, instead.

• does a recurrence help you? – ILikeMath Aug 9 '13 at 19:51
• Sorry for the confusion, Pratyush. I meant you should link to the question of which your original was a duplicate. A link to a deleted question won't stay active for long. – Cameron Buie Aug 9 '13 at 19:56
• @DiegoHuerfano Of course a explicit formula is better but I would like to see your recurrence solution. – Pratyush Sarkar Aug 9 '13 at 20:02
• "If $n_1 = \cdots n_k=1$, then of course this is just a standard permutation problem" ... only if $k=N$, no? – leonbloy Aug 9 '13 at 20:16
• @leonbloy If $n_1 = \dotsb = n_k = 1$, then the total number of objects is $n_1 + \dotsb + n_k = 1 + \dotsb + 1 = k$ and I am choosing and ordering $N$ objects so the answer is ${}^kP_N = \frac{k!}{(k - N)!}$. For the even more special case $k = N$, its ${}^kP_k = k!$. – Pratyush Sarkar Aug 9 '13 at 20:51

Consider the recurrence where $n$ is the number of elements to choose, $k$ is the class that we are considering and $f(n,k)$ means the number of ways of take $n$ elements with elements of the classes $1,2,...,k$

$$f(n,k)=\sum\limits_{i=0}^{min(n,n_{k})}{ \frac{1}{i!} f(n-i,k-1)}, \space\space\space\space k>0$$ $$f(0,0)=1$$ $$f(n,0)=0,\space\space\space\space n>0.$$

We know that if we have $n$ letters and there are $k$ subclasses where each class have $n_j$ letters $L_j$ with $n_1+...+n_k=n$, then the number of all possible permutations is

$$\frac{n!}{n_1!...n_k!} \space\space\space\space(1)$$

because each $n_j$ letters $L_j$ are indistinguishable.

Now there are $n_1+...+n_k$ letters in total and first we want to choose $n$ of them without permute them, then for each class $k$ we will take $i=0$, or $i=1$,..., or $i=n_k$. So we will add up each election which yields to $f(n,k)=\sum\limits_{i=0}^{min(n,n_{k})}{ f(n-i,k-1)}$. But we want to choose them permute them, so will use the formula $(1)$ and we obtain the above recurrence. Therefore the answer will be

$$N!f(N,k).$$

• I don't quite understand what is $f(n,k)=\sum\limits_{i=0}^{min(n,n_{k})}{ f(n-i,k-1)}$ and how you got it in the last paragraph. – Pratyush Sarkar Aug 9 '13 at 21:42
• I think I get that equation now. But now I am not sure about the upper limit $min(n,n_{k})$ of that sum. – Pratyush Sarkar Aug 9 '13 at 21:51
• If we are in the class $k$, we can choose $0$ elements of them, or $1$, .... So we will add up those "elections". Whenever we choose an element of the class $k$, we substract to the total elements for choose $n$ so we have $f(n,k)=f(n-0,k-1)+f(n-1,k-1)+...$. The $k-1$, if we already choose a number of elements in class $k$, we need to choose elements in the next stage ($k-1$ class). The $min(n,n_k)$ is to fix a limit, beacuse in the stage $k$ we can not choose a number of elements more than $n_k$, but we can not choose a number of elements more than $n$ (the remain). – ILikeMath Aug 9 '13 at 21:54
• Thanks. I get it now. But now I don't understand the $\frac{1}{i!}$ factor hehe. I don't think it is needed because nothing is counted more than once. – Pratyush Sarkar Aug 9 '13 at 22:15
• I don't think so. If we quit $\frac{1}{i!}$ factor, then the answer $N!f(N,k)$ will count more than we need. So, if we put that factor, we are using the formula $(1)$ with $\frac{N!}{i_1!...i_k!}$. – ILikeMath Aug 9 '13 at 22:20

Let $m_i$ be the number of objects of type $i$ that were picked. Then $0\le m_i \le n_i$ and $\sum_{i=1}^k m_i = N$. For a given set $\{m_i\}$, there are $N!/\prod (m_i!)$ permutations. Hence the count is given by

$$\sum_{ m_1,m2 \cdots m_k } \frac{N!}{\prod m_i!}$$

Where the sum is restricted to $0\le m_i \le n_i$ and $\sum m_i=N$. That is:

$$N ! \sum_{m_1=0}^{\min(N,n_1)} \frac{1}{m_1!} \sum_{m_2=0}^{\min(N-m_1,n_2)} \frac{1}{m_2!} \cdots \sum_{m_{k-1}=0}^{\min(N-m_1-m_2-\cdots,n_{k-1})} \frac{1}{m_{k-1}!} \frac{[N-(m_1+m_2 + \cdots +m_{k-1})\le n_k]}{(N-(m_1+m_2 + \cdots +m_{k-1}))!}$$

• But for each $m_i$ elements, we can choose them of $\binom{n_i}{m_i}$ ways!. – ILikeMath Aug 9 '13 at 21:10
• mmm, no, I don't read the problem in that way, I consider the elements inside each set as undistinguishable. Say, if $n_1=5$ and I choose $m_1=3$, there are not ${5 \choose 3}$ ways of picking those 3, there is only one way. $n_1=5$ just gives me a bound on $m_1$. Of course, this is a matter of interpretation. – leonbloy Aug 9 '13 at 21:14
• leonbloy is right. What I intended was for any $i$, $X_i, \dots, X_i$ are identical. – Pratyush Sarkar Aug 9 '13 at 21:16
• @leonbloy If I were to find the solution in a straight forward way, your answer is the same thing I would do also but the problem is $\sum_{ m_1,m2 \cdots m_k } \frac{N!}{\prod m_i!}$ is very hard to calculate. – Pratyush Sarkar Aug 9 '13 at 21:19
• Yes, they are identical, but I think that, for example, if we have $2$ undistinguishable objects we can choose one of them of $2$ ways no of $1$ way. – ILikeMath Aug 9 '13 at 21:19