In how many ways can (1,2,3,4) be arranged so that at least one of the numbers is in the correct position?

Printable View

- February 26th 2011, 08:27 PMalexmahoneNumber of combinations
In how many ways can (1,2,3,4) be arranged so that at least one of the numbers is in the correct position?

- February 26th 2011, 08:48 PMragnar
Presumably, one of the numbers being in the correct position means 1 is first or 2 is second, so on. So there are four ways this could be. In each of them, there are 3! ways to rearrange the remaining digits. The total number of possibilities is the sum of the number of possibilities in each of the four cases.

- February 26th 2011, 08:53 PMalexmahone
- February 26th 2011, 09:07 PMragnar
Oh crappers, in each of the four we get duplicate situations.

So a new approach. The total possibilities without the constraint is 4!. The total number of ways where*all*the numbers are out of their respective place are 3*2*1, and these are precisely the scenarios we wish to exclude, so the answer is 4! - 3! = (4-1)3! = 18. I think this is right. - February 26th 2011, 09:17 PMalexmahone
Actually, the answer is 15:

(1, 2, 3 ,4), (1, 2, 4, 3), (1, 3, 2, 4), (1, 3, 4 ,2), (1, 4, 3, 2)

(1, 4, 2, 3), (3, 2, 1, 4), (3, 2, 4, 1), (4, 2, 3, 1), (4, 2, 1, 3),

(2, 1, 3, 4), (2, 4, 3, 1), (4, 1, 3, 2), (3, 1, 2, 4), (2, 3, 1, 4).

However, I am looking for a combinatorial way of solving this problem. - February 26th 2011, 10:40 PMragnar
I should probably shut up, but I have an answer, so maybe someone can verify me. It comes out with 15, but it's not the most combinatoric.

How many ways can all four be in the correct position? 1

How many ways can exactly three be? 0

How many ways can exactly two be? 6

(Argument: 1,2,_,_ has only one possibility. The number of such situations is like number of distinguishable permutations, where places filled in are not distinguishable and places not filled in are indistinguishable, so the total number is 4!/2!2! = 6.)

How many ways can exactly 1 be? 8

(Argument: 1,_,_,_ has two possibilities. The second position must be filled in with 3 or 4, and thereafter the remaining choices are fixed. There are 4 such situations, thus 2*4 = 8.)

1+0+6+8 = 15

I doubt a more combinatoric argument can be given, but my gut has obviously been wrong a lot tonight. - February 28th 2011, 02:11 PMawkward
You may find the following web page informative:

Derangements and the Inclusion-Exclusion Principle