Number of possibilities of words with limitations

[nuuskur]

Homework Statement

Given the word "DEEPBLUE" - possibilities of words such that two "E"-s are not adjacent in any word.

Homework Equations

The Attempt at a Solution

There are 8 symbols. If 2 E-s cannot be adjacent then how can I calculate the possibilities of placing all the 3 E-s such that the criterion is satisfied?

A small side-tracking - in a way it reminds me a little bit of a problem where we have a long-table with N seats and we have N/2 men and women, what are all the possibilities of seating people such that no 2 men or 2 women sit next to one another? Well it would be 2(N/2)! - rule of product.

The E-s are all identical now, therefore there is no need for permutations.
ALL of the possible combinations of 3 would be C_(8,3), but this also considers the possibilities where all 3 are together AND when 2 are adjacent and the 3rd is not adjacent to either side.
In case of 3 E-s stuck together there are only 6 possibilities, right? We can subtract that.
What about the number of possibilities of 2 E-s adjacent and the 3rd not adjacent?

If 2 E-s are together then there are 7 possibilities to place the 2 E-s and then:
2 of possibilities have the 2 E-s at the side, wihch leaves 5 possibilities to the leftover E to not be adjacent - 10 possibilities
5 possibilities where for each there are 4 possible positions for the left over E - 20 possibilities * 2 (counting also the mirror image) - 40 possibilities.
Total 50 possibilities that violate the criterion hence $\frac{8!}{5!3!} - 50$ possibilities. 6 possibilities to place the E-s.

We have 5 unique symbols left over and 5 spots - 5! possibilities.
Applying the rule of product the total number of words would be 720. Is this correct?

Expanding on the second part of the problem.

What happens if for 5 left over spots, we have 3 unique symbols and for now, no criteria be set on any repetition? is it simply 3⁵ possibilities?
If there was extra conditions, such that if the left over symbols are A,B,C and ANY of the symbols are not allowed to be adjacent.
I would have 3 possible ways to place the ABC in the 5 symbol space. Then also 6 ways to rearrange ABC - 18 possibilities.

This is where my wits end:
For any arbitrary variation within the 5 symbol space, how do I exactly know how I can place the other symbols such that the criterion holds.

In the context of the original problem - the 5 symbol space is not all in one piece, how do I account for the disjuctions created by the E-s that will possibly increase the number of possible words?

What kind of material is there to look into to get a better grasp for this type of problem?


Is there a way to generalize this to N symbols and M repeative symbols?

 

[mfb]

I guess you are looking for the number of permutations of those 8 symbols.

5 possibilities where for each there are 4 possible positions for the left over E - 20 possibilities * 2 (counting also the mirror image) - 40 possibilities.

You are double-counting here. The 4 possible positions already consider both sides.
Apart from that, the approach looks fine.

There is an easier way: you have 5 "separators", giving you 6 "places" where an E can be. 3 of them have to be used...

Just to demonstrate that there are more than 6 solutions for the E positions:
ExExExxx and xxxExExE
ExExxExx and xxExxExE
ExExxxEx and xExxxExE
ExExxxxE and ExxxxExE
(those are not all)

If you have a condition like "no A,B,C can be next to each other", just treat them all as "E" for their positions and care about their arrangement later.

 

[Orodruin]

In case of 3 E-s stuck together there are only 6 possibilities, right? We can subtract that.

2 of possibilities have the 2 E-s at the side, wihch leaves 5 possibilities to the leftover E to not be adjacent - 10 possibilities
5 possibilities where for each there are 4 possible positions for the left over E - 20 possibilities * 2 (counting also the mirror image) - 40 possibilities.
Total 50 possibilities that violate the criterion hence ... 50 possibilities. 6 possibilities to place the E-s.

You are also only subtracting the 50 possibilities you got for sticking only two together and forgetting about the 6 combinations with three Es together, which would actually have gotten you zero combinations. It is even easier to see that this must be wrong ...
The double counting occurs when you assume that there is also a mirror image of each (that image is already counted by another position of the pair).

 

[haruspex]

Is it only the anagrams of all 8 that you are interested in, or do you also have to consider shorter words?

 

[nuuskur]

Oh dear - was too sleepy :< Yes, we are concerned about anagrams with given limitations, at the moment.
Round 2:

* Subtracting the 3 E in a row combinations i.e
EEExxxxx
xEEExxxx
xxEEExxx
...
Total of 6

** Now the 2 E combinations. If the 2 Es are on the sides
EExxxxxx - E cannot be on position 3 since that is counted in * - leaves 5 possibilities. But there is also
xxxxxxEE - The word will be different hence we should also count that, no? 10 possibilities

*** 2 E combinations NOT on the sides
xEExxxxx - remaining E cannot be in position 1 or 4, we would have what we already considered in * - that leaves 4 possibilities.
There also exists xxxxxEEx - the mirror image which also has 4 possibilities.

Where am I making the double counting? - I can't understand that, although I see that the difference will indeed be 0, which is clearly incorrect.

 

[Orodruin]

Where am I making the double counting?

There also exists xxxxxEEx - the mirror image which also has 4 possibilities.

You are double counting here. Yes, there also exists xxxxxEEx, but that is going to be taken care of when you come to that positioning of xxxxxEEx for the EE. You cannot count the mirror image at the same time as you are computing all of the possible positions of EE, this will make you count double. In other terms, later you get to the position xxxxxEEx, which is one of your five options, and include that one and xEExxxxx again.

The easier route is the one mentioned by mfb:

There is an easier way: you have 5 "separators", giving you 6 "places" where an E can be. 3 of them have to be used...

Assuming you correct for your double counting, these two approaches will (of course) give the same result.

 

[nuuskur]

Now I understand, there is no "mirror image" to speak of.
That makes 20+10 +6 possibilities that don't fit the bill.

20 possible ways to combine the E-s as necessary and 20*5! = 2400 words

 

[Orodruin]

Assuming, as haruspex pointed out, that we are only dealing with words containing all letters, yes.

Do you understand how mfb's approach gives the answer in a more straightforward fashion?

 

[nuuskur]

Trying to wrap my head around how we can conclude there are 6 possible positions for the E-s.
For every configuration
E x x x x x x x - If position 1 is fixed, then we are left with:
3,4,5,6,7,8 for the second E - 6 possibilities.

If positions 1,3 are fixed we are left with 5,6,7 or 8 for the remaining E - so in total, 6 positions again

What if I fix positions 1,4 - we are left with 6,7 or 8 - only 5 positions.
This logic doesn't hold :/ Where am I going wrong?

 

[Orodruin]

No, the actual positions of the Es are not the "bins" mfb is talking about. The bins are the spaces in between the other letters. Think of it in the following fashion: We have 5 other letters, DPBLU. We can order them in 5! different ways, but let us work with the example DPBLU. There are now six different places where you can insert an E, namely "before the D", "between D and P", "between P and B", "between B and L", "between L and U", and "after U". Since you are not allowed to put two Es in the same bin, i.e., you are not allowed to put two Es between D and P, you need to pick three out of these positions to put an E.