Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Whilst solving a question, I have come across a problem regarding the maximal number of possible distinct $k$-length binary sub-strings in an $n$-length binary string.

My thought process was that if you take some $n$-length binary string, then the number of possible sub-strings could be found as follows:

$$\sum_{k=1}^{n}{n-k+1}=n^{2}-\frac{n(n+1)}{2}+n=\frac{n^{2}+n}{2}$$

But this doesn't take into account the maximum possible number of distinct sub-strings, which will be $2^{k}$, when we're looking for sub-strings of length $k$.

Does anyone have any suggestions as to how I could find the maximal number of distinct sub-strings (of length $k\le n$) contained within some binary string of length $n$?

Thanks in advance!

share|cite|improve this question
    
Calculate it for some small values of $n$, then look it up in the Online Encyclopedia of Integer Sequences. – Gerry Myerson Jun 16 '12 at 12:31
up vote 1 down vote accepted

I took my own advice: it's "Maximal number of distinct nonempty substrings of any binary string of length n." It seems that there is a question about this sequence that is very simple to state but is still open.

share|cite|improve this answer
    
Ahh, so as yet there is no known closed-form to solve this problem? – Shaktal Jun 16 '12 at 12:37
    
That's my interpretation of what it says at the OEIS. – Gerry Myerson Jun 16 '12 at 12:51
    
Okay, thanks then! – Shaktal Jun 16 '12 at 12:55

"On the maximum number of distinct factors of a binary string" (also here), by Jeffrey Shallit, proves that the answer (the attained maximum number of distinct factors of a length-$n$ binary string) is $$\binom{n-k+1}{2}+2^{k+1}-1,$$ where $k$ is the unique integer such that $$2^k + k - 1\ \le\ n\ \lt\ 2^{k+1}+(k+1)-1.$$ (This counts the empty string as a factor of every string.)


NB: A "closed form" for the answer can be found by noting that $k$ is just $\lfloor x \rfloor$, where $x$ is the real number such that $$2^x + x - 1=n.$$ Now, the substitutions $$\begin{align} X &:= \log(2)\ (n-x+1)\\ Y &:= \log(2)\ 2^{n+1} \end{align} $$ transform this equation into $$X\ e^X = Y$$ whose solution is $$X = W(Y),$$ where $W$ is the (principal branch of) the Lambert $W$ function.

Therefore, $$\log(2)\ (n-x+1) = W(\log(2)\ 2^{n+1})$$ giving
$$k = \left\lfloor n+1-\frac{W(\log(2)\ 2^{n+1})}{\log(2)}\right\rfloor.$$


NB: Some comments at the OEIS link refer to the above results as "conjectures", in spite of the proof given in the cited paper.

share|cite|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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