Abstract
In this paper, we focus on shape partitions. We show that for any fixed k, one can symbolically characterize the shape partition on a k × n rectangular grid by a context-free grammar. We explicitly give this grammar for k = 2 and k = 3 (for k = 1, this corresponds to compositions of integers). From these grammars, we deduce the number of shape partitions for the k × n rectangular grids for k ∈ {1, 2, 3} and every n, as well as the limiting Gaussian distribution of the number of connected components. This also enables us to randomly and uniformly generate shape partitions of large size.