A Snappy Proof That 123-Avoiding Words are Equinumerous with 132-Avoiding Words

Doron ZEILBERGER ^{1}

Define a mapping F on a word w in the alphabet {1, 2, …, n} recursively as follows. If w is empty, then F (w) := w. Otherwise, i := w_{1}, and let W be the word obtained from w by first beheading it, and then replacing all letters larger than i + 1 by i + 1, and let s be the sub-sequence of w obtained by deleting the letters ≤ i. Let s̄ be the reverse of s. Let V := F (W), and let U be the word obtained from V by replacing (in order) the letters that are i + 1 by the members of s̄. Finally let F (w) := iU.

F is an involution that sends 123-avoiding words to 132-avoiding ones, and vice versa. This follows from the fact that s above in then non-increasing and non-decreasing respectively. Hence, for any vector of non-negative integers (a_{1}, …, a_{n}), amongst the (a_{1} + … + a_{n})!/(a_{1}! ⋯ a_{n}!) words with a_{1} 1’s, …, a_{n} n’s, the number of those that avoid the pattern 123 equals the number of those that avoid 132, a result first proved by Albert, Aldred, Atkinson, Handley and Holton (Europ. J. Comb. 22 (2001), 1021-1031). For permutations (i.e. a_{1} = … = a_{n} = 1), F coincides with the classical bijection of Rodica Simion and Frank Schmidt (Europ. J. Comb. 6 (1985), 386-406), but my recursive formulation (that only works because we have the extra elbow-room of words!) is more transparent.

It also follows that we have a quick recurrence that enables us to compute the number of such words, let’s call it A(a_{1}, …, a_{n}).

A(a_{1}, …, a_{n}) = ∑_{i=1}^{n} A(a_{1}, …, a_{i−1}, a_{i} − 1, a_{i+1} + … + a_{n}) .

My brilliant student, Lara Pudwell, is currently exploring extensions and ramifications.

1 Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen

Rd., Piscataway, NJ 08854-8019, USA. zeilberg at math dot rutgers dot edu , http://www.math.rutgers.edu/~zeilberg/.

April 11, 2005. Exclusively published in the Personal Journal of Ekhad and Zeilberger http://www.math.rutgers.edu/~zeilberg/pj.html . Supported in part by the NSF. Accompanied by Maple program http://www.math.rutgers.edu/~zeilberg/tokhniot/A123.