"Symmetrically constraint compositions"

Matthias Beck
San Francisco State University

Thursday, December 10, 2009
1:00 pm
845 POT

Abstract:

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 our study), we mention compositions (x_1, x_2, x_3) of an integer m (i.e., m = x_1 + x_2 + x_3 and all x_j are nonnegative integers) that satisfy the six "triangle conditions"

x_p(1) + x_p(2) + x_p(3) for every permutation p in S_3.

George Andrews proved in the 1970's that the number D(m) of such compositions of m is encoded by the generating function

sum_{ m >= 0 } D(m) q^m = 1/(1-q^2)^2(1-q) .

More generally, for fixed given integers a_1, a_2, ..., a_n, we call a composition x_1 + x_2 + ... + x_n symmetrically constrained if it satisfies each of the the n! constraints

a_1 x_p(1) + ... + a_n x_p(n) >= 0 for every permutation p in S_n.

We 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.