\documentclass[12pt]{article} \textwidth= 6.5in \textheight= 9.0in \topmargin = -20pt \evensidemargin=0pt \oddsidemargin=0pt \headsep=25pt \parskip=10pt \font\smallit=cmti10 \font\smalltt=cmtt10 \font\smallrm=cmr9 \usepackage{amsmath} %\usepackage{maple2e} \usepackage{amssymb} \usepackage{latexsym} %\usepackage{boxedminipage} %\usepackage{epsfig} %\textwidth 6.0in %\textheight 8.5in %\topmargin -0.25in %\oddsidemargin 0.25in %\parskip .1in \newcommand{\Om}{\begin{array}{c}{\Omega}\vspace{-.1cm}\\{\ge}\end{array}} \newcommand{\la}{\lambda} \newcommand{\bof}{\noindent{\bf Proof}} \newcommand{\eof}{\hfill{$\Box$}} \newcommand{\ld}{\left(} \newcommand{\rd}{\right)} \newcommand{\C}{{\mathcal C}} \newtheorem{definition}{Definition} \newtheorem{lemma}{Lemma} \newtheorem{theorem}{Theorem} \newtheorem{proposition}{Proposition} \newtheorem{corollary}{Corollary} \newtheorem{basicrule}{Basic Rule} \newtheorem{omegarule}{Omega Rule} %\title{A Note on Partitions and Compositions Defined by Inequalities} % % %\author{Sylvie Corteel\\ %{CNRS PRiSM, UVSQ}\\ %{45 Avenue des Etats-Unis}\\ %{ 78035 Versailles, France}\\ %{\tt syl@prism.uvsq.fr}\\ %\and %Carla D. Savage %\thanks{Research supported in part by NSF grants DMS-0300034 and INT-0230800}\\ %{Dept. of Computer Science}\\ %{N. C. State University, Box 8206 }\\ %{ Raleigh, NC 27695, USA}\\ %{\tt savage@csc.ncsu.edu} %\and %Herbert S. Wilf\\Department of Mathematics \\University of %%Pennsylvania\\Philadelphia, PA 19104-6395\\ Note on Partitions and Compositions Defined by Inequalities %{\tt wilf@math.upenn.edu} %} \begin{document} \vspace*{-60pt} \centerline{\smalltt INTEGERS: \smallrm ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY \smalltt 5(1) (2005), \#A24} \vskip 50pt \begin{center} {\bf A NOTE ON PARTITIONS AND COMPOSITIONS DEFINED BY INEQUALITIES} \vskip 20pt {\bf Sylvie Corteel}\\ {\smallit 45 Avenue des Etats-Unis, 78035 Versailles, France}\\ {\tt syl@prism.uvsq.fr}\\ \vskip 10pt {\bf Carla D. Savage\footnote{Research supported in part by NSF grants DMS-0300034 and INT-0230800}}\\ {\smallit Department of Computer Science, North Carolina State University, Box 8206, Raleigh, NC 27695, USA}\\ {\tt savage@csc.ncsu.edu}\\ \vskip 10pt {\bf Herbert S. Wilf}\\ {\smallit Department of Mathematics, University of Pennsylvania, Philadelphia, PA 19104-6395, USA}\\ {\tt wilf@math.upenn.edu}\\ \end{center} \vskip 30pt \centerline{\smallit Received: 2/10/05, Revised: 11/1/05, Accepted: 11/3/05, Published: 11/22/05} \vskip 30pt \centerline{\bf Abstract} We \hfil consider \hfil the \hfil problem \hfil of \hfil enumerating \hfil the \hfil %set $S_C$ of nonnegative \hfil integer \hfil sequences \hfil $\lambda =$ \vskip -10pt \noindent $(\lambda_1, \lambda_2, \ldots, \lambda_n)$ satisfying the constraints \begin{equation*} c_{i,1}\lambda_1 + c_{i,2}\lambda_2 + \ldots + c_{i,n}\lambda_n \geq 0, \ \ \ 1 \leq i \leq n, \end{equation*} for a given an $n \times n$ integer matrix $C=[c_{i,j}]$. We show that, in the area of partition and composition enumeration, many familiar sets of linear constraints can be easily handled by a matrix inversion. \pagestyle{myheadings} \markright{\smalltt INTEGERS: \smallrm ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY \smalltt 5 (2005), \#A24\hfill} \thispagestyle{empty} \baselineskip=15pt \vskip 30pt \section*{\normalsize 1. Introduction} For a sequence $\lambda = (\lambda_1, \lambda_2, \ldots, \lambda_n)$ of integers, define the {\em weight} of $\lambda$ to be $|\lambda|=\lambda_1 + \cdots + \lambda_n$. If sequence $\lambda$ of weight $N$ has all parts nonnegative, we call it a {\em composition} of $N$; if, in addition, $\lambda$ is a nonincreasing sequence, we call it a {\em partition} of $N$. Given an $n \times n$ integer matrix $C=[c_{i,j}]$, we consider the set $S_C$ of compositions $\lambda = (\lambda_1, \lambda_2, \ldots, \lambda_n)$ satisfying the constraints \begin{equation} c_{i,1}\lambda_1 + c_{i,2}\lambda_2 + \ldots + c_{i,n}\lambda_n \geq 0, \ \ \ 1 \leq i \leq n. \label{constraints} \end{equation} In \cite{rama}, we gave sufficient conditions for the generating function of $S_{C}$ to have a product form: \begin{equation} F_{C}(q) = \sum_{\la \in S_C} q^{|\la|} = \prod_{j=1}^n \frac{1}{(1-q^{b_j})}, \label{product-form} \end{equation} for some positive integers $b_1, \ldots, b_n$. Specifically, it was shown that if $C$ is an upper triangular matrix with all $c_{i,i}=1$, and if $B=C^{-1}$ has nonnegative entries, then $F_{C}(q)$ is given by (\ref{product-form}), where $b_j$ is the sum of the entries in column $j$ of $B=[b_{i,j}]$. Moreover, it was shown that this provides a natural bijection between the ``partitions'' of $N$ into parts from the multiset $\{b_1, \ldots, b_n\}$ and the compositions of $N$ in $S_C$ given by: \begin{equation} b_1^{m_1}b_2^{m_2} \cdots b_n^{m_n} \leftrightarrow (\la_1, \la_2, \ldots, \la_n), \label{bijection} \end{equation} where $\la_i = \sum_{j=i}^nb_{i,j}m_j$. Consequently, both the generating function for $S_C$ and the bijection can be ``read off'' from $C^{-1}$. This result automatically gives the product form generating functions, as well as the corresponding ``natural bijections'', for all of the following families: \begin{itemize} \item {\em Hickerson partitions} \cite{hickerson} Given a positive integer $r$, the partitions $\la=(\la_1, \ldots, \la_n)$ satisfying $\la_i \geq r\la_{i+1}$ have generating function \[ \prod_{j=1}^n \frac{1}{1-q^{1+r+ \cdots + r^{j-1}}}. \] This follows by inverting the constraint matrix: \begin{equation*} C^{-1} = \left[ \begin{array}{rrrrrrr} 1 & -r & 0 & 0 & 0 & \ldots & 0 \\ 0 & 1 & -r & 0 & 0 & \ldots & 0 \\ 0 & 0 & 1 & -r & 0 & \ldots &0 \\ \vdots & \vdots & \vdots & \vdots & \vdots & \ldots & \vdots \\ 0 & 0 & 0 & 0 & 0 & \ldots & 1 \\ \end{array} \right]^{-1} = \left[ \begin{array}{lllllll} 1 & r & r^2 & r^3 & r^4 & \ldots & r^{n-1}\\ 0 & 1 & r & r^2 & r^3 & \ldots & r^{n-2} \\ 0 & 0 & 1 & r & r^2 & \ldots & r^{n-3} \\ \vdots & \vdots & \vdots & \vdots & \vdots & \ldots & \vdots \\ 0 & 0 & 0 & 0 & 0 & \ldots & 1 \\ \end{array} \right]. \end{equation*} \item {\em Santos' interpretation of Euler} \cite{santos} The number of partitions $\la=(\la_1, \ldots, \la_n)$ of $N$ into $n$ nonnegative parts satisfying the additional constraint $\la_1 \geq \sum_{i=2}^n \la_{i}$, is the same as the number of partitions of $N$ into odd parts in $\{1,3, \ldots, 2n-1\}$. (See next example.) \item {\em Sellers' generalization of Santos} \cite{sellers,sellers2}: The set of partitions $\la=(\la_1, \ldots, \la_n)$ into $n$ nonnegative parts satisfying the additional constraint $\la_1 \geq \sum_{i=2}^n k_i \la_{i}$, for a given sequence of nonnegative integers $(k_2, \ldots, k_n)$ with $k_2 > 0$ has generating function \begin{equation} \frac{1}{(1-q)(1-q^{k_2+1}) (1-q^{k_2+k_3+2}) (1-q^{k_2+k_3+k_4+3}) \cdots (1-q^{k_2+k_3+ \cdots + k_n+n-1})}. \label{sellers-gf} \end{equation} This follows because the constraint matrix has the form \[ C = \left[ \begin{array}{rrrrrrr} 1 & -k_2 & -k_3 & -k_4 & -k_5 & \ldots & -k_n\\ 0 & 1 & -1 & 0 & 0 & \ldots & 0 \\ 0 & 0 & 1 & -1 & 0 & \ldots & 0 \\ \vdots & \vdots & \vdots & \vdots & \vdots & \ldots & \vdots \\ 0 & 0 & 0 & 0 & 0 & \ldots & 1 \\ \end{array} \right], \] and its inverse is \[ C^{-1} = \left[ \begin{array}{ccccccc} 1 & k_2 & k_2+k_3 & k_2+k_3+k_4 & k_2+k_3+k_4+k_5 & \ldots & k_2+ \cdots+ k_n\\ 0 & 1 & 1 & 1 & 1 & \ldots & 1 \\ 0 & 0 & 1 & 1 & 1 & \ldots & 1 \\ \vdots & \vdots & \vdots & \vdots & \vdots & \ldots & \vdots \\ 0 & 0 & 0 & 0 & 0 & \ldots & 1 \\ \end{array} \right]. \] Setting $k_2= \cdots = k_n=1$ gives Santos' result. In fact, note that we can relax Sellers' requirements that $k_2>0$ and $k_i \geq 0$: as long as all partial sums $k_2+ \cdots + k_i$, $2 \leq i \leq n$, are nonnegative, (\ref{sellers-gf}) is still the generating function for the set of compositions of $N$ (no longer necessarily partitions) satisfying $\la_1 \geq \sum_{i=2}^n k_i \la_{i}$ and $\la_i \geq \la_{i+1}$ for $2 \leq i \leq n-1$. For example, we could have $k_i=1$ if $i$ is even, $k_i=-1$ if $i$ is odd. \item {\em Partitions with nonnegative second differences} \cite{PA2}, {\em super-concave partitions} \cite{snellman} Partitions $(\la_1, \la_2, \ldots, \la_n)$ with the additional constraint that $\la_i \geq 2\la_{i+1}-\la_{i+2}$ for $1 \leq i \leq n-1$, with $\la_{n+2}=0$ were first considered by Andrews in \cite{PA2} as {\em partitions with nonnegative second differences}. He used partition analysis to show that they have the same generating function as partitions into the {\em triangular numbers} $\{{i+1 \choose 2} | 1 \leq i \leq n\}$ and also to give a bijection. We can get the same generating function and a bijection from (\ref{product-form}) and (\ref{bijection}) by inverting the constraint matrix. Snellman and Paulsen arrived at the same family via a different definition in \cite{snellman}. Their interest was in partitions $(\la_1, \la_2, \ldots, \la_n)$ satisfying $\la_i(k-j)+\la_j(i-k)+\la_k(j-i) \geq 0$ for all positive integers $i < j < k \leq n+1$, where $\la_{n+1}=0$. They called these {\em super concave partitions} and proved that they are equivalent to the partitions with nonnegative second differences. \item {\em Partitions with $r$-th differences nonnegative} \cite{PA2,CCH,SC} Generalizing the case for $r=2$, these are the partitions $(\la_1, \la_2, \ldots, \la_n)$ satisfying \[ \sum_{j=0}^r(-1)^j \la_{i+j}{r \choose j} \geq 0 \] for $1 \leq i \leq n-1$, with $\la_{n+1}= \cdots = \la_{n+r-1}=0$, defined by Andrews in \cite{PA2}. He used partition analysis to show that they have the same generating function as partitions into parts in $\{{i+r \choose 2} | 0 \leq i \leq n-1\}$ and a bijection appears in \cite{CCH,SC}. Again, here, we can get the generating function and a bijection by inverting the constraint matrix. \item {\em Examples {\rm (}0-5{\rm )} of Pak in} \cite{pak}. \end{itemize} Many other examples are provided in \cite{rama}, where the main result was extended to handle the case where any subset of the constraints (\ref{constraints}) could require equality and also to handle certain inhomogenous constraints. On the other hand, consider the following simple example where the results of \cite{rama} do not directly apply. Let $S$ be the set of integer sequences $(\la_1,\la_2,\la_3)$ satisfying \begin{eqnarray} \la_1 & \geq & \la_2+\la_3 \nonumber\\ \la_2 & \geq & \la_3 \nonumber\\ 2\la_3 & \geq & \la_1-\la_2. \label{example1} \end{eqnarray} The constraint matrix is \begin{eqnarray} C= \left[ \begin{array}{rrr} 1 & -1 & -1 \\ 0 & 1 & -1 \\ -1 & 1 & 2 \end{array} \right], \label{example1matrix} \end{eqnarray} which is not upper triangular and its diagonal entries are not all 1. The purpose of this note is to extend the result of \cite{rama} to more general systems, including (\ref{example1}). We show that for any constraint matrix $C$, as long as the matrix $B=C^{-1}$ has all nonnegative {\em integer} entries, then the generating function for the set $S_C$, of integer sequences satisfying (\ref{constraints}), has the form (\ref{product-form}), where $b_j$ is the sum of the entries in column $j$ of $B=[b_{i,j}]$. Again, this comes supplied with the natural bijection (\ref{bijection}). As in \cite{rama}, this extends to the case where some of the inequalities are equalities and some of the inequalities may be inhomogeneous. Furthermore, the multivariable generating function \begin{equation} F_C(x_1,x_2, \ldots, x_n) = \sum_{\la \in S_C}x_1^{\la_1}x_2^{\la_2} \cdots x_n^{\la_n} \label{multivariable} \end{equation} can also be ``read'' from the $B$ matrix: $q^{b_j}$ in (\ref{product-form}) just becomes: $x_1^{b_{1,j}} x_2^{b_{2,j}} \cdots x_n^{b_{n,j}}$ in (\ref{multivariable}). Note that the polynomial $F_C(x_1,x_2, \ldots, x_n)$ is an encapsulation of the set $S_C$: the coefficient of $q^N$ in $F_C(qx_1,qx_2, \ldots, qx_n)$ is a listing (as the terms of a polynomial) of all integer solutions to (\ref{constraints}) of weight $N$. In the next section we state and prove the extended theorem and follow in Section 3 with some examples. \vskip 30pt \section*{\normalsize 2. The Main Theorem} Suppose $S$ is a multiset of positive integers. We want to define a partition of $n$ into parts taken from $S$. Suppose $i$ is some element of $S$ which appears with multiplicity $>1$. Then imagine that the different copies of $i$ have different colors. We will count as different a partition of $n$ that uses two red copies of $i$ and six green copies of $i$, on the one hand, and a partition of $n$ that uses five red copies of $i$ and three green copies of $i$, on the other hand. It is in this sense that we will be counting the partitions of $n$ into parts taken from $S$. \begin{theorem} Let $C$ be an $n \times n$ matrix of integers such that $C^{-1} = B = [b_{i,j}]$ exists and has all entries nonnegative integers. Let $e_1, \ldots, e_n$ be nonnegative integer constants. Let $EQ$ be a subset of $\{1, \ldots, n\}$. For each $1 \leq i \leq n$, let $c_i$ be the constraint \[ \left\{ \begin{array}{ll} c_{i,1}\lambda_1 + c_{i,2}\lambda_2 + \ldots c_{i,n}\lambda_n \geq e_i & \mbox{if $i \not \in EQ$}\\ c_{i,1}\lambda_1 + c_{i,2}\lambda_2 + \ldots c_{i,n}\lambda_n = e_i & \mbox{if $i \in EQ$} \end{array} \right. \] Let $S_C$ be the set of nonnegative integer sequences $\la= (\la_1,\la_2, \ldots,\la_n)$ satisfying the constraints $c_i$ for all $i$, $1 \leq i \leq n$. The generating function for $S_C$ is: \[ F_C(x_1,x_2, \ldots, x_n) = \sum_{\lambda \in S_C}x_1^{\la_1} x_2^{\la_2} \cdots x_n^{\la_n} = \frac{\prod_{j=1}^{n}(x_1^{b_{1,j}}x_2^{b_{2,j}} \cdots x_n^{b_{n,j}})^{e_j}} {\prod_{j \in \{1, \ldots, n\}-EQ} (1-x_1^{b_{1,j}}x_2^{b_{2,j}} \cdots x_n^{b_{n,j}}) }. \] Furthermore, let $b_j$ be the sum of the entries in column $j$ of $B=C^{-1}$. Then an explicit bijection between \begin{quote} \vspace{-.3in} \item {(\rm i)} partitions of $N$ into parts from the multiset $\{b_1, \ldots, b_n\}$ with the restriction that part $b_j$ occurs at least $e_j$ times if $j \not \in EQ$ and exactly $e_j$ times if $j \in EQ$ and \item {(\rm ii)} sequences $\la \in S_C$ of weight $N$ \end{quote} is given by \[ b_1^{m_1}b_2^{m_2} \cdots b_n^{m_n} \rightarrow (\la_1, \la_2, \ldots, \la_n) \] where $\la_i = \sum_{j=i}^nb_{i,j}m_j$. \label{Cmatrix} \end{theorem} \noindent {\bf Proof.} If $\lambda \in S_C$, then for $1 \leq i \leq n$, \[ s_i = \left ( \sum_{j=1}^n c_{i,j} \lambda_j \right ) -e_i \geq 0, \] and $s_i=0$ if $i \in EQ$. Conversely, if $B$ has all nonnegative integer entries, then given nonnegative integers $s_1, s_2, \ldots, s_n$, with $s_i=0$ if $i \in EQ$, define $\la$ by \begin{equation} \left [ \begin{array}{c} \lambda_1 \\ \vdots \\ \lambda_n \end{array} \right ] = B \left [ \begin{array}{c} s_1+e_1 \\ \vdots \\ s_n+e_n \end{array} \right ]. \label{bse} \end{equation} Then the $\la_i$ are nonnegative integers and since $B=C^{-1}$, \[ C \left [ \begin{array}{c} \lambda_1 \\ \vdots \\ \lambda_n \end{array} \right ] = \left [ \begin{array}{c} s_1+e_1 \\ \vdots \\ s_n+e_n \end{array} \right ]. \] So for $1 \leq i \leq n$, $\la$ satisfies \[ c_{i,1}\lambda_1 + c_{i,2}\lambda_2 + \ldots c_{i,n}\lambda_n = s_i+e_i \left\{ \begin{array}{ll} \geq 0 & \mbox{if $i \not \in EQ$}\\ = 0 & \mbox{if $i \in EQ$} \end{array} \right. \] that is, $\la \in S_C$. Thus, \begin{eqnarray*} F_C(x_1, \ldots, x_n) & = & \sum_{\lambda \in S_C} \prod_{i=1}^n x_i^{\lambda_i}\\ & =& \sum_{\begin{array}{c} s_1, \ldots, s_n \geq 0 \\ k \in EQ \rightarrow (s_k=0) \end{array}} \prod_{i=1}^n x_i^{b_{i,1}(s_1+e_1)+ \cdots + b_{i,n}(s_n+e_n)}\\ & =& \sum_{\begin{array}{c} s_1, \ldots, s_n \geq 0 \\ k \in EQ \rightarrow (s_k=0) \end{array}} \prod_{j=1}^n (x_1^{b_{1,j}}x_2^{b_{2,j}} \cdots x_n^{b_{n,j}})^{(s_j+e_j)}\\ & =& \prod_{j=1}^{n}(x_1^{b_{1,j}} x_2^{b_{2,j}} \cdots x_n^{b_{n,j}})^{e_j} \sum_{\begin{array}{c} s_1, \ldots, s_n \geq 0 \\ k \in EQ \rightarrow (s_k=0) \end{array}} \prod_{j=1}^n (x_1^{b_{1,j}} x_2^{b_{2,j}} \cdots x_n^{b_{n,j}})^{s_j} \end{eqnarray*} and the result follows. \hfill{$\Box$} \vskip 30pt \section*{\normalsize 3. Examples} \noindent {\bf Example 1} We revisit the example from the introduction. Let $S$ be the set of integer sequences $(\la_1,\la_2,\la_3)$ satisfying the constraints (\ref{example1}). The constraint matrix $C$ is (\ref{example1matrix}) which is not upper triangular. However, $C^{-1}$ has all nonnegative integer entries: \[ C^{-1}= \left[ \begin{array}{rrr} 3 & 1 & 2 \\ 1 & 1 & 1 \\ 1 & 0 & 1 \end{array} \right], \] so by Theorem \ref{Cmatrix}, the multivariable generating function is \begin{eqnarray*} \sum_{(\la_1,\la_2,\la_3) \in S}x_1^{\la_1}x_2^{\la_2}x_3^{\la_3}&=& \frac{1} {(1-x_1^{3}x_2x_3) (1-x_1x_2) (1-x_1^2x_2x_3)}. \end{eqnarray*} \noindent {\bf Example 2.} Consider the set $T$ of nondegenerate incongruent integer-sided triangles which were treated by Andrews in \cite{PA2}. These are partitions into 3 parts $(\la_1,\la_2,\la_3)$ satisfying $\la_1 \geq \la_2 \geq \la_3 \geq 0$ and $\la_1+\la_2 > \la_3$, $\la_2+\la_3 > \la_1$, $\la_1+\la_3 > \la_2$. Equivalently, $T$ is the set of nonnegative integer sequences $(\la_1,\la_2,\la_3)$ satisfying \begin{eqnarray} \la_1 & \geq & \la_2 \nonumber\\ \la_2 & \geq & \la_3 \nonumber\\ \la_3 & \geq & \la_1-\la_2+1. \label{triconstraints} \end{eqnarray} Then in the hypotheses of Theorem \ref{Cmatrix}, $EQ = \emptyset$, $e_1=e_2=0$, $e_3=1$, and the constraint matrix is \[ C = \left[ \begin{array}{rrr} 1 & -1 & 0 \\ 0 & 1 & -1 \\ -1 & 1 & 1 \end{array} \right] \] (which is not upper triangular). The inverse is: \[ B= C^{-1} = \left[ \begin{array}{rrr} 2 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 0 & 1 \end{array} \right], \] so by Theorem \ref{Cmatrix} the multivariable generating function is \begin{eqnarray*} \sum_{(\la_1,\la_2,\la_3) \in T}x_1^{\la_1}x_2^{\la_2}x_3^{\la_3}&=& \frac{x_1^{b_{1,3}}x_2^{b_{2,3}}x_3^{b_{3,3}}} {(1-x_1^{b_{1,1}}x_2^{b_{2,1}}x_3^{b_{3,1}}) (1-x_1^{b_{1,2}}x_2^{b_{2,2}}x_3^{b_{3,2}}) (1-x_1^{b_{1,3}}x_2^{b_{2,3}}x_3^{b_{3,3}})}\\ &=& \frac{x_1x_2x_3} {(1-x_1^{2}x_2x_3) (1-x_1x_2) (1-x_1x_2x_3)}. \end{eqnarray*} Setting $x_1=x_2=x_3=q$ gives \[ \sum_{(\la_1,\la_2,\la_3) \in T}q^{\la_1+\la_2+\la_3}= \frac{q^{3}}{(1-q^{4})(1-q^{2})(1-q^{3})}. \] Also, Theorem \ref{Cmatrix} gives an explicit bijection between the partitions of $N$ into parts $2,3,4$ with at least one part 3 (i.e. at least $e_3=1$ copies of $b_3=1+1+1$) and the triangles $(\la_1, \la_2, \la_3)$ of perimeter $N$ satisfying (\ref{triconstraints}). Specifically: the partition $4^{m_1}2^{m_2}3^{m_3}$ (using multiplicity representation), with $m_3 \geq 1$, maps to the triangle $(2m_1+m_2+m_3,m_1+m_2+m_3,m_1+m_3)$, the same bijection obtained in \cite{PA2}. Continuing with the integer-sided triangles, suppose we only wanted those in which the lengths of the three sides were distinct. Then $EQ = \emptyset$, $e_1=e_2=e_3=1$, and the multivariable generating function would be: \[ \frac{(x_1^{2}x_2x_3)(x_1x_2)(x_1x_2x_3)} {(1-x_1^{2}x_2x_3) (1-x_1x_2) (1-x_1x_2x_3)} = \frac{x_1^{4}x_2^{3}x_3^{2}} {(1-x_1^{2}x_2x_3) (1-x_1x_2) (1-x_1x_2x_3)}. \] If we wanted the two smallest sides to be the same length and to differ from the largest by at least 2, then $EQ=2$, $e_1=2, e_2=0, e_3=1$, and the generating function is: \[ \frac{(x_1^{2}x_2x_3)^2(x_1x_2x_3)} {(1-x_1^{2}x_2x_3) (1-x_1x_2x_3)} = \frac{(x_1^{5}x_2^{3}x_3^{3})} {1-x_1^{2}x_2x_3 (1-x_1x_2x_3)}. \] \noindent {\bf Example 3.} Analogous to the super concave partitions of Snellman and Paulsen in \cite{snellman}, call a partition {\em super convex} if it satisfies \[ \la_1 \geq \la_2 \geq \cdots \geq \la_n \geq 0; \ \ \ \ \ 2 \la_i \geq \la_{i-1}+\la_{i+1}, \ \ i \geq 2, \] assuming $\la_{n+1}=0$. To our knowledge, these were first considered by Andrews in \cite{PA2}, where he called them {\em partitions with mixed difference conditions} and computed their generating function using partition analysis. The generating function is also easy to compute from Theorem \ref{Cmatrix}. The constraint matix is (e.g., for $n=6$) \[ C= \left [ \begin{array}{rrrrrr} 1& -1& 0& 0& 0& 0\\ -1& 2& -1& 0& 0 &0\\ 0& -1& 2& 1& 0& 0\\ 0& 0& -1& 2& -1& 0\\ 0& 0& 0& -1& 2& -1\\ 0& 0& 0& 0& -1& 2 \end{array} \right ] \] and the inverse is \[ C^{-1}= \left [ \begin{array}{rrrrrr} 6&5&4&3&2&1\\ 5&5&4&3&2&1\\ 4&4&4&3&2&1\\ 3&3&3&3&2&1\\ 2&2&2&2&2&1\\ 1&1&1&1&1&1\\ \end{array} \right ] \] so by Theorem \ref{Cmatrix}, the multivariable generating function is \[ \prod_{j=1}^n \left( 1-\prod_{i=1}^j(x_i \cdots x_n) \right)^{-1}. \] We can generalize this a bit: the generating function for the nonnegative integer sequences $\la$ satisfying \[ \la_1 \geq t \la_2; \ \ \ (t+1) \la_i \geq \la_{i-1}+t\la_{i+1}, \ \ i \geq 2, \] assuming $\la_{n+1}=0$, is \[ \prod_{j=1}^n \left( 1-\prod_{i=1}^j(x_i^{t^0}x_{i+1}^{t^1} \cdots x_n^{t^{n-i}}) \right)^{-1}. \] \noindent {\bf Example 4.} In \cite{PA2}, Andrews defines $\Delta_m$ as the number of partitions $\la_1, \la_2, \ldots, \la_{2m+1}$ satisfying the additional constraints \begin{equation} \la_{2i-1}-\la_{2i}-\la_{2i+1}+\la_{2i+2} \leq 0, \ \ 1 \leq i \leq m-1; \ \ \ \la_{2m-1}-\la_{2m}-\la_{2m+1} \leq 0, \label{Dconstraints} \end{equation} and shows that the generating function of $\Delta_m$ is \begin{equation} \prod_{h=1}^m \frac{1}{1-q^{2h}} \prod_{j=0}^m \frac{1}{1-q^{(j+1)(2m+1-j)}}. \label{Dgf} \end{equation} (Then $\Delta_1$ is the set of incongruent {\em nonnegative} integer-sided triangles.) The constraints (\ref{Dconstraints}), together with the constraints $\la_i \geq \la_{i+1}$, $1 \leq i \leq 2m$, give a total of $3m-1$ constraints in $2m+1$ variables. It is easy to check that the set of constraints $\{\la_{2i+1} \geq \la_{2i+2} | 1 \leq i n$. (It can be checked that the elements of $S_n$ are partitions.) By Theorem \ref{Cmatrix} and (\ref{invert}), the generating function for $S_n$ is \[ S_n(x_1,x_2, \ldots, x_n)= \frac{1}{(1-x_1)(1-x_1^2x_2)(1-x_1^2x_2^2x_3) \cdots (1-x_1^2x_2^2 \cdots x_{n-1}^2x_n)}. \] So, the number of partitions of $N$ into odd parts in $\{1,3, \ldots, 2n-1\}$ is equal to number of partitions of $N$ in $S_n$ and the bijection is given by \[ 1^{m_1}3^{m_2}5^{m_3} \cdots (2n-1)^{m_n} \rightarrow (m_1+ 2\sum_{j=2}^n m_j,\ \ \ m_2+ 2\sum_{j=3}^n m_j,\ \ \ m_3+ 2\sum_{j=4}^n m_j,\ \ \ \ldots,\ \ \ m_n). \] \vskip 30pt \section*{\normalsize 4. Conclusion} Theorem 1 provides a uniform treatment of a broad class of partition identities, many of which have been handled elsewhere by a variety of techniques. We propose Theorem 1 as the ``method of first attack'' since, when it does apply, it gives the generating function and the bijection, for the price of inverting a matrix. It also gives the multivariable generating function, which can be viewed as an encoding of all possible solutions. It is not hard to find examples beyond the scope of this method. Consider the constraints for one of the special cases of {\em constrained compositions} from \cite{PA7}: \[ (nk-1)\la_j \geq \sum_{i=1}^n k \la_i; \ \ \ j=1, \ldots, n. \] The inverse of the constraint matrix for this system does not have all entries nonnegative. Nevertheless, it is shown in \cite{PA7} that the mutivariable generating function has a simple form. As another example, define the {\em super convex compositions} to be those integer sequences $\la = (\la_1,\la_2, \ldots, \la_n)$ satisfying \[ 2 \la_i \geq \la_{i-1}+\la_{i+1}, \ \ 1 \leq i \leq n, \] where we assume $\la_0=\la_{n+1}=0$. These differ from the super-convex partitions of Example 3 in that here $2\la_1 \geq \la_2$, but the $\la_i$ need not be weakly decreasing. The inverse of the constraint matrix for this system no longer has integer entries. In fact, we offer as an open question the challenge of computing the generating function for this family. \noindent {\bf Acknowledgement.} The second author would like thank Sunyoung Lee for technical support. \bibliographystyle{plain} \begin{thebibliography}{10} \footnotesize \bibitem{PA2} George~E. Andrews. \newblock Mac{M}ahon's partition analysis. {II}. {F}undamental theorems. \newblock {\em Ann. Comb.}, 4(3-4):327--338, 2000. \newblock Conference on Combinatorics and Physics (Los Alamos, NM, 1998). \bibitem{PA7} George~E. Andrews, Peter Paule, and Axel Riese. \newblock Mac{M}ahon's partition analysis. {VII}. {C}onstrained compositions. \newblock In {\em $q$-series with applications to combinatorics, number theory, and physics (Urbana, IL, 2000)}, volume 291 of {\em Contemp. Math.}, pages 11--27. Amer. Math. Soc., Providence, RI, 2001. \bibitem{CCH} Rod Canfield, Sylvie Corteel, and Pawel Hitczenko. \newblock Random partitions with non negative $r^{th}$ differences. \newblock {\em Adv. Applied Maths}, 27:298--317, 2001. \bibitem{rama} Sylvie Corteel and Carla~D. Savage. \newblock Partitions and compositions defined by inequalities. \newblock {\em Ramanujan J.}, 8(3):357--381, 2004. \bibitem{hickerson} D.~R. Hickerson. \newblock A partition identity of the {E}uler type. \newblock {\em Amer. Math. Monthly}, 81:627--629, 1974. \bibitem{pak} Igor Pak. \newblock Partition identities and geometric bijections. \newblock {\em Proc. Amer. Math. Soc.}, 132(12):3457--3462 (electronic), 2004. \bibitem{santos} Jose Pl{\'{\i}}nio~O. Santos. \newblock On a new combinatorial interpretation for a theorem of {E}uler. \newblock {\em Adv. Stud. Contemp. Math. (Pusan)}, 3(2):31--38, 2001. \bibitem{sellers} James~A. Sellers. \newblock Extending a recent result of {S}antos on partitions into odd parts. \newblock {\em Integers}, 3:A4, 5 pp. (electronic), 2003. \bibitem{sellers2} James~A. Sellers. \newblock Corrigendum to: ``{E}xtending a recent result of {S}antos on partitions into odd parts'' [{I}ntegers {\bf 3} (2003), {A}4, 5 pp. (electronic)]. \newblock {\em Integers}, 4:A8, 1 pp. (electronic), 2004. \bibitem{snellman} Jan Snellman and Michael Paulsen. \newblock Enumeration of concave integer partitions. \newblock {\em J. Integer Seq.}, 7(1):Article 04.1.3, 10 pp. (electronic), 2004. \bibitem{SC} Doron Zeilberger. \newblock Sylvie {C}orteel's one line proof of a partition theorem generated by {A}ndrews-{P}aule-{R}iese's computer. \newblock {\em Shalosh B. Ekhad's and Doron Zeilberger's Very Own Journal}, 1998. \end{thebibliography} \end{document}