Fooling around

How many ways can you rearrange the letters of FOOLING so that no letter winds up in the same spot?

Clarification: The "O's" are indistinguishable, so the resulting set of letters can't have an O in the second or third spot.


For more Permutations quizzes.


The answer is 640.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

4 solutions

Geoff Pilling
May 10, 2016

First off, without loss of generality, we can pick two places for the O's that weren't previously occupied by O's in the orignial word, FOOLING. Since there are 5 such spots, and 2 indistinguishable O's to put them in, there are ( 5 2 ) \binom{5}{2} ways to do this.

Next, we pick 2 2 letters to go in the second and third spots (originally containing O's) and 3 3 to go in the "non-original-O" spots in such a way that none of these letters is in its original place. Now, there are ! 5 + 2 ! 4 + ! 3 !5 + 2\cdot!4 + !3 ways to do this, where ! n = n ! ( 1 1 / 1 ! + 1 / 2 ! 1 / 3 ! + . . . . ) !n = n!(1 - 1/1! + 1/2! - 1/3! + ....) is the derangement equation or the number of ways you can arrange n n distinguishable objects so that no object ends up in the same spot. (In this case the "objects" are the letters in FOOLING) I will leave the full derivation of this equation as an exercise to the reader! :)

So, the total number of ways is ( 5 2 ) ( ! 5 + 2 ! 4 + ! 3 ) = 10 ( 44 + 2 9 + 2 ) = 640 \binom{5}{2}(!5 + 2\cdot!4 + !3) = 10(44+2\cdot9+2) = \boxed{640}

For a word with n i n_i letters of X i X_i , then by principle of inclusion and exclusion , the number of derangments are

0 e x P n i ( x ) d x \left| \int_0^\infty e^{-x} \prod P_{n_i} (x) \, dx \right|

where P n P_n are the Laguerre polynomials .

In this particular case, we have P 1 = x + 1 , P 2 = 1 2 ( x 2 4 x + 2 ) P_1 = -x +1, P_2 = \frac{1}{2} (x^2 - 4x+2) and so we obtain

0 e x ( x + 1 ) 5 × 1 2 ( x 2 4 x + 2 ) d x = 640 \left| \int_0^\infty e^{-x} (-x+1)^5 \times \frac{1}{2} ( x^2 - 4x + 2) \, dx \right| = 640

Calvin Lin Staff - 5 years, 1 month ago

Log in to reply

Whoa, nice solution, Calvin! So, lets see, can we apply this to a word like GOOFING that has 2 O's and 2 G's?

Geoff Pilling - 5 years, 1 month ago

@Calvin Lin I just noticed that P n ( x ) P_n(x) doesn't appear in the initial equation. I assume P n P_n is missing just before the ( x ) (x) ? And later, you refer to them as L n L_n . I guess that should be P n P_n ? Or perhaps they should all be L n L_n ?

Geoff Pilling - 5 years, 1 month ago

Log in to reply

Thanks. Fixed.

Calvin Lin Staff - 5 years, 1 month ago

Yours is a wonderful solution, do comment on mine @Geoff Pilling

Mayank Singh - 5 years ago
Prakhar Bindal
May 11, 2016

I did it this way

Firstly i selected two wrong places for placing two identical O's that can be done is 5C2 = 10 Ways

Now

We Are Left with 5 letters and 5 places

Illustratively take them as F,L,I,N,G and places which we have selected for two O's be 1 and 4 .

So the places we are left with are 2,3,5,6,7 For F,L,I,N,G (Which have there numbers as 1,4,5,6,7)

As we can see for every valid Selection of places for two O's we will be left with exactly three letters whose place numbers are still there like here I,N,G have there rank as 5,6,7 and there place ranks are also there 5,6,7

We Make three Cases

Case-1 When I,N,G Go into 5,6,7 and F,L Go into 1,4

Number of ways would Be = D3 * 2 (D3 Is dearrangement of 3 objects) = 4

Case-2 When When I,N,G Go into exactly two of 5,6,7

Number of ways would be = (3C2) * (2C1) 3 2 = 36

Case-3 When I,N,G Go into exactly one of 5,6,7

Number of ways would be = (3C1) (2C1) 2*2 = 24

So total ways of arrangement of 5 letters = 24+36+4 = 64

Hence total arrangements = 64*5C2 = 640

Nice problem! :) . Keep posting more

Nice solution, Prakhar!

Geoff Pilling - 5 years, 1 month ago

Log in to reply

Thanks! :)

Prakhar Bindal - 5 years, 1 month ago

Its interesting how such a seemingly simple problem can have three very different, but equally correct, solutions! :)

Geoff Pilling - 5 years, 1 month ago

Log in to reply

Yeah thats why mathematics is my first love

Prakhar Bindal - 5 years, 1 month ago
Aryan Goyat
May 12, 2016

i took the two Os to initially O1 and O2 so total dearrangment is D7=1854 now let when O1 is at O2 is at 1/6 of the cases=309

O2 happens at O1=309 but we have included twice the cases in which O1 at O2 and O2 at O1 so 309*2-D5

so extra cases=574

so net rearrangment=1280

but since O1 and O2 are same so divide by 2

In my opinion, this is the clearest solution. @aryan goyat , if you polish your solution (by adding LaTeX and structure), I believe it will get more attention! :)

Christopher Boo - 5 years ago

Log in to reply

i would be very thankful to you

aryan goyat - 5 years ago

Sounds like you aren't the only one, Christopher... Aryan just got featured as one of the top solution writers... Nicely done, @aryan goyat ! :^)

Geoff Pilling - 5 years ago

Nice approach, Aryan!

Geoff Pilling - 5 years, 1 month ago

Log in to reply

Thanks! :)

aryan goyat - 5 years, 1 month ago

Yes. This solution is nice and clear and to the point! :)

Geoff Pilling - 5 years ago
Mayank Singh
May 21, 2016

Here's mine

First consider the two O s Os to be distinct, say O1 and O2.

Then the number of solutions are D(7).

Now we delete those cases where O1 has come to O2's place and O2 at that of O1

and there are D(5) such cases.

So we're left with D(7)-D(5).

Pay attention to the fact that since O1 and O2 are indistinguishable, we need to divide the left out cases by 2 ( for example when O1 is at first place and O2 is at last, there's exists an analogous case where O1 is at last place and O2 first)

There's still some problem, we have counted even those erraneous cases when O2 has come to O1's original place and O1 is taking other places. Since O1 and O2 are indistinguishable, they must not be counted.

So we finally delete D(6)

The final answer is D ( 7 ) D ( 5 ) 2 \frac{D(7)-D(5)}{2} - D ( 6 ) D(6)

Note D ( n ) D(n) means a derangement of n items

Oh, that's a nice interpretation to use PIE. Can we generalize that further?

Calvin Lin Staff - 5 years ago

Log in to reply

@Mayank Singh @Calvin Lin Yeah, I agree... Can we extend it to an N N letter word that has m m number of letters that are repeated repeated { a 1 , a 2 , . . . , a m } \{a_1,a_2,...,a_m\} times respectively?

Geoff Pilling - 5 years ago

Ah, very nice, Mayank! :)

Geoff Pilling - 5 years ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...