Discrete CATS Seminar
####
**
**#####
U N I V E R S I T Y
O F
K E N T U C K Y

DISCRETE
CATS
SEMINAR

WHERE CATS =
COMBINATORICS,
ALGEBRA,
TOPOLOGY
&
STATISTICS!

845 PATTERSON OFFICE TOWER

FALL 2009

##
"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.