Possible combinations for word KEEPER by intuition

[physio]

Hello,

I am having trouble understanding the answer to the above question. The answer is 6!/3! and below is my working. I am having trouble arriving at the above answer and here is my approach.

The question is to find the permutations of KEEPER minus all the duplicates.

Therefore, to count the permutations intuitively, I follow the method below:
For the first position there are 6 possibilities i.e. K or E or E or P or E or R but we want to eliminate repeats thus all
cases obtained with the first, second and third E are the same and this boils down to one case. Examining that one case closely where the word starts with E we can weed out all the repeats by dividing by 3! since there are 3 positions to be filled by E and all possible permutations are 3!. Thus for that one case where the starting letter is E we have number of arrangements = 5!/3!. Similarly for the words starting with K, P and R we get 5!/3! by the same reasoning as (K or P or R and (6-1)! possibilities for the remaining letters of that word). Thus the total is 5!/3! (for E) + 5!/3! (for K) + 5!/3! (for P) + 5!/3! (for R). This is equal to 4.5!/3! which is incorrect according to the answer. What am I missing. Sorry for such a long post. Thanks in advance for your replies!

 

[aikismos]

Check out this link. It has a formula that shows the difference. (http://www.regentsprep.org/regents/math/algebra/apr2/LpermRep.htm)

EDIT: Okay, couldn't let it go at this...

Remember, that indistinguishable elements can be written to satisfy both the need to show they're the same as each other, and yet they are distinct from each other. To wit:

In the string "KEEPER", we can represent the E's like this: $\{ E_1, E_2, E_3 \}$, and no matter what the permutation of "KEEPER" is, they must occur in some order. So:

$"KE_{1}E_{2}PE_{3}R"$
$"KE_{1}E_{3}PE_{2}R"$
$"KE_{2}E_{1}PE_{3}R"$
$"KE_{2}E_{3}PE_{1}R"$
$"KE_{3}E_{1}PE_{2}R"$
$"KE_{3}E_{2}PE_{1}R"$

So essentially... we're dividing out redundancy, and that redundancy is itself permutational in nature.

 

[physio]

Hello aikismos,

I thank you for your reply! I wanted to know why is my method incorrect? Is my approach incorrect?? I haven't understood why the formula for permutations with repetitions is the way it is and I am trying to arrive at this formula by solving the above problem.

 

[physio]

Hello aikismos,

Does that mean these cases are redundant and should reduce to one case?

E₁, ...,...,...,...,...
E₂, ...,...,...,...,...
E₃, ...,...,...,...,...

In that case we would have the following cases:

K,...,...,...,...,...
.
.
.
E,...,...,...,...,...
.
.
.
P,...,...,...,...,...
.
.
.
R, ...,...,...,...,...
.
.
.
and hence my answer as 4.5!/3!. Please do let me know what am I missing?

 

[aikismos]

If someone else can't give a more detailed explanation, I'll see if I can't put together something after work.

 

[physio]

Hello aikismos,

I thank you for putting in the effort. Much appreciated!

 

[aikismos]

Hello aikismos,

I thank you for putting in the effort. Much appreciated!

Well, it's my idea of fun. :D

Before I do a more detailed write-up... with some extra examples... you might be able to get there first if you realize that it might be better to think of having not 4 partitions:

{ "K*", "E*", "P*", "R*"}

but 6 of them:

{"K*", "E1*", "E2*", "E3*", "P*", "R*"}.

That's why you're numerator comes out lower than the formula $\frac{n!}{e!}$.

 

[physio]

Hello aikismos,

Thank you for your reply :) The reason I have made 4 partitions is because E1=E2=E3=E. Won't the permutations be the same if you consider E1 as the first element or E2 as the first element or E3 as the first element and then the remaining elements. Will the set of words starting with E1 be equal to the set of words starting with E2 be equal to the set of words starting with E3 as E1=E2=E3?? I am stuck in this place otherwise I have arrived at the formula intuitively. Thanks!

 

[Vanadium 50]

I think you're making this too hard. KEEPER has 6 letters, including 3 E's. How many ways are there to permute the 6 letters? How many ways to permute the 3 E's? How much double-counting was done by treating the E's as distinct?

To solve another problem, how many ways are there to do the same to the word BEEKEEPER? It's 9!/5! = 3024.

Another - and slightly harder - way to think about it is I have 5 E's. I have a B - how many places are there to place it among the five E's? Six: BEEEEE, EBEEEE, EEBEEE, etc. Now I have a K - how many ways are there to place the K? Seven. Then eight for the P and nine for the R: 6 x 7x 8 x 9 = 3024.

 

[physio]

I believe I have understood now. Thanks for your reply Vanadium 50! If I use my method then the answer should be 3.5!/3! + 5!/2! (and not 4.5!/3!) which is equal to 6!/3! = 120. I was making a mistake while dividing the E1 block as now when you have E1 as the starting element then there are only 2 positions (i.e. E2, E3) to shuffle i.e. 2! and hence you divide by 2! when considering the repeat case. Thanks once again aikismos and Vanadium 50. I am needlessly complicating the matter :)

 

[aikismos]

Hello aikismos,

Thank you for your reply :) The reason I have made 4 partitions is because E1=E2=E3=E. Won't the permutations be the same if you consider E1 as the first element or E2 as the first element or E3 as the first element and then the remaining elements. Will the set of words starting with E1 be equal to the set of words starting with E2 be equal to the set of words starting with E3 as E1=E2=E3?? I am stuck in this place otherwise I have arrived at the formula intuitively. Thanks!

Vanadium is right in that you're thinking hard, but I see you're interested in clearing up your misconception. Since your answer didn't come to the correct answer, then obviously there's a flaw in your reasoning. I'll address that, but first, here's another way of looking at the situation.

"KEEPER" gives us 6 positions in the string and having the E's be interchangeable can help us to think of the situation in a simpler fashion.
If "K", "P", and "R" are distinct, we could create another way of representing the strings mathematically using an ordered triplet. Let's look at (K, P, R)
For instance, (1, 4, 6) is the same as the "KEEPER" because K maps to the first position, P to the fourth, and R to the 6th. Other examples:
"KREEPE" = (1, 5, 2), "EEEKPR" = (4, 5, 6), and "KPREEE" = (1, 2, 3). Notice, in this way we can generalize the problem back to what we're familiar with already, which is a permutation of n elements P(n, k), in this case six letters taken in three ways P(6, 3) since the E's just fill in the blanks in our method of string construction. Of course, it's the same as $\frac{n!}{(n-k)!}$ which in this case simplifies to $\frac{6!}{3!}$. That might be a more succinct way of explaining why generally $\frac{n!}{e!}$ works.

As for your logic, let me reread what you're trying to do to see where your assumptions when awry.

 

[aikismos]

I believe I have understood now. Thanks for your reply Vanadium 50! If I use my method then the answer should be 3.5!/3! + 5!/2! (and not 4.5!/3!) which is equal to 6!/3! = 120. I was making a mistake while dividing the E1 block as now when you have E1 as the starting element then there are only 2 positions (i.e. E2, E3) to shuffle i.e. 2! and hence you divide by 2! when considering the repeat case. Thanks once again aikismos and Vanadium 50. I am needlessly complicating the matter :)

What is it you mean by 3.5! ? How are you defining that, as the definition of factorial (at least the one I know) requires natural numbers?

 

[physio]

I meant 3 * 5! :)

 

[physio]

@aikismos: Thanks for that wonderful explanation :) Cleared everything up!

 

[aikismos]

I meant 3 * 5! :)

Ok... but in the future, if you're going to represent multiplication in text mode stick with (3 x 5)! or 3 x 5! Your other option is to use the the latex and the \cdot operator between the double pound symbols which are used to represent math mode.

Anytime. Lots of big brains on this site that I learn from too!

 

[Orodruin]

Does that mean these cases are redundant and should reduce to one case?

No. If you do this you are double counting redundancy for those words and will get a too small answer. The redundancy is removed when you divide by the number of possible permutations of the Es. If you do both that and count words starting with E only once before, you will be undercounting.

 

[Orodruin]

There is an alternative solution, although a bit messier. You can consider how many words you can make of KPR (3!). For each such word you then need to figure out in how many ways you can distribute three Es into four possible positions (before the word, after the first letter, after the second letter, after the entire word). You have three possibilities you need to take into account: all Es in distinct positions, two Es in the same position and the third distinct, all Es in the same position.

It is a nice exercise to do these combinatorics and see that they add up to the same number.