Combinatorics of Permutations, 2nd Edition

310 Combinatorics of Permutations, Second Edition

FIGURE 7.19

A counterexample.

10. The numbers I

n

(1234) are equal to the Motzkin numbers, that is,

I

n

(1234) =

n/2



i=0

C

i



n

2i



.

This result was first proved by Amitaj Regev in [218], who used sym-

metric functions in his argument. A simpler proof is given in [240],

Exercise 7.16.b, but that proof still uses symmetric functions. In recent

years, there are a plethora of results on the subject, that together yield

that I

n

(1234) = M

n

, and do not use symmetric functions. In fact, it is

known that

M

n

= I

n

(2143) = I

n

(1243) = I

n

(1234).

The first of the above three equalities was bijectively proved in [164],

the second