I have a problem in counting the total of unique string combination. Provided a string of length 5 which is composed of 4 characters (ABCD), I would like to generate all the possible string combinations from one to four characters addition excluding both end addition.
Provided that the input string is ABCDA, I want to insert additional characters: w; w and x; w, x and y; w, x, y and z into any possible combination into the input string while avoiding insertion at both ends. So that the resulting combination would be: (AwBCDA, ABwCDA, ABCwDA,..., ABCDwA); (AwxBCDA, AwBxCDA, AwBCxDA,..., ABCDwxA); (AwxyBCDA, AwxByCDA, AwxBCyDA,..., ABCDwxyA); (AwxyzBCDA, AwxyBzCDA, AwxyBCzDA,..., ABCDwxyzA). And then for each substituents w, x, y, and z are substituted into A, B, C, or D.
I solved the combination above with the formula: $$ s(r, n) = \sum_{k=1}^{r} 4^{k} {{n+k-2}\choose{k}} $$ for $1\leq r\leq4$. The result from the above formula contains duplicates and I would like to count all the unique strings in $s(r, n)$. I tried to solve it using the following double summation: $$ s_{U}(r, n) = \sum_{k=1}^{r}1+\sum_{l=1}^{k}3^{l}{{n+k-2}\choose {l}} $$ which is rearranged to: $$ s_{U}(r, n) = r+\sum_{k=1}^{r}\sum_{l=1}^{k}3^{l}{{n+k-2}\choose {l}} $$ for $1 \leq r \leq 4$. Please kindly check whether is the formula and also the writing is correct or not.
Thank you.