Number of possible cases on RNA strand. A RNA strand made up of $22$ base pairs
can have A, C, G or U per each pair.
If the base C are continuously arranged for $4$ times like
AGUGCCCCAAAAAAAAAAAAUU
this RNA strand could act as a blueprint of carcinogen so We have to know how many possible cases of $22$-bps long RNA can have at least one 'CCCC' in the strand.
What's the number of possible different arrangements of $22$-base pairs long RNA strand, which have at least one 'CCCC' in it?
 A: The number of 22-strings is $4^{22}$. If we required that it has "CCCC" in a given position, 18 letters remain to be chosen freely, so there are $4^{18}$ such strings. Next, the "CCCC" can be in one of 19 different positions, which makes for $19\cdot4^{18}$ different ways of selecting the 22-string and a "CCCC" inside it.
However, if a string contains multiple "CCCC" substrings, either disjoint or overlapping in a longer C-repeat, these will be counted multiple times. E.g., a string that contains "CCCCCC" will be counted three times in the above scheme. Thus, the ratio $19\cdot4^{18}/4^{22}=19/64$ is the expected number of "CCCC" substrings in a random 22-string.
One fix is to use the inclusion-exclusion principle to ensure strings containing multiple "CCCC" are counted only once. Basically, if $N_k$ is the number of ways to pick a 22-string and $k$ occurrences of "CCCC" therein, the number of 22-strings containing one or more is $N_1-N_2+N_3-\cdots$. However, 2 occurrences of "CCCC" can be non-overlapping, or overlapping by 1 to 3 letters ("CCCCCCC", "CCCCCC", or "CCCCC") which all have to be counted. So, while this approach may be good for a quick estimate, it is not very practical for an exact computations.
Another approach is to use recursion to count all ways of generating such strings of arbitrary length. To do this with recursion first, we count $n$-strings not containing "CCCC": let $A_n$ be the number of such strings that do not end in $C$, and $B_n$ the number the number that end in $C$. Then, we get
$$
A_n=3(A_{n-1}+B_{n-1})
\quad\text{and}\quad
B_n=A_{n-1}+A_{n-2}+A_{n-3}
$$
where $A_0=1$, $B_0=0$, and both are zero for $n<0$. These two equations correspond to adding one of the three letters from {A,G,U}, or a sequence of 1 to 3 copies of C. The total number of $n$-string not containing "CCCC" is then $C_n=A_n+B_n$. Entering $n=22$ gives $C_n=16612233171696$. So, the number of strings with "CCCC" is $4^{22}-C_n = 979952872720$.
This same approach can also be encoded using generating functions.
