1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Number of possibilities of words with limitations

  1. Jan 27, 2015 #1
    1. The problem statement, all variables and given/known data
    Given the word "DEEPBLUE" - possibilities of words such that two "E"-s are not adjacent in any word.

    2. Relevant equations


    3. 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 [itex]\frac{8!}{5!3!} - 50[/itex] 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 35 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?
     
  2. jcsd
  3. Jan 27, 2015 #2

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    I guess you are looking for the number of permutations of those 8 symbols.
    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.
     
  4. Jan 27, 2015 #3

    Orodruin

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    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).
     
  5. Jan 27, 2015 #4

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    Is it only the anagrams of all 8 that you are interested in, or do you also have to consider shorter words?
     
  6. Jan 28, 2015 #5
    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.
     
  7. Jan 28, 2015 #6

    Orodruin

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    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:
    Assuming you correct for your double counting, these two approaches will (of course) give the same result.
     
  8. Jan 28, 2015 #7
    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
     
  9. Jan 28, 2015 #8

    Orodruin

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    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?
     
  10. Jan 28, 2015 #9
    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?
     
  11. Jan 28, 2015 #10

    Orodruin

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted