In this article, we analyse the joint distribution of some given set of patterns in fundamental combinatorial structures such as words and random walks (directed lattice paths on ℤ²). Our method relies on a vectorial generalization of the classical kernel method, and on a matricial generalization of the autocorrelation polynomial (thus extending the univariate case of Guibas and Odlyzko). This gives access to the multivariate generating functions, for walks, meanders (walks constrained to be above the x-axis), and excursions (meanders constrained to end on the x-axis). We then demonstrate the power of our methods by obtaining closed-form expressions for an infinite family of models, in terms of simple combinatorial quantities. Finally, we prove that the joint distribution of the patterns in walks/bridges/excursions/meanders satisfies a multivariate Gaussian limit law.

Abstract In this article we develop a vectorial kernel method—a powerful method which solves in a unified framework all the problems related to the enumeration of words generated by a pushdown automaton. We apply it for the enumeration of lattice paths that avoid a fixed word (a pattern), or for counting the occurrences of a given pattern. We unify results from numerous articles concerning patterns like peaks, valleys, humps, etc., in Dyck and Motzkin paths. This refines the study by Banderier and Flajolet from 2002 on enumeration and asymptotics of lattice paths: we extend here their results to pattern-avoiding walks/bridges/meanders/excursions. We show that the autocorrelation polynomial of this forbidden pattern, as introduced by Guibas and Odlyzko in 1981 in the context of rational languages, still plays a crucial role for our algebraic languages. En passant, our results give the enumeration of some classes of self-avoiding walks, and prove several conjectures from the On-Line Encyclopedia of Integer Sequences. Finally, we also give the trivariate generating function (length, final altitude, number of occurrences of the pattern p), and we prove that the number of occurrences is normally distributed and linear with respect to the length of the walk: this is what Flajolet and Sedgewick call an instance of Borges’s theorem.

A polycube is a face-connected set of cubical cells on ℤ3. To-date, no formulae enumerating polycubes by volume (number of cubes) or perimeter (number of empty cubes neighboring the polycube) are known. We present a few formulae enumerating polycubes with a fixed deviation from the maximum possible perimeter.