Here is a combinatorial problem I came up with:
For example, XSESESXEX is a valid arrangement but SSSEEEXXX is not.
To be clear, every letter in an arrangement must differ from the letter directly to the left of it (except for the first letter).
Good luck.
For example, XSESESXEX is a valid arrangement but SSSEEEXXX is not.
To be clear, every letter in an arrangement must differ from the letter directly to the left of it (except for the first letter).
Good luck.
Let's start with a simpler case, how many ways are there to arrange SEXSEX without having any adjacent letters?
Clearly, there are only 2 cases to consider here:
Case 1: The arrangement ends in some permutation of SEX
Case 2: The arrangement ends in ABA form where A and B represent any 2 characters from the set {S, E, X}.
There are 3 x 2 possible endings here, you can also think of it as (3 choose 2) x 2, both are equal to 6.
For each ending, there is only one way to arrange the beginning so it remains valid.
As an example, consider the ending XEX. It's easy to see that the only valid arrangement with this ending is SESXEX.
So we have 1 x 6 = 6
Total:
Adding those cases up, we have 24 + 6 = 30. That answers the simplified version of this question.
Back to the original problem: What if we added another SEX?
Again, we have the same 2 possible cases for the last 3 letters.
Either we can end with the remaining letters SEX or some arrangement in ABA form.
Case 1:
We build up from our previous answer, starting out with 30 options and doing the same thing we did in case 1 earlier, choose a different letter from the previous one (2 options), and finally arrange the last 2 remaining letters.
30 x 2 x 2! = 120
Case 2:
This one is a little more complicated. If we ended in ABA form,
That would leave us with 3 of one letter, 2 of one letter, and 1 of one letter.
The number of possible arrangements for the beginning would be equivalent to the number of valid arrangements for SSSEEX.
Explaining this would be tedious, but there are only 10 possible ways to arrange SSSEEX without 2 adjacent letters (since there weren't too many possibilites, you could have manually counted these pretty quickly with good heuristics).
Now if we stick ABA to the end, we have to be careful to exclude the case where our sixth letter happens to be the same as the letter we chose for A, luckily there is only one such case, let's say our ending was XEX. the only valid arrangement for the beginning with the sixth letter being X is SESESX.
So, (10 - 1) x 6 = 54.
Final Answer
Adding our cases up again, we have 120 + 54 = 174.
So there are 174 valid arrangements in total.
Clearly, there are only 2 cases to consider here:
Case 1: The arrangement ends in some permutation of SEX
- The first 3 letters will also be some permutation of SEX, so we start with 3! options.
- Then, the next letter just has to be one of {S, E, X} but different from the previous letter we chose, so that only leaves us with 2 options.
- From there, the remaining 2 letters can be arranged however we like, so we have 2! options for those.
Case 2: The arrangement ends in ABA form where A and B represent any 2 characters from the set {S, E, X}.
There are 3 x 2 possible endings here, you can also think of it as (3 choose 2) x 2, both are equal to 6.
For each ending, there is only one way to arrange the beginning so it remains valid.
As an example, consider the ending XEX. It's easy to see that the only valid arrangement with this ending is SESXEX.
So we have 1 x 6 = 6
Total:
Adding those cases up, we have 24 + 6 = 30. That answers the simplified version of this question.
Back to the original problem: What if we added another SEX?
Again, we have the same 2 possible cases for the last 3 letters.
Either we can end with the remaining letters SEX or some arrangement in ABA form.
Case 1:
We build up from our previous answer, starting out with 30 options and doing the same thing we did in case 1 earlier, choose a different letter from the previous one (2 options), and finally arrange the last 2 remaining letters.
30 x 2 x 2! = 120
Case 2:
This one is a little more complicated. If we ended in ABA form,
That would leave us with 3 of one letter, 2 of one letter, and 1 of one letter.
The number of possible arrangements for the beginning would be equivalent to the number of valid arrangements for SSSEEX.
Explaining this would be tedious, but there are only 10 possible ways to arrange SSSEEX without 2 adjacent letters (since there weren't too many possibilites, you could have manually counted these pretty quickly with good heuristics).
Now if we stick ABA to the end, we have to be careful to exclude the case where our sixth letter happens to be the same as the letter we chose for A, luckily there is only one such case, let's say our ending was XEX. the only valid arrangement for the beginning with the sixth letter being X is SESESX.
So, (10 - 1) x 6 = 54.
Final Answer
Adding our cases up again, we have 120 + 54 = 174.
So there are 174 valid arrangements in total.
