$k$-substrings of a binary string

Question

Let $k > 1,$ and $a=a_1a_2...a_{2k-1}$ be a binary string, i.e. $a_i\in \{0,1\}$. Consider contiguous substrings of $a$ of length $k (k-$substrings$): b_i := a_ia_{i+1}...a_{i+k-1}, 1\leq i\leq k$. Weight of a string $x$, $w(x)$, is the number of ones in the string. For the given string $a$ consider the multiset of weights of its $k$-substrings: $W(a) = \{w(b_1), w(b_2), ...,w(b_k)\}$. For example if $k=3$ and $a=10100$, then $W(a)=\{w(101),w(010),w(100)\}=\{1,1,2\}.$ Consider the following equivalence relation for strings of length $2k-1:x\sim y$ if and only if $W(x)=W(y)$. How many equivalence classes are there? For example if $k=2$, the answer is $5$. An upper bound for the answer would also be helpful. A trivial upper bound would be $\left(\!\!{2k\choose k}\!\!\right)$, but we count many not valid multisets there, for example there are no multisets that contain both $k$ and $0$ together.

Answer 1

The equivalence classes of multisets may be described by integer sequences with length $k$ satisfying the following property:

$a_n ≤ k$

$a_n ≥ 0$

$a_{n} ≤ a_{n+1} ≤ a_{n} + 1$ for all $1≤n≤k-1$

Denote the number of such sequences $b_k$. We have $b_{k+1}= 2b_k + 2^{k-1}$, as the $2b_k$ part comes from extending the sequences $a_n$ of length $k$ by $a_k+1$ or $a_k$, and the $2^{k-1}$ part comes from sequences ending with $...,k+1,k+1$, which does not have such extension.