Consider generating a 4-length code using only 3 digits. The possible number of permutations is 3⁴=81. However what if all 3 digits had to be used. How many permutations exist? In other words only one duplication of a digit is allowed, but it could be any of the digits.

 

Drawing a tree I can see some sort of pattern for n=3 r=4 and n=4 r=5 but I can't get it to gel and extrapolate to n=3 r=5 where two duplications or a triple is allowed and so on.

 

Is there a generalised formula that allows this to be calculated?

 

TIA

 

Update - to put it another way if n is the number of elements and r is the number to be selected then if I write the permutation as P(n r) then how to calculate P(3 4)? Further I know that P(4 4) =24 and that P(3 4) is 36, but P(2 4) is 14 and of course P(1 4) is 1. Lowering n then P(3 3) is 6, but P(2 3) is 8. So beyond how to calculate P(n-1 n) can it be shown that P(n-1 n) > P(n-2 n) for all cases of n?

Edited July 17, 201213 yr by FlipC

Could you not think of it in different terms. For example with 5 places to be filled and three digits to be used the number of codewords with two digits used twice and one used once looks remarkably similar to the chances of getting two pair in a poker hand (with a very shortened deck) - and that is easy to calculate.

So pretend I have a 'pack' of 112233 and calculate the odds of a single pair in a hand of 4 or two pairs or a triple in a hand of 5. Except isn't that a combination rather than a permutation? Order is important here 1123 is different to 3211