In this paper, we study the properties of k-omnisequences of length n, defined to be strings of length n that contain all strings of smaller length k embedded as (not necessarily contiguous) subsequences. We start by proving an elementary result that relates our problem to the classical coupon collector problem. After a short survey of relevant results in coupon collection, we focus our attention on the number M of strings (or words) of length k that are not found as subsequences of an n string, showing that there is a gap between the probability threshold for the emergence of an omnisequence and the zero-infinity threshold for E(M).
| Identifer | oai:union.ndltd.org:ETSU/oai:dc.etsu.edu:etsu-works-16066 |
| Date | 01 June 2013 |
| Creators | Abraham, Sunil, Brockman, Greg, Sapp, Stephanie, Godbole, Anant P. |
| Publisher | Digital Commons @ East Tennessee State University |
| Source Sets | East Tennessee State University |
| Detected Language | English |
| Type | text |
| Source | ETSU Faculty Works |
Page generated in 0.0019 seconds