Ternary Bracketing Problem from the Theory of Formal Languages

摘要

Whether or not there exists a sizable number of permutations that can not begenerated in the following way is addressed: put the numbers 1 to n in a row, and take two adjacent nonempty 'segments', interchange the two segments, keeping order inside each of them; then proceed in the same way independently within each segment or within the set of (as yet) unused elements, and do this as far as one likes. The permutations that can be obtained in this way are called k permutations. The number of these k permutations is not actually derived, but an upper bound is given instead by studying a generalization, of Catalan numbers.