On the number of distinct <i>k</i>-decks: Enumeration and bounds

The \begin{document}$ k $\end{document} -deck of a sequence is defined as the multiset of all its subsequences of length \begin{document}$ k $\end{document} . Let \begin{document}$ D_k(n) $\end{document} denote the number of distinct \begin{document}$ k $\end{document} -decks for binary sequences of length \begin{document}$ n $\end{document} . For binary alphabet, we determine the exact value of \begin{document}$ D_k(n) $\end{document} for small values of \begin{document}$ k $\end{document} and \begin{document}$ n $\end{document} , and provide asymptotic estimates of \begin{document}$ D_k(n) $\end{document} when \begin{document}$ k $\end{document} is fixed. Specifically, for fixed \begin{document}$ k $\end{document} , we introduce a trellis-based method to compute \begin{document}$ D_k(n) $\end{document} in time polynomial in \begin{document}$ n $\end{document} . We then compute \begin{document}$ D_k(n) $\end{document} for \begin{document}$ k \in \{3,4,5,6\} $\end{document} and \begin{document}$ k \leqslant n \leqslant 30 $\end{document} . We also improve the asymptotic upper bound on \begin{document}$ D_k(n) $\end{document} , and provide a lower bound thereupon. In particular, for binary alphabet, we show that \begin{document}$ D_k(n) = O\bigl(n^{(k-1)2^{k-1}+1}\bigr) $\end{document} and \begin{document}$ D_k(n) = \Omega(n^k) $\end{document} . For \begin{document}$ k = 3 $\end{document} , we moreover show that \begin{document}$ D_3(n) = \Omega(n^6) $\end{document} while the upper bound on \begin{document}$ D_3(n) $\end{document} is \begin{document}$ O(n^9) $\end{document} .