0

It's not difficult to find a formula to calculate the number of permutations given no repeats or any number of repeats. However, I am trying to find a way of calculating the number of permutations if a choice can only be made, say, twice.

For example, given the numbers 1-9, how many permutations of a five-number sequence are there, given that the numbers 1-9 may be repeated (but only once)?

Valid combinations include 12345, 15233 (two 3s), 89349 (two 9s), 10130 (two 1s, two 0s). Invalid combinations include 14333 and 10101.

freethebees
  • 103

1 Answers1

1

You may refer to the research paper: Haim Mendelson (1981), On permutations with limited repetition, Journal of combinatorial theory, Series A, vol. 30

The paper provides the following recursive equations, with $n$ the number of objects, $r$ the size of the permutation, and $s$ the number of possible repetitions for each object \begin{align} f(n,r+1,s)&=n f(n,r,s)-n\left(^r_s\right)f(n-1,r-s,s) \quad \textrm{ for } n=2,3,... ; r \ge s\\ f(n,r,s)&=n^r \quad \textrm{ for } n=1,2,3,\dots;r \le s\\ f(1,r,s)&=0 \quad \textrm{ for } r>s \end{align}

The paper gives the following explanation for the first equation:

"There are $f(n,r,s)$ ways to select the first $r$ elements without repeating any object more than $s$ times. Out of these, there are $\left(^r_s\right)f(n-1,r-s,s)$ r-permutations with a given object exaclty $s$ times. Thus, out of the $nf(n,r,s)$ possibilities attained by appending an r-permutation with limited repetition $s$ with an $(r+1)$st element, $n\left(^r_s\right)f(n-1,r-s,s)$ will violate the upper limit $s$."

The second equation is the case when the number of repetitions is larger than the size of the permutation (identical to unlimited repetitions).

borisd
  • 121