Knuth and Me (Guest Post by Sergey Kitaev)

Guest post by Sergey Kitaev, a very good colleague of mine from the combinatorics group at Reykjavík University.

To show the significance of Donald Knuth in my life, it would probably be enough to indicate that he introduced in 1969 the area of “permutation patterns” which is the field of my main research interest in combinatorics that I’m dealing with almost every day. However, while thinking on the subject, it comes to mind the personal communications with Knuth at Mittag-Leffler Institute at the beginning of 2005. In particular, after attending my talk on partially ordered generalized patterns, Knuth decided to include a result of mine in volume 4 of “Art of computer programming.” It is remarkable that Knuth was collecting information for this volume for over 40 years! However, this was not the thing I was offered Knuth’s famous $1.28 reward for. Unlike most other rewards, this one was not directly related to mathematics – I let Knuth know the middle name of Alexandr Kostochka that he recorded in his name database both in English and Russian (Knuth is able of writing things in Russian which he learned in college, and I find this to be impressive). In any case, stupidly enough, I refused taking the check from Knuth, which would be a nice souvenir as I realized later on; I simply told Knuth that it was a great pleasure for me to be helpful for him …

Addendum. A (permutation) pattern is a permutation of a totally ordered set. An occurrence of a pattern P in a permutation p is a subsequence of letters of p whose relative order is the same as that of the letters in P. As an example, the permutation 461352 has three occurrences of the pattern 321, namely the subsequences 432, 632 and 652.

The initial motivation for studying pattern avoiding permutations came from its connections with container data types in computer science. In 1969 Don Knuth pioneered this work by showing that the stack sortable permutations are exactly the 231-avoiding permutations.