Combinatorics of Permutations, 2nd Edition

232 Combinatorics of Permutations, Second Edition

1 2 3

4 5 6

7 8 9

FIGURE 5.2

The chosen squares lead to the subword 48526, then to p(S) = 25314.

the left of that 3-superpattern, so we certainly have all patterns that

start with 1 or 4. One then verifies that the remaining 12 patterns are

also present. This construction is due to Rebecca Smith. Note that

computer data proves that there is no 4-superpattern of length 8.

10. This result was proved in [125]. The authors proved the upper bound

constructively as follows. Let us consider an m × n chess board, in

which, like in real chess, the bottom right corner square is white. Let us

pick a subset S of t squa ...