Tutte seminar - Jason Gao

Locally Restricted Compositions

Abstract:

A composition of n is a finite list of positive integers c₁,...,c_k (called the parts) that sum to n. A locally restricted composition is a composition in which parts within a given distance of each other are required to satisfy some conditions. Carlitz compositions, in which adjacent parts are distinct, are a classic example of locally restricted compositions. To rule out integer partitions, we impose a recurrence condition. We survey some recent results about the asymptotic behavior of locally restricted compositions including normal distribution of some parameters, the largest part, and probability of being gap-free. Combinatorial arguments, generating functions and infinite transfer matrices are used. The talk is based on joint works with Bender and Canfield.