A lower bound on the length of a sequence containing all permutations as subsequences

DOI10.1016/0097-3165(76)90057-1zbMath0333.05003OpenAlexW2079303095MaRDI QIDQ1228615

Daniel J. Kleitman, D. J. Kwiatkowski

Publication date: 1976

Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0097-3165(76)90057-1

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Permutations, words, matrices (05A05) Designs and configurations (05B99)

Related Items (12)

Shortest prefix strings containing all subset permutations ⋮ Skip letters for short supersequence of all permutations ⋮ On a conjecture of H. Gupta ⋮ Synchronizing Boolean networks asynchronously ⋮ An asymptotically tight lower bound for superpatterns with small alphabets ⋮ Fixing monotone Boolean networks asynchronously ⋮ Containing All Permutations ⋮ A Note on Universal and Canonically Coloured Sequences ⋮ Preferential arrangement superpatterns ⋮ Lower bounds on the lengths of node sequences in directed graphs ⋮ Some results on superpatterns for preferential arrangements ⋮ Lower bounds for superpatterns and universal sequences

Cites Work

• Short permutation strings
• On Permutation-Embedding Sequences
• Shortest string containing all permutations

This page was built for publication: A lower bound on the length of a sequence containing all permutations as subsequences