33 minutes ago · Science · hide

A word is universal if it contains every permutation of its alphabet as a subsequence: the letters must appear in order, but gaps are allowed. For example, you can find all six permutations of the digits 1, 2, and 3 inside the string 1231213. Not all permutations can be found as a contiguous substring—that would be a superpermutation—but all can be found as a subsequence. The word 01234567890123456780293451670823451960782134506978231405678213904567823109456782301 is universal for the set of 10 digits. This word was discovered some time ago, but Jason Davies has recently proved that this the smallest universal word on 10 digits. It has 83 characters, and Davies proved that no word of 82 characters is universal over the digits. See his paper here. I’m surprised that all 10! = 3,628,800 permutations of 10 digits can be found as subsequences of such a relatively short word. Universal words, or supersequences, are easily confused with superpermutations. See OEIS sequences A062714 and…

Commenting on Bubbles has been removed. Why? If you want to talk about this post, write to the author, use the comments on their blog if it has them, or reply with a "RE:" post on your own blog. Suggestions? feedback@bubbles.town