1
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

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$

$\endgroup$

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.