# Finding $n$ permutations $r$ with repetitions

I have given $n$ items and I have to find ${}^nP_r$ and $\sum_{r=0}^n{}^nP_r$ with repetitions allowed. Is there any closed formula for this?

For $n=3$ and $r=1$, possible permutations are:
$\{1\},\{2\},\{3\}$
Total: 3

For $n=3$ and $r=2$, possible permutations are:
$\{1,1\},\{2,2\},\{3,3\},\{1,2\},\{2,1\},\{1,3\},\{3,1\},\{2,3\},\{3,2\}$
Total: 9

For $n=3$ and $r=3$, possible permutations are:
$\{1,1,1\},\{2,2,2\},\{3,3,3\},$
$\{1,1,2\},\{1,2,1\},\{2,1,1\},$
$\{1,2,2\},\{2,1,2\},\{2,2,1\},$
$\{1,1,3\},\{1,3,1\},\{3,1,1\},$
$\{1,3,3\},\{3,1,3\},\{3,3,1\},$
$\{2,2,3\},\{2,3,2\},\{3,2,2\},$
$\{2,3,3\},\{3,2,3\},\{3,3,2\}$,
$\{1,2,3\},\{1,3,2\}$,
$\{2,1,3\},\{2,3,1\}$,
$\{3,1,2\},\{3,2,1\}$,
Total: 27

Can we come up with any closed formula for individual ${}^nP_r$ with repetitions and also for their sum i.e. here $3+9+27=39$

I understand that I cannot call this exactly the permutation, since ${}^3P_3$ is strictly $6$, while above its $27$, since I allow repetitions, but then whatever it is, how do I get the count?

Note that permutations with repetition is usually the well known case corresponding to $\frac{n!}{n_1!n_2!...n_i!}$, which is not what I am asking here. Is what am asking also some well know case, and I am stupidly not able to guess it? My primary guess is that, there cannot be any closed formula. Is it right?

• What exactly is the condition you're looking for? I notice that the permutation $1,2,3$ is excluded - is this intentional? – platty Aug 20 '17 at 15:31
• In fact, it looks like you left out all the permutations of $1,2,3$ - is this intentional? – platty Aug 20 '17 at 15:41
• Nope, I missed it. Sorry. – anir Aug 20 '17 at 15:43
• I dont know it feels fuzzy. Is it just ${}^nP_r \text{with repetition} = n^r$?. Feels like so. Let me read question and answers again. – anir Aug 20 '17 at 15:47
• Your formula is not for permutations with replacements. It's for combinations with replacements. Are you actually looking for the expression for multinominal coefficients? – Vim Aug 20 '17 at 15:48

If you just want unrestricted strings consisting of $r$ letters, chosen with replacement from $n$, you can just use the multiplication rule to get $n^r$; there's $n$ choices for the first one, $n$ choices for the second, etc.

Extending this, we can use this to find the number of strings with length up to $r$ by summing the intermediate results: $$1+n+n^2+\dots +n^r$$ This is the sum of a geometric series, which means we can apply the formula to get $\frac{n^{r+1}-1}{n-1}$.

If you mean "permutations with replacements" then the answer is just $n^r$. But this doesn't match your result for $n=r=3$ which should be $27$? If you actually mean combinations with replacements, then see the below hint.

Hint: you are basically putting $r$ identical balls into $n$ different jars, or equivalently, finding the number of non-negative integer solutions to $$x_1+\cdots+x_n=r$$ To solve this, first let $y_i:=x_i+1$ (which are bijections) then try finding the number of positive integer solutions to the equation $$y_1+\cdots+y_n=r+n.$$ Try Stars & Bars technique.

• I don't think this is correct - OP has order mattering in the listed examples. – platty Aug 20 '17 at 15:39
• @platty this is really confusing, because in this case the third result should be 27. Clearly there is some misphrasing in the question. – Vim Aug 20 '17 at 15:41
Note that in your last paragraph, you say that $\frac{n!}{n_1!n_2! \dots n_i!}$ is the formula for permutations with repetition, but perhaps a better way to word it would be that this is a generalized formula for partitioning a set of $n$ objects into $i$ cells with each "cell" being distinguishable, but elements within their respective cells are not.
As noted before, permutations with repetition allowed can be represented with $n^r$, which @platty already explained. This is the formula you would use to solve the second example I gave, as well as what you seem to be looking for in your example.
the number of words, from alphabet $\{1,\cdots,n\}$, of length $r$ and max repetition $r$,
i.e. simply the number of words, from alphabet $\{1,\cdots,n\}$, of length $r$
which are $n^r$.