Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
We are making $10$ letter words using the letters $A,C,G,T$.
How many possible words are there of the form $A...AC...CG...GT...T$
This is where all of the $A's$ go before the all of the $C's$ and all of the $C's$ go before all of the $G's$ and all of the $G's$ go before all of the $T's$?
I know there are $4^{10}$ possible words comprised of the letters $A,C,G,T$ but I have no idea how to account for the overcounting in this bit.
This problem is equivalent to finding the number of ways to partition $10$ into four parts, in which the order of the partitioning matters. For example, $10 = 2 + 3 + 3 + 2$ is not the same as $10 = 3 + 2 + 2 + 3$. The first number represents the number of A's, the second number represents the number of C's, and so on.
In order to then count the number of ways, think of $10$ dots and $3$ lines. The $3$ lines will divide the $10$ dots into four parts. So, we have a total of $10 + 3 = 13$ spaces to choose from, and we need to place 3 lines. Therefore, the answer will be ${13 \choose 3} = 286$.
Illustrations of $10$ dots and $3$ lines: $$\cdot\cdot|\cdot\cdot\cdot|\cdot\cdot\cdot\cdot|\cdot$$ $$\cdot\cdot\cdot|\cdot|\cdot|\cdot\cdot\cdot\cdot\cdot$$ $$\cdot\cdot\cdot\cdot\cdot\cdot\cdot\cdot|\cdot\cdot||$$ $$\cdot\cdot\cdot|\cdot\cdot\cdot|\cdot\cdot|\cdot\cdot$$
This is "stars-&-bars" - you're picking the points in the string where the 3 transitions are. So it's just $${10+3 \choose 3}=\frac{13!}{10!\:3!} = 286$$
Effectively we're extending the ten real positions in the string to include an extra three positions to place the transition markers (the "bars").
$$\circ\circ\circ\circ\circ\circ \circ\circ\circ\circ\circ\circ\circ$$
The transition markers are in predetermined order so they do not need identification; we can mark them up after we have selected their positions: $\newcommand{transit}[2]{\tiny{\frac{#1}{#2}}}$
$$\circ\circ\circ/\circ\circ \circ\circ//\circ\circ\circ$$
$$\circ\circ\circ{\transit AC}\circ\circ \circ\circ{\transit CG}{\transit GT}\circ\circ\circ$$
Then can fill in the real values - the "stars" - based on the separators.
$$AAA{\transit AC}CCCC{\transit CG}{\transit GT}TTT$$
and eliminate the transitions:
$$AAACCCCTTT$$
It's an easy and common blind alley to explore, to look at all combinations and then try to think of a way to eliminate duplicates, but this is obviously a far simpler approach.
Assume that the 10 letters are balls (denoted by O). So you would have $10$ balls, i.e. O O O O O O O O O O. Now, you can put $3$ slashes in the middle to make $4$ sets of these $10$ balls, for example, O|O O O|O O|O O O O. Now, assume that the number of balls before each slash is the letter required, i.e. in the example, the word is ACCCGGTTTT. So, the number of ways to arrange the slashes would give the number of required word. The number of ways the slashes can be arranged is [10 (balls) + 4 (divisions) - 1] choose 10 (balls), i.e. $\binom{10+4-1}{10} = \binom{13}{10} = \binom{13}{3}=\frac{13\cdot 12\cdot 11}{3\cdot 2\cdot 1} = 286$. So, there are 286 words possible with the given conditions.
This is an illustration of how Stars and Bars works.
