Fixed elements in a permutation.

1.6k Views Asked by At

Let, S = {A, B, C, D}. How many 3-elements' permutations can be formed from S were B and C both are always present.

My attempted solution:

$^4P_3 = \frac{4!}{(4-3)!} = 4! = 24$

Since, $2$ elements B and C are fixed, the result is, $\frac{24}{2!} = 12$.


Is this solution correct?

If not why?

1

There are 1 best solutions below

0
On BEST ANSWER

The final numeral result is correct, but I am not sure yet if it is simply because of a fluke. The (presumed) logic (since you didn't explain where the formula you used comes from) appears incorrect. I much prefer avoiding division by symmetry arguments (what I may have described as shepherd's principle to you or someone else before over the past few days) whenever possible as it can be ambiguous why we are deciding to divide and requires extra steps to verify that the outcomes are infact counted the same number of times each extra. Instead, we can approach directly via rule of product without any appeal to any other counting principles.

Step 1: Pick the location of the $B$: $3$ options

Step 2: Pick the location of the $C$: $2$ remaining options

Step 3: Pick the letter which occupies the final remaining position: $2$ remaining options

This gives $3\cdot 2\cdot 2=12$ total results.


As a test to see if your proposed formula is correct, it appears as though you intend that for $n$ letters and choosing $k$ of them such that $r$ are always present that the result would be $\dfrac{~^nP_k}{r!}$

The correct generalized formula, using the method I described above would come out to be $~^kP_r\cdot ~^{(n-r)}P_{(k-r)}$

This follows the same steps as above: Pick the location used by the "smallest" required letter. Pick the location used by the second "smallest" required letter.... Pick the location used by the final required letter. Pick the remaining letter to be used in the left-most unused space. Pick the remaining letter to be used in the left-most remaining unused space..... Pick the remaining letter to be used in the final remaining space.

By plugging in some test values, these are indeed different expressions. For example, it appears as though your proposed formula would give $\frac{6\cdot 5\cdot 4}{2}=60$ arrangements where we have $6$ letters, $\{A,B,C,D,E,F\}$ that we want to take three of them but $B$ and $C$ both must be used, whereas my formula comes to $3\cdot 2\cdot 4=24$ arrangements.