Letter combinatorics problem

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 ?
 

chiro

Science Advisor
4,783
127
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 ?
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?
 
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.
 

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving

Hot Threads

Top