# The Umbral Transfer-Matrix Method. IV. Counting Self-Avoiding Polygons and Walks

### Abstract

This is the fourth installment of the five-part saga on the Umbral Transfer-Matrix method, based on Gian-Carlo Rota's seminal notion of the umbra. In this article we describe the Maple packages *USAP*, *USAW*, and *MAYLIS*. *USAP* automatically constructs, for any specific $r$, an Umbral Scheme for enumerating, according to perimeter, the number of self-avoiding polygons with $\leq 2r$ horizontal edges per vertical cross-section. The much more complicated *USAW* does the analogous thing for self-avoiding walks. Such Umbral Schemes enable counting these classes of self-avoiding polygons and walks in polynomial time as opposed to the exponential time that is required by naive counting. Finally *MAYLIS* is targeted to the special case of enumerating classes of saps with at most two horizontal edges per vertical cross-section (equivalently column-convex polyominoes by perimeter), and related classes. In this computationally trivial case we can actually *automatically* solve the equations that were *automatically* generated by *USAP*. As an example, we give the first *fully computer-generated* proof of the celebrated Delest-Viennot result that the number of convex polyominoes with perimeter $2n+8$ equals $(2n+11)4^n-4(2n+1)!/n!^2$.