INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 5(1) (2005), #A24

A NOTE ON PARTITIONS AND COMPOSITIONS DEFINED BY INEQUALITIES

Sylvie Corteel

45 Avenue des Etats-Unis, 78035 Versailles, France

                             syl@prism.uvsq.fr

Carla D. Savage^{1}

Department of Computer Science, North Carolina State University, Box 8206, Raleigh, NC 27695, USA

                            savage@csc.ncsu.edu

Herbert S. Wilf

Department of Mathematics, University of Pennsylvania, Philadelphia, PA 19104-6395, USA

                            wilf@math.upenn.edu

Received: 2/10/05, Revised: 11/1/05, Accepted: 11/3/05, Published: 11/22/05

Abstract

We consider the problem of enumerating the nonnegative integer sequences λ = (λ_{1}, λ_{2}, …, λ_{n}) satisfying the constraints

c_{i,1}λ_{1} + c_{i,2}λ_{2} + … + c_{i,n}λ_{n} ≥ 0, 1 ≤ i ≤ n,

for a given an n × 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.

1. Introduction

For a sequence λ = (λ_{1}, λ_{2}, …, λ_{n}) of integers, define the weight of λ to be |λ| = λ_{1}+⋯+λ_{n}. If sequence λ of weight N has all parts nonnegative, we call it a composition of N; if, in addition, λ is a nonincreasing sequence, we call it a partition of N.

Given an n × n integer matrix C = [c_{i,j}], we consider the set S_{C} of compositions λ = (λ_{1}, λ_{2}, …, λ_{n}) satisfying the constraints

c_{i,1}λ_{1} + c_{i,2}λ_{2} + … + c_{i,n}λ_{n} ≥ 0, 1 ≤ i ≤ n.  (1)

1Research supported in part by NSF grants DMS-0300034 and INT-0230800

In [4], we gave sufficient conditions for the generating function of S_{C} to have a product form:

F_{C}(q) = ∑_{λ∈S_{C}} q^{|λ|} = ∏_{j=1}^{n} \frac{1}{(1 − q^{b_{j}})},  (2)

for some positive integers b_{1}, …, 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 (2), 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}, …, b_{n}} and the compositions of N in S_{C} given by:

b_{1}^{m_{1}}b_{2}^{m_{2}} ⋯ b_{n}^{m_{n}} ↔ (λ_{1}, λ_{2}, …, λ_{n}),  (3)

where λ_{i} = ∑_{j=i}^{n} b_{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:

• Hickerson partitions [5] Given a positive integer r, the partitions λ = (λ_{1}, …, λ_{n}) satisfying λ_{i} ≥ rλ_{i+1} have generating function

∏_{j=1}^{n} \frac{1}{1 − q^{1+r+···+r^{j−1}}} .

This follows by inverting the constraint matrix:

C^{−1} = [ \begin{matrix}1 & −r & 0 & 0 & 0 & … & 0 \\ 0 & 1 & −r & 0 & 0 & … & 0 \\ 0 & 0 & 1 & −r & 0 & … & 0 \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & … & ⋮ \\ 0 & 0 & 0 & 0 & 0 & … & 1 \end{matrix} ]^{−1} = [ \begin{matrix}1 & r & r^{2} & r^{3} & r^{4} & … & r^{n−1} \\ 0 & 1 & r & r^{2} & r^{3} & … & r^{n−2} \\ 0 & 0 & 1 & r & r^{2} & … & r^{n−3} \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & … & ⋮ \\ 0 & 0 & 0 & 0 & 0 & … & 1 \end{matrix} ] .

• Santos’ interpretation of Euler [7] The number of partitions λ = (λ_{1}, …, λ_{n}) of N into n nonnegative parts satisfying the additional constraint λ_{1} ≥ ∑_{i=2}^{n} λ_{i}, is the same as the number of partitions of N into odd parts in {1, 3, …, 2n − 1}. (See next example.)

• Sellers’ generalization of Santos [8, 9]:

The set of partitions λ = (λ_{1}, …, λ_{n}) into n nonnegative parts satisfying the additional constraint λ_{1} ≥ ∑_{i=2}^{n} k_{i}λ_{i}, for a given sequence of nonnegative integers (k_{2}, …, k_{n}) with k_{2} > 0 has generating function

\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}) ⋯ (1 − q^{k_{2}+k_{3}+···+k_{n}+n−1})}. (4)

This follows because the constraint matrix has the form

C = [ \begin{matrix}1 & −k_{2} & −k_{3} & −k_{4} & −k_{5} & … & −k_{n} \\ 0 & 1 & −1 & 0 & 0 & … & 0 \\ 0 & 0 & 1 & −1 & 0 & … & 0 \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & … & ⋮ \\ 0 & 0 & 0 & 0 & 0 & … & 1 \end{matrix} ] ,

and its inverse is

C^{−1} = [ \begin{matrix}1 & k_{2} & k_{2} + k_{3} & k_{2} + k_{3} + k_{4} & k_{2} + k_{3} + k_{4} + k_{5} & … & k_{2} + ⋯ + k_{n} \\ 0 & 1 & 1 & 1 & 1 & … & 1 \\ 0 & 0 & 1 & 1 & 1 & … & 1 \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & … & ⋮ \\ 0 & 0 & 0 & 0 & 0 & … & 1 \end{matrix} ] .

Setting k_{2} = ⋯ = k_{n} = 1 gives Santos’ result. In fact, note that we can relax Sellers’ requirements that k_{2} > 0 and k_{i} ≥ 0: as long as all partial sums k_{2} +⋯+k_{i}, 2 ≤ i ≤ n, are nonnegative, (4) is still the generating function for the set of compositions of N (no longer necessarily partitions) satisfying λ_{1} ≥ ∑_{i=2}^{n} k_{i}λ_{i} and λ_{i} ≥ λ_{i+1} for 2 ≤ i ≤ n−1. For example, we could have k_{i} = 1 if i is even, k_{i} = −1 if i is odd.

• Partitions with nonnegative second differences [1], super-concave partitions [10]

Partitions (λ_{1}, λ_{2}, …, λ_{n}) with the additional constraint that λ_{i} ≥ 2λ_{i+1} − λ_{i+2} for 1 ≤ i ≤ n − 1, with λ_{n+2} = 0 were first considered by Andrews in [1] as partitions with nonnegative second differences. He used partition analysis to show that they have the same generating function as partitions into the triangular numbers \{\binom{i+1}{2}|1 ≤ i ≤ n\} and also to give a bijection. We can get the same generating function and a bijection from (2) and (3) by inverting the constraint matrix.

Snellman and Paulsen arrived at the same family via a different definition in [10]. Their interest was in partitions (λ_{1}, λ_{2}, …, λ_{n}) satisfying λ_{i}(k − j) + λ_{j}(i − k) + λ_{k}(j − i) ≥ 0 for all positive integers i < j < k ≤ n + 1, where λ_{n+1} = 0. They called these super concave partitions and proved that they are equivalent to the partitions with nonnegative second differences.

• Partitions with r-th differences nonnegative [1, 3, 11]

Generalizing the case for r = 2, these are the partitions (λ_{1}, λ_{2}, …, λ_{n}) satisfying

∑_{j=0}^{r}(−1)^{j}λ_{i+j}\binom{r}{j} ≥ 0

for 1 ≤ i ≤ n − 1, with λ_{n+1} = ⋯ = λ_{n+r−1} = 0, defined by Andrews in [1]. He used partition analysis to show that they have the same generating function as partitions into parts in \{\binom{i+r}{2}|0 ≤ i ≤ n − 1\} and a bijection appears in [3, 11]. Again, here, we can get the generating function and a bijection by inverting the constraint matrix.

• Examples (0-5) of Pak in [6].

Many other examples are provided in [4], where the main result was extended to handle the case where any subset of the constraints (1) could require equality and also to handle certain inhomogenous constraints.

On the other hand, consider the following simple example where the results of [4] do not directly apply. Let S be the set of integer sequences (λ_{1}, λ_{2}, λ_{3}) satisfying

λ_{1} ≥ λ_{2} + λ_{3}
λ_{2} ≥ λ_{3}
2λ_{3} ≥ λ_{1} − λ_{2}.  (5)

The constraint matrix is

C = [ \begin{matrix}1 & −1 & −1 \\ 0 & 1 & −1 \\ −1 & 1 & 2 \end{matrix} ] ,  (6)

which is not upper triangular and its diagonal entries are not all 1.

The purpose of this note is to extend the result of [4] to more general systems, including (5). We show that for any constraint matrix C, as long as the matrix B = C^{−1} has all nonnegative integer entries, then the generating function for the set S_{C}, of integer sequences satisfying (1), has the form (2), 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 (3). As in [4], 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

F_{C}(x_{1}, x_{2}, …, x_{n}) = ∑_{λ∈S_{C}} x_{1}^{λ_{1}}x_{2}^{λ_{2}} ⋯ x_{n}^{λ_{n}}  (7)

can also be “read” from the B matrix: q^{b_{j}} in (2) just becomes: x_{1}^{b_{1,j}}x_{2}^{b_{2,j}} ⋯ x_{n}^{b_{n,j}} in (7). Note that the polynomial F_{C}(x_{1}, x_{2}, …, x_{n}) is an encapsulation of the set S_{C}: the coefficient of q^{N} in F_{C}(qx_{1}, qx_{2}, …, qx_{n}) is a listing (as the terms of a polynomial) of all integer solutions to (1) of weight N.

In the next section we state and prove the extended theorem and follow in Section 3 with some examples.

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.

Theorem 1 Let C be an n × n matrix of integers such that C^{−1} = B = [b_{i,j}] exists and has all entries nonnegative integers. Let e_{1}, …, e_{n} be nonnegative integer constants. Let EQ be a subset of {1, …, n}. For each 1 ≤ i ≤ n, let c_{i} be the constraint

\{ \begin{matrix}c_{i,1}λ_{1} + c_{i,2}λ_{2} + … c_{i,n}λ_{n} ≥ e_{i} & if i ∉ EQ \\ c_{i,1}λ_{1} + c_{i,2}λ_{2} + … c_{i,n}λ_{n} = e_{i} & if i ∈ EQ \end{matrix}

Let S_{C} be the set of nonnegative integer sequences λ = (λ_{1}, λ_{2}, …, λ_{n}) satisfying the constraints c_{i} for all i, 1 ≤ i ≤ n. The generating function for S_{C} is:

F_{C}(x_{1}, x_{2}, …, x_{n}) = ∑_{λ∈S_{C}} x_{1}^{λ_{1}}x_{2}^{λ_{2}} ⋯ x_{n}^{λ_{n}} = \frac{∏_{j=1}^{n}(x_{1}^{b_{1,j}}x_{2}^{b_{2,j}} ⋯ x_{n}^{b_{n,j}})^{e_{j}}}{∏_{j∈\{1,... ,n\}−EQ}(1 − x_{1}^{b_{1,j}}x_{2}^{b_{2,j}} ⋯ 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

(i) partitions of N into parts from the multiset {b_{1}, …, b_{n}} with the restriction that part b_{j} occurs at least e_{j} times if j ∉ EQ and exactly e_{j} times if j ∈ EQ and

(ii) sequences λ ∈ S_{C} of weight N

is given by

b_{1}^{m_{1}}b_{2}^{m_{2}} ⋯ b_{n}^{m_{n}} → (λ_{1}, λ_{2}, …, λ_{n})

where λ_{i} = ∑_{j=i}^{n} b_{i,j}m_{j}.

Proof. If λ ∈ S_{C}, then for 1 ≤ i ≤ n,

s_{i} = (∑_{j=1}^{n} c_{i,j}λ_{j}) − e_{i} ≥ 0,

and s_{i} = 0 if i ∈ EQ. Conversely, if B has all nonnegative integer entries, then given nonnegative integers s_{1}, s_{2}, …, s_{n}, with s_{i} = 0 if i ∈ EQ, define λ by

[ λ_{1} ; ⋮ ; λ_{n} ] = B [ s_{1} + e_{1} ; ⋮ ; s_{n} + e_{n} ] .  (8)

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 5 (2005), #A24 6

Then the λ_{i} are nonnegative integers and since B = C^{−1},

C [ λ_{1} ; ⋮ ; λ_{n} ] = [ s_{1} + e_{1} ; ⋮ ; s_{n} + e_{n} ] .

So for 1 ≤ i ≤ n, λ satisfies

c_{i,1}λ_{1} + c_{i,2}λ_{2} + … c_{i,n}λ_{n} = s_{i} + e_{i} \{ \begin{matrix}≥ 0 & if i ∉ EQ \\ = 0 & if i ∈ EQ \end{matrix}

that is, λ ∈ S_{C}.

Thus,

F_{C}(x_{1}, …, x_{n}) = ∑_{λ∈S_{C}} ∏_{i=1}^{n} x_{i}^{λ_{i}}
= ∑ ; \begin{matrix}s_{1}, …, s_{n} ≥ 0 \\ k ∈ EQ → (s_{k} = 0) \end{matrix} ∏_{i=1}^{n} x_{i}^{b_{i,1}(s_{1}+e_{1})+···+b_{i,n}(s_{n}+e_{n})}
= ∑ ; \begin{matrix}s_{1}, …, s_{n} ≥ 0 \\ k ∈ EQ → (s_{k} = 0) \end{matrix} ∏_{j=1}^{n}(x_{1}^{b_{1,j}}x_{2}^{b_{2,j}} ⋯ x_{n}^{b_{n,j}})^{(s_{j}+e_{j})}
= ∏_{j=1}^{n}(x_{1}^{b_{1,j}}x_{2}^{b_{2,j}} ⋯ x_{n}^{b_{n,j}})^{e_{j}} ∑ ; \begin{matrix}s_{1}, …, s_{n} ≥ 0 \\ k ∈ EQ → (s_{k} = 0) \end{matrix} ∏_{j=1}^{n}(x_{1}^{b_{1,j}}x_{2}^{b_{2,j}} ⋯ x_{n}^{b_{n,j}})^{s_{j}}

and the result follows. □

3. Examples Example 1 We revisit the example from the introduction. Let S be the set of integer sequences (λ_{1}, λ_{2}, λ_{3}) satisfying the constraints (5). The constraint matrix C is (6) which is not upper triangular. However, C^{−1} has all nonnegative integer entries:

C^{−1} = [ \begin{matrix}3 & 1 & 2 \\ 1 & 1 & 1 \\ 1 & 0 & 1 \end{matrix} ] ,

so by Theorem 1, the multivariable generating function is

∑_{(λ_{1},λ_{2},λ_{3})∈S} x_{1}^{λ_{1}}x_{2}^{λ_{2}}x_{3}^{λ_{3}} = \frac{1}{(1 − x_{1}^{3}x_{2}x_{3})(1 − x_{1}x_{2})(1 − x_{1}^{2}x_{2}x_{3})}.

Example 2. Consider the set T of nondegenerate incongruent integer-sided triangles which were treated by Andrews in [1]. These are partitions into 3 parts (λ_{1}, λ_{2}, λ_{3}) satisfying λ_{1} ≥ λ_{2} ≥ λ_{3} ≥ 0 and λ_{1} + λ_{2} > λ_{3}, λ_{2} + λ_{3} > λ_{1}, λ_{1} + λ_{3} > λ_{2}. Equivalently, T is the set of nonnegative integer sequences (λ_{1}, λ_{2}, λ_{3}) satisfying

λ_{1} ≥ λ_{2}
λ_{2} ≥ λ_{3}
λ_{3} ≥ λ_{1} − λ_{2} + 1.  (9)

Then in the hypotheses of Theorem 1, EQ = ∅, e_{1} = e_{2} = 0, e_{3} = 1, and the constraint matrix is

C = [ \begin{matrix}1 & −1 & 0 \\ 0 & 1 & −1 \\ −1 & 1 & 1 \end{matrix} ]

(which is not upper triangular). The inverse is:

B = C^{−1} = [ \begin{matrix}2 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 0 & 1 \end{matrix} ] ,

so by Theorem 1 the multivariable generating function is

∑_{(λ_{1},λ_{2},λ_{3})∈T} x_{1}^{λ_{1}}x_{2}^{λ_{2}}x_{3}^{λ_{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_{1}x_{2}x_{3}}{(1 − x_{1}^{2}x_{2}x_{3})(1 − x_{1}x_{2})(1 − x_{1}x_{2}x_{3})}.

Setting x_{1} = x_{2} = x_{3} = q gives

∑_{(λ_{1},λ_{2},λ_{3})∈T} q^{λ_{1}+λ_{2}+λ_{3}} = \frac{q^{3}}{(1 − q^{4})(1 − q^{2})(1 − q^{3})}.

Also, Theorem 1 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 (λ_{1}, λ_{2}, λ_{3}) of perimeter N satisfying (9). Specifically: the partition 4^{m_{1}}2^{m_{2}}3^{m_{3}} (using multiplicity representation), with m_{3} ≥ 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 [1].

Continuing with the integer-sided triangles, suppose we only wanted those in which the lengths of the three sides were distinct. Then EQ = ∅, e_{1} = e_{2} = e_{3} = 1, and the multivariable generating function would be:

\frac{(x_{1}^{2}x_{2}x_{3})(x_{1}x_{2})(x_{1}x_{2}x_{3})}{(1 − x_{1}^{2}x_{2}x_{3})(1 − x_{1}x_{2})(1 − x_{1}x_{2}x_{3})} = \frac{x_{1}^{4}x_{2}^{3}x_{3}^{2}}{(1 − x_{1}^{2}x_{2}x_{3})(1 − x_{1}x_{2})(1 − x_{1}x_{2}x_{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_{2}x_{3})^{2}(x_{1}x_{2}x_{3})}{(1 − x_{1}^{2}x_{2}x_{3})(1 − x_{1}x_{2}x_{3})} = \frac{(x_{1}^{5}x_{2}^{3}x_{3}^{3})}{1 − x_{1}^{2}x_{2}x_{3}(1 − x_{1}x_{2}x_{3})}.

Example 3. Analogous to the super concave partitions of Snellman and Paulsen in [10], call a partition super convex if it satisfies

λ_{1} ≥ λ_{2} ≥ ⋯ ≥ λ_{n} ≥ 0; 2λ_{i} ≥ λ_{i−1} + λ_{i+1}, i ≥ 2,

assuming λ_{n+1} = 0. To our knowledge, these were first considered by Andrews in [1], where he called them partitions with mixed difference conditions and computed their generating function using partition analysis. The generating function is also easy to compute from Theorem 1. The constraint matix is (e.g., for n = 6)

C = [ \begin{matrix}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{matrix} ]

and the inverse is

C^{−1} = [ \begin{matrix}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{matrix} ]

so by Theorem 1, the multivariable generating function is

∏_{j=1}^{n} (1 − ∏_{i=1}^{j}(x_{i} ⋯ x_{n}))^{−1} .

We can generalize this a bit: the generating function for the nonnegative integer sequences λ satisfying

λ_{1} ≥ tλ_{2}; (t + 1)λ_{i} ≥ λ_{i−1} + tλ_{i+1}, i ≥ 2,

assuming λ_{n+1} = 0, is

∏_{j=1}^{n} (1 − ∏_{i=1}^{j}(x_{i}^{t^{0}}x_{i+1}^{t^{1}} ⋯ x_{n}^{t^{n−i}}))^{−1} .

Example 4. In [1], Andrews defines Δ_{m} as the number of partitions λ_{1}, λ_{2}, …, λ_{2m+1} satisfying the additional constraints

λ_{2i−1} − λ_{2i} − λ_{2i+1} + λ_{2i+2} ≤ 0, 1 ≤ i ≤ m − 1; λ_{2m−1} − λ_{2m} − λ_{2m+1} ≤ 0,  (10)

and shows that the generating function of Δ_{m} is

∏_{h=1}^{m} \frac{1}{1 − q^{2h}} ∏_{j=0}^{m} \frac{1}{1 − q^{(j+1)(2m+1−j)}} .  (11)

(Then Δ_{1} is the set of incongruent nonnegative integer-sided triangles.)

The constraints (10), together with the constraints λ_{i} ≥ λ_{i+1}, 1 ≤ i ≤ 2m, give a total of 3m − 1 constraints in 2m + 1 variables. It is easy to check that the set of constraints {λ_{2i+1} ≥ λ_{2i+2}|1 ≤ i < m} is redundant. Deleting these gives a system of 2m + 1 constraints in 2m + 1 variables defining Δ_{m}. The constraint matrix, e.g. when m = 4, is:

C = [ \begin{matrix}1 & −1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ −1 & 1 & 1 & −1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & −1 & 1 & 1 & −1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & −1 & 1 & 1 & −1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & −1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & −1 \\ 0 & 0 & 0 & 0 & 0 & 1 & −1 & 0 & 0 \\ 0 & 0 & 0 & 1 & −1 & 0 & 0 & 0 & 0 \\ 0 & 1 & −1 & 0 & 0 & 0 & 0 & 0 & 0 \end{matrix} ] ,

and its inverse is:

C^{−1} = [ \begin{matrix}5 & 4 & 3 & 2 & 1 & 1 & 1 & 1 & 1 \\ 4 & 4 & 3 & 2 & 1 & 1 & 1 & 1 & 1 \\ 4 & 4 & 3 & 2 & 1 & 1 & 1 & 1 & 0 \\ 3 & 3 & 3 & 2 & 1 & 1 & 1 & 1 & 0 \\ 3 & 3 & 3 & 2 & 1 & 1 & 1 & 0 & 0 \\ 2 & 2 & 2 & 2 & 1 & 1 & 1 & 0 & 0 \\ 2 & 2 & 2 & 2 & 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \end{matrix} ] .

Generalizing this to arbitrary m, the last m columns of C^{−1} give rise to the first product in (11) and the first m + 1 columns, the second product.

Example 5. Theorem 1 can be used to work backwards from a target generating function. For example, starting with the matrix on the right below and considering its inverse gives another “Euler bijection”. Observe that

C^{−1} = [ \begin{matrix}1 & −2 & 2 & −2 & 2 & … & (−1)^{n+1}2 \\ 0 & 1 & −2 & 2 & −2 & … & (−1)^{n}2 \\ 0 & 0 & 1 & −2 & 2 & … & (−1)^{n+1}2 \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & … & ⋮ \\ 0 & 0 & 0 & 0 & 0 & … & 1 \end{matrix} ]^{−1} = [ \begin{matrix}1 & 2 & 2 & 2 & 2 & … & 2 \\ 0 & 1 & 2 & 2 & 2 & … & 2 \\ 0 & 0 & 1 & 2 & 2 & … & 2 \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & … & ⋮ \\ 0 & 0 & 0 & 0 & 0 & … & 1 \end{matrix} ] . (12)

Using C as a constraint matrix defines the set S_{n} of sequences λ_{1}, …, λ_{n} satisfying λ_{i} ≥ 2(λ_{i+1} − λ_{i+2} + λ_{i+3} − λ_{i+4} + ⋯), where we assume λ_{i} = 0 if i > n. (It can be checked that the elements of S_{n} are partitions.) By Theorem 1 and (12), the generating function for S_{n} is

S_{n}(x_{1}, x_{2}, …, x_{n}) = \frac{1}{(1 − x_{1})(1 − x_{1}^{2}x_{2})(1 − x_{1}^{2}x_{2}^{2}x_{3}) ⋯ (1 − x_{1}^{2}x_{2}^{2} ⋯ x_{n−1}^{2}x_{n})}.

So, the number of partitions of N into odd parts in {1, 3, …, 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}} ⋯ (2n − 1)^{m_{n}} → (m_{1} + 2 ∑_{j=2}^{n} m_{j}, m_{2} + 2 ∑_{j=3}^{n} m_{j}, m_{3} + 2 ∑_{j=4}^{n} m_{j}, …, m_{n}).

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 constrained compositions from [2]:

(nk − 1)λ_{j} ≥ ∑_{i=1}^{n} kλ_{i}; j = 1, …, n.

The inverse of the constraint matrix for this system does not have all entries nonnegative. Nevertheless, it is shown in [2] that the mutivariable generating function has a simple form.

As another example, define the super convex compositions to be those integer sequences λ = (λ_{1}, λ_{2}, …, λ_{n}) satisfying

2λ_{i} ≥ λ_{i−1} + λ_{i+1}, 1 ≤ i ≤ n,

where we assume λ_{0} = λ_{n+1} = 0. These differ from the super-convex partitions of Example 3 in that here 2λ_{1} ≥ λ_{2}, but the λ_{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.

Acknowledgement. The second author would like thank Sunyoung Lee for technical support.

References

[1] George E. Andrews. MacMahon’s partition analysis. II. Fundamental theorems. Ann. Comb., 4(3-4):327–338, 2000. Conference on Combinatorics and Physics (Los Alamos, NM, 1998).

[2] George E. Andrews, Peter Paule, and Axel Riese. MacMahon’s partition analysis. VII. Constrained compositions. In q-series with applications to combinatorics, number theory, and physics (Urbana, IL, 2000), volume 291 of Contemp. Math., pages 11–27. Amer. Math. Soc., Providence, RI, 2001.

[3] Rod Canfield, Sylvie Corteel, and Pawel Hitczenko. Random partitions with non negative r^{th} differences. Adv. Applied Maths, 27:298–317, 2001.

[4] Sylvie Corteel and Carla D. Savage. Partitions and compositions defined by inequalities. Ramanujan J., 8(3):357–381, 2004.

[5] D. R. Hickerson. A partition identity of the Euler type. Amer. Math. Monthly, 81:627–629, 1974.

[6] Igor Pak. Partition identities and geometric bijections. Proc. Amer. Math. Soc., 132(12):3457–3462 (electronic), 2004.

[7] Jose Plínio O. Santos. On a new combinatorial interpretation for a theorem of Euler. Adv. Stud. Contemp. Math. (Pusan), 3(2):31–38, 2001.

[8] James A. Sellers. Extending a recent result of Santos on partitions into odd parts. Integers, 3:A4, 5 pp. (electronic), 2003.

[9] James A. Sellers. Corrigendum to: “Extending a recent result of Santos on partitions into odd parts” [Integers 3 (2003), A4, 5 pp. (electronic)]. Integers, 4:A8, 1 pp. (electronic), 2004.

[10] Jan Snellman and Michael Paulsen. Enumeration of concave integer partitions. J. Integer Seq., 7(1):Article 04.1.3, 10 pp. (electronic), 2004.

[11] Doron Zeilberger. Sylvie Corteel’s one line proof of a partition theorem generated by Andrews-Paule-Riese’s computer. Shalosh B. Ekhad’s and Doron Zeilberger’s Very Own Journal, 1998.