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. 



$k$-substrings of a binary string
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.


