0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ What exactly is the condition you're looking for? I notice that the permutation $1,2,3$ is excluded - is this intentional? $\endgroup$ – platty Aug 20 '17 at 15:31
  • $\begingroup$ In fact, it looks like you left out all the permutations of $1,2,3$ - is this intentional? $\endgroup$ – platty Aug 20 '17 at 15:41
  • $\begingroup$ Nope, I missed it. Sorry. $\endgroup$ – anir Aug 20 '17 at 15:43
  • $\begingroup$ 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. $\endgroup$ – anir Aug 20 '17 at 15:47
  • $\begingroup$ Your formula is not for permutations with replacements. It's for combinations with replacements. Are you actually looking for the expression for multinominal coefficients? $\endgroup$ – Vim Aug 20 '17 at 15:48
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Please dont delete answers since I have updated question. Update instead. Let me read all answers once. $\endgroup$ – anir Aug 20 '17 at 15:48
0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ I don't think this is correct - OP has order mattering in the listed examples. $\endgroup$ – platty Aug 20 '17 at 15:39
  • $\begingroup$ @platty this is really confusing, because in this case the third result should be 27. Clearly there is some misphrasing in the question. $\endgroup$ – Vim Aug 20 '17 at 15:41
  • $\begingroup$ Please dont delete answers since I have updated question. Update instead. Let me read all answers once. $\endgroup$ – anir Aug 20 '17 at 15:48
0
$\begingroup$

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.

This could be where some confusion is coming from, as the term repetition can be interpreted in a few different ways depending on the problem. For example, you can use this formula to find the number of ways to arrange the letters of the word TOOTH (as noted in the link you provided, we have some letters repeating), but this formula is not the one you would use to, say, find the number of 4 letter passwords using the letters A through Z with repetition allowed.

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.

$\endgroup$
0
$\begingroup$

Actually, from the examples you give, we are speaking of
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$.

$\endgroup$
  • $\begingroup$ Please dont delete answers since I have updated question. Update instead. Let me read all answers once. $\endgroup$ – anir Aug 20 '17 at 15:48

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.