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.
4
- 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– Gerry Myerson2018-10-18 23:02:50 +00:00Commented Oct 18, 2018 at 23:02
- $\begingroup$ Isn't that A045623? $\endgroup$LeechLattice– LeechLattice2018-10-19 04:50:57 +00:00Commented Oct 19, 2018 at 4:50
- $\begingroup$ @Bullet51 yes it is $\endgroup$DavitS– DavitS2018-10-19 04:57:21 +00:00Commented Oct 19, 2018 at 4:57
- $\begingroup$ @GerryMyerson thanks Gerry for the Encyclopedia, didn't know about it, found very helpful info $\endgroup$DavitS– DavitS2018-10-19 06:30:34 +00:00Commented Oct 19, 2018 at 6:30
Add a comment |
1 Answer
$\begingroup$ $\endgroup$
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.
