Reconstructing compositions

Discrete Mathematics, 308 (2008), 1524–1530.

We consider the problem of reconstructing compositions of an integer from their subcompositions, which was raised by Raykova (albeit disguised as a question about layered permutations). We show that every composition w of n ≥ 3k+1 can be reconstructed from its set of k-deletions, i.e., the set of all compositions of n-k contained in w. As there are compositions of 3k with the same set of k-deletions, this result is best possible.

Download the paper:

• from the journal (subscription required)
• pdf
• source: zip

Related links:

• The accompanying Maple package, COMPBUILDER.

< back to homepage