# $k$-substrings of a binary string

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.

• Have you calculated the number of equivalence classes for a few small values of $k$, and then consulted the Online Encyclopedia of Integer Sequences? – Gerry Myerson Oct 18 '18 at 23:02
• Isn't that A045623? – Bullet51 Oct 19 '18 at 4:50
• @Bullet51 yes it is – DavitS Oct 19 '18 at 4:57
• @GerryMyerson thanks Gerry for the Encyclopedia, didn't know about it, found very helpful info – DavitS Oct 19 '18 at 6:30

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.