1. On the number of distinct k-decks: Enumeration and bounds
- Author
-
Alexander Vardy, Johan Chrisnata, Hanwen Yao, Sankeerth Rao Karingula, Eitan Yaakobi Yao, and Han Mao Kiah
- Subjects
Polynomial (hyperelastic model) ,Combinatorics ,Multiset ,Algebra and Number Theory ,Computer Networks and Communications ,Applied Mathematics ,Enumeration ,Discrete Mathematics and Combinatorics ,Microbiology ,Omega ,Upper and lower bounds ,Binary alphabet ,Mathematics - Abstract
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} .
- Published
- 2023