Matrix Compositions

Emanuele Munarini Politecnico di Milano Dipartimento di Matematica Piazza Leonardo da Vinci 32 20133 Milano Italy

                  emanuele.munarini@polimi.it

Maddalena Poneti and Simone Rinaldi Università di Siena Dipartimento di Scienze Matematiche e Informatiche Pian dei Mantellini 44 53100 Siena Italy

               poneti@tiscali.it rinaldi@unisi.it

Abstract In this paper we study the class of m-row matrix compositions (m-compositions, for short), i.e., m-row matrices with nonnegative integer entries in which every column has at least one non-zero element. We provide several enumerative results, various combinatorial identities, and some combinatorial interpretations. Most of these properties are an extension to matrix compositions of the combinatorial properties of ordinary compositions.

1 Introduction

A composition (or ordered partition) of length k of a natural number n is a k-tuple (x_{1}, …, x_{k}) of positive integers such that x_{1}+⋯+x_{k} = n. Compositions are very well known combinatorial objects [1, 11, 12, 13, 17, 27], and their study has been improved in several recent papers [7, 8, 14, 18, 21, 25, 26, 29, 30, 37]. Moreover, in certain algebraic contexts [5, 7, 8, 42, 44, 45], compositions are ordered to form a partially ordered set which generalizes Young’s lattice for partitions. Finally, compositions have been generalized in various ways: we have the vector compositions [1, p.57][2, 3, 4] by P. A. MacMahon [34, 35, 36], the m-colored compositions by Drake and Petersen [19], the compositions defined by Lin and Rui [31], and the packed matrices by Duchamp, Hivert and Thibon [20].

Another slight generalization of ordinary compositions to the bidimensional case is given by the 2-compositions, introduced to encode L-convex polyominoes [16], Clearly, 2-compositions are a particular case of m-compositions. Indeed, more precisely, for any non-negative integer m, we define an m-row matrix composition, or m-composition for short, as an m × k matrix with nonnegative integer entries

M = [\begin{matrix}x_{11} & x_{12} & … & x_{1k} \\ x_{21} & x_{22} & … & x_{2k} \\ ⋮ & ⋮ & ... & ⋮ \\ x_{m1} & x_{m2} & … & x_{mk} \end{matrix}]

where each column has at least one non-zero element. We say that the length of M is the number k of its columns. Moreover, we say that M is an m-composition of a non-negative integer n when the sum σ(M) of all its entries is equal to n. For instance, we have the following seven 2-compositions of n = 2 :

[\begin{matrix}0 \\ 2 \end{matrix}] , [\begin{matrix}1 \\ 1 \end{matrix}] , [\begin{matrix}2 \\ 0 \end{matrix}] , [\begin{matrix}1 & 0 \\ 0 & 1 \end{matrix}] , [\begin{matrix}0 & 1 \\ 1 & 0 \end{matrix}] , [\begin{matrix}1 & 1 \\ 0 & 0 \end{matrix}] , [\begin{matrix}0 & 0 \\ 1 & 1 \end{matrix}] .

The aim of this paper is to give an elementary introduction to the combinatorics of matrix compositions. In particular, by using standard combinatorial techniques, we obtain several enumerative results, such as generating series, recurrences and explicit formulas, for m-compositions, m-compositions without zero rows, m-compositions with palindromic rows and m-compositions of Carlitz type (i.e., without equal consecutive columns). Moreover, we give some combinatorial interpretations of matrix compositions in terms colored linear partitions, labelled bargraphs and words of regular languages. Finally, by employing some of the results obtained by these combinatorial interpretations, we also prove a Cassini-like determinantal identity for m-compositions.

Other results concerning matrix compositions can be found in paper [23], where the problem of generating efficiently m-compositions and m-partitions has been treated, and in paper [32], where the probabilistic aspects of m-compositions have been studied.

2 Enumeration of m-compositions

Basic enumeration and combinatorial properties of m-compositions can be easily determined by using the technique of generating series.

Since matrix compositions can be expressed in a natural way in terms of multisets, we recall the following definitions. Let ℕ be the set of all non-negative integer numbers. A multiset on a set X is a function μ : X → ℕ. The multiplicity of an element x ∈ X is μ(x) . The order of μ is the sum ord(μ) of the multiplicities of the elements of X, i.e.,

\begin{matrix}n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ m = 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ m = 1 & 1 & 1 & 2 & 4 & 8 & 16 & 32 & 64 & 128 & 256 & 512 \\ m = 2 & 1 & 2 & 7 & 24 & 82 & 280 & 956 & 3264 & 11144 & 38048 & 129904 \\ m = 3 & 1 & 3 & 15 & 73 & 354 & 1716 & 8318 & 40320 & 195444 & 947380 & 4592256 \\ m = 4 & 1 & 4 & 26 & 164 & 1031 & 6480 & 40728 & 255984 & 1608914 & 10112368 & 63558392 \\ m = 5 & 1 & 5 & 40 & 310 & 2395 & 18501 & 142920 & 1104060 & 8528890 & 65885880 & 508970002 \\ m = 6 & 1 & 6 & 57 & 524 & 4803 & 44022 & 403495 & 3698352 & 33898338 & 310705224 & 2847860436 \end{matrix}

Table 1: The numbers c_{n}^{(m)} . For m = 3, 4, 5, 6 , we have the sequences \underline{A145839}, \underline{A145840}, \underline{A145841}, \underline{A161434} in [43].

ord(μ) = ∑_{x∈X} μ(x) . The number of all multisets of order k on a set of size n is the multiset coefficient [46]

\begin{aligned}( \\ ( & {n \atop k} & ) \\ & & ) \end{aligned} = \binom{n + k − 1}{k} = \frac{n(n + 1) ⋯ (n + k − 1)}{k!} .

Let C_{nk}^{(m)} be the set of all m-compositions of n of length k and let C_{n}^{(m)} be the set of all m-compositions of n. Then let c_{nk}^{(m)} = |C_{nk}^{(m)}| and c_{n}^{(m)} = |C_{n}^{(m)}| (see Table 1). For simplicity, sometimes we just write c_{n} for the coefficients c_{n}^{(2)} .

Proposition 1. The generating series of m-compositions according to the sum (marked by x) and the length (marked by y), is

c^{(m)}(x, y) = ∑_{n≥0} c_{nk}^{(m)}x^{n} = \frac{(1 − x)^{m}}{(1 + y)(1 − x)^{m} − y} .  (1)

In particular, the generating series of m-compositions according to the sum is

c^{(m)}(x) = ∑_{n≥0} c_{n}^{(m)}x^{n} = \frac{(1 − x)^{m}}{2(1 − x)^{m} − 1} .  (2)

Proof. An m-composition M can always be considered as the concatenation of its columns. Since each column of M is equivalent to a multiset on an m-set with non-zero order, the generating series for the columns is

h^{(m)}(x) = ∑_{k≥1} \begin{aligned}( \\ ( & {m \atop k} & ) \\ & & ) \end{aligned}x^{k} = \frac{1}{(1 − x)^{m}} − 1 .  (3)

Hence, c^{(m)}(x, y) = (1−h^{(m)}(x)y)^{−1} , that is (1). Finally, series (2) follows at once by setting y = 1 in (1).

Reading the denominator of the rational generating series (1) and (2), we can immediately obtain a linear recurrence for the numbers c_{nk}^{(m)} and c_{n}^{(m)} , namely we can obtain recurrences (9) and (10) that will be proved in Proposition 4 with a combinatorial argument explaining their form. Here, we obtain two other recurrences just by manipulating series in formal way. Recall that the incremental ratio of a formal series f(x) = ∑_{n≥0} f_{n}x^{n} is the series defined by Rf(x) = (f(x) − f_{0})/x = ∑_{n≥0} f_{n+1}x^{n}.

Proposition 2. The numbers c_{n}^{(m)} satisfy the recurrence

c_{n+1}^{(m)} = −δ_{n,0} + 2c_{n}^{(m)} + ∑_{k=0}^{n} \binom{m + k − 1}{k + 1}c_{n−k}^{(m)} .  (4)

Proof. Rewriting series (2) in the following form

c^{(m)}(x) = \frac{1}{2 − \frac{1}{(1 − x)^{m}}} = \frac{1 − x}{2 − 2x − \frac{1}{(1 − x)^{m−1}}} ,

we obtain the identity

(2 − 2x − \frac{1}{(1 − x)^{m−1}} ) c^{(m)}(x) = 1 − x

and hence the equation

c^{(m)}(x) = 1 − x + 2xc^{(m)}(x) + (\frac{1}{(1 − x)^{m−1}} − 1) c^{(m)}(x) .

Now, taking the incremental ratio of both sides, we have

Rc^{(m)}(x) = −1 + 2c^{(m)}(x) + R (\frac{1}{(1 − x)^{m−1}} − 1) c^{(m)}(x)

from which we obtain

c_{n+1}^{(m)} = −δ_{n,0} + 2c_{n}^{(m)} + ∑_{k=1}^{n+1} \begin{aligned}( \\ ( & {m − 1 \atop k} & ) \\ & & ) \end{aligned}c_{n−k+1}^{(m)} = −δ_{n,0} + 2c_{n}^{(m)} + ∑_{k=0}^{n} \begin{aligned}( \\ ( & {m − 1 \atop k + 1} & ) \\ & & ) \end{aligned}c_{n−k}^{(m)} ,

which simplifies in (4).

Recurrence (4) generalizes the identity c_{n+2} = 3c_{n+1} + c_{n} + ⋯ + c_{0} , obtained in [16] by simple manipulations of the recurrence c_{n+2} = 4c_{n+1} − 2c_{n}. Proposition 3. The numbers c_{nk}^{(m)} satisfy the recurrence

c_{n+1,k+1}^{(m+1)} = c_{n+1,k+1}^{(m)} − c_{n,k+1}^{(m)} + ∑_{i,j=0}^{n,k+1} c_{ij}^{(m)}c_{n−i,k−j+1}^{(m+1)} + ∑_{i,j=0}^{n,k} c_{ij}^{(m)}c_{n−i,k−j}^{(m+1)} .  (5)

Similarly, the numbers c_{n}^{(m)} satisfy the recurrence

c_{n+1}^{(m+1)} = c_{n+1}^{(m)} − c_{n}^{(m)} + 2 ∑_{k=0}^{n} c_{k}^{(m)}c_{n−k}^{(m+1)} .  (6)

Proof. For simplicity, we just prove identity (6). Identity (5) can be proved in a completely similar way. From (2), we have

(1 − x)^{m} = \frac{c^{(m)}(x)}{2c^{(m)}(x) − 1} .

Now, substituting m with m + 1 and (1 − x)^{m} with the above expression in identity (2), we obtain straightforwardly the relation

c^{(m+1)}(x) = \frac{(1 − x)c^{(m)}(x)}{1 − 2xc^{(m)}(x)} ,

and hence the equation

c^{(m+1)}(x) = (1 − x)c^{(m)}(x) + 2xc^{(m)}(x)c^{(m+1)}(x) .

Finally, taking the incremental ratio of both sides, we have at once (6).

3 Combinatorial identities

In this section we give a combinatorial interpretation of some formulas concerning mcompositions. Most of them can be obtained by employing the classical Principle of Inclusion-Exclusion [41, 46].

Proposition 4. The coefficients c_{nk}^{(m)} satisfy the recurrence

c_{n+m,k+1}^{(m)} = ∑_{i=1}^{n+m−k} \begin{aligned}( \\ ( & {m \atop i} & ) \\ & & ) \end{aligned}c_{n+m−i,k}^{(m)} .  (7)

Similarly, the coefficients c_{n}^{(m)} satisfy the recurrence

c_{n+m}^{(m)} = ∑_{i=1}^{n+m} \begin{aligned}( \\ ( & {m \atop i} & ) \\ & & ) \end{aligned} c_{n+m−i}^{(m)} .  (8)

Proof. Any m-composition M ∈ C_{n+m,k+1}^{(m)} can always be decomposed into two parts: the first column, equivalent to a multiset on the set {1, …, m} of non-zero order i (with 0 ≤ i ≤ n + m − k), and the rest of the matrix, equivalent to an m-composition of n + m − i of length k. This decomposition implies at once recurrence (7). The same argument also implies (8).

Recurrences (7) and (8) can be easily obtained, but they have a complex structure since they involve a summation. However, we also have the following linear recurrences.

Proposition 5. The numbers c_{nk}^{(m)} satisfies the recurrence

c_{n+m,k+1}^{(m)} = ∑_{i=1}^{m} \binom{m}{i}(−1)^{i−1}c_{n+m−i,k}^{(m)} + ∑_{i=1}^{m} \binom{m}{i}(−1)^{i−1}c_{n+m−i,k+1}^{(m)} .  (9)

Similarly, the numbers c_{n}^{(m)} satisfies the recurrence

c_{n+m}^{(m)} = 2 ∑_{i=1}^{m} \binom{m}{i}(−1)^{i−1}c_{n+m−i}^{(m)} .  (10)

Proof. For simplicity, we only prove recurrence (10) (the same argument, also proves recurrence (9)). Let A_{i} be the set of all m-compositions M of n + m with a positive entry in position (i, 1) along the first column. Since the first column of M is non-zero, it follows that C_{n+m}^{(m)} = A_{1} ∪ ⋯ ∪ A_{m}. Hence, by the Principle of Inclusion-Exclusion, we have

c_{n+m}^{(m)} = |A_{1} ∪ ⋯ ∪ A_{m}| = ∑_{{S⊆[m] \atop S≠∅}}(−1)^{|S|−1} |⋂_{i∈S} A_{i}| .

The set ⋂_{i∈S} A_{i} is formed of all m-compositions M = [x_{ij}] of n + m having positive entries in the first column in all positions indexed by S. If, for every i ∈ S, we replace the entry x_{i1} with x_{i1}−1 , then the first column of M either becomes the zero vector or it remains different from it. In the first case, removing the first column, we have an m-compositions of n+m−|S|. In the second case, we have an m-composition of n + m − |S|. Hence |⋂_{i∈S} A_{i}| = 2 c_{n+m−|S|}^{(m)} . Since this identity depends only on the size of S, we obtain (10).

Remark 6. For m = 2 , recurrence (10) reduces to the recurrence c_{n+2} = 4c_{n+1} − 2c_{n}, already obtained in [16]. For m = 3 and 4 , we have the following recurrences

c_{n+3}^{(3)} = 6c_{n+2}^{(3)} − 6c_{n+1}^{(3)} + 2c_{n}^{(3)}, c_{n+4}^{(4)} = 8c_{n+3}^{(4)} − 12c_{n+2}^{(4)} + 8c_{n+1}^{(4)} − 2c_{n}^{(4)} .

Proposition 7. The numbers c_{nk}^{(m)} admit the explicit expression

c_{nk}^{(m)} = ∑_{i=0}^{k} \binom{k}{i}\begin{matrix}( \\ ( & {m(k − i) \atop n} & ) \\ & & ) \end{matrix}(−1)^{i} .  (11)

Similarly, the numbers c_{n}^{(m)} admit the explicit expression

c_{n}^{(m)} = ∑_{k=0}^{n} c_{nk}^{(m)} = ∑_{k=0}^{n} ∑_{i=0}^{k} \binom{k}{i}\begin{matrix}( \\ ( & {m(k − i) \atop n} & ) \\ & & ) \end{matrix}(−1)^{i} .  (12)

Proof. Let A_{i} be the set of all matrices M ∈ M_{m,k}(ℕ) where the i-th column is equal to the zero vector and σ(M) = n. By the Principle of Inclusion-Exclusion, we have

c_{nk}^{(m)} = |A′_{1} ∩ ⋯ ∩ A′_{k}| = ∑_{S⊆[k]}(−1)^{|S|} |⋂_{i∈S} A_{i}| .

The intersection ⋂_{i∈S} A_{i} is the set of all matrices M ∈ M_{mk}(ℕ) with a zero vector in all columns indexed by the elements of S. So, it is equivalent to the set of all multisets of order n on a set of size mk − m|S|, and hence |⋂_{i∈S} A_{i}| = \begin{aligned}( \\ ( & {m(k−|S|) \atop n} & ) \\ & & ) \end{aligned}. Since this identity depends only on the size of S, we have (11).

The combinatorial argument used in the proof of Proposition (7) can be easily generalized to the set C_{k}^{(m)}(r_{1}, …, r_{m}) of all m-compositions of length k where the i-th row has sum equal to r_{i}, for every i = 1, …, m. Let c_{k}^{(m)}(r_{1}, …, r_{m}) be the cardinality of such a set.

Proposition 8. The numbers c_{k}^{(m)}(r_{1}, …, r_{m}) admit the explicit expression

c_{k}^{(m)}(r_{1}, …, r_{m}) = ∑_{i=0}^{k} \binom{k}{i}\begin{aligned}( \\ ( & {k − i \atop r_{1}} & ) \\ & & ) \end{aligned} ⋯ \begin{matrix}( \\ ( & {k − i \atop r_{m}} & ) \\ & & ) \end{matrix}(−1)^{i} .  (13)

Proof. Let A_{i} be the set of all matrices M ∈ M_{m,k}(ℕ) having the i-th column equal to the zero vector, and row-sums r_{1} , …, r_{m}. Then, by the Principle of Inclusion-Exclusion, we have

c_{k}^{(m)}(r_{1}, …, r_{m}) = |A′_{1} ∩ … ∩ A′_{k}| = ∑_{S⊆[k]}(−1)^{|S|} |⋂_{i∈S} A_{i}| .

The intersection ⋂_{i∈S} A_{i} contains all matrices M ∈ M_{mk}(ℕ) with the zero vector in all columns indexed by the elements of S. Since the i-th row of such a matrix M corresponds to a multiset of order r_{i} on a set of size k − |S|, it follows that

|⋂_{i∈S} A_{i}| = \begin{aligned}( \\ ( & {k − |S| \atop r_{1}} & ) \\ & & ) \end{aligned} ⋯ \begin{aligned}( \\ ( & {k − |S| \atop r_{m}} & ) \\ & & ) \end{aligned} .

Since this cardinality depends only on the size of S, we have (13).

Identity (13) already appears in the book [1] where, however, it is proved in a formal way manipulating generating series.

Now, identities (11), (12) and (13) can be rewritten in terms of the Stirling numbers of the first kind \left[{n \atop k}\right] ([22], sequences \underline{A008275} and \underline{A048994} in [43]) the Stirling numbers of the second kind \left\{{n \atop k}\right\} ([22], sequences \underline{A008277} and \underline{A048933} in [43]), and the numbers t_{n} of preferential arrangements [24, 46, 47] (sequence \underline{A000670} in [43]).

Proposition 9. The numbers c_{nk}^{(m)} , c_{n}^{(m)} and c_{k}^{(m)}(r_{1}, …, r_{m}) can be expressed as follows:

c_{nk}^{(m)} = \frac{k!}{n!} ∑_{j=k}^{n} \left[{n \atop j}\right]\left\{{j \atop k}\right\}m^{j}  (14)

c_{n}^{(m)} = \frac{1}{n!} ∑_{k=0}^{n} \left[{n \atop k}\right]m^{k}t_{k}  (15)

c_{k}^{(m)}(r_{1}, …, r_{m}) = \frac{k!}{r_{1}! ⋯ r_{m}!} ∑_{j_{1},...,j_{m}=0}^{r_{1},...,r_{m}} ∑_{k≥0} \left[{r_{1} \atop j_{1}}\right] ⋯ \left[{r_{m} \atop j_{m}}\right]\left\{{j_{1} + ⋯ + j_{m} \atop k}\right\} .  (16)

Proof. Using the ordinary expansion

x\overline{n} = x(x + 1) ⋯ (x + n − 1) = ∑_{k=0}^{n} \left[{n \atop k}\right]x^{k}  (17)

of the rising factorials, identity (11) becomes

c_{nk}^{(m)} = \frac{1}{n!} ∑_{j=0}^{n} \left[{n \atop j}\right]m^{j} ∑_{i=0}^{k} \binom{k}{i}(k − i)^{j}(−1)^{i} .

The second sum on the right hand-side is the number of all surjective functions from an n-set to a k-set [46], and can be expressed as

∑_{i=0}^{k} \binom{k}{i}(k − i)^{n}(−1)^{i} = \left\{{n \atop k}\right\}k! .  (18)

Hence we have identity (14). Now, from (14), we have

c_{n}^{(m)} = ∑_{k=0}^{n} c_{nk}^{(m)} = ∑_{k=0}^{n} \frac{k!}{n!} ∑_{j=k}^{n} \left[{n \atop j}\right]\left\{{j \atop k}\right\}m^{j} = \frac{1}{n!} ∑_{j=0}^{n} \left[{n \atop j}\right]m^{j} ∑_{k=0}^{n} \left\{{j \atop k}\right\}k! .

Since

t_{n} = ∑_{k=0}^{n} \left\{{n \atop k}\right\} k! ,  (19)

we obtain at once identity (15). Finally, by using (17) once again, identity (13) can be written as

c_{k}^{(m)}(r_{1}, …, r_{m}) = \frac{1}{r_{1}! ⋯ r_{m}!} ∑_{j_{1},...,j_{m}=0}^{r_{1},...,r_{m}} ∑_{k≥0} \left[{r_{1} \atop j_{1}}\right] ⋯ \left[{r_{m} \atop j_{m}}\right] ∑_{i=0}^{k} \binom{k}{i}(k − i)^{j_{1}+···+j_{m}}(−1)^{i} .

Hence, from (18), we obtain (16).

Remark 10. From (14) and (15), it follows that both c_{nk}^{(m)} and c_{n}^{(m)} are polynomial expressions in m.

Remark 11. Every m-composition M ∈ C_{nn}^{(m)} is an m × n (0, 1)-matrix with exactly a 1 in each column, and hence is equivalent to a function f : [n] → [m] . So, c_{nn}^{(m)} = m^{n}. Now, by using (11), we have

∑_{k=0}^{n} \binom{n}{k}\begin{matrix}( \\ ( & {mk \atop n} & ) \\ & & ) \end{matrix}(−1)^{k} = m^{n} .

Notice that this identity can also be obtained from (14).

4 Binet-like formulas and asymptotics

In this section we will obtain a Binet-like formula and an asymptotic expansion for the coefficients c_{n}^{(m)} .

Proposition 12. The numbers c_{n}^{(m)} admit the following Binet-like formula

c_{n}^{(m)} = \frac{1}{2} [δ_{n,0} + \frac{1}{m \sqrt[m]{2}} ∑_{k=0}^{m−1} \frac{ω_{m}^{k}}{x_{k}^{n+1}} ] = \frac{1}{2} δ_{n,0} + \frac{1}{2m} ∑_{k=0}^{m−1} \frac{ω_{m}^{k}}{\sqrt[m]{2} − ω_{m}^{k}} ( \frac{\sqrt[m]{2}}{\sqrt[m]{2} − ω_{m}^{k}} )^{n}  (20)

where

x_{k} = 1 − \frac{1}{\sqrt[m]{2}} ω_{m}^{k}  (k = 0, 1, …, m − 1)  (21)

where ω_{m} = e^{2πi/m} is a primitive root of unity.

Proof. Series (2) can be rewritten as

c^{(m)}(x) = \frac{1}{2} [1 + \frac{1}{2(1 − x)^{m} − 1}] .

The roots of the polynomial at the denominator are the numbers x_{k} given in (21). Then we have the expansion in partial fractions

\frac{1}{2(1 − x)^{m} − 1} = \frac{A_{0}}{x − x_{0}} + ⋯ + \frac{A_{m−1}}{x − x_{m−1}}

where the coefficients A_{k} are defined by

A_{k} = lim_{x→x_{k}} \frac{x − x_{k}}{2(1 − x)^{m} − 1} .

By applying De l’Hopital rule, we have

A_{k} = lim_{x→x_{k}} \frac{1}{−2m(1 − x)^{m−1}} = \frac{1}{−2m(1 − x_{k})^{m−1}} = −\frac{ω_{m}^{k}}{m \sqrt[m]{2}} .

Hence

c^{(m)}(x) = \frac{1}{2} [1 − \frac{1}{x_{k}} ∑_{k=0}^{m−1} \frac{A_{k}}{1 − x/x_{k}} ] = \frac{1}{2} [1 + \frac{1}{m \sqrt[m]{2} x_{k}} ∑_{k=0}^{m−1} \frac{ω_{m}^{k}}{1 − x/x_{k}} ]

from which we obtain (20).

Proposition 13. For n → ∞, we have the asymptotic expansion

c_{n}^{(m)} ∼ \frac{1}{2m( \sqrt[m]{2} − 1)} ( \frac{\sqrt[m]{2}}{\sqrt[m]{2} − 1})^{n} .

In particular, we have the limit

lim_{n→∞} \frac{c_{n}^{(m)}}{c_{n+1}^{(m)}} = 1 − \frac{1}{\sqrt[m]{2}} .

Proof. The statement follows at once from the fact that the dominant singularity (i.e., the root with minimum modulus) is x_{0} = 1 − 1/ \sqrt[m]{2} .

5 Combinatorial interpretations

5.1 Colored linear partitions

Matrix compositions can be interpreted in terms of linear species [6, 28] as follows. Let [m] = {1, …, m} be a set of colors, totally ordered in the natural way. We say that a linearly ordered set [n] = {1, 2, …, n} is m-colored when each of its elements is colored with one of the colors in [m] respecting the following condition: for every elements x, with color i, and y with color j, if x ≤ y then i ≤ j. In other words, an m-coloring of [n] is an order-preserving map γ : [n] → [m] . We define an m-colored linear partition of [n] as a linear partition in which each block is m-colored.

The m-compositions of length k of n are equivalent to the m-colored linear partitions of [n] with k blocks. Indeed, any M ∈ C_{nk}^{(m)} corresponds to the m-colored linear partition π of [n] obtained transforming the i-th column (h_{1}, …, h_{m}) of M into the i-th block of π of size h_{1} + ⋯ + h_{m} with the first h_{1} elements of color 1 , …, the last h_{m} elements of color m, for every i = 1, …, k. For instance, the 3-composition

M = [\begin{matrix}2 & 0 & 1 & 2 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 2 \end{matrix}]  (22)

corresponds to the following 3-colored partition of the set {1, 2, 3, …, 11}

[figure: 1; 1; 3; 2; 1; 3; 1; 1; 2; 3; 3]

which can also be represented as π = [[1, 1, 3], [2], [1, 3], [1, 1, 2, 3, 3]] .

Proposition 14. Let C^{(m)} be the linear species of m-compositions, i.e., the linear species of m-colored linear partitions. Let G be the uniform linear species. Let Map_{≠∅}^{(m)} be the linear species of multisets of non-zero order on the set [m] . Then

C^{(m)} = G ∘ Map_{≠∅}^{(m)} .  (23)

Proof. To give an m-colored linear partition on a linearly ordered set L is equivalent to assign a linear partition π on L and then an m-coloring (i.e., an order-preserving map in [m] ) on each block of π. Since an order-preserving map f : [k] → [m] is equivalent to a multiset of order k on the set [m] , we have at once (23).

Remark 15. From identity (23), we reobtain at once (2). Indeed, since Card(G; x) = 1/(1−x) and Card(Map_{≠∅}^{(m)}; x) = h^{(m)}(x) , where h^{(m)}(x) is series (3), we have Card(C^{(m)}; x) = Card(G; x) ∘ Card(Map_{≠∅}^{(m)}; x) = c^{(m)}(x) .

Using this interpretation, we can obtain the following identities we will employ in Section 6 to prove a Cassini-like identity.

Proposition 16. We have the following identity

c_{i+j+1}^{(m)} = ∑_{h,k≥0} \begin{aligned}( \\ ( & {m \atop h + k + 1} & ) \\ & & ) \end{aligned}c_{i−h}^{(m)}c_{j−k}^{(m)} .  (24)

Proof. Let L = {x_{1}, …, x_{i+1}, …, x_{i+j+1}} be a linearly ordered set with size i + j + 1 and let π ∈ C^{(m)}[L] . The element x_{i+1} belongs to a block B of the form {x_{i−h+1}, …, x_{i}, x_{i+1}, x_{i+2}, …, x_{i+k+1}} with h, k ∈ ℕ, as in the following picture:

[figure: π_{1}; π_{2}; x_{i+1}; x_{i}; x_{i+2}; x_{i−h+1}; x_{i+k+1}; i − h; h; k; j − k]

Removing the block B, π splits into an m-colored linear partition π_{1} on a linear order of size i − h and into an m-colored linear partition π_{2} on a linear order of size j − k.

Proposition 17. We have the identity

\begin{aligned}( \\ ( & {m \atop i + j + 1} & ) \\ & & ) \end{aligned} = ∑_{k=1}^{m} \begin{aligned}( \\ ( & {k \atop i} & ) \\ & & ) \end{aligned}\begin{aligned}( \\ ( & {m − k + 1 \atop j} & ) \\ & & ) \end{aligned} = ∑_{k=0}^{m−1} \binom{i + k}{i}\begin{aligned}( \\ ( & {m − k \atop j} & ) \\ & & ) \end{aligned} .  (25)

Proof. The coefficient \begin{aligned}( \\ ( & {m \atop i+j+1} & ) \\ & & ) \end{aligned} gives the number of all the order-preserving maps f : [i + j + 1] → [m] . Now, suppose that f(i + 1) = k, with k ∈ [m] . Since f is orderpreserving, it follows that f(x) ∈ [k] for every x ∈ [i] and f(x) ∈ {k, …, m} for every x ∈ {i + 2, …, i + j + 1}. Hence we have at once identity (25).

5.2 Surjective families of order-preserving maps

Let P_{1} , …, P_{m} and Q be finite linearly ordered sets. We say that F = {f_{i} : P_{i} → Q}_{i=1}^{m} is a surjective family of order-preserving maps when for every element q ∈ Q there exists at least one index i and one element p ∈ P_{i} such that q = f_{i}(p) . The single maps are not necessarily surjective, but every element of the codomain admits at least one preimage along one of the maps of the family.

Proposition 18. Let P_{1} , …, P_{m} and Q be finite linearly ordered sets with |P_{1}| = r_{1} , …, |P_{m}| = r_{m} and |Q| = k. Then the number of all surjective families F = {f_{i} : P_{i} → Q}_{i=1}^{m} is c_{k}^{(m)}(r_{1}, …, r_{m}) .

Proof. Let Q = {q_{1}, …, q_{k}}. A surjective family F = {f_{i} : P_{i} → Q}_{i=1}^{m} is equivalent to the m-composition M of length k with row-sum vector (r_{1}, …, r_{k}) , whose i-row is r_{i} = (|f_{i}^{•}(q_{1})|, …, |f_{i}^{•}(q_{k})|) , where f_{i}^{•}(q_{j}) is the set of all preimages of q_{j} along the map f_{i}. Clearly, the sum of the i-row r_{i} is |P_{i}| = r_{i}. Moreover, since F is a surjective family, any column of M is different from the zero vector.

5.3 Labelled bargraphs

The interpretation of matrix compositions in terms of colored linear partitions can be reformulated in terms of labelled bargraphs. A bargraph is a column-convex polyomino where all columns are bottom justified (see Figure 1 (a)). A bargraph is completely determined by the height of its columns and gives a graphical representation of an ordinary composition (as already pointed out in [37]). Bargraphs, and more generally polyominoes [9], are well-known combinatorial objects. In particular, the enumeration of bargraphs according to perimeter, area and site-perimeter has been treated in [39, 40], in relation to the study of percolation models, and more recently, from an analytical point of view, in [10].

Figure 1: (a) a bargraph; (b) a labelled bargraph of degree 4.

Let M = [a_{ij}] be an m-composition, equivalent to an m-colored linear partition π = [B_{1}, …, B_{k}] where the block B_{j} has the form [1, …, 1, 2, …, 2, …, m, …, m], and for every i = 1, …, m, i occurs exactly a_{ij} times. Now, draw each block vertically as a stack of cells, and label each cell with the corresponding color. What we obtain is a bargraph in which, along each column, the labels are weakly increasing from the bottom to the top. For instance, the 3-composition (22), equivalent to the 3-colored linear partition π = [[1, 1, 3], [2], [1, 3], [1, 1, 2, 3, 3]] , is represented by the following labelled bargraph of area 11 with 4 columns:

113 2 13 11233

Similarly, the labelled bargraph in Figure 1(b) represents the following 4-composition of 33 :

[ \begin{matrix}2 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 2 & 0 \\ 0 & 1 & 0 & 3 & 1 & 0 & 0 & 3 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 & 0 & 4 & 0 & 0 & 0 & 0 & 2 \\ 0 & 0 & 0 & 1 & 2 & 1 & 0 & 0 & 2 & 2 & 0 & 1 \end{matrix} ] .

So, we define a labelled bargraph as a bargraph in which all cells are labelled with positive integers so that, along each column, the label of a cell is less then or equal to the label of the cell immediately above (if any) (see Figure 1(b)). The degree is the maximal label of the bargraph. In this way, an m-composition of n of length k is equivalent to a labelled bargraph of area n with k columns and degree at most m.

5.4 Words of a regular language on finite many letters

Matrix compositions (as concatenation of columns) can be easily encoded as words of a language on infinite letters. However, they can also be encoded as words of a regular language on the finite alphabet A_{m} = {a_{1}, ⋯, a_{m}, b_{1}, …, b_{m}}. This encoding extends the encoding described in [8] for the ordinary compositions, Let C^{(m)} be the set of all m-compositions and let ℓ : C^{(m)} → A_{m}^{∗} be the map defined in the following way. First, write an m-composition M as the formal sum (juxtaposition) of its columns. Then write each column as juxtaposition of simple columns, that is columns containing exactly one non-zero entry. Now, order all simple columns according to the position of the non-zero entry. This convention allows to write each simple column as juxtaposition of elementary columns, that is columns containing exactly one non-zero entry, equal to 1 . Finally, substitute each elementary column with a letter according to the following rules

1 0 ⋮ 0 ⟼^{ℓ} a_{1} , …, 0 ⋮ 0 1 ⟼^{ℓ} a_{m} ,  +1 0 ⋮ 0 ⟼^{ℓ} b_{1} , …, +0 ⋮ 0 1 ⟼^{ℓ} b_{m}  (26)

For instance, by applying this procedure to the 3-composition

M = [\begin{matrix}2 & 0 & 1 & 2 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 2 \end{matrix}] ,

we have

M ⇝ 2 0 1 + 0 1 0 + 1 0 1 + 2 1 2

⇝ 2 0 0 0 0 1 + 0 1 0 + 1 0 0 0 0 1 + 2 0 0 0 1 0 0 0 2

⇝ 1 1 0 0 0 0 0 0 1 + 0 1 0 + 1 0 0 0 0 1 + 1 1 0 0 0 0 0 1 0 0 0 0 0 1 1

and hence ℓ(M) = a_{1}a_{1}a_{3}b_{2}b_{1}a_{3}b_{1}a_{1}a_{2}a_{3}a_{3} .

Proposition 19. The language L^{(m)} = ℓ(C^{(m)}) on the alphabet A_{m} corresponding to the m-compositions is the regular language defined by the unambiguous regular expression

L^{(m)} = ε + L_{1}^{(m)}L_{2}^{(m)}  (27)

where ε, as usual, is the empty word, and

L_{1}^{(m)} = ( a_{1}^{+}a_{2}^{∗} ⋯ a_{m}^{∗} + a_{2}^{+}a_{3}^{∗} ⋯ a_{m}^{∗} + ⋯ + a_{m}^{+} )
L_{2}^{(m)} = ( b_{1}a_{1}^{∗}a_{2}^{∗} ⋯ a_{m}^{∗} + b_{2}a_{2}^{∗} ⋯ a_{m}^{∗} + ⋯ + b_{m}a_{m}^{∗})^{∗} .

Proof. Non-empty words in L^{(m)} are characterized by the following conditions:

1. the first letter is always an a_{i}, with i = 1, 2, …, m;

2. the letters a_{i} and b_{i} can always be followed by any b_{j}, but they can be followed by an a_{j} only when i ≤ j.

This characterization implies that the non-empty words in L^{(m)} have a unique factorization of the form xy, where

1. x is a non-empty word of the form a_{1}^{i_{1}} ⋯ a_{m}^{i_{m}}, with i_{1}, …, i_{m} ≥ 0 ;

2. y is a (possibly empty) word y = y_{1} ⋯ y_{k}, where y_{r} = b_{j}a_{j}^{q_{j}} ⋯ a_{m}^{q_{m}} with q_{j}, …, q_{m} ≥ 0 , for every r = 1, …, k.

This factorization implies at once identity (27).

Remark 20. The encoding just described is the basis for an efficient algorithm for the exhaustive generation of m-compositions, and for the definition of a Gray code on the set of m-compositions of a given size, as described in [23].

6 Cassini-like identities

For m = 2 , the numbers c_{n} satisfy the following Cassini-like identity [16]:

c_{n}c_{n+2} − c_{n+1}^{2} = −2^{n−1} (for n ≥ 1) .

This identity can be generalized to arbitrary m-compositions, as proved in the following

Proposition 21. For every m, n ≥ 1 , we have the generalized Cassini-like identity:

|\begin{matrix}c_{n}^{(m)} & c_{n+1}^{(m)} & … & c_{n+m−1}^{(m)} \\ c_{n+1}^{(m)} & c_{n+2}^{(m)} & … & c_{n+m}^{(m)} \\ ⋮ & ⋮ & & ⋮ \\ c_{n+m−1}^{(m)} & c_{n+m}^{(m)} & … & c_{n+2m−2}^{(m)} \end{matrix}| = (−1)^{⌊m/2⌋} 2^{n−1}.  (28)

Proof. Let C_{n}^{(m)} = [ c_{n+i+j}^{(m)} ]_{i,j=0}^{m−1} be the matrix appearing on the left-hand side of (28). Since the main recurrence (10) is of the form

c_{n+m}^{(m)} = α_{m−1}c_{n+m−1}^{(m)} + ⋯ + α_{1}c_{n+1}^{(m)} + α_{0}c_{n}^{(m)} (where α_{k} = (−1)^{m−k−1}2\binom{m}{k}) ,

we can simplify the last row of the determinant |C_{n}^{(m)}| simply by subtracting to it a suitable linear combination of the first m − 1 rows. More precisely, we have

|C_{n}^{(m)}| = |\begin{matrix}c_{n}^{(m)} & c_{n+1}^{(m)} & … & c_{n+m−1}^{(m)} \\ c_{n+1}^{(m)} & c_{n+2}^{(m)} & … & c_{n+m}^{(m)} \\ ⋮ & ⋮ & & ⋮ \\ c_{n+m−2}^{(m)} & c_{n+m−1}^{(m)} & … & c_{n+2m−3}^{(m)} \\ α_{0}c_{n−1}^{(m)} & α_{0}c_{n}^{(m)} & … & α_{0}c_{n+m−2}^{(m)} \end{matrix}| .

Now, we can extract α_{0} = (−1)^{m−1}2 from the last row and shift cyclically all rows downward, obtaining the identity |C_{n}^{(m)}| = 2 |C_{n−1}^{(m)}|. From this recurrence, it follows at once that

|C_{n}^{(m)}| = 2^{n−1} |C_{1}^{(m)}| (for every n ≥ 1) .

It remains to evaluate the determinant of the matrix C_{1}^{(m)} = [ c_{i+j+1}^{(m)} ]_{i,j=0}^{m−1} .

Identity (24) is equivalent to the matrix factorization

C_{1}^{(m)} = L^{(m)}M^{(m)}L_{T}^{(m)}

where

L^{(m)} = [ c_{i−j}^{(m)} ]_{i,j=0}^{m−1} and M^{(m)} = [ \begin{matrix}( \\ ( & {m \atop i + j + 1} & ) \\ & & ) \end{matrix} ]_{i,j=0}^{m−1} .

Since L^{(m)} is triangular and its diagonal entries are equal to c_{0}^{(m)} = 1 , it follows that

|C_{1}^{(m)}| = |M^{(m)}|.

Similarly, identity (25) is equivalent to the matrix factorization

M^{(m)} = B^{(m)}B̃^{(m)}

where

B^{(m)} = [ \binom{i + j}{i} ]_{i,j=0}^{m−1} and B̃^{(m)} = [ \begin{matrix}( \\ ( & {m − i \atop j} & ) \\ & & ) \end{matrix} ]_{i,j=0}^{m−1} .

Since B̃^{(m)} = J^{(m)}B^{(m)} , where J^{(m)} = [δ_{i+j,m−1}]_{i,j=0}^{m−1} , it follows that

M^{(m)} = B^{(m)}J^{(m)}B^{(m)} .

Since |J^{(m)}| = (−1)^{⌊m/2⌋} and |B^{(m)}| = 1 , it follows that |M^{(m)}| = (−1)^{⌊m/2⌋}. Finally, for every n ≥ 1 , we have

|C_{n}^{(m)}| = 2^{n−1} |C_{1}^{(m)}| = 2^{n−1} |M^{(m)}| = (−1)^{⌊m/2⌋}2^{n−1} ,

that is we have identity (28).

7 Matrix compositions without zero rows

In this section, we will consider the class of all m-compositions where all rows are different from the zero vector. Let f_{n}^{(m)} be the number of all m-compositions of n of this kind.

Proposition 22. The numbers f_{n}^{(m)} admit the explicit expression

f_{n}^{(m)} = ∑_{k=0}^{m} \binom{m}{k}(−1)^{k}c_{n}^{(m−k)} = ∑_{k=0}^{m} \binom{m}{k}(−1)^{m−k}c_{n}^{(k)} .  (29)

Proof. Let A_{i} be the set of all m-compositions M ∈ C_{n}^{(m)} where the i-th row is zero. Then, by the Principle of Inclusion-Exclusion, we have

f_{n}^{(m)} = |A′_{1} ∩ ⋯ ∩ A′_{m}| = ∑_{S⊆[m]}(−1)^{|S|} |⋂_{i∈S} A_{i}| .

Since there is an evident bijective correspondence between ⋂_{i∈S} A_{i} and the set of all (m−|S|)- compositions of n, we have at once (29).

Remark 23. Since the set C_{n}^{(m)} can be partitioned according to the number of zero rows, we also have the identity

c_{n}^{(m)} = ∑_{k=0}^{m} \binom{m}{k}f_{n}^{(k)} .  (30)

Now, by inverting this formula, we reobtain (29). Viceversa, we can obtain (30) by inverting (29).

Proposition 24. The generating series for the numbers f_{n}^{(m)} is

f^{(m)}(x) = ∑_{k=0}^{m} \binom{m}{k}(−1)^{m−k}c^{(k)}(x) = ∑_{k=0}^{m} \binom{m}{k}(−1)^{m−k} \frac{(1 − x)^{k}}{2(1 − x)^{k} − 1} .  (31)

Proof. This is an immediate consequence of identity (29).

Proposition 25. For n ≥ 1 , the numbers f_{n}^{(m)} satisfy a homogeneous linear recurrence with constant coefficients of order \binom{m+1}{2} .

Proof. Immediate consequence of the fact that the rational series (31) has the form

f^{(m)}(x) = \frac{x^{m}F_{m}(x)}{(1 − 2x)(1 − 4x + 2x^{2}) ⋯ (2(1 − x)^{m} − 1)}  (32)

where F_{m}(x) is a polynomial with degree (less than or) equal to \binom{m}{2} .

Remark 26. The recurrence satisfied by the numbers f_{n}^{(m)} can be deduced from the denominator of series (32). For instance, for m = 2 , we have the series

f^{(2)}(x) = \frac{3x^{2} − 2x^{3}}{(1 − 2x)(1 − 4x + 2x^{2})} = \frac{3x^{2} − 2x^{3}}{1 − 6x + 10x^{2} − 4x^{3}}

and hence the recurrence

f_{n+3}^{(2)} = 6f_{n+2}^{(2)} − 10f_{n+1}^{(2)} + 4f_{n}^{(2)} .

Similarly, for m = 3 , we have the series

f^{(3)}(x) = \frac{13x^{3} − 24x^{4} + 16x^{5} − 4x^{6}}{1 − 12x + 52x^{2} − 102x^{3} + 96x^{4} − 44x^{5} + 8x^{6}}

and hence the recurrence

f_{n+6}^{(3)} = 12f_{n+5}^{(3)} − 52f_{n+4}^{(3)} + 102f_{n+3}^{(3)} − 96f_{n+2}^{(3)} + 44f_{n+1}^{(3)} − 8f_{n}^{(3)} .

n  0 1 2 3 4  5  6  7  8  9  10
m = 0 1 0 0 0 0  0  0  0  0  0  0
m = 1  1 2 4 8  16  32  64  128  256  512
m = 2  3 16 66 248 892  3136  10888  37536  128880
m = 3  13 132 924 5546 30720 162396 834004  4204080
m = 4  75 1232 13064 114032 893490 6550112 45966744
m = 5  541 13060 195020 2327960 24418640 235804122
m = 6  4683 155928 3116220 48697048 657516672
Table 2: The numbers f_{n}^{(m)} .

Proposition 27. The numbers f_{n}^{(m)} have the following explicit expression

f_{n}^{(m)} = ∑_{{ρ∈ℙ^{m} \atop |ρ|=n}} ∑_{k≥0} ∑_{i=0}^{k} \binom{k}{i}\begin{aligned}( \\ ( & {k − i \atop r_{1}} & ) \\ & & ) \end{aligned} ⋯ \begin{matrix}( \\ ( & {k − i \atop r_{m}} & ) \\ & & ) \end{matrix}(−1)^{i} ,  (33)

where ℙ is the set of all positive integers.

Proof. Since f_{n}^{(m)} counts all m-compositions with non-zero row-sums, we have

f_{n}^{(m)} = ∑_{k≥0} ∑_{{(r_{1},...,rm)∈ℙ^{m} \atop r_{1}+···+rm=n}} c_{k}^{(m)}(r_{1}, …, r_{m}) = ∑_{k≥0} ∑_{{ρ∈ℙ^{m} \atop |ρ|=n}} c_{k}^{(m)}(ρ)

where ρ = (r_{1}, …, r_{m}) and |ρ| = r_{1} + ⋯ + r_{m}. Hence, by (13), we have at once (33).

Let f_{nk}^{(m)} be the number of all m-compositions, without zero rows, of n of length k.

Proposition 28. The numbers f_{nk}^{(m)} admit the explicit expression

f_{nk}^{(m)} = ∑_{i=0}^{m} ∑_{j=0}^{k} \binom{m}{i}\binom{k}{j}\begin{matrix}( \\ ( & {(m − i)(k − j) \atop n} & ) \\ & & ) \end{matrix}(−1)^{i+j} .  (34)

Proof. Let A_{ij} be the set of all matrices M ∈ M_{mk}(ℕ) with the i-th row and the j-th column equal to the zero vector. Then, by the Principle of Inclusion-Exclusion, we have

f_{nk}^{(m)} = | ⋂_{(i,j)∈[m]×[k]} A′_{ij}| = ∑_{{I⊆[m] \atop J⊆[k]}}(−1)^{|I|+|J|} |⋂_{{i∈I \atop j∈J}} A_{ij}| .

Since the intersection ⋂_{i∈I, j∈J} A_{ij} is in bijective correspondence with the set of all multisets of order n on a set of size (m − |I|)(k − |J|) , identity (34) follows at once.

Also the numbers f_{nk}^{(m)} and f_{n}^{(m)} can be expressed in terms of Stirling numbers and of the numbers t_{k} of preferential arrangements.

Proposition 29. The numbers f_{nk}^{(m)} can be expressed as

f_{nk}^{(m)} = \frac{m!k!}{n!} ∑_{h=0}^{n} \left[{n \atop h}\right]\left\{{h \atop m}\right\}\left\{{h \atop k}\right\} .  (35)

Similarly, the numbers f_{n}^{(m)} can be expressed as

f_{n}^{(m)} = \frac{m!}{n!} ∑_{k=m}^{n} \left[{n \atop k}\right]\left\{{k \atop m}\right\}t_{k} .  (36)

Proof. By using (17), identity (34) can be rewritten as

f_{nk}^{(m)} = \frac{1}{n!} ∑_{h=0}^{n} \left[{n \atop h}\right] ∑_{i=0}^{m} \binom{m}{i}(m − i)^{h}(−1)^{i} ∑_{j=0}^{k} \binom{k}{j}(k − j)^{h}(−1)^{j} .

Now, by (18), we have (35). Finally, using the fact that f_{n}^{(m)} = ∑_{k=0}^{n} f_{nk}^{(m)} and identities (19) and (35), we have at once identity (36).

Clearly, f_{n}^{(m)} = 0 whenever n < m. In particular, we have

f_{n}^{(n)} = t_{n} , f_{n+1}^{(n)} = \frac{n}{2} (t_{n+1} + t_{n}) ,

f_{n+2}^{(n)} = \frac{n}{24} [(3n + 1)t_{n+2} + 6(n + 1)t_{n+1} + (3n + 5)t_{n}] .

The identity f_{n}^{(n)} = t_{n} can also be proved combinatorially since preferential arrangements can be represented as matrix compositions in a very natural way. Since a preferential arrangement is a set partition in which the blocks are linearly ordered [24, 46, 47], with a given preferential arrangement π = (B_{1}, …, B_{k}) of an n-set X we can always associate the matrix M having as columns the characteristic vectors of the blocks of π. For instance, the preferential arrangement π = ({2, 3}, {1, 5}, {4}) of the set X = {1, 2, 3, 4, 5} corresponds to the matrix

M = [\begin{matrix}0 & 1 & 0 \\ 1 & 0 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{matrix}] .

So, if π is a partition of an n-set with k blocks, then the matrix M has n rows each of which contains exactly one non-zero entry equal to 1 , k columns different from the zero vector and σ(M) = n. This means that M is an n-composition of n without zero rows. Since this correspondence is clearly a bijection between the class of preferential arrangements of an n-set and the class of n-composition of n without zero rows, there follows the identity f_{n}^{(n)} = t_{n}.

\begin{matrix}n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ m = 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ m = 1 & 1 & 1 & 1 & 3 & 4 & 7 & 14 & 23 & 39 & 71 & 124 \\ m = 2 & 1 & 2 & 5 & 18 & 53 & 162 & 505 & 1548 & 4756 & 14650 & 45065 \\ m = 3 & 1 & 3 & 12 & 58 & 255 & 1137 & 5095 & 22749 & 101625 & 454116 & 2028939 \\ m = 4 & 1 & 4 & 22 & 136 & 793 & 4660 & 27434 & 161308 & 948641 & 5579224 & 32811986 \\ m = 5 & 1 & 5 & 35 & 265 & 1925 & 14056 & 102720 & 750255 & 5480235 & 40031030 & 292408771 \\ m = 6 & 1 & 6 & 51 & 458 & 3984 & 34788 & 303902 & 2654064 & 23179743 & 202445610 & 1768099107 \end{matrix}

Table 3: The numbers z_{n}^{(m)} .

Remark 30. Another kind of matrix compositions are packed matrices [20], that is matrices with nonnegative integer entries without zero rows or zero columns. Let b_{n} be the number of all packed matrices M with σ(M) = n. These numbers form sequence \underline{A120733} in [43], and, by (36), can be expressed as

b_{n} = ∑_{m=0}^{n} f_{n}^{(m)} = \frac{1}{n!} ∑_{k=0}^{n} \left[{n \atop k}\right]t_{k}^{2} .

8 Matrix compositions of Carlitz type

We say that an m-composition is of Carlitz type when no two adjacent columns are equal. For m = 1 , we have the ordinary Carlitz compositions [11] (see also [13, 33, 29] and [18]). Let z_{n}^{(m)} be the number of all m-composition of n of Carlitz type. For m = 1 we have sequence \underline{A003242} in [43], while for m ≥ 2 we have new sequences (see Table 3).

Proposition 31. The generating series of the numbers z_{n}^{(m)} is

z^{(m)}(x) = ∑_{n≥0} z_{n}^{(m)} x^{n} = \frac{1}{1 − ∑_{k≥1} \begin{aligned}( \\ ( & {m \atop k} & ) \\ & & ) \end{aligned}\frac{x^{k}}{1 + x^{k}}} ,  (37)

or, equivalently,

z^{(m)}(x) = \frac{1}{1 + ∑_{k≥1}(−1)^{k} \frac{1 − (1 − x^{k})^{m}}{(1 − x^{k})^{m}}} = \frac{1}{1 + ∑_{k≥1}(−1)^{k}h^{(m)}(x^{k})} .  (38)

Proof. Let x_{μ} be an indeterminate marking a column of an m-matrix equivalent to a multiset μ ∈ M_{≠0}^{(m)} , and let X be the set of all these indeterminates. Let z^{(m)}(X) be the generating series for the set of all m-compositions of Carlitz type and let z_{μ}^{(m)}(X) be the generating series for the set of all m-compositions of Carlitz type whose last column corresponds to the multiset μ. Then we have at once the linear system

\begin{cases}z^{(m)}(X) = 1 + ∑_{μ∈M_{≠0}^{(m)}} z_{μ}^{(m)}(X) \\ z_{μ}^{(m)}(X) = (z^{(m)}(X) − z_{μ}^{(m)}(X)) x_{μ} ∀ μ ∈ M_{≠0}^{(m)} \end{cases}

from which

z_{μ}^{(m)}(X) = \frac{x_{μ}}{1 + x_{μ}} z^{(m)}(X) and z^{(m)}(X) = \frac{1}{1 − ∑_{μ∈M_{≠0}^{(m)}} \frac{x_{μ}}{1 + x_{μ}}} .

Now, to obtain (37) it is sufficient to substitute x_{μ} with x^{ord(μ)} in z^{(m)}(X) .

Finally, (38) can be obtained with the same argument used in [11] by Carlitz, or simply by rewriting in a suitable way the series at the denominator of (37).

Proposition 32. The numbers z_{n}^{(m)} can be expressed as

z_{n}^{(m)} = ∑_{k≥0} ∑_{{α,β∈ℙ^{k} \atop α·β=n}} \begin{matrix}( \\ ( & {m \atop α} & ) \\ & & ) \end{matrix}(−1)^{|β|−k} .  (39)

where, for every α = (a_{1}, …, a_{k}) and β = (b_{1}, …, b_{k}) , α · β = a_{1}b_{1} + ⋯ + a_{k}b_{k}, |β| =

b_{1} + ⋯ + b_{k} and \begin{aligned}( \\ ( & {m \atop α} & ) \\ & & ) \end{aligned} = \begin{aligned}( \\ ( & {m \atop a_{1}} & ) \\ & & ) \end{aligned} … \begin{aligned}( \\ ( & {m \atop a_{k}} & ) \\ & & ) \end{aligned}.

Proof. From (37), we have

z^{(m)}(x) = ∑_{k≥0} (∑_{n≥1} \begin{aligned}( \\ ( & {m \atop n} & ) \\ & & ) \end{aligned}\frac{x^{n}}{1 + x^{n}} )^{k}

= ∑_{k≥0} ∑_{a_{1}≥1} \begin{aligned}( \\ ( & {m \atop a_{1}} & ) \\ & & ) \end{aligned}\frac{x^{a_{1}}}{1 + x^{a_{1}}} ⋯ ∑_{a_{k}≥1} \begin{aligned}( \\ ( & {m \atop a_{k}} & ) \\ & & ) \end{aligned}\frac{x^{a_{k}}}{1 + x^{a_{k}}}

= ∑_{k≥0} ∑_{a_{1},...,a_{k}≥1} \begin{aligned}( \\ ( & {m \atop a_{1}} & ) \\ & & ) \end{aligned} … \begin{aligned}( \\ ( & {m \atop a_{k}} & ) \\ & & ) \end{aligned}\frac{x^{a_{1}}}{1 + x^{a_{1}}} ⋯ \frac{x^{a_{k}}}{1 + x^{a_{k}}}

= ∑_{k≥0} ∑_{{a_{1},...,a_{k}≥1 \atop b_{1},...,b_{k}≥1}} \begin{aligned}( \\ ( & {m \atop a_{1}} & ) \\ & & ) \end{aligned} … \begin{matrix}( \\ ( & {m \atop a_{k}} & ) \\ & & ) \end{matrix}(−1)^{b_{1}+···+b_{k}−k}x^{a_{1}b_{1}+···+a_{k}b_{k}}

= ∑_{n≥0} (∑_{k≥0} ∑_{{α,β∈ℕ^{k}_{0} \atop α·β=n}} \begin{matrix}( \\ ( & {m \atop α} & ) \\ & & ) \end{matrix}(−1)^{|β|−k}) x^{n}

Hence, we have (39).

n  0 1 2 3 4  5  6  7  8  9  10
m = 0 1 0 0 0 0  0  0  0  0  0  0
m = 1  1 1 3 4  7  14  23  39  71  124
m = 2  3 12 45 148 477  1502  4678  14508  44817
m = 3  13 108 672 3622 18174 87474  410379  1894116
m = 4  75 1056 10028 79508 570521 3850376 24966124
m = 5  541 11520 155840 1705915 16529925 148188201
m = 6  4683 140256 2566554 37084794 465922722
Table 4: The numbers g_{n}^{(m)} .

\begin{matrix}n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ m = 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ m = 1 & 1 & 1 & 2 & 2 & 4 & 4 & 8 & 8 & 16 & 16 & 32 \\ m = 2 & 1 & 2 & 5 & 8 & 18 & 28 & 62 & 96 & 212 & 328 & 724 \\ m = 3 & 1 & 3 & 9 & 19 & 48 & 96 & 236 & 468 & 1146 & 2270 & 5556 \\ m = 4 & 1 & 4 & 14 & 36 & 101 & 240 & 648 & 1520 & 4082 & 9560 & 25660 \\ m = 5 & 1 & 5 & 20 & 60 & 185 & 501 & 1470 & 3910 & 11390 & 30230 & 88002 \\ m = 6 & 1 & 6 & 27 & 92 & 309 & 930 & 2939 & 8640 & 27048 & 79280 & 247968 \end{matrix}

Table 5: The numbers p_{n}^{(m)} .

Now, let g_{n}^{(m)} be the number of all m-compositions of Carlitz type of n without zero rows. With arguments completely similar to the ones used in the case of ordinary m-compositions, we have

z_{n}^{(m)} = ∑_{k=0}^{m} \binom{m}{k}g_{n}^{(k)} and g_{n}^{(m)} = ∑_{k=0}^{m} \binom{m}{k}(−1)^{m−k}z_{n}^{(k)} .  (40)

Every n-composition of n without zero rows is necessarily of Carlitz type. Indeed, it corresponds to a preferential arrangement and this implies at once that there are no two equal columns. Then g_{n}^{(n)} = f_{n}^{(n)} = t_{n}.

9 Matrix compositions with palindromic rows

An ordinary composition is palindromic when its elements are the same in the given or in the reverse order [14, 15, 27, 37]. Here, we say that an m-composition is palindromic when all its rows are palindromic. For instance,

M = [\begin{matrix}1 & 2 & 1 & 2 & 1 \\ 2 & 0 & 3 & 0 & 2 \\ 0 & 0 & 1 & 0 & 0 \\ 3 & 1 & 1 & 1 & 3 \end{matrix}]

is a palindromic 4-composition of length 5 of 24 . Let p_{n}^{(m)} be the number of all palindromic m-compositions of n (see Table 5).

m/n 0 1 2 3 4 5 6 7  8  9  10
m = 0 1 0 0 0 0 0 0 0  0  0  0
m = 1  1 2 2 4 4 8 8 16 16  32
m = 2  1 4 10 20 46 80 180 296 660
m = 3  1 6 24 74 204 558 1334 3480
m = 4  1 8 44 192 706 2384 7652
m = 5  1 10 70 400 1930 8182
m = 6  1 12 102 724 4404
Table 6: The numbers q_{n}^{(m)} .

Proposition 33. The generating series for the palindromic m-compositions is

p^{(m)}(x) = ∑_{n≥0} p_{n}^{(m)} x^{n} = \frac{(1 + x)^{m}}{2(1 − x^{2})^{m} − 1} .  (41)

In particular, the numbers p_{n}^{(m)} can be expressed as

p_{n}^{(m)} = ∑_{k=0}^{⌊n/2⌋} \begin{aligned}( \\ ( & {m \atop n − 2k} & ) \\ & & ) \end{aligned}c_{k}^{(m)} .  (42)

Proof. A palindromic m-composition of even length has the form [M|M_{s}] and a palindromic m-composition of odd length has the form [M|v|M_{s}] , where M is an arbitrary mcomposition, M_{s} is the specular m-composition obtained from M by reversing every row and v is an arbitrary non-zero column vector. Hence

p^{(m)}(x) = c^{(m)}(x^{2}) + [\frac{1}{(1 − x)^{m}} − 1] c^{(m)}(x^{2}) = \frac{c^{(m)}(x^{2})}{(1 − x)^{m}} ,

that is (41). Finally, identity (42) can be obtained by expanding the series on the right-hand side of the above equations.

Now, let q_{n}^{(m)} be the number of all m-compositions of n with palindromic non-zero rows (see Table 6). With arguments similar to those used in the case of ordinary m-compositions, we have

p_{n}^{(m)} = ∑_{k=0}^{m} \binom{m}{k}q_{n}^{(k)} and q_{n}^{(m)} = ∑_{k=0}^{m} \binom{m}{k}(−1)^{m−k}p_{n}^{(k)} .  (43)

When n = m, the column vector with all entries equal to 1 is the only n-composition with palindromic rows. So, q_{n}^{(n)} = 1 .

10 Matrices generated by m-compositions

Identities (29), (30), (40) and (43) can be reformulated in terms of matrices. In particular, we will consider the following pairs of infinite matrices.

1. The matrix C = [c_{n}^{(m)}]_{m,n≥0} generated by m-compositions (see Table 1), and the the upper triangular matrix F = [f_{n}^{(m)}]_{m,n≥0} generated by m-compositions without zero rows (see Table 2).

2. The matrix Z = [z_{n}^{(m)}]_{m,n≥0} generated by m-compositions of Carlitz type (see Table 3), and the upper triangular matrix G = [g_{n}^{(m)}]_{m,n≥0} generated by m-compositions of Carlitz type without zero rows (see Table 4).

3. The matrix P = [p_{n}^{(m)}]_{m,n≥0} generated by m-compositions with palindromic rows (see Table 5), and the upper triangular matrix Q = [q_{n}^{(m)}]_{m,n≥0} generated by m-compositions with palindromic rows without zero rows (see Table 6).

Finally, we also need the ordinary binomial matrix B = [\binom{m}{n}]_{m,n≥0} . Moreover, if X = [x_{ij}]_{i,j≥0} if an infinite matrix, then we can always consider the partial matrices X_{k} = [x_{ij}]_{i,j=0}^{k}, for every k ∈ ℕ.

Proposition 34. We have the following LU-factorizations over ℕ: C = BF , Z = BG, P = BQ. Similarly, C_{k} = B_{k}F_{k}, Z_{k} = B_{k}G_{k}, P_{k} = B_{k}Q_{k}, for every k ∈ ℕ.

Proposition 35. For every k ∈ ℕ, we have det C_{k} = det Z_{k} = t_{0}t_{1} ⋯ t_{k} and det P_{k} = 1 .

Proof. Since B_{k}, F_{k}, G_{k} and Q_{k} are triangular matrices and f_{n}^{(n)} = g_{n}^{(n)} = t_{n} and q_{n}^{(n)} = 1 for every n ∈ ℕ, the factorizations in Proposition 34 and Binet’s theorem imply at once the stated identities.

11 Final remarks

In this final section, we present some open problems on matrix compositions and some possible lines of research on this topic.

L-convex polyominoes. As remarked in the introduction, 2-compositions have been introduced in [16] to provide a simple encoding of L-convex polyominoes. This result led us to consider m-compositions with the hope of encoding some larger class of polyominoes. To find such larger classes of polyominoes, however, seems to be much more problematic and is still a completely open problem.

Labelled bargraphs. The simple correspondence between m-compositions and labelled bargraphs with degree at most m (considered in Subsection 5.3) suggests to study some particular subclasses of matrix compositions arising in a very natural way as subclasses of bargraphs, such as the following ones.

1. The class of bargraphs having all the m labels in each column (Figure 2(a)), corresponding to the set of m-compositions containing no 0’s.

Figure 2: Labelled bargraphs of degree 3: (a) having all the labels in each of its columns;

(b) a 3-partition; (c) a labelled stack of degree 3.

2. The class of labelled Ferrers diagrams, i.e., labelled bargraphs in which each column has height greater than or equal to the height of the column on its right (see Figure 2 (b)). A labelled Ferrers diagram of degree m corresponds to an m-composition such that the sum of the entries of each column is greater than or equal to the sum of the entries of column on its right. We call these objects m-partitions. This definition is motivated by the fact that the ordinary partitions correspond to Ferrers diagrams, that is labelled Ferrers diagrams of degree 1 . For instance, the bargraph in Figure 2 (b) corresponds to the following 3-partition of 20 :

[\begin{matrix}1 & 3 & 0 & 1 & 0 & 0 \\ 4 & 0 & 1 & 2 & 0 & 1 \\ 1 & 2 & 2 & 0 & 2 & 0 \end{matrix}] .

3. The class of labelled stacks, that is of labelled bargraphs in which each row is connected. These objects have the shape of stack polyominoes, as can be seen in Figure 2(c). Given a labelled stack, let c_{i} be the sum of the entries of its i-th column. Then a labelled stack of degree m corresponds to an m-composition in which the sequence c_{1}, …, c_{k} is unimodal.

The problem of generating efficiently the m-partitions has been studied in [23], while the problem of enumerating labelled Ferrers diagrams and labelled stacks has been solved in [38], in a more general context.

m-colored compositions. Another interesting problem concerns the generalization to matrix compositions of the poset of ordinary compositions considered by Björner and Stanley [8]. A first step in this direction has been made, independently, by Drake and Petersen in [19], where they introduced the m-colored compositions. What is relevant here is that the m-colored compositions can be considered as a particular kind of matrix compositions. Indeed an m-colored composition α is an ordered tuple of “colored” positive integers, that is α = (a_{1}ω^{s_{1}}, …, a_{k}ω^{s_{k}}) , where the a_{i}’s are positive integers, ω is a primitive m-root of unity and 0 ≤ s_{i} ≤ m−1 for each i = 1, …, k. The i-th part of α is a_{i}ω^{s_{i}} and has color ω^{s_{i}}. Moreover, α is an m-colored composition of an integer number n when a_{1}+⋯+a_{k} = n. Hence an m-colored composition α of a integer n is uniquely represented by the m-composition M(α) of n where in column i appears exactly one non-zero entry, equal to a_{i}, in position (s_{i} +1, i) , for each i = 1, …, k. So, for instance, the 3-colored composition α = (2ω, 3, 1, ω^{2}, 3ω) of 10 is equivalent to the 3-composition

M(α) = [\begin{matrix}0 & 3 & 1 & 0 & 0 \\ 2 & 0 & 0 & 0 & 3 \\ 0 & 0 & 0 & 1 & 0 \end{matrix}] .

This suggests that the poset of m-colored compositions can be generalized to a poset of matrix compositions. This generalization will be studied in detail in a further work. Finally, it could be interesting to study the natural generalization of m-compositions to r-colored m-compositions.

References

[1] G. E. Andrews, The Theory of Partitions, Encyclopedia of Mathemetics and its Applications, Addison-Wesley Publishing Company, Reading, Massachusetts, 1976.

[2] G. E. Andrews, The theory of compositions, II: Simon Newcom’s problem, Utilitas Math. 7 (1975), 33–54.

[3] G. E. Andrews, The theory of compositions, I: The ordered factorizations of n and a conjecture of C. Long, Canadian Math. Bull. 18 (1976), 479–484.

[4] G. E. Andrews, The theory of compositions, III: The MacMahon formula and the Stanton-Cowan numbers, Utilitas Math. 9 (1976), 283–290.

[5] F. Bergeron, M. Bousquet-Mélou, and S. Dulucq, Standard paths in the composition poset, Ann. Sci. Math. Québec 19 (1995), 139–151.

[6] F. Bergeron, G. Labelle, and P. Leroux, Combinatorial Species and Tree-like Structures, Encyclopedia of Mathematics and Its Applications 67, G.-C. Rota editor, Cambridge University Press, Cambridge, 1998.

[7] A. Björner and B. Sagan, Rationality of the Möbius function of a composition poset, Theoret. Comput. Sci. 359 (2006), 282–298.

[8] A. Björner and R. Stanley, An analogue of Young’s lattice for compositions, preprint at arXiv:math/0508043v4.

[9] M. Bousquet-Mélou, A method for the enumeration of various classes of column-convex polygons, Discrete Math. 154 (1996), 1–25.

[10] M. Bousquet-Mélou and A. Rechnitzer, The site-perimeter of bargraphs, Adv. in Appl. Math. 31 (2003), 86–112.

[11] L. Carlitz, Restricted compositions, Fibonacci Quart. 14 (1976), 254–264.

[12] L. Carlitz, Enumeration of compositions by rises, falls and levels. Math. Nachr. 77 (1977), 361–371.

[13] L. Carlitz, Restricted compositions. II, Fibonacci Quart. 17 (1979), 321–328.

[14] P. Chinn and S. Heubach, Compositions of n with no occurrence of k, Proceedings of the Thirty-Fourth Southeastern International Conference on Combinatorics, Graph Theory and Computing. Congr. Numer. 164 (2003), 33–51.

[15] P. Chinn and S. Heubach, Integer sequences related to compositions without 2’s, J. Integer Seq. 6 (2003).

[16] G. Castiglione, A. Frosini, E. Munarini, A. Restivo, and S. Rinaldi, Combinatorial aspects of L-convex polyominoes, Europ. J. Comb. 28 (2007), 1724–1741.

[17] L. Comtet, Advanced Combinatorics, Reidel, Dordrecht-Holland, Boston, 1974.

[18] S. Corteel and P. Hitczenko, Generalizations of Carlitz compositions, J. Integer Seq. 10 (2007), Article 07.8.8, 13 pp. (electronic).

[19] B. Drake and T. K. Petersen, The m-colored composition poset, Electron. J. Combin. 14 (2007), Research Paper 23, 14 pp. (electronic).

[20] G. Duchamp, F. Hivert, and J.-Y. Thibon, Noncommutative symmetric functions VI: Free quasi-symmetric functions and related algebras, Internat. J. Alg. Comp. 12 (2002), 671–717.

[21] A. Frosini and S. Rinaldi, On the sequence \underline{A079500} and its combinatorial interpretations, J. Integer Seq. 9 (2006), Article 06.3.1, 13 pp. (electronic).

[22] R. L. Graham, D. E. Knuth, and O. Patashnik, Concrete Mathematics, Addison-Wesley, Reading, Massachusetts, 1989.

[23] E. Grazzini, E. Munarini, M. Poneti, and S. Rinaldi, m-compositions and m-partitions: exhaustive generation and Gray code, Pure Math. Appl. 17 (2006), 111–121.

[24] O. A. Gross, Preferential arrangements, Amer. Math. Monthly 69 (1962), 4–8.

[25] S. Heubach and T. Mansour, Compositions of n with parts in a set, Proceedings of the Thirty-Fifth Southeastern International Conference on Combinatorics, Graph Theory and Computing. Congr. Numer. 168 (2004), 127–143.

[26] S. Heubach and T. Mansour, Counting rises, levels, and drops in compositions, Integers 5 (2005), A11, 24 pp. (electronic).

[27] V. E. Hoggatt, Jr. and M. Bicknell, Palindromic compositions, Fibonacci Quart. 13 (1975), 350–356.

[28] A. Joyal, Une théorie combinatoire des séries formelles, Adv. in Math. 42 (1981), 1–82.

[29] A. Knopfmacher and H. Prodinger, On Carlitz compositions, European J. Combin. 19 (1998), 579–589.

[30] A. Knopfmacher and N. Robbins, Compositions with parts constrained by the leading summand, Ars Combinatorica 76 (2005), 287–295.

[31] Z. Lin and H. Rui, Cyclotomic Q-Schur algebras and Schur-Weyl duality. Representations of algebraic groups, quantum groups, and Lie algebras, 133–155, Contemp. Math., 413, Amer. Math. Soc., Providence, RI, 2006.

[32] G. Louchard, Matrix compositions: a probabilistic approach, Proceedings of GASCom and Bijective Combinatorics 2008, Bibbiena, Italy, 159–170.

[33] G. Louchard and H. Prodinger, Probabilistic analysis of Carlitz compositions, Discrete Math. Theor. Comput. Sci. 5 (2002), 71–95 (electronic).

[34] P. A. MacMahon, Memoir on the theory of the compositions of numbers, Phil. Trans. Royal Soc. 184 (1894), 835–901.

[35] P. A. MacMahon, Second memoir on the compositions of numbers, Phil. Trans. Royal Soc. 207 (1908), 65–134.

[36] P. A. MacMahon, Combinatory Analysis, vol. 1, Cambridge Univerity Press, Cambridge 1915 (reprinted: Chelsea, New York 1960).

[37] D. Merlini, F. Uncini, and C. Verri, A unified approach to the study of general and palindromic compositions, Integers 4 (2004), A23, 26 pp. (electronic).

[38] E. Munarini, Column enriched bargraphs, preprint.

[39] A. L. Owczarek and T. Prellberg, Exact solution of the discrete (1+1)-dimensional SOS model with field and surface interactions, J. Stat. Phys. 70 (1993), 1175–1194.

[40] T. Prellberg and R. Brak, Critical exponents from non-linear functional equations for partially directed cluster models, J. Stat. Phys. 78 (1995), 701–730.

[41] J. Riordan, An Introduction to Combinatorial Analysis, Dover Publications, 2002.

[42] B. Sagan and V. R. Vatter, The Möbius function of a composition poset, J. Algebraic Combin. 24 (2006), 117–136.

[43] N. J. A. Sloane, On-Line Encyclopedia of Integer Sequences, published electronically at

    http://www.research.att.com/~njas/sequences/.

[44] J. Snellman, Saturated chains in composition posets, preprint availeble at

    arXiv:math.CO/0505262.

[45] J. Snellman, Standard paths in another composition poset, Electron. J. Combin. 11 (1) (2004), Research Paper 76, 8 pp. (electronic).

[46] R. P. Stanley, Enumerative Combinatorics, Volume 1, Cambridge Studies in Advanced Mathematics 49, Cambridge University Press, Cambridge, 1997.

[47] H. S. Wilf, Generatingfunctionology, Academic Press, Boston, MA, 1990.

2000 Mathematics Subject Classification: Primary 05A17; Secondary 05A15.

Keywords: compositions, multisets, Cassini identity, Carlitz compositions, palindromic compositions, preferential arrangements, bargraphs, Stirling number, enumeration.

(Concerned with sequences \underline{A000670}, \underline{A003242}, \underline{A008275}, \underline{A008277}, \underline{A048933}, \underline{A048994}, \underline{A079500}, \underline{A120733}, \underline{A145839}, \underline{A145840}, \underline{A145841}, and \underline{A161434}.)

Received July 25 2008; revised version received June 16 2009. Published in Journal of Integer Sequences, June 20 2009.

Return to Journal of Integer Sequences home page.