# Count of near matching sequences

Consider all pairs of binary strings $P$ and $T$. Let the length of $P$ be $n$ and the length of $T$ be $2n-1$. For each such pair, we can compute the Hamming distance between $P$ and each of the $n$ substrings of $T$ in order from left to right and output a sequence representing these results. For example:

$$P = 11011, T = 110011001$$

gives an output sequence:

$$1,1,4,4,1.$$

For my problem I just want to record where the Hamming distance is at most 1. We write a $Y$ where this is the case and an $N$ otherwise. So in this case I would get:

$$Y,Y,N,N,Y$$

where $Y$ represents Hamming distance at most $1$ and $N$ represents Hamming distance greater than $1$

If we iterate over all possible pairs $P$, $T$ we can count how many distinct sequences of $Y$s and $N$s we get from the outputs. For $n = 1, \dots, 9$ we get the following interesting result:

$$1 ,4, 8, 16, 32, 63, 120, 216, 368$$

Is it possible to give a closed form formula for the number of distinct sequences of $Y$s and $N$s?

Related In Count number of exact matching sequences a very nice solution is given by Smylic which corresponds to this problem with a Hamming distance bound of $0$ rather $1$.

• Interestingly, this sequence is not in the OEIS database: oeis.org. – jvdhooft Jun 3 '17 at 9:06
• @jvdhooft Yes, I checked there first. – felipa Jun 3 '17 at 9:06
• Related questions: math.stackexchange.com/questions/2183085/… and math.stackexchange.com/questions/2186041/… – Smylic Jun 8 '17 at 16:22
• @Smylic Thank you I will add the first link (with your very nice answer) to the question. Do you think this question is also tractable? – felipa Jun 8 '17 at 18:11
• @felipa if I knew I would post the answer :-) I guess it is tractable, however may be much harder. Anyway I still don't know closed form (summation-free non-recurrent formula) of the number of exact matching sequences. – Smylic Jun 8 '17 at 18:55

I'll show that the number $F_1(n)$ of near matching sequences is in $\Omega(n^2 \log n)$. I will use my previous result that the number $F_0(n)$ of exact matching sequences is $\frac12 n^2 \ln n (1 + O(1))$. (The only difference in definition of this type of sequences is that Y corresponds to zero Hamming distance that is reflected in the lower index.)

1. $F_1(2n) \ge F_0(n)$.
Proof. Let $P = p_1p_2\ldots p_n$ and $T = t_1t_2\ldots t_{2n-1}$ produce exact matching sequence $m_1m_2\ldots m_n$. Then $P' = p_1p_1p_2p_2\ldots p_np_n$ and $T' = t_1t_1t_2t_2\ldots t_{2n-1}t_{2n-1}0$ produce near matching sequence $m_1x_1m_2x_2\ldots m_nx_n$ for some $x_1, x_2, \ldots x_n$. The reason is that distance $d$ between $P$ and $t_i\ldots t_{i + n - 1}$ gives distance exactly $2d$ between $P'$ and $t_it_i\ldots t_{i + n - 1}t_{i + n - 1}$. $\square$

2. $F_1(2n+1) \ge F_0(n)$.
Proof. Let $P = p_1p_2\ldots p_n$ and $T = t_1t_2\ldots t_{2n-1}$ produce near matching sequence $m_1m_2\ldots m_n$. Then $P' = p_1p_1p_2p_2\ldots p_np_n0$ and $T' = t_1t_1t_2t_2\ldots t_{2n-1}t_{2n-1}000$ produce near matching sequence $m_1x_1m_2x_2\ldots x_{n-1}m_nx_nx_{n+1}$ for some $x_1, x_2, \ldots x_{n+1}$. The reason is that distance $d$ between $P$ and $t_i\ldots t_{i + n - 1}$ gives distance either $2d$ or $2d + 1$ between $P'$ and $t_it_i\ldots t_{i + n - 1}t_{i + n - 1}t_{i + n}$, where $t_{2n} = 0$. $\square$

Therefore $F_1(n) \ge F_0(\lfloor n/2 \rfloor) \sim \frac{n^2}{8} \ln n$ and $F_1(n) = \Omega(n^2 \log n)$. This bound may be rather weak.

Conjecture. Each near matching sequence with at least two Y's has the following form: $$N \times n_1, (Y, N \times n_2) \times n_3, Y, N \times (n_2n_4 + n_4 - 1), Y, (N \times n_2, Y) \times n_5, N \times n_6,$$ where $S \times k$ means sequence $S$ repeated $k$ times and $n_i$ are non-negative integers. Also each such sequence is a near matching sequence.

This would imply that $F_1(n) = \Theta(n^4)$.

It was easy to find that this conjecture is wrong comparing the number of described sequences with the number of near matching sequences. Even for $n = 6$ there are near matching sequences YNNYNY, YNYNNY, YNYNYY and YYNYNY that have other pattern. However it may be possible to use the number of described sequences as a lower bound for the number of near matching sequences.

Computational results: $$\begin{array}{c|c|c|c} n & F_1(n) & \frac{F_1(n)}{n^4} & \frac{F_1(n)}{n^4 \ln n}\\\hline 1 & 1 & 2 & -\\ 2 & 4 & 0.25 & 0.361\\ 3 & 8 & 0.099 & 0.090\\ 4 & 16 & 0.063 & 0.045\\ 5 & 32 & 0.051 & 0.032\\ 6 & 63 & 0.049 & 0.027\\ 7 & 120 & 0.050 & 0.026\\ 8 & 216 & 0.054 & 0.025\\ 9 & 368 & 0.056 & 0.026\\ 10 & 596 & 0.060 & 0.026\\ 11 & 930 & 0.064 & 0.026\\ 12 & 1387 & 0.067 & 0.027\\ 13 & 2009 & 0.070 & 0.027\\ 14 & 2818 & 0.073 & 0.028\\ 15 & 3872 & 0.076 & 0.028\\ 16 & 5191 & 0.079 & 0.029\\ 17 & 6850 & 0.082 & 0.029\\ 18 & 8838 & 0.084 & 0.029\\ 19 & 11310 & 0.087 & 0.029\\ 20 & 14209 & 0.089 & 0.030\\ 21 & 17687 & 0.091 & 0.030\\ 22 & 21719 & 0.093 & 0.030\\ 23 & 26512 & 0.095 & 0.030\\ 24 & 31938 & 0.096 & 0.030\\ \end{array}$$

EDIT. Looking at these results I guess that $F_1(n)$ is close to $\frac1{30}n^4 \ln n$.

• Thank you this is interesting. Wrt the first part of your answer about $\Omega(n^2 \log{n})$. Isn't that immediate from the fact that the exact matching sequences are a subset of the ones we are counting here? Your conjecture is very interesting. – felipa Jun 12 '17 at 13:51
• It doesn't immediately imply. Let $P$ and $T$ give exact matching sequence $R_0$. Near matching sequence $R_1$ inherits all Y's from $R_0$, but some N's of $R_0$ become Y's going from $R_0$ to $R_1$. This is the reason why different $R_0$'s transform to the same $R_1$. Therefore it is not obvious that $F_1(n) \ge F_0(n)$. It is even false for $n = 1$ :-) – Smylic Jun 12 '17 at 14:02
• @felipa I've added 6 more values and comparison with probable asymptotics. – Smylic Jun 16 '17 at 13:17
• Intriguing. Thank you! – felipa Jun 20 '17 at 7:02

(I post a new answer because it gives much better bound and almost full characterization of near matching sequences.)

Conjecture. Each near matching sequence $S$ satisfies at least one of the following conditions:

1. There is some number $d$ such that distance between each pair of successive Y's is $d$ with at most one exception of distance that is not $d$, but is divisible by $d$.
2. There is some number $d$ such that distance between each pair of successive Y's is $d$ with exactly two exceptions that are divisible by $d$ and are either two leftmost distances or two rightmost distances.
3. Sequence $S$ has exactly four Y's and satisfies some other restrictions.

Also each sequence satisfying at least one of these conditions except single N is near matching sequence.

Examples of near matching sequences of each type:

1. NYYYYYYYYNNYYYYYYYYYNNN, NNYYYYYYYYYYYYYYNNNNN, NNNNNNNNNNNNNNNNN, NYNYNYNYNYNYNNNYNYNNNNN.
2. NYYYYYNNYNNNYNNNNNNNNNN, YNNYNNYNNYNNNNNYNNNNNYN, YNNYNNYYYYNNNNNNNNNNNNN.
3. YNYNNNNNNNNNNNYNNYNNNNN, NNNYNNNNYNNNNNNNNYNNNNY.

This conjecture was checked for all $n \le 22$. Let's prove that all sequences satisfying either the first or the second condition are near matching sequences.

Claim 1. All sequences satisfying the first condition are near matching sequences.
Proof. TODO $\square$

Claim 2. All sequences satisfying the second condition are near matching sequences.
Proof. TODO $\square$

Further proof of the conjecture needs more details in the third condition. However we can compute the number of near matching sequences satisfying either the first or the second condition.

One sequence with no Y is near matching sequence if $n > 1$, $n$ sequences with one Y are near matching sequences. Now let compute all other near matching sequences satisfying the first condition. We can choose any $d$ between $1$ and $n - 1$, inclusive. Further we choose residue of the leftmost Y position modulo $d$ (any $r$ between $0$ and $d - 1$ inclusive). Then for the case of all distances equal to $d$ we choose only leftmost and rightmost positions of Y among $\left\lceil\frac{n - r}{d}\right\rceil$ possible ones in $\binom{\left\lceil\frac{n - r}{d}\right\rceil}{2}$ ways. If we have a distance other than $d$ it is the same as we choose two more borders for missing Y's. Here we need to have at least three Y's. And there are some cases: leftmost Y is single (i. e. has distance more than $d$ to the next one), right Y is single, neither leftmost nor rightmost Y is single. Two first cases give $\binom{\left\lceil\frac{n - r}{d}\right\rceil - 1}{3}$ ways each and the last one gives $\binom{\left\lceil\frac{n - r}{d}\right\rceil - 1}{4}$ ways. (Minus one here means that firstly we decrease the number of possible positions for the reason to insert N between left and right parts of Y's.) So we have $$[n > 1] + n + \sum_{d = 1}^{n - 1}\sum_{r = 0}^{d - 1}\binom{\left\lceil\frac{n - r}{d}\right\rceil}{2} + 2\binom{\left\lceil\frac{n - r}{d}\right\rceil - 1}{3} + \binom{\left\lceil\frac{n - r}{d}\right\rceil - 1}{4}$$ in total for the number of near matching sequences satisfying the first condition.

For the second condition we have the same situation with $d$ and $r$. Further there are two cases: there are at least four Y's in $2\overline{\binom{\left\lceil\frac{n - r}{d}\right\rceil - 2}{4}}$ ways (where $\overline{\binom{n}{k}}$ means $\binom{\max\{\,0, n\,\}}{k}\,\}$) to choose left or right side, positions of the single Y's and the range of other Y's (minus two means that we decrease the number of possible positions to insert later two n's), or there are exactly three Y's. To compute the number of ways in the last case it is better to remove earlier counted triples of Y's giving equal distances and triples of Y's and triples of Y's on two non-equal, but one-side divisible distances and then add all triples of Y's: $$\binom{n}{3} + \sum_{d = 1}^{n - 1}\sum_{r = 0}^{d - 1} 2\binom{\left\lceil\frac{n - r}{d}\right\rceil - 2}{4} - \binom{\left\lceil\frac{n - r}{d}\right\rceil - 2}{1} - 2\binom{\left\lceil\frac{n - r}{d}\right\rceil - 2}{2}.$$

Just to show how many near matching sequences are counted and not counted I give the following table: $$\begin{array}{c|c|c|c} n & F_1(n) & \text{The first condition} & \text{The second condition}&\text{Remaning}\\\hline 1 & 1 & 1 & 0 & 0 \\ 2 & 4 & 4 & 0 & 0 \\ 3 & 8 & 8 & 0 & 0 \\ 4 & 16 & 16 & 0 & 0 \\ 5 & 32 & 32 & 0 & 0 \\ 6 & 63 & 59 & 4 & 0 \\ 7 & 120 & 106 & 14 & 0 \\ 8 & 216 & 175 & 40 & 1 \\ 9 & 368 & 280 & 88 & 0 \\ 10 & 596 & 425 & 170 & 1 \\ 11 & 930 & 627 & 300 & 3 \\ 12 & 1387 & 885 & 494 & 8 \\ 13 & 2009 & 1235 & 768 & 6 \\ 14 & 2818 & 1664 & 1142 & 12 \\ 15 & 3872 & 2207 & 1646 & 19 \\ 16 & 5191 & 2869 & 2292 & 30 \\ 17 & 6850 & 3687 & 3122 & 41 \\ 18 & 8838 & 4642 & 4148 & 48 \\ 19 & 11310 & 5806 & 5428 & 76 \\ 20 & 14209 & 7142 & 6964 & 103 \\ 21 & 17687 & 8731 & 8826 & 130 \\ 22 & 21719 & 10555 & 11020 & 144 \\ 23 & 26512 & 12667 & 13628 & 217 \\ 24 & 31938 & 15033 & 16636 & 269 \\ \end{array}$$

It is easy to see that uncertain third condition doesn't give many new near matching sequences. More interesting is that this sequence is not non-decreasing.

To compute the asymptotic of the number of near matching sequences we can notice that there are at most $\binom{n}{4}$ sequences satisfying the third condition if the conjecture is true. Therefore if the conjecture is true then there are $F_1(n)$ near matching sequences such that $$g(n) \le F_1(n) \le g(n) + \binom{n}{4}$$ where $$g(n) = [n > 1] + n + \binom{n}{3} + \sum_{d = 1}^{n - 1}\sum_{r = 0}^{d - 1}\binom{\left\lceil\frac{n - r}{d}\right\rceil}{2} + 2\binom{\left\lceil\frac{n - r}{d}\right\rceil - 1}{3} + \binom{\left\lceil\frac{n - r}{d}\right\rceil - 1}{4} + \\ 2\overline{\binom{\left\lceil\frac{n - r}{d}\right\rceil - 2}{4}} - \overline{\binom{\left\lceil\frac{n - r}{d}\right\rceil - 2}{1}} - 2\overline{\binom{\left\lceil\frac{n - r}{d}\right\rceil - 2}{2}}\\ =o(n^4) + \sum_{d = 1}^{n - 1}\sum_{r = 0}^{d - 1}\binom{\left\lceil\frac{n - r}{d}\right\rceil}{2} + 2\binom{\left\lceil\frac{n - r}{d}\right\rceil - 1}{3} + \binom{\left\lceil\frac{n - r}{d}\right\rceil - 1}{4} + \\ 2\overline{\binom{\left\lceil\frac{n - r}{d}\right\rceil - 2}{4}} - \overline{\binom{\left\lceil\frac{n - r}{d}\right\rceil - 2}{1}} - 2\overline{\binom{\left\lceil\frac{n - r}{d}\right\rceil - 2}{2}}.$$

Let's find asymptotic of $\sum_{d = 1}^{n - 1}\sum_{r = 0}^{d - 1}\overline{\binom{\left\lceil\frac{n - r}{d}\right\rceil - a}{b}}$ for constant integers $a$ and $b$ ($a \ge 0$, $1 \le b \le 4$). $$h(n, a, b) = \sum_{d = 1}^{n - 1}\sum_{r = 0}^{d - 1}\overline{\binom{\left\lceil\frac{n - r}{d}\right\rceil - a}{b}}\\ = \sum_{d = 1}^{n - 1}\sum_{r = 0}^{d - 1}[n - r > (a + b - 1)d]\binom{\left\lceil\frac{n - r}{d}\right\rceil - a}{b}\\ = \sum_{d = 1}^{n - 1}\sum_{r = 0}^{\min\{\,d - 1, n - (a + b - 1)d - 1\,\}}\binom{\left\lceil\frac{n - r}{d}\right\rceil - a}{b}.$$

Therefore $$\sum_{d = 1}^{n - 1}\sum_{r = 0}^{\min\{\,d - 1, n - (a + b - 1)d - 1\,\}}\binom{\frac{n - r}{d} - a}{b} \le h(n, a, b) < \sum_{d = 1}^{n - 1}\sum_{r = 0}^{\min\{\,d - 1, n - (a + b - 1)d - 1\,\}}\binom{\frac{n - r}{d} + 1 - a}{b},\\ \sum_{d = 1}^{n - 1}\sum_{r = 0}^{\min\{\,d - 1, n - (a + b - 1)d - 1\,\}}\binom{\frac{n - r}{d} - a}{b} \le h(n, a, b) < \sum_{d = 1}^{n - 1}\sum_{r = 0}^{\min\{\,d - 1, n - (a + b - 1)d - 1\,\}}\binom{\frac{n - r}{d} + 1 - a}{b}.$$

For $b \le 3$: $$h(n, a, b) < \sum_{d = 1}^{n - 1}\sum_{r = 0}^{\min\{\,d - 1, n - (a + b - 1)d - 1\,\}}\binom{\frac{n - r}{d} + 1 - a}{b} \le \sum_{d = 1}^{n - 1}d\binom{\frac{n}{d} + 1 - a}{b} \le\\ \sum_{d = 1}^{n - 1}d\binom{\frac{n}{d} + 1 - a}{b} = \sum_{d = 1}^{n - 1} O\left(d\frac{n^b}{d^b}\right) = \sum_{d = 1}^{n - 1} O(n^b d^{1 - b}) = o(n^4).$$

And for $b = 4$ we find both upper and lower bounds. Let's start from the lower one. $$h(n, a, 4) \ge \sum_{d = 1}^{n - 1}\sum_{r = 0}^{\min\{\,d - 1, n - (a + 4 - 1)d - 1\,\}}\binom{\frac{n - r}{d} - a}{4} >\\ \sum_{d = 1}^{\left\lfloor\frac{n - 1}{a + 3}\right\rfloor}\sum_{r = 0}^{\min\{\,d - 1, n - (a + 3)d - 1\,\}}\binom{\frac{n}{d} - 1 - a}{4} = \\ \sum_{d = 1}^{\left\lfloor\frac{n - 1}{a + 3}\right\rfloor}\sum_{r = 0}^{d - 1}\frac{1}{24}\left(n^4d^{-4} + O(n^3 d^{-3}) + O(n^2 d^{-2}) + O(n d^{-1}) + O(1)\right) = \\ \sum_{d = 1}^{\left\lfloor\frac{n - 1}{a + 3}\right\rfloor}\frac{1}{24}\left(n^4d^{-3} + O(n^3 d^{-2}) + O(n^2 d^{-1}) + O(n) + O(d)\right) \sim \\ \frac{\zeta(3)}{24}n^4 \approx 0.05n^4,$$ where $\zeta(\cdot)$ is Riemann zeta-function. And we continue with the upper bound. $$h(n, a, 4) < \sum_{d = 1}^{n - 1}\sum_{r = 0}^{\min\{\,d - 1, n - (a + 4 - 1)d - 1\,\}}\binom{\frac{n - r}{d} + 1 - a}{4} \le\\ \sum_{d = 1}^{n - 1}\sum_{r = 0}^{\min\{\,d - 1, n - (a + 3)d - 1\,\}}\binom{\frac{n}{d} + 1 - a}{4} = \\ \sum_{d = 1}^{n - 1}\sum_{r = 0}^{\min\{\,d - 1, n - (a + 3)d - 1\,\}}\frac{1}{24}\left(n^4d^{-4} + O(n^3 d^{-3} + O(n^2 d^{-2} + O(n d^{-1}) + O(1)\right) \le\\ \sum_{d = 1}^{n - 1}\sum_{r = 0}^{d - 1}\frac{1}{24}\left(n^4d^{-4} + \max\{\,0, O(n^3 d^{-3} + O(n^2 d^{-2} + O(n d^{-1}) + O(1)\,\}\right) \sim\\ \frac{\zeta(3)}{24}n^4 \approx 0.05n^4\\$$

Therefore $$h(n, a, 4) \sim \frac{\zeta(3)}{24}n^4 \approx 0.05n^4.$$

Now we note that $\binom{n}{k} = \overline{\binom{n}{k}}$ if $n \ge k$ and return to $g(n)$. $$g(n) = o(n^4) + \sum_{d = 1}^{n - 1}\sum_{r = 0}^{d - 1}\binom{\left\lceil\frac{n - r}{d}\right\rceil}{2} + 2\binom{\left\lceil\frac{n - r}{d}\right\rceil - 1}{3} + \binom{\left\lceil\frac{n - r}{d}\right\rceil - 1}{4} + \\ 2\overline{\binom{\left\lceil\frac{n - r}{d}\right\rceil - 2}{4}} - \overline{\binom{\left\lceil\frac{n - r}{d}\right\rceil - 2}{1}} - 2\overline{\binom{\left\lceil\frac{n - r}{d}\right\rceil - 2}{2}} \sim\\ \frac{3\zeta(3)}{24}n^4 = \frac{\zeta(3)}{8}n^4 \approx 0.15 n^4.$$

Since $$g(n) \le F_1(n) \le g(n) + \binom{n}{4}$$ we conclude that $$F_1(n) = \Theta(n^4).$$

This estimation doesn't match the earlier computed table, but 24 is not so big number.