1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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" ? $\endgroup$ – kimchi lover Aug 27 '17 at 16:18
  • $\begingroup$ @kimchilover If the string be abcabc, then we have 2 ways to pick abc. $\endgroup$ – Doralisa Aug 27 '17 at 16:22
  • $\begingroup$ Do the substrings have to be contiguous? For example if the string is ABCDEFG, are you allowed to have substring ADG? $\endgroup$ – user326210 Aug 27 '17 at 16:24
  • $\begingroup$ @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. $\endgroup$ – Doralisa Aug 27 '17 at 16:31
  • $\begingroup$ 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$.) $\endgroup$ – user326210 Aug 27 '17 at 16:31
0
$\begingroup$
  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!}$$

$\endgroup$
0
$\begingroup$

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.]

$\endgroup$

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.