Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Letter combinatorics problem

  1. Mar 30, 2012 #1
    The problem is : In how many ways can the letters of the word ASSASSINATION be arranged so that no two Ss are next to each other ?

    Tried taking the interval to the first S as x1, from then to the next S as x2...etc. with sum being 9.

    Possible partitions , including repeats, comes out as 211. This is the part where I am doubtful. Normally, I'd say ans would be (9!/4!) x 211, but the answer is given as (9!/4!) x 205.

    what exactly is the error ? I am trying to assume x1 = 0, x2 = 1, x3 = 1 at which point 7 spaces remain , which can be partitioned in 7 ways among the remaining parts. An AP forms with 7,6,5.. for x3 > 1 which I solve for those cases using brute force to get 211....am I correct ?
     
  2. jcsd
  3. Mar 30, 2012 #2

    chiro

    User Avatar
    Science Advisor

    Hey Perpendicular and welcome to the forums.

    One suggestion I have is to break your problem firstly into a different problem.

    We know that the S's can't be next to each other so first consider finding the problem of if we have two groups A and B where A is an S and B is anything else, then what is the probability of getting no two A's next to each other. B in this case is any combination of characters that allows us to have an alternation between A and B. For example given four S's we have to have BABABABAB or ABABABAB as our only choices but for this to happen we need to have enough non S's left over for all of the later B's. So in this way we have only two choice's in terms of the A's and B's.

    Now from this we need to find all of the combinations for the B's in the problem above. They can be arranged in any way as long as we have enough elements left over in the later B's so that we have enough B's for the 1st and second situation. We then calculate the combinations for each situation, add them up and that will give you the frequency information. If you need a probability then divide it by 13! to get a total probability.

    Using this hint, does this make it easier to solve the problem?
     
  4. Mar 30, 2012 #3
    I would find out how many ways you can arrange AAINATION.

    Now, for each arrangement of AAINATION, you have 10 "slots" in which you are allowed to put AT MOST one S. So, now you have to find how many ways there are to choose 4 spots from 10 spots to place the 4 S's.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Letter combinatorics problem
  1. Combinatorical Problem (Replies: 1)

  2. Combinatorics problem (Replies: 14)

  3. Combinatorics problem (Replies: 2)

Loading...