Block-connected set partitions

This paper introduces two statistics on set partitions, namely connector and circular connector. If B 1 / … / B k is a partition of { 1 , … , n } with k > 1 blocks, then a connector is an ordered pair ( c , c + 1 ) satisfying c ∈ B i , c + 1 ∈ B i + 1 , i = 1 , … , n − 1 . A circular connector is a connector when the blocks of a partition are arranged on a circle. We concentrate on the enumeration of partitions according to the two statistics, and certain variations thereof. Our results include several nice generating functions and explicit formulas. We also establish connections between connected partitions and words over a finite alphabet, and random walks on a square lattice.