On the Number of Distinct k-Decks: Enumeration and Bounds
On the Number of Distinct k-Decks: Enumeration and Bounds
复制标题
DOI：
10.1109/iscit.2019.8905191
复制
发表时间：
2019-09
期刊：
影响因子：
--
通讯作者：
Johan Chrisnata;Han Mao Kiah;Sankeerth Rao;A. Vardy;Eitan Yaakobi;Hanwen Yao
中科院分区：
文献类型：
--
作者：
Johan Chrisnata;Han Mao Kiah;Sankeerth Rao;A. Vardy;Eitan Yaakobi;Hanwen Yao
序列的 k-deck 被定义为长度为 k 的所有子序列的多重集，并令 Dk (n) 表示长度为 n 的二进制序列的不同 k-deck 的数量。在本文中，我们针对 k 和 n 的小值确定 Dk (n) 的精确值，并在 k 固定时提供 Dk(n) 的渐近估计。具体来说，对于固定 k，我们提供一种基于网格的方法来计算 n 中的时间多项式中的 Dk (n)。然后，我们计算 k ∈ {3, 4, 5, 6} 且 k ≤ n ≤ 30 的 Dk (n)。我们还改进了 Dk (n) 的渐近上限，特别是，显示 ${D_k}(n) = O\left( {{n^{(k - 1){2^{k - 1}} + 1}}} \right)$。对于 k = 3 时的具体情况，我们显示 D3(n) = Ω(n6)，而上限表明 D3(n) = O(n9)。
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).