# Number of permutations with repetition

I have to form a permutation of N elements with each element less than or equal to M.

I need to count the number of unique permutations possible with 2 of the elements fixed as 2 and 3.

Note that each number can be used multiple times and 2 and 3 can occur anywhere in the permutation.

I came up with the formula :

N*(N-1)* pow(M , N-2 ).

N places for 3 to occur , hence there are N-1 places for 2 to occur followed by M choices for the remaining N-2 places. However it is resulting in over-counting.

for N=3 M=4 :

fix first place for 3 and second place for 2:

3 2 1

3 2 2

3 2 3

3 2 4

fix first place for 3 and third place for 2:

3 1 2

3 2 2

3 3 2

3 4 2

Already there is over-counting of the permutation 3 2 2 in my method.

How do I determine the total unique permutations?

I'm reading that the combination must include at least one 2 and at least one 3 somewhere in it.

Suppose you just consider one of required inclusions:

Constraint A: the combination must include at least one 2

How many of the total possibilities without Constraint A are removed by this constraint?

Total combinations $C_T = M^N$

with constraint $A$ only, $C_A = M^N - (M-1)^N$

for the other constraint:

Constraint B: the combination must include at least one 3

with constraint $B$ only, $C_B = M^N - (M-1)^N$

However with both constraint we need inclusion-exclusion to make sure we don't double-count excluded possibilities:

Both constraints: $C_{AB} = M^N - 2(M-1)^N + (M-2)^N$