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.

  • 2
    $\begingroup$ Have you calculated the number of equivalence classes for a few small values of $k$, and then consulted the Online Encyclopedia of Integer Sequences? $\endgroup$ – Gerry Myerson Oct 18 '18 at 23:02
  • $\begingroup$ Isn't that A045623? $\endgroup$ – Bullet51 Oct 19 '18 at 4:50
  • $\begingroup$ @Bullet51 yes it is $\endgroup$ – DavitS Oct 19 '18 at 4:57
  • $\begingroup$ @GerryMyerson thanks Gerry for the Encyclopedia, didn't know about it, found very helpful info $\endgroup$ – 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.


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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