ABSTRACT
It is a capital mistake to theorize before one has data.
–Sherlock Holmes (from A Scandal in Bohemia)
In this chapter, we discuss some of the data arrangements that gave rise to the idea
of this book, data and its structures that cannot be properly characterized with the
usual assumptions we make in the analysis on uniform models. We start with re-
stricted permutations of a particular type. We demonstrate several ways of obtaining
combinatorial information about such permutations, culminating in the use of finite
automata to recognize these special data arrangements. Then, we consider permu-
tations “enriched” by repetitions, or in another word, multisets, again looking for
algorithmically related features. The last few sections consider trees laden with data;
most are binary trees.