Finding total unique combination for character deletion in a string Is there any general formula to determine a unique combination for character deletion in a string comprised of 4 characters? Let's say that I have $str1 = {ABCDA}$ and I want to delete from one up to four position in that string. Thus all the combination for deletion up to four position of str1 would be:
$$
s(1, str1) = BCDA, ACDA, ABDA, ABCA, ABCD = 5
$$
$$
s(2, str1) = CDA, BDA, BCA, BCD, ADA, ACA, ACD, ABA, ABD, ABC = 10
$$
$$
s(3, str1) = DA, CA, CD, BA, BD, BC, AA, AD, AC, AB = 10
$$
$$
s(4, str1) = A, D, C, B, A = 5
$$
and gives 30 in total, and only 29 unique strings. In general, the total combination could be solved using the formula $\sum_{k=1}^{r} {{n}\choose{k}}$. However I could not find a formula to calculate total unique combination from a given string since the relative position of characters determine the total unique combination. Let's say that another 5-character long string is str2 = {AAABC}, then the number of unique sequences will be different:
$$
s(1, str2) = AABC, AABC, AABC, AAAC, AAAB
$$
$$
s(2, str2) = ABC, ABC, AAC, AAB, ABC, AAC, AAB, AAC, AAB, AAA
$$
$$
s(3, str2) = BCA, AC, AB, AC, AB, AA, AC, AB, AA, AA
$$
$$
s(4, str3) = C, B, A, A, A
$$
The total combinations is still 30, but the unique combinations reduce to 14. Is there any way to count such unique combination for any string with length n composed of four characters (A, B, C, and D)?
 A: I found a hint for calculating unique combination for one character deletion such that the unique combination is equal to total combination as long as there is no consecutive character repeat:
$$
s(1, ABCDA) = BCDA, ACDA, ABDA, ABCA, ABCD
$$
$$
s_{U}(1, ABCDA) = BCDA, ACDA, ABDA, ABCA, ABCD
$$
When repeats of characters occur, then the unique combination will be reduced:
$$
s(1, AABCD) = ABCD, ABCD, AACD, AABD, AABC
$$
$$
s_{U}(1, AABCD) = ABCD, AABD, AACD, AABC
$$
from this observation I conclude that the unique combination of any string of length n depends on the occurrence of runs, such that:
$$
s_{U}(1, AABCD) = s(1, AABCD) - (r\times d)
$$
$$
= {{5}\choose{1}} - (1 . 1) = 4
$$
I find it also true for string containing multiple runs, such as AAABBCD, where: $s_{U} = {{7}\choose{1}} - ((1\times 2)+(1\times 1)) = 4$. However I find difficulties when I try the same formula for 2, 3, or four character deletion. My hypothesis is that the unique combination can be obtained by subtracting the total combination with some factors. I presumed that these factors involve the occurrence of repeats.
Any help for this problem?
