  A sample of n generic points in the xy-plane defines a permutation that
relates their ranks along the two axes. Every subset of k points similarly
defines a pattern, which occurs in that permutation. The number of occurrences
of small patterns in a large permutation arises in many areas, including
nonparametric statistics. It is therefore desirable to count them more
efficiently than the straightforward ~O(n^k) time algorithm.
  This work proposes new algorithms for counting patterns. We show that all
patterns of order 2 and 3, as well as eight patterns of order 4, can be counted
in nearly linear time. To that end, we develop an algebraic framework that we
call corner tree formulas. Our approach generalizes the existing methods and
allows a systematic study of their scope.
  Using the machinery of corner trees, we find twenty-three independent linear
combinations of order-4 patterns, that can be computed in time ~O(n). We also
describe an algorithm that counts one of the remaining 4-patterns, and hence
all 4-patterns, in time ~O(n^(3/2)).
  As a practical application, we provide a nearly linear time computation of a
statistic by Yanagimoto (1970), Bergsma and Dassios (2010). This statistic
yields a natural and strongly consistent variant of Hoeffding's test for
independence of X and Y, given a random sample as above. This improves upon the
so far most efficient ~O(n^2) algorithm.
