# How Many $m$ substrings of length $3$ can be chosen from a string of length $n$

Suppose we have a string of length $n$ like $a_1a_2 \cdots a_n$.

If we want to choose 2 substrings of length 3 then we can do this in $2\times (n-5)+ 2\times (n-6) + 2\times (n-7)+ \sum_{i=4}^{n-6} (i-2)+ (n-i-2)$ ways.

The reason is that if the beginning of the first substring be $a_1$ or $a_{n-3}$, then we have $n-3-3+1$ other ways to choose the second substring. If the beginning the first substring be $a_2$ or $a_{n-4}$, then we have $n-3-3+1-1$ other ways to choose the second substring. If the beginning of the first substring be $a_3$ or $a_{n-5}$, then we have $n-3-3+1-2$ other ways to choose the second substring. If the beginning of the first substring be $a_i$ for $i\geq 4$, then we should count numbers of way which we can choose the second string before and after the first string which would be $i-3+1$ and $n-i-3+1$ respectively.

So by simplification we have $2\times (n-5)+ 2\times (n-6) + 2\times (n-7)+ (n-9)(n-4)$ ways to choose two substrings of length 3 of one string of length $n$.

There are similar questions here and here. But my question is asking for finding numbers of ways that we can choose $m$ substrings instead of one substring.

Edit: We are allowed to choose same strings again. For example, if we have the string $abcabc$ we have two ways to choose $abc$. So the content of the string is not important but the number of ways which we can choose substrings is our goal.

• Are the substrings allowed to overlap? If the string is "abcabc" are there 1 or 2 ways to pick the pair of length 3 substrings "abc" and "abc" ? – kimchi lover Aug 27 '17 at 16:18
• @kimchilover If the string be abcabc, then we have 2 ways to pick abc. – Doralisa Aug 27 '17 at 16:22
• Do the substrings have to be contiguous? For example if the string is ABCDEFG, are you allowed to have substring ADG? – user326210 Aug 27 '17 at 16:24
• @user326210 No! I shared the links of two similar questions. I think if we were allowed to have ADG, then the answer could be found using permutation. – Doralisa Aug 27 '17 at 16:31
• Also just to clarify your earlier answer, are substrings allowed to overlap? For example, if the string is ABCDEFG and you want two substrings, can you pick #1 = ABC and #2 = BCD? (It's unclear to me how you get counts like $n-3+1$.) – user326210 Aug 27 '17 at 16:31

1. The general question is how many ways are there of finding $m$ non-overlapping contiguous substrings of length $k$ in a string of length $n$.

2. For any such arrangement, the $n$ letters will be divided into $m$ substrings of length $k$, plus $n-mk$ remaining letters that weren't included.

3. Hence the problem can be re-described as follows: you have $m$ blocks each representing a substring of length $k$, as well as $n-mk$ blocks each representing an unused letter. How many different ways can these blocks be arranged in a list?

4. Or, more abstractly: you have $m$ black balls and $n-mk$ white balls. In how many different ways can they be arranged in a list (given that balls of the same color are indistinguishable)?

5. Now we've reduced the problem to a standard combinatorics problem. In general, the number of ways of arranging $a$ black balls and $b$ white balls in a list is ${a+b \choose a} = \frac{(a+b)!}{a! b!}$, because you are essentially taking $a+b$ balls and choosing which $a$ of them will be black.

6. Hence the number of ways of finding $m$ non-overlapping contiguous substrings of length $k$ in a string of length $n$ is:

$${(n-mk) + m \choose m } = \frac{(n-mk + m)!}{m! (n-mk)!}$$

Let's look at a specific example. In particular, if we want to find $m=2$ substrings of length $k=3$ in a string of length $n$, there are

$${n - 2(3-1) \choose 2} = {n-4 \choose 2}$$

ways to do it.

• For example, when $n=6$, there is exactly one way [▬ ▬].
• When $n=7$, there are three ways [• ▬ ▬], [▬ • ▬], [▬ ▬ •].
• When $n=8$, there are six ways: [• • ▬ ▬], [• ▬ • ▬], [• ▬ ▬ • ], [▬ • • ▬], [▬ • ▬ •], [ ▬ ▬ • •].
• When $n<6$, there are no ways, etc.

And consequently the number of ways of selecting $M$ (nonoverlapping, continguous) substrings of length 3 from a string of length $N$ is:

$${N-2M \choose M} = \frac{(N-M)!}{(N-2M)!\, M!}$$

This can be considered from the standpoint of arranging a mix of 3-length blocks and single items.

Basically we reduce each 3-block to a type-b item, giving $n-2m$ items, and then the arrangement options are $\dbinom {n-2m}{m}$

[I'm assuming that the substrings cannot overlap in any one choice.]