1
$\begingroup$

I have a string of length n which is comprised of four characters only (say ABCD) and I would like to make 1 until 4 substitutions to this string. The character use for substitution would also comprised the same character ABCD. Therefore, the total ways for making such combination can be calculated: $$ s^r \binom{n}{r} $$

where: $n$ = length of a string; $s$ = number of substituting characters (4); $r$ = number of position to be substituted in a string (1 to 4 position)

so for $n$ = 5 (say ABCDA), it will give: $$ 1subs = 4^1 \binom{5}{1} = 20 $$ $$ 2subs = 4^2 \binom{5}{2} = 160 $$ $$ 3subs = 4^3 \binom{5}{3} = 640 $$ $$ 4subs = 4^4 \binom{5}{4} = 1280 $$

Example from 1subs: ABCDA, BBCDA, CBCDA, DBCDA AACDA, ABCDA, ACCDA, ADCDA ABADA, ABBDA, ABCDA, ABDDA ABCAA, ABCBA, ABCCA, ABCDA ABCDA, ABCDB, ABCDC, ABCDD

Notice that ABCDA was duplicated 5 times and among the 20 elements, only 16 are unique. I currently solve the unique sets of these combinations using polynomial functions and I got: $$ 1subs = 3n + 1 $$ $$ 2subs = \frac{9}{2}n^2 - \frac{3}{2}n + 1 $$ $$ 3subs = \frac{27}{6}n^3 - 9n^2 + 15n + 1 $$ $$ 4subs = \frac{27}{8}n^4 - \frac{63}{4}n^3 + \frac{225}{8}n^2 - \frac{51}{4}n + 1 $$

So, for $n = 5$, the unique elements for 1 until 4 substitution will be: $16, 106, 376, 781$. However, the polynomial functions above are generated in the presence of data and I want to count the unique combinations for any arbitrary $n$ (assuming the absence of such data). Is there any combinatorial formula to solve this?

Thanks

$\endgroup$
0
$\begingroup$

The total number of strings of length $n$ comprised of four characters is $4^n$, that is $4$ options for each position in the string. To count the number of unique strings that can be result from the substitution of characters, count only the substitutions that change the string: $$3^r\binom{n}{r}$$ This will give you the number of new strings that can be made when exactly $r$ characters have been replaced with a character other than the original. If you want to allow a character to be replaced with itself you need to take the sum for each $r$ up to the maximum number of characters to be replaced and include the original string: $$1+\sum_{k=1}^r 3^k\binom{n}{k}$$

$\endgroup$
  • $\begingroup$ Wow..thanks a lot!! It really helps :D And, could you help to simplify the above formula by avoiding the sigma notation? So that I could calculate for cases involving large number of r and n without having to write each summation element recurrently. $\endgroup$ – Vic Brown Dec 27 '18 at 7:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.