Problem of the Week
Hilton Memorial Lecture
The study of partitions and compositions (i.e., ordered partitions) of integers goes back centuries and has applications in various areas within and outside of mathematics. Partition analysis is full of beautiful—and sometimes surprising—identities.
As an example (and the first motivation for this study), I mention compositions (λ1, λ2, λ3) of an integer m (i.e., m = λ1 + λ2 + λ3 and all λj in Z≥0) that satisfy the six “triangle conditions”
λπ(1) + λπ(2) ≥ λπ(3)
for every permutation π in S3 . George Andrews proved in the 1970's that the number Δ(m) of such compositions of m is encoded by the generating function
Σm ≥ 0 Δ(m) qm = 1/(1-q2)2(1-q) .
More generally, for fixed given integers a1, a2, …, an, we call a composition λ1 + λ2 + … + λn symmetrically constrained if it satisfies each of the the n! constraints
Σj=1n aj λπ(j) ≥ 0
for every permutation π in Sn . I will show how to compute the generating functions of these compositions, combining methods from partition theory, permutation statistics, and polyhedral geometry.
This is joint work with Ira Gessel, Sunyoung Lee, and Carla Savage.