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.
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.
For a word with n i letters of X i , then by principle of inclusion and exclusion , the number of derangments are
∣ ∣ ∣ ∣ ∫ 0 ∞ e − x ∏ P n i ( x ) d x ∣ ∣ ∣ ∣
where P n are the Laguerre polynomials .
In this particular case, we have P 1 = − x + 1 , P 2 = 2 1 ( x 2 − 4 x + 2 ) and so we obtain
∣ ∣ ∣ ∣ ∫ 0 ∞ e − x ( − x + 1 ) 5 × 2 1 ( x 2 − 4 x + 2 ) d x ∣ ∣ ∣ ∣ = 6 4 0
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?
@Calvin Lin I just noticed that P n ( x ) doesn't appear in the initial equation. I assume P n is missing just before the ( x ) ? And later, you refer to them as L n . I guess that should be P n ? Or perhaps they should all be L n ?
Yours is a wonderful solution, do comment on mine @Geoff Pilling
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!
Its interesting how such a seemingly simple problem can have three very different, but equally correct, solutions! :)
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! :)
Log in to reply
i would be very thankful to you
Sounds like you aren't the only one, Christopher... Aryan just got featured as one of the top solution writers... Nicely done, @aryan goyat ! :^)
Nice approach, Aryan!
Yes. This solution is nice and clear and to the point! :)
Here's mine
First consider the two O s 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 2 D ( 7 ) − D ( 5 ) - D ( 6 )
Note D ( n ) means a derangement of n items
Oh, that's a nice interpretation to use PIE. Can we generalize that further?
Log in to reply
@Mayank Singh @Calvin Lin Yeah, I agree... Can we extend it to an N letter word that has m number of letters that are repeated repeated { a 1 , a 2 , . . . , a m } times respectively?
Ah, very nice, Mayank! :)
Problem Loading...
Note Loading...
Set Loading...
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 ( 2 5 ) ways to do this.
Next, we pick 2 letters to go in the second and third spots (originally containing O's) and 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 ways to do this, where ! n = n ! ( 1 − 1 / 1 ! + 1 / 2 ! − 1 / 3 ! + . . . . ) is the derangement equation or the number of ways you can arrange 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 ( 2 5 ) ( ! 5 + 2 ⋅ ! 4 + ! 3 ) = 1 0 ( 4 4 + 2 ⋅ 9 + 2 ) = 6 4 0