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

DOI10.1016/0097-3165(76)90057-1MaRDI QIDQ1228615zbMATH OpenOpenAlexFDO

Authors 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

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

Cites work

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

Cited in

(13)

• Shortest prefix strings containing all subset permutations
• Lower bounds on the lengths of node sequences in directed graphs
• Lower bounds for superpatterns and universal sequences
• Fixing monotone Boolean networks asynchronously
• Skip letters for short supersequence of all permutations
• A note on universal and canonically coloured sequences
• On a conjecture of H. Gupta
• Preferential arrangement superpatterns
• Containing all permutations
• Synchronizing Boolean networks asynchronously
• An asymptotically tight lower bound for superpatterns with small alphabets
• The tree-child network inference problem for line trees and the shortest common supersequence problem for permutation strings
• Some results on superpatterns for preferential arrangements

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1228615)