On the Number of Distinct k-Decks: Enumeration and Bounds
Johan Chrisnata, Han Mao Kiah, Sankeerth Rao Karingula, Alexander Vardy, Eitan Yaakobi, Hanwen Yao · 2019
The k-deck of a sequence is defined to be the multiset of all its subsequences of length k and let Dk(n) denote the number of distinct k-decks for binary sequences of length n. In this paper, we determine the exact value of Dk(n) for small values of k and n and provide asymptotic estimates of Dk(n) when k is fixed.Specifically, for fixed k, we provide a trellis-based method to compute Dk(n) in time polynomial in n. We then compute Dk(n) for k ∈ {3, 4, 5, 6} and k ≤ n ≤ 30. We also improve the asymptotic upper bound on Dk(n) and in particular, show ${D_k}(n) = O\left( {{n^{(k - 1){2^{k - 1}} + 1}}} \right)$. For the specific case when k = 3, we show D3(n) = Ω(n6) while the upper bound states that D3(n) = O(n9).