\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}

\newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\begin{center}
\vskip 1cm{\LARGE\bf Matrix Compositions
}
\vskip 1cm
\large
Emanuele Munarini\\
Politecnico di Milano \\
Dipartimento di Matematica \\
Piazza Leonardo da Vinci 32 \\
20133 Milano \\
Italy \\
\href{mailto:emanuele.munarini@polimi.it}{\tt emanuele.munarini@polimi.it}
\ \\
Maddalena Poneti and Simone Rinaldi\\
Universit\`a di Siena \\
Dipartimento di Scienze Matematiche e Informatiche \\
Pian dei Mantellini 44 \\
53100 Siena \\
Italy \\
\href{mailto:poneti@tiscali.it}{\tt poneti@tiscali.it}
\href{mailto:rinaldi@unisi.it}{\tt rinaldi@unisi.it} \\
\end{center}

\vskip .2 in

\begin{abstract}
 In this paper we study the class of \emph{$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.
\end{abstract}

\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{defin}[theorem]{Definition}
\newenvironment{definition}{\begin{defin}\normalfont\quad}{\end{defin}}
\newtheorem{examp}[theorem]{Example}
\newenvironment{example}{\begin{examp}\normalfont\quad}{\end{examp}}
\newtheorem{rema}[theorem]{Remark}
\newenvironment{remark}{\begin{rema}\normalfont\quad}{\end{rema}}

%\newtheorem{proposition}{Proposition}
%\newcommand{\eproof}{\hspace*{\fill}$\Box$\vspace{1mm}}
%\newenvironment{proof}{\emph{Proof}.}{\eproof}
%\newenvironment{remark}{\medskip\textbf{Remark.}}{}




%\usepackage[latin1]{inputenc}
%\usepackage{fullpage}
%\usepackage{indentfirst}
%\usepackage{latexsym}
%\usepackage{amssymb, amsmath}
%\usepackage{amsfonts}
%\usepackage{epsfig}
%\usepackage{psfig}

\newcommand{\ee}{\mathrm{e}}
\newcommand{\ii}{\mathrm{i}}
\newcommand{\rr}{\mathbf{r}}
\newcommand{\CC}{\mathcal{C}}
\newcommand{\FF}{\mathcal{F}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\Zz}{\mathbb{Z}}
\newcommand{\RR}{\mathcal{R}}
\newcommand{\MM}{\mathcal{M}}
\newcommand{\PP}{\mathbb{P}}
\newcommand{\ZZ}{\mathcal{Z}}
\renewcommand{\AA}{\mathcal{A}}
\newcommand{\LL}{\mathcal{L}}
\newcommand{\ord}{\mathrm{ord}}
\newcommand{\Card}{\mathbf{Card}}
\newcommand{\mchoose}[2]{ { \left(\!\!\!\left( { #1 \atop #2 } \right)\!\!\!\right) } }
\newcommand{\Mchoose}[2]{ { \left(\!\!\left( { #1 \atop #2 } \right)\!\!\right) } }
\newcommand{\map}[3]{ { #1 } : { #2 } \rightarrow { #3 } }

%\newcommand{\qed}{\hfill\square\medskip}



\section{Introduction}

A \emph{composition} (or \emph{ordered partition}) of length $ k$ of a natural number $n $
is a $k$-tuple $ ( x_1, \ldots, x_k ) $ of positive integers such that $ x_1 + \cdots + x_k = n \,$.
%It is well known that there are $ { n - 1 \choose k - 1 } $ compositions of length $ k $ of $ n $
%and $ 2^{n-1} $ compositions of $ n $ (when $ n \geq 1 \,$).
Compositions are very well known combinatorial objects
\cite{Andrews,Carlitz,CarlitzE,CarlitzII,Comtet,HoggattBicknell},
and their study has been improved in several recent papers
\cite{BjornerSagan,BjornerStanley,ChinnHeubach,CorteelHitczenko,FrosiniRinaldi,HeubachMansour04,HeubachMansour05,KnopfmacherProdinger,KnopfmacherRobbins,MerliniUnciniVerri}.
Moreover, in certain algebraic contexts
\cite{BergeronBousquetMelouDulucq,BjornerSagan,BjornerStanley,SaganVatter,Snellman,Snellman2},
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 \emph{vector compositions} \cite[p.57]{Andrews}\cite{Andrews75,Andrews76a,Andrews76b}
by P. A. MacMahon \cite{MacMahon1,MacMahon2,MacMahon3},
the $m$-\emph{colored compositions} by Drake and Petersen \cite{DrakePetersen},
the compositions defined by Lin and Rui \cite{LinRui},
and the \emph{packed matrices} by Duchamp, Hivert and Thibon \cite{DuchampHivertThibon}.

Another slight generalization of ordinary compositions to the bidimensional case
is given by the \emph{$2$-compositions},
introduced to encode $L$-convex polyominoes \cite{CastiglioneFrosiniMunariniRestivoRinaldi},
Clearly, $2$-compositions are a particular case of \emph{$m$-compositions}.
Indeed, more precisely, for any non-negative integer $ m $,
we define an \emph{m-row matrix composition}, or \emph{m-composition} for short,
as an $ m \times k $ matrix with nonnegative integer entries
$$
 M = \begin{bmatrix}
      x_{11} & x_{12} & \ldots & x_{1k} \\
      x_{21} & x_{22} & \ldots & x_{2k} \\
      \vdots & \vdots & \ddots & \vdots \\
      x_{m1} & x_{m2} & \ldots & x_{mk}
     \end{bmatrix}
$$
where each column has at least one non-zero element.
We say that the \emph{length} of $ M $ is the number $ k $ of its columns.
Moreover, we say that $ M $ is an \emph{m-composition} of a non-negative integer $ n $
when the sum $ \sigma(M) $ of all its entries is equal to $ n \,$.
For instance, we have the following seven $2$-compositions of $ n = 2 \,$:
$$
 \begin{bmatrix} 0 \\ 2 \end{bmatrix}, \quad
 \begin{bmatrix} 1 \\ 1 \end{bmatrix}, \quad
 \begin{bmatrix} 2 \\ 0 \end{bmatrix}, \quad
 \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}, \quad
 \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}, \quad
 \begin{bmatrix} 1 & 1 \\ 0 & 0 \end{bmatrix}, \quad
 \begin{bmatrix} 0 & 0 \\ 1 & 1 \end{bmatrix}.
$$

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 \cite{GrazziniMunariniPonetiRinaldi},
where the problem of generating efficiently $m$-compositions and $m$-partitions has been treated,
and in paper \cite{Louchard}, where the probabilistic aspects of $m$-compositions have been studied.

\section{Enumeration of $m$-compositions}\label{sec-languages}

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 $ \NN $ be the set of all non-negative integer numbers.
A \emph{multiset} on a set $ X $ is a function $ \map{\mu}{X}{\NN} \,$.
The \emph{multiplicity} of an element $ x \in X $ is $ \mu(x) \,$.
The \emph{order} of $ \mu $ is the sum $ \ord(\mu) $ of the multiplicities of the elements of $ X \,$,
i.e., $ \ord(\mu) = \sum_{x \in X} \mu(x) \,$.
The number of all multisets of order $ k $ on a set of size $ n $ is the \emph{multiset coefficient} \cite{Stanley}
$$ \Mchoose{n}{k} = {{n+k-1}\choose {k}} = \frac{n(n+1)\cdots (n+k-1)}{k!} \, . $$

Let $ \CC_{nk}^{(m)} $ be the set of all $m$-compositions of $ n $ of length $ k $
and let $ \CC_{n}^{(m)} $ be the set of all $m$-compositions of $ n \,$.
Then let $ c_{nk}^{(m)} = | \CC_{nk}^{(m)} | $ and $ c_{n}^{(m)} = | \CC_{n}^{(m)} | $
(see Table \ref{table-cnm}).
For simplicity, sometimes we just write $ c_n $ for the coefficients $ c_n^{(2)} \,$.
\begin{table}
 $$
 \footnotesize
 \begin{array}{|c|ccccccccccc|}
  \hline
     n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\
  \hline
   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 \\
  \hline
 \end{array}
 $$
 \caption{The numbers $ c_n^{(m)} \,$.
  For $ m = 3, 4, 5, 6 \,$, we have the sequences \seqnum{A145839},
  \seqnum{A145840}, \seqnum{A145841}, \seqnum{A161434} in \cite{sloane}.}
 \label{table-cnm}
\end{table}

\begin{proposition}
 The generating series of $m$-compositions
 according to the sum (marked by $ x $) and the length (marked by $ y \,$), is
 \begin{equation}\label{gfmn}
  c^{(m)}(x,y) = \sum_{n\geq 0} c_{nk}^{(m)} x^n = \frac{(1-x)^m}{(1+y)(1-x)^m-y} \, .
 \end{equation}
 In particular, the generating series of $m$-compositions according to the sum is
 \begin{equation}\label{gfCmn}
  c^{(m)}(x) = \sum_{n\geq 0} c_{n}^{(m)} x^n = \frac{(1-x)^m}{2(1-x)^m-1} \, .
 \end{equation}
\end{proposition}
\begin{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
 \begin{equation}\label{series-h}
  h^{(m)}(x) = \sum_{k \geq 1} \Mchoose{m}{k} x^k = \frac{1}{(1-x)^m}-1 \, .
 \end{equation}
 Hence, $ c^{(m)}(x,y) = (1-h^{(m)}(x)y)^{-1} \,$, that is (\ref{gfmn}).
 Finally, series (\ref{gfCmn}) follows at once by setting $ y = 1 $ in (\ref{gfmn}).
\end{proof}

Reading the denominator of the rational generating series (\ref{gfmn}) and (\ref{gfCmn}),
we can immediately obtain a linear recurrence for the numbers $ c_{nk}^{(m)} $ and $ c_n^{(m)} \,$,
namely we can obtain recurrences (\ref{MainRecurrence-cnk}) and (\ref{MainRecurrence})
that will be proved in Proposition \ref{prop-recurrences} with a combinatorial argument explaining their form.
Here, we obtain two other recurrences just by manipulating series in formal way.
Recall that the \emph{incremental ratio} of a formal series $ f(x) = \sum_{n\geq 0} f_n x^n $
is the series defined by $ R f(x) = (f(x)-f_0)/x = \sum_{n\geq 0} f_{n+1} x^n \,$.
\begin{proposition}
 The numbers $ c_n^{(m)} $ satisfy the recurrence
 \begin{equation}\label{rec-cn2}
  c^{(m)}_{n+1} = - \delta_{n,0} + 2 c^{(m)}_{n} + \sum_{k=0}^n { m + k - 1 \choose k + 1 } c^{(m)}_{n-k} \, .
 \end{equation}
\end{proposition}
\begin{proof}
 Rewriting series (\ref{gfCmn}) in the following form
 $$ c^{(m)}(x) = \frac{1}{2-\displaystyle\frac{1}{(1-x)^m}} = \frac{1-x}{2-2x-\displaystyle\frac{1}{(1-x)^{m-1}}} \, , $$
 we obtain the identity
 $$ \left( 2-2x-\frac{1}{(1-x)^{m-1}} \right) c^{(m)}(x) = 1 - x $$
 and hence the equation
 $$ c^{(m)}(x) = 1 - x + 2 x c^{(m)}(x) + \left( \frac{1}{(1-x)^{m-1}} - 1 \right) c^{(m)}(x) \, . $$
 Now, taking the incremental ratio of both sides, we have
 $$ R c^{(m)}(x) = - 1 + 2 c^{(m)}(x) + R \left( \frac{1}{(1-x)^{m-1}} - 1 \right) c^{(m)}(x) $$
 from which we obtain
 $$
  c^{(m)}_{n+1} = - \delta_{n,0} + 2 c^{(m)}_{n} + \sum_{k=1}^{n+1} \mchoose{m-1}{k} c^{(m)}_{n-k+1}
                = - \delta_{n,0} + 2 c^{(m)}_{n} + \sum_{k=0}^n \mchoose{m-1}{k+1} c^{(m)}_{n-k} \, ,
 $$
 which simplifies in (\ref{rec-cn2}).
\end{proof}

Recurrence (\ref{rec-cn2}) generalizes the identity $ c_{n+2} = 3c_{n+1}+ c_n + \cdots + c_0 \,$,
obtained in \cite{CastiglioneFrosiniMunariniRestivoRinaldi}
by simple manipulations of the recurrence $ c_{n+2} = 4c_{n+1} - 2 c_n \,$.

\begin{proposition}
 The numbers $ c_{nk}^{(m)} $ satisfy the recurrence
 \begin{equation}\label{rec-cnk-3}
  c_{n+1,k+1}^{(m+1)} = c_{n+1,k+1}^{(m)} - c_{n,k+1}^{(m)} +
   \sum_{i,j=0}^{n,k+1} c_{ij}^{(m)} c_{n-i,k-j+1}^{(m+1)} + \sum_{i,j=0}^{n,k} c_{ij}^{(m)} c_{n-i,k-j}^{(m+1)} \, .
 \end{equation}
 Similarly, the numbers $ c_n^{(m)} $ satisfy the recurrence
 \begin{equation}\label{rec-cn-3}
  c_{n+1}^{(m+1)} = c_{n+1}^{(m)} - c_n^{(m)} + 2 \sum_{k=0}^n c_k^{(m)} c_{n-k}^{(m+1)} \, .
 \end{equation}
\end{proposition}
\begin{proof}
 For simplicity, we just prove identity (\ref{rec-cn-3}).
 Identity (\ref{rec-cnk-3}) can be proved in a completely similar way.
 From (\ref{gfCmn}), 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 (\ref{gfCmn}),
 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) + 2 x c^{(m)}(x) c^{(m+1)}(x) \, . $$
 Finally, taking the incremental ratio of both sides, we have at once (\ref{rec-cn-3}).
\end{proof}

\section{Combinatorial identities}

In this section we give a combinatorial interpretation of some formulas concerning $m$-compositions.
Most of them can be obtained by employing the classical Principle of Inclusion-Exclusion \cite{Riordan,Stanley}.
\begin{proposition}\label{prop-recurrences}
 The coefficients $ c_{nk}^{(m)} $ satisfy the recurrence
 \begin{equation}\label{rec-cnk-basic}
  c_{n+m,k+1}^{(m)} = \sum_{i=1}^{n+m-k} \Mchoose{m}{i} c_{n+m-i,k}^{(m)} \, .
 \end{equation}
 Similarly, the coefficients $ c_n^{(m)} $ satisfy the recurrence
 \begin{equation}\label{rec-cn-basic}
  c_{n+m}^{(m)} = \sum_{i=1}^{n+m} \Mchoose{m}{i}\; c_{n+m-i}^{(m)} \, .
 \end{equation}
\end{proposition}
\begin{proof}
 Any $m$-composition $ M \in \CC_{n+m,k+1}^{(m)} $ can always be decomposed into two parts:
 the first column, equivalent to a multiset on the set $ \{ 1, \ldots, m \}$
 of non-zero order $ i $ (with $ 0 \leq i \leq 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 (\ref{rec-cnk-basic}).
 The same argument also implies (\ref{rec-cn-basic}).
\end{proof}

Recurrences (\ref{rec-cnk-basic}) and (\ref{rec-cn-basic}) can be easily obtained,
but they have a complex structure since they involve a summation.
However, we also have the following linear recurrences.
\begin{proposition}
 The numbers $ c_{nk}^{(m)} $ satisfies the recurrence
 \begin{equation}\label{MainRecurrence-cnk}
  c_{n+m,k+1}^{(m)} = \sum_{i=1}^m { m \choose i } (-1)^{i-1} c_{n+m-i,k}^{(m)} +
  \sum_{i=1}^m { m \choose i } (-1)^{i-1} c_{n+m-i,k+1}^{(m)} \, .
 \end{equation}
 Similarly, the numbers $ c_n^{(m)} $ satisfies the recurrence
 \begin{equation}\label{MainRecurrence}
  c_{n+m}^{(m)} = 2 \sum_{i=1}^m { m \choose i } (-1)^{i-1} c_{n+m-i}^{(m)} \, .
 \end{equation}
\end{proposition}
\begin{proof}
 For simplicity, we only prove recurrence (\ref{MainRecurrence})
 (the same argument, also proves recurrence (\ref{MainRecurrence-cnk})).
 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 $ \CC_{n+m}^{(m)} = A_1 \cup \cdots \cup A_m \,$.
 Hence, by the Principle of Inclusion-Exclusion, we have
 $$
  c_{n+m}^{(m)} = | A_1 \cup \cdots \cup A_m |
  = \sum_{S \subseteq [m] \atop S \ne \emptyset} (-1)^{|S|-1} \left| \bigcap_{i \in S} A_i \right| \, .
 $$
 The set $ \bigcap_{i \in 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 \in 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 $ \left| \bigcap_{i \in S} A_i \right| = 2\, c_{n+m-|S|}^{(m)} \,$.
 Since this identity depends only on the size of $ S \,$, we obtain~(\ref{MainRecurrence}).
\end{proof}

\begin{remark}
 For $ m = 2 \,$, recurrence (\ref{MainRecurrence})
 reduces to the recurrence $ c_{n+2} = 4 c_{n+1} - 2 c_n \,$,
 already obtained in \cite{CastiglioneFrosiniMunariniRestivoRinaldi}.
 For $ m = 3 $ and $ 4 \,$, we have the following recurrences
 $$
  c_{n+3}^{(3)} = 6 c_{n+2}^{(3)} - 6 c_{n+1}^{(3)} + 2 c_n^{(3)}, \quad
  c_{n+4}^{(4)} = 8 c_{n+3}^{(4)} - 12 c_{n+2}^{(4)} + 8 c_{n+1}^{(4)} - 2 c_n^{(4)} \, .
 $$
\end{remark}

\begin{proposition}\label{prop-formulas}
 The numbers $ c_{nk}^{(m)} $ admit the explicit expression
 \begin{equation}\label{cnk-formula}
  c_{nk}^{(m)} = \sum_{i=0}^k { k \choose i } \mchoose{m(k-i)}{n} (-1)^i \, .
 \end{equation}
 Similarly, the numbers $ c_{n}^{(m)} $ admit the explicit expression
 \begin{equation}\label{cn-formula}
  c_n^{(m)} = \sum_{k=0}^n c_{nk}^{(m)} = \sum_{k=0}^n \sum_{i=0}^k { k \choose i } \mchoose{m(k-i)}{n} (-1)^i \, .
 \end{equation}
\end{proposition}
\begin{proof}
 Let $ A_i $ be the set of all matrices $ M \in \MM_{m,k}(\NN) $
 where the $i$-th column is equal to the zero vector and $ \sigma(M)=n \,$.
 By the Principle of Inclusion-Exclusion, we have
 $$
  c_{nk}^{(m)} = | A'_1 \cap \cdots \cap A'_k | = \sum_{S \subseteq [k]} (-1)^{|S|} \left| \bigcap_{i \in S} A_i \right| \, .
 $$
 The intersection $ \bigcap_{i \in S} A_i $ is the set of all matrices $ M \in \MM_{mk}(\NN) $ 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 $ m k - m |S| \,$,
 and hence $ \left| \bigcap_{i \in S} A_i \right| = \Mchoose{m(k-|S|)}{n} \,$.
 Since this identity depends only on the size of $ S \,$, we have (\ref{cnk-formula}).
\end{proof}

The combinatorial argument used in the proof of Proposition (\ref{prop-formulas}) can be easily generalized
to the set $ \CC_k^{(m)}(r_1,\ldots,r_m) $ of all $m$-compositions of length $ k $
where the $i$-th row has sum equal to $ r_i \,$, for every $ i = 1, \ldots, m \,$.
Let $ c_k^{(m)}(r_1,\ldots,r_m) $ be the cardinality of such a set.
\begin{proposition}
 The numbers $ c_k^{(m)}(r_1,\ldots,r_m) $ admit the explicit expression
 \begin{equation}\label{cmkrho}
  c_k^{(m)}(r_1,\ldots,r_m) = \sum_{i=0}^k { k \choose i } \mchoose{k-i}{r_1} \cdots \mchoose{k-i}{r_m} (-1)^i \, .
 \end{equation}
\end{proposition}
\begin{proof}
 Let $ A_i $ be the set of all matrices $ M \in \MM_{m,k}(\NN) $ having the $i$-th column equal to the zero vector,
 and row-sums $ r_1 \,$, \ldots, $ r_m \,$.
 Then, by the Principle of Inclusion-Exclusion, we have
 $$
  c_k^{(m)}(r_1,\ldots,r_m) = | A'_1 \cap \ldots \cap A'_k | =
  \sum_{S \subseteq [k]} (-1)^{|S|} \left| \bigcap_{i \in S} A_i \right| \, .
 $$
 The intersection $ \bigcap_{i \in S} A_i $ contains all matrices $ M \in \MM_{mk}(\NN) $
 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
 $$ \left| \bigcap_{i \in S} A_i \right| = \mchoose{k-|S|}{r_1} \cdots \mchoose{k-|S|}{r_m} \, . $$
 Since this cardinality depends only on the size of $ S \,$, we have (\ref{cmkrho}).
\end{proof}

Identity (\ref{cmkrho}) already appears in the book \cite{Andrews} where, however,
it is proved in a formal way manipulating generating series.

Now, identities (\ref{cnk-formula}), (\ref{cn-formula}) and (\ref{cmkrho}) can be rewritten in terms of the
\emph{Stirling numbers of the first kind} $ { n \brack k } $
(\cite{GrahamKnuthPatashnik}, sequences \seqnum{A008275} and \seqnum{A048994} in \cite{sloane})
the \emph{Stirling numbers of the second kind} $ { n \brace k } $
(\cite{GrahamKnuthPatashnik}, sequences \seqnum{A008277} and \seqnum{A048933} in \cite{sloane}),
and the numbers $ t_n $ of \emph{preferential arrangements}
\cite{Gross,Stanley,Wilf} (sequence \seqnum{A000670} in \cite{sloane}).
\begin{proposition}
 The numbers $ c_{nk}^{(m)} \,$, $ c_{n}^{(m)} $ and $ c_k^{(m)}(r_1,\ldots,r_m) $ can be expressed as follows:
 \begin{equation}\label{cnk-Sformula}
  c_{nk}^{(m)} = \frac{k!}{n!} \sum_{j=k}^n { n \brack j } { j \brace k } m^j
 \end{equation}
 \begin{equation}\label{cn-Sformula}
  c_n^{(m)} = \frac{1}{n!} \sum_{k=0}^n { n \brack k } m^k t_k
 \end{equation}
 \begin{equation}\label{cnkrrr-Sformula}
  c_k^{(m)}(r_1,\ldots,r_m) =
  \frac{k!}{r_1! \cdots r_m!} \sum_{j_1, \ldots, j_m = 0}^{r_1, \ldots, r_m}
  \sum_{k \geq 0} { r_1 \brack j_1 } \cdots { r_m \brack j_m } { j_1+\cdots+j_m \brace k } \, .
 \end{equation}
\end{proposition}
\begin{proof}
 Using the ordinary expansion
 \begin{equation}\label{risingExpansion}
  x^{\overline{n}} = x(x+1)\cdots(x+n-1) = \sum_{k=0}^n { n \brack k } x^k
 \end{equation}
 of the \emph{rising factorials}, identity (\ref{cnk-formula}) becomes
 $$ c_{nk}^{(m)} = \frac{1}{n!} \sum_{j=0}^n { n \brack j } m^j \sum_{i=0}^k { k \choose 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 \cite{Stanley}, and can be expressed as
 \begin{equation}\label{surjFzId}
  \sum_{i=0}^k { k \choose i } (k-i)^n (-1)^i = { n \brace k } k! \, .
 \end{equation}
 Hence we have identity (\ref{cnk-Sformula}).
 Now, from (\ref{cnk-Sformula}), we have
 $$
  c_n^{(m)} = \sum_{k=0}^n c_{nk}^{(m)}
            = \sum_{k=0}^n \frac{k!}{n!} \, \sum_{j=k}^n { n \brack j } { j \brace k } m^j
            = \frac{1}{n!} \sum_{j=0}^n { n \brack j } m^j \, \sum_{k=0}^n { j \brace k } k! \, .
 $$
 Since
 \begin{equation}\label{formula-tn}
  t_n = \sum_{k=0}^n \, { n \brace k } \, k! \, ,
 \end{equation}
 we obtain at once identity (\ref{cn-Sformula}).
 Finally, by using (\ref{risingExpansion}) once again, identity (\ref{cmkrho}) can be written as
 $$
  c_k^{(m)}(r_1,\ldots,r_m) =
  \frac{1}{r_1! \cdots r_m!} \sum_{j_1, \ldots, j_m = 0}^{r_1, \ldots, r_m}
  \sum_{k \geq 0} { r_1 \brack j_1 } \cdots { r_m \brack j_m }
  \sum_{i=0}^k { k \choose i } (k-i)^{j_1+\cdots+j_m} (-1)^i \, .
 $$
 Hence, from (\ref{surjFzId}), we obtain (\ref{cnkrrr-Sformula}).
\end{proof}

\begin{remark}
 From (\ref{cnk-Sformula}) and (\ref{cn-Sformula}), it follows
 that both $ c_{nk}^{(m)} $ and $ c_n^{(m)} $ are polynomial expressions in $ m \,$.
\end{remark}

\begin{remark}
 Every $m$-composition $ M \in \CC^{(m)}_{nn} $ is an $ m \times n $ $(0,1)$-matrix
 with exactly a $ 1 $ in each column, and hence is equivalent to a function $ \map{f}{[n]}{[m]} \,$.
 So, $ c^{(m)}_{nn} = m^n \,$. Now, by using (\ref{cnk-formula}), we have
 $$ \sum_{k=0}^n { n \choose k } \mchoose{mk}{n} (-1)^k = m^n \, . $$
 Notice that this identity can also be obtained from (\ref{cnk-Sformula}).
\end{remark}

\section{Binet-like formulas and asymptotics}

In this section we will obtain a \emph{Binet-like formula}
and an asymptotic expansion for the coefficients $ c^{(m)}_n \,$.
\begin{proposition}
 The numbers $ c^{(m)}_n $ admit the following Binet-like formula
 \begin{equation}\label{formula-binetlike}
  c^{(m)}_n
  = \frac{1}{2} \left[ \delta_{n,0} + \frac{1}{m\sqrt[m]{2}} \sum_{k=0}^{m-1} \frac{\omega_m^k}{x_k^{n+1}} \right]
  = \frac{1}{2}\; \delta_{n,0} +
    \frac{1}{2m} \sum_{k=0}^{m-1} \frac{\omega_m^k}{\sqrt[m]{2}-\omega_m^k}
    \left( \frac{\sqrt[m]{2}}{\sqrt[m]{2}-\omega_m^k} \right)^{\!n}
 \end{equation}
 where
 \begin{equation}\label{x-roots}
  x_k = 1 - \frac{1}{\sqrt[m]{2}}\; \omega_m^k \qquad (k = 0, 1, \ldots, m-1)
 \end{equation}
 where $ \omega_m = \ee^{2 \pi \ii / m} $ is a primitive root of unity.
\end{proposition}
\begin{proof}
 Series (\ref{gfCmn}) can be rewritten as
 $$ c^{(m)}(x) = \frac{1}{2} \left[ 1 + \frac{1}{2(1-x)^m-1} \right] \, . $$
 The roots of the polynomial at the denominator are the numbers $ x_k $ given in (\ref{x-roots}).
 Then we have the expansion in partial fractions
 $$ \frac{1}{2(1-x)^m-1} = \frac{A_0}{x-x_0} + \cdots + \frac{A_{m-1}}{x-x_{m-1}} $$
 where the coefficients $ A_k $ are defined by
 $$ A_k = \lim_{x \to x_k} \frac{x-x_k}{2(1-x)^m-1} \, . $$
 By applying De l'Hopital rule, we have
 $$ A_k = \lim_{x \to x_k} \frac{1}{-2m(1-x)^{m-1}} = \frac{1}{-2m(1-x_k)^{m-1}} = - \frac{\omega_m^k}{m\sqrt[m]{2}} \, . $$
 Hence
 $$
  c^{(m)}(x) = \frac{1}{2} \left[ 1 - \frac{1}{x_k} \sum_{k=0}^{m-1} \frac{A_k}{1-x/x_k} \right]
  = \frac{1}{2} \left[ 1 + \frac{1}{m\sqrt[m]{2}\; x_k} \sum_{k=0}^{m-1} \frac{\omega_m^k}{1-x/x_k} \right]
 $$
 from which we obtain (\ref{formula-binetlike}).
\end{proof}

\begin{proposition}
 For $ n \to \infty \,$, we have the asymptotic expansion
 $$ c^{(m)}_n \sim  \frac{1}{2m(\sqrt[m]{2}-1)} \left( \frac{\sqrt[m]{2}}{\sqrt[m]{2}-1} \right)^{\!\!n}. $$
 In particular, we have the limit
 $$ \lim_{n\to\infty} \frac{c^{(m)}_n}{c^{(m)}_{n+1}} = 1 - \frac{1}{\sqrt[m]{2}}\, . $$
\end{proposition}
\begin{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} \,$.
\end{proof}

\section{Combinatorial interpretations}

\subsection{Colored linear partitions}

Matrix compositions can be interpreted in terms of linear species \cite{BergeronLabelleLeroux,Joyal} as
follows. Let $ [m] = \{ 1, \ldots, m \} $ be a set of colors, totally ordered in the natural way.
We say that a linearly ordered set $ [n]=\{1,2,\ldots,n\} $ is \emph{$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 \leq y $ then $ i \leq j \,$.
In other words, an $m$-coloring of $ [n] $ is an order-preserving map $ \map{\gamma}{[n]}{[m]} \,$.
We define an \emph{$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 \in \CC_{nk}^{(m)} $ corresponds to the $m$-colored linear partition $ \pi $ of $ [n] $
obtained transforming the $i$-th column $ ( h_1, \ldots, h_m ) $ of $ M $
into the $i$-th block of $ \pi $ of size $ h_1 + \cdots + h_m $
with the first $ h_1 $ elements of color $ 1 \,$, \ldots,
the last $ h_m $ elements of color $ m \,$, for every $ i = 1, \ldots, k \,$.
For instance, the $3$-composition
\begin{equation}\label{Mexample}
 M = \begin{bmatrix}
      2 & 0 & 1 & 2 \\
      0 & 1 & 0 & 1 \\
      1 & 0 & 1 & 2 \\
     \end{bmatrix}
\end{equation}
corresponds to the following $3$-colored partition of the set $ \{ 1, 2, 3, \ldots, 11 \} $
\begin{center}
 \setlength{\unitlength}{1cm}
 \begin{picture}(10,0.6)(0,-0.2)
  %\put(1,0){\oval(2.4,0.7)}
  %\put(3,0){\oval(0.9,0.7)}
  %\put(4.5,0){\oval(1.4,0.7)}
  %\put(8,0){\oval(4.4,0.7)}
  \put(-0.3,-0.2){\dashbox{0.1}(2.6,0.6){}}
  \put(2.7,-0.2){\dashbox{0.1}(0.6,0.6){}}
  \put(3.7,-0.2){\dashbox{0.1}(1.6,0.6){}}
  \put(5.7,-0.2){\dashbox{0.1}(4.6,0.6){}}
  %\put(1,0){\oval(2.4,0.6)}
  %\put(3,0){\oval(0.4,0.4)}
  %\put(4.5,0){\oval(1.4,0.4)}
  %\put(8,0){\oval(4.4,0.4)}
  \put(0,0){\line(1,0){10}}
  \put(0,0){\circle*{0.15}}
  \put(1,0){\circle*{0.15}}
  \put(2,0){\circle*{0.15}}
  \put(3,0){\circle*{0.15}}
  \put(4,0){\circle*{0.15}}
  \put(5,0){\circle*{0.15}}
  \put(6,0){\circle*{0.15}}
  \put(7,0){\circle*{0.15}}
  \put(8,0){\circle*{0.15}}
  \put(9,0){\circle*{0.15}}
  \put(10,0){\circle*{0.15}}
%  \put(0,0){\textcolor{red}{\circle*{0.15}}}
%  \put(1,0){\textcolor{red}{\circle*{0.15}}}
%  \put(2,0){\textcolor{blue}{\circle*{0.15}}}
%  \put(3,0){\textcolor{green}{\circle*{0.15}}}
%  \put(5,0){\textcolor{blue}{\circle*{0.15}}}
%  \put(6,0){\textcolor{red}{\circle*{0.15}}}
%  \put(7,0){\textcolor{red}{\circle*{0.15}}}
%  \put(8,0){\textcolor{green}{\circle*{0.15}}}
%  \put(9,0){\textcolor{blue}{\circle*{0.15}}}
%  \put(10,0){\textcolor{blue}{\circle*{0.15}}}
  \put(0.1,0.17){\makebox(0,0){\scriptsize$1$}}
  \put(1,0.17){\makebox(0,0){\scriptsize$1$}}
  \put(1.9,0.17){\makebox(0,0){\scriptsize$3$}}
  \put(3,0.17){\makebox(0,0){\scriptsize$2$}}
  \put(4.1,0.17){\makebox(0,0){\scriptsize$1$}}
  \put(4.9,0.17){\makebox(0,0){\scriptsize$3$}}
  \put(6.1,0.17){\makebox(0,0){\scriptsize$1$}}
  \put(7.1,0.17){\makebox(0,0){\scriptsize$1$}}
  \put(8,0.17){\makebox(0,0){\scriptsize$2$}}
  \put(8.9,0.17){\makebox(0,0){\scriptsize$3$}}
  \put(9.9,0.17){\makebox(0,0){\scriptsize$3$}}
 \end{picture}
\end{center}
which can also be represented as $ \pi = [[1,1,3],[2],[1,3],[1,1,2,3,3]] \,$.

\begin{proposition}
 Let $ \mathbf{C}^{(m)} $ be the linear species of $m$-compositions,
 i.e., the linear species of $m$-colored linear partitions.
 Let $ \mathbf{G} $ be the uniform linear species.
 Let $ \mathbf{Map}^{(m)}_{\ne \emptyset} $ be the linear species of
 multisets of non-zero order on the set $ [m] \,$.
 %the order-preserving maps from a nonempty linear order to the set of colors $ [m] \,$.
 Then
 \begin{equation}\label{species-C}
  \mathbf{C}^{(m)} = \mathbf{G} \circ \mathbf{Map}^{(m)}_{\ne \emptyset} \, .
 \end{equation}
\end{proposition}
\begin{proof}
 To give an $m$-colored linear partition on a linearly ordered set $ L $
 is equivalent to assign a linear partition $ \pi $ on $ L $
 and then an $m$-coloring (i.e., an order-preserving map in $ [m] \,$) on each block of $ \pi \,$.
 Since an order-preserving map $ \map{f}{[k]}{[m]} $
 is equivalent to a multiset of order $ k $ on the set $ [m] \,$, we have at once (\ref{species-C}).
\end{proof}

\begin{remark}
 {From} identity (\ref{species-C}), we reobtain at once (\ref{gfCmn}).
 Indeed, since $ \Card(\mathbf{G};x) = 1/(1-x) $ and
 $ \Card(\mathbf{Map}^{(m)}_{\ne \emptyset};x) = h^{(m)}(x) \,$,
 where $ h^{(m)}(x) $ is series (\ref{series-h}), we have
 $ \Card(\mathbf{C}^{(m)};x) = \Card(\mathbf{G};x) \circ \Card(\mathbf{Map}^{(m)}_{\ne \emptyset};x) = c^{(m)}(x) \,$.
\end{remark}

\medskip

Using this interpretation, we can obtain the following identities we will employ in Section~\ref{sec-cassini}
to prove a Cassini-like identity.
\begin{proposition}
 We have the following identity
 \begin{equation}\label{cassinisum}
  c_{i+j+1}^{(m)} = \sum_{h,k\geq 0} \mchoose{m}{h+k+1} c_{i-h}^{(m)} c_{j-k}^{(m)} \, .
 \end{equation}
\end{proposition}
\begin{proof}
 Let $ L = \{ x_1,\ldots, x_{i+1}, \ldots, x_{i+j+1} \} $ be a linearly ordered set with size $ i+j+1 $
 and let $ \pi \in \mathbf{C}^{(m)}[L] \,$.
 The element $ x_{i+1} $ belongs to a block $ B $
 of the form $ \{ x_{i-h+1}, \ldots, x_i, x_{i+1}, x_{i+2}, \ldots, x_{i+k+1} \} $
 with $ h, k \in \NN \,$, as in the following picture:
\setlength{\unitlength}{1cm}
\begin{center}
 \begin{picture}(12,2)(0,-1)
  \put(1,0){\oval(2.6,0.6){}}
  \put(1,0.6){\makebox(0,0){$\pi_1$}}
  \put(2.7,-0.3){\dashbox{0.1}(6.6,0.6){}}
  \put(11,0){\oval(2.6,0.6){}}
  \put(11,0.6){\makebox(0,0){$\pi_2$}}
  \put(0,0){\line(1,0){12}}
  \put(0,0){\circle*{0.15}}
  \put(1,0){\circle*{0.15}}
  \put(2,0){\circle*{0.15}}
  \put(3,0){\circle*{0.15}}
  \put(4,0){\circle*{0.15}}
  \put(5,0){\circle*{0.15}}
  \put(6,0){\circle*{0.15}} \put(6,0){\circle{0.3}}
  \put(7,0){\circle*{0.15}}
  \put(8,0){\circle*{0.15}}
  \put(9,0){\circle*{0.15}}
  \put(10,0){\circle*{0.15}}
  \put(11,0){\circle*{0.15}}
  \put(12,0){\circle*{0.15}}
  \put(6,0.5){\makebox(0,0){$x_{i+1}$}}
  \put(5,0.5){\makebox(0,0){$x_{i}$}}
  \put(7,0.5){\makebox(0,0){$x_{i+2}$}}
  \put(3,0.5){\makebox(0,0){$x_{i-h+1}$}}
  \put(9,0.5){\makebox(0,0){$x_{i+k+1}$}}
  \put(0,-0.7){\line(0,1){0.2}}\put(0,-0.6){\line(1,0){0.3}}\put(2,-0.6){\line(-1,0){0.3}}\put(2,-0.7){\line(0,1){0.2}}
  \put(1,-0.6){\makebox(0,0){$i-h$}}
  \put(3,-0.7){\line(0,1){0.2}}\put(3,-0.6){\line(1,0){0.6}}\put(5,-0.6){\line(-1,0){0.6}}\put(5,-0.7){\line(0,1){0.2}}
  \put(4,-0.6){\makebox(0,0){$h$}}
  \put(7,-0.7){\line(0,1){0.2}}\put(7,-0.6){\line(1,0){0.6}}\put(9,-0.6){\line(-1,0){0.6}}\put(9,-0.7){\line(0,1){0.2}}
  \put(8,-0.6){\makebox(0,0){$k$}}
  \put(10,-0.7){\line(0,1){0.2}}\put(10,-0.6){\line(1,0){0.3}}\put(12,-0.6){\line(-1,0){0.3}}\put(12,-0.7){\line(0,1){0.2}}
  \put(11,-0.6){\makebox(0,0){$j-k$}}
 \end{picture}
\end{center}
 Removing the block $ B \,$, $ \pi $ splits
 into an $m$-colored linear partition $ \pi_1 $ on a linear order of size $ i-h $
 and into an $m$-colored linear partition $ \pi_2 $ on a linear order of size $ j-k \,$.
\end{proof}

\begin{proposition}
 We have the identity
 \begin{equation}\label{mchoosesum}
  \mchoose{m}{i+j+1} = \sum_{k=1}^m \mchoose{k}{i} \mchoose{m-k+1}{j}
                     = \sum_{k=0}^{m-1} {i+ k \choose i } \mchoose{m-k}{j} \, .
 \end{equation}
\end{proposition}
\begin{proof}
 The coefficient $ \Mchoose{m}{i+j+1} $ gives the number of all the order-preserving maps $ \map{f}{[i+j+1]}{[m]} \,$.
 Now, suppose that $ f(i+1) = k \,$, with $ k \in [m] \,$.
 Since $ f $ is order-preserving, it follows that $ f(x) \in [k] $ for every $ x \in [i] $
 and $ f(x) \in \{k,\ldots,m\} $ for every $ x \in \{i+2,\ldots,i+j+1\} \,$.
 Hence we have at once identity (\ref{mchoosesum}).
\end{proof}

\subsection{Surjective families of order-preserving maps}

Let $ P_1 \,$, \ldots, $ P_m $ and $ Q $ be finite linearly ordered sets.
We say that $ \FF = \{\map{f_i}{P_i}{Q} \}_{i=1}^m $ is a \emph{surjective family} of order-preserving maps
when for every element $ q \in Q $
there exists at least one index $ i $ and one element $ p \in 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.
\begin{proposition}
 Let $ P_1 \,$, \ldots, $ P_m $ and $ Q $ be finite linearly ordered sets
 with $ |P_1| = r_1 \,$, \ldots, $ |P_m| = r_m $ and $ |Q| = k \,$.
 Then the number of all surjective families $ \FF = \{\map{f_i}{P_i}{Q} \}_{i=1}^m $
 is $ c_k^{(m)}(r_1,\ldots,r_m) \,$.
\end{proposition}
\begin{proof}
 Let $ Q = \{ q_1, \ldots, q_k \} \,$.
 A surjective family $ \FF = \{\map{f_i}{P_i}{Q} \}_{i=1}^m $ is equivalent
 to the $m$-composition $ M $ of length $ k $ with row-sum vector $ ( r_1, \ldots, r_k ) \,$,
 whose $i$-row is $ \rr_i = ( |f_i^\bullet(q_1)|, \ldots, |f_i^\bullet(q_k)| ) \,$,
 where $ f_i^\bullet(q_j) $ is the set of all preimages of $ q_j $ along the map $ f_i \,$.
 Clearly, the sum of the $i$-row $ \rr_i $ is $ |P_i| = r_i \,$.
 Moreover, since $ \FF $ is a surjective family, any column of $ M $ is different from the zero vector.
\end{proof}

\subsection{Labelled bargraphs}\label{LabbeledBargraphsSec}

The interpretation of matrix compositions in terms of colored linear partitions
can be reformulated in terms of \emph{labelled bargraphs}.
A \emph{bargraph} is a column-convex polyomino
where all columns are bottom justified (see Figure \ref{bargraph} (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 \cite{MerliniUnciniVerri}).
Bargraphs, and more generally polyominoes \cite{mbm2}, are well-known combinatorial objects.
In particular, the enumeration of bargraphs according to perimeter,
area and site-perimeter has been treated in \cite{OP,PB}, in relation to the study of percolation models,
and more recently, from an analytical point of view, in~\cite{BMR}.
\begin{figure}[htb]
 \centerline{\hbox{\psfig{figure=bargraph.eps,width=4.8in,clip=}}}
 \caption{(a) a bargraph; (b) a labelled bargraph of degree $4$.}
 \label{bargraph}
\end{figure}

Let $ M = [ a_{ij} ] $ be an $m$-composition,
equivalent to an $m$-colored linear partition $ \pi = [B_1,\ldots,B_k] $
where the block $ B_j $ has the form $ [1,\ldots,1, 2,\ldots, 2, \ldots, m, \ldots, m] $,
and for every $ i = 1, \ldots, 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 (\ref{Mexample}),
equivalent to the $3$-colored linear partition $ \pi = [[1,1,3],[2],[1,3],[1,1,2,3,3]] \,$,
is represented by the following labelled bargraph of area $ 11 $ with $ 4 $ columns:
\begin{center}
 \setlength{\unitlength}{5mm}
 \begin{picture}(4,5)
  \put(0,0){\line(1,0){4}}
  \put(0,1){\line(1,0){4}}
  \put(0,2){\line(1,0){1}}
  \put(2,2){\line(1,0){2}}
  \put(0,3){\line(1,0){1}}
  \put(3,3){\line(1,0){1}}
  \put(3,4){\line(1,0){1}}
  \put(3,5){\line(1,0){1}}
  \put(0,0){\line(0,1){3}}
  \put(1,0){\line(0,1){3}}
  \put(2,0){\line(0,1){2}}
  \put(3,0){\line(0,1){5}}
  \put(4,0){\line(0,1){5}}
  \put(0.5,0.5){\makebox(0,0){1}}
  \put(0.5,1.5){\makebox(0,0){1}}
  \put(0.5,2.5){\makebox(0,0){3}}
  \put(1.5,0.5){\makebox(0,0){2}}
  \put(2.5,0.5){\makebox(0,0){1}}
  \put(2.5,1.5){\makebox(0,0){3}}
  \put(3.5,0.5){\makebox(0,0){1}}
  \put(3.5,1.5){\makebox(0,0){1}}
  \put(3.5,2.5){\makebox(0,0){2}}
  \put(3.5,3.5){\makebox(0,0){3}}
  \put(3.5,4.5){\makebox(0,0){3}}
 \end{picture}
\end{center}
Similarly, the labelled bargraph in Figure \ref{bargraph}(b) represents the following $4$-composition of $ 33 \,$:
$$
 \left[
 \begin{array}{cccccccccccc}
  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{array}
 \right].
$$

So, we define a \emph{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 \ref{bargraph}(b)).
The \emph{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 \,$.

\subsection{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 $ \AA_m = \{ a_1, \cdots, a_m, b_1,\ldots, b_m \} \,$.
This encoding extends the encoding described in \cite{BjornerStanley} for the ordinary compositions,
Let $ \CC^{(m)} $ be the set of all $m$-compositions
and let $ \map{\ell}{\CC^{(m)}}{\AA_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 \emph{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 \emph{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
\begin{equation}\label{coding}
 \begin{matrix} 1 \\ 0 \\ \vdots \\ 0 \end{matrix} \; \stackrel{\ell}{\longmapsto}\; a_1 \, ,
 \quad \ldots, \quad
 \begin{matrix} 0 \\ \vdots \\ 0 \\ 1 \end{matrix} \;\stackrel{\ell}{\longmapsto}\; a_m \, ,
 \qquad
 + \begin{matrix} 1 \\ 0 \\ \vdots \\ 0 \end{matrix} \;\stackrel{\ell}{\longmapsto}\; b_1 \, ,
 \quad \ldots, \quad
 + \begin{matrix} 0 \\ \vdots \\ 0 \\ 1 \end{matrix} \;\stackrel{\ell}{\longmapsto}\; b_m
\end{equation}
For instance, by applying this procedure to the $3$-composition
$$
 M = \begin{bmatrix}
      2 & 0 & 1 & 2 \\
      0 & 1 & 0 & 1 \\
      1 & 0 & 1 & 2 \\
     \end{bmatrix},
$$
we have
\begin{eqnarray*}
 M & \rightsquigarrow & \begin{matrix} 2 \\ 0 \\ 1 \\ \end{matrix} \; + \;
         \begin{matrix} 0 \\ 1 \\ 0 \\ \end{matrix} \; + \;
         \begin{matrix} 1 \\ 0 \\ 1 \\ \end{matrix} \; + \;
         \begin{matrix} 2 \\ 1 \\ 2 \\ \end{matrix} \\
   & \rightsquigarrow & \begin{matrix} 2 & 0 \\ 0 & 0 \\ 0 & 1 \end{matrix} \; + \;
         \begin{matrix} 0 \\ 1 \\ 0 \\ \end{matrix} \; + \;
         \begin{matrix} 1 & 0 \\ 0 & 0 \\ 0 & 1 \\ \end{matrix} \; + \;
         \begin{matrix} 2 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 2 \\ \end{matrix} \\
   & \rightsquigarrow & \begin{matrix} 1 & 1 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 1 \\ \end{matrix} \; + \;
         \begin{matrix} 0 \\ 1 \\ 0 \\ \end{matrix} \; + \;
         \begin{matrix} 1 & 0 \\ 0 & 0 \\ 0 & 1 \\ \end{matrix} \; + \;
         \begin{matrix} 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 \\ \end{matrix}
\end{eqnarray*}
and hence $\; \ell(M) = a_1 a_1 a_3 b_2 b_1 a_3 b_1 a_1 a_2 a_3 a_3 \,$.

\begin{proposition}
 The language $ \LL^{(m)} = \ell(\CC^{(m)}) $
 on the alphabet $ \AA_m $ corresponding to the $m$-compositions
 is the regular language defined by the unambiguous regular expression
 \begin{equation}\label{formula-L}
  \LL^{(m)} = \varepsilon + \LL_1^{(m)} \LL_2^{(m)}
 \end{equation}
 where $ \varepsilon \,$, as usual, is the empty word, and
 $$ \LL_1^{(m)} = \left( \, a_1^+ a_2^* \cdots a_m ^* + a_2^+ a_3^* \cdots a_m ^* + \cdots + a_m^+ \, \right) $$
 $$ \LL_2^{(m)} = \left( \, b_1 a_1^* a_2^* \cdots a_m ^* + b_2a_2^* \cdots a_m ^* + \cdots + b_ma_m^* \, \right)^* \, . $$
\end{proposition}
\begin{proof}
 Non-empty words in $ \LL^{(m)} $ are characterized by the following conditions:
 \begin{enumerate}
  \item the first letter is always an $ a_i \,$, with $ i = 1, 2, \ldots, m \,$;
  \item 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 \leq j $.
 \end{enumerate}
 This characterization implies that the non-empty words in $ \LL^{(m)} $
 have a unique factorization of the form $ x y \,$, where
 \begin{enumerate}
  \item $ x $ is a non-empty word of the form $ a_1^{i_1}\cdots a_m^{i_m}\,$, with $ i_1, \ldots ,i_m \geq 0 \,$;
  \item $ y $ is a (possibly empty) word $ y = y_1 \cdots y_k \,$,
   where $ y_r = b_j a_{j}^{q_j}\cdots a_m^{q_m} $ with $ q_j, \ldots , q_m \geq 0 \,$,
   for every $ r = 1, \ldots, k \,$.
 \end{enumerate}
 This factorization implies at once identity (\ref{formula-L}).
\end{proof}

\begin{remark}
 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 \cite{GrazziniMunariniPonetiRinaldi}.
\end{remark}

\section{Cassini-like identities}\label{sec-cassini}

For $ m = 2 \,$, the numbers $ c_n $ satisfy
the following \emph{Cassini-like identity} \cite{CastiglioneFrosiniMunariniRestivoRinaldi}:
$$ c_n c_{n+2} - c_{n+1}^2 = - 2^{n-1}\qquad (\text{for}\, n \geq 1)\, . $$
This identity can be generalized to arbitrary $m$-compositions, as proved in the following
\begin{proposition}
 For every $ m,n \geq 1 \,$, we have the generalized Cassini-like identity:
 \begin{equation}\label{CassinilikeIdentity}
  \begin{vmatrix}
         c_n^{(m)} & c_{n+1}^{(m)} & \ldots & c_{n+m-1}^{(m)}  \\
     c_{n+1}^{(m)} & c_{n+2}^{(m)} & \ldots & c_{n+m}^{(m)}    \\
            \vdots &        \vdots &        &           \vdots \\
   c_{n+m-1}^{(m)} & c_{n+m}^{(m)} & \ldots & c_{n+2m-2}^{(m)} \\
  \end{vmatrix} =
  (-1)^{\lfloor m/2 \rfloor}\; 2^{n-1}.
 \end{equation}
\end{proposition}
\begin{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 (\ref{CassinilikeIdentity}).
 Since the main recurrence (\ref{MainRecurrence}) is of the form
 $$
  c_{n+m}^{(m)} = \alpha_{m-1} c_{n+m-1}^{(m)} + \cdots + \alpha_1 c_{n+1}^{(m)} + \alpha_0 c_n^{(m)}
  \quad \left(\text{where}\;\, \alpha_k = (-1)^{m-k-1} 2 { m \choose k } \right) \, ,
 $$
 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{vmatrix}
         c_n^{(m)} & c_{n+1}^{(m)} & \ldots & c_{n+m-1}^{(m)}  \\
     c_{n+1}^{(m)} & c_{n+2}^{(m)} & \ldots & c_{n+m}^{(m)}    \\
            \vdots &        \vdots &        &           \vdots \\
   c_{n+m-2}^{(m)} & c_{n+m-1}^{(m)} & \ldots & c_{n+2m-3}^{(m)} \\
   \alpha_0 c_{n-1}^{(m)} & \alpha_0 c_{n}^{(m)} & \ldots & \alpha_0 c_{n+m-2}^{(m)} \\
  \end{vmatrix}.
 $$
 Now, we can extract $ \alpha_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)} | \qquad (\text{for every}\;\, n \geq 1)\, . $$
 It remains to evaluate the determinant of the matrix $ C_1^{(m)} = [\; c_{i+j+1}^{(m)} \;]_{i,j=0}^{m-1} \,$.

 Identity (\ref{cassinisum}) is equivalent to the matrix factorization
 $$ C_1^{(m)} = L^{(m)} M^{(m)} L^{(m)}_T $$ where
 $$
  L^{(m)} = [\; c_{i-j}^{(m)} \;]_{i,j=0}^{m-1}
  \qquad\text{and}\qquad
  M^{(m)} = \left[\;\mchoose{m}{i+j+1}\;\right]_{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 (\ref{mchoosesum}) is equivalent to the matrix factorization
 $$ M^{(m)} = B^{(m)} \widetilde{B}^{(m)} $$ where
 $$
  B^{(m)} = \left[\; { i + j \choose i } \;\right]_{i,j=0}^{m-1}
  \qquad\text{and}\qquad
  \widetilde{B}^{(m)} = \left[\; \mchoose{m-i}{j}\; \right]_{i,j=0}^{m-1} \, .
 $$
 Since $ \widetilde{B}^{(m)} = J^{(m)} B^{(m)} \,$,
 where $ J^{(m)} = [ \delta_{i+j,m-1} ]_{i,j=0}^{m-1} \,$, it follows that
 $$ M^{(m)} = B^{(m)} J^{(m)} B^{(m)} \, . $$
 Since $ |J^{(m)}| = (-1)^{\lfloor m/2 \rfloor} $ and $ |B^{(m)}| = 1 \,$,
 it follows that $ |M^{(m)}| = (-1)^{\lfloor m/2 \rfloor} \,$.
 Finally, for every $ n \geq 1 \,$, we have
 $$ |C_n^{(m)}| = 2^{n-1}\; |C_1^{(m)}| = 2^{n-1}\; |M^{(m)}| = (-1)^{\lfloor m/2 \rfloor} 2^{n-1}\,, $$
 that is we have identity (\ref{CassinilikeIdentity}).
\end{proof}

%Its $i$-th row is $ \mathbf{r}_i = [\; c_{n+i+j}^{(m)} \;]_{j=0}^{m-1} \,$.
%In particular, by recurrence (\ref{MainRecurrence}), the last row is
%$$
% \mathbf{r}_m = 2 \sum_{k=1}^m {m \choose k } (-1)^{k-1} \mathbf{r}_{m-k}
%              = 2 \sum_{k=1}^{m-1} {m \choose k } (-1)^{k-1} \mathbf{r}_{m-k} + (-1)^{m-1} 2\; \mathbf{r}_0
%$$
%where $ \mathbf{r}_0 = [\; c_{n-1+j}^{(m)} \;]_{j=0}^{m-1} \,$. Then subtracting to the last row the following
%linear combination of the previous rows:
%$$ 2 \sum_{k=1}^{m-1} {m \choose k } (-1)^{k-1} \mathbf{r}_{m-k} $$
%the last row of $ \det C_n^{(m)} $ becomes $ (-1)^{m-1} 2 \; \mathbf{r}_0 \,$. Extracting $ (-1)^{m-1} 2 $
%from the last line and then shifting cyclically all rows downward we obtain that:
%$$ \det C_n^{(m)} = 2 \det C_{n-1}^{(m)} \, . $$
%Then, for every $ n \geq 1 \,$, it follows that: $ \det C_n^{(m)} = 2^{n-1} \det C_1^{(m)} \,$.
%So we have to compute only the determinant of the matrix $ C_1^{(m)} = [\; c_{i+j+1}^{(m)} \;]_{i,j=0}^{m-1} \,$.
%By identity (\ref{cassinisum}) we have the decomposition $ C_1^{(m)} = L_m M_m L_m^T \;$
%where $ L_m = [\; c_{i-j}^{(m)} \;]_{i,j=0}^{m-1} \,$,
%$ M_m = \left[\;\mchoose{m}{i+j+1}\;\right]_{i,j=0}^{m-1} \;$
%and $ L_m^T \;$ is the transpose of $\; L_m \,$.
%Since $\; L_m \;$ is a triangular matrix with unitary diagonal elements,
%it follows that $\; \det C_1^{(m)} = \det M_m \,$.
%Now identity (\ref{mchoosesum}) implies that $\; M_m = B_m \widetilde{B}_m \;$
%where $\; B_m = \left[\; { i + j \choose i } \;\right]_{i,j=0}^{m-1} \;$ and
%$\; \widetilde{B}_m = \left[\; \mchoose{m-i}{j}\; \right]_{i,j=0}^{m-1} \,$.
%Being $\; \widetilde{B}_m = J_m B_m \;$ where $\; J_m = [ \delta_{i+j,m-1} ]_{i,j=0}^{m-1} \,$,
%it is $\; M_m = B_m J_m B_m \;$ and $\; \det M_m = \det J_m ( \det B_m )^2 \,$.
%Since, as very well known, $\; \det J_m = (-1)^{\lfloor m/2 \rfloor} \;$ and  $\; \det B_m = 1 \,$,
%it follows that $\; \det M_m = (-1)^{\lfloor m/2 \rfloor} \;$
%and consequently $\; \det C_1^{(m)} = (-1)^{\lfloor m/2 \rfloor} \,$.
%Finally we have: $\; \det C_n^{(m)} = (-1)^{\lfloor m/2 \rfloor} 2^{n-1} \,$, for every $\; n \geq 1 \,$.

\section{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.
\begin{proposition}
 The numbers $ f_n^{(m)} $ admit the explicit expression
 \begin{equation}\label{fmncmn}
  f_n^{(m)} = \sum_{k=0}^m { m \choose k } (-1)^k c_n^{(m-k)} = \sum_{k=0}^m { m \choose k } (-1)^{m-k} c_n^{(k)} \, .
 \end{equation}
\end{proposition}
\begin{proof}
 Let $ A_i $ be the set of all $m$-compositions $ M \in \CC_n^{(m)}$ where the $i$-th row is zero.
 Then, by the Principle of Inclusion-Exclusion, we have
 $$ f_n^{(m)} = | A'_1 \cap \cdots \cap A'_m | = \sum_{S \subseteq [m]} (-1)^{|S|} \left| \bigcap_{i \in S} A_i \right| .$$
 Since there is an evident bijective correspondence between $ \bigcap_{i \in S} A_i $
 and the set of all $(m-|S|)$-compositions of $ n \,$, we have at once (\ref{fmncmn}).
\end{proof}

\begin{remark}
 Since the set $ \CC_n^{(m)}$ can be partitioned according to the number of zero rows,
 we also have the identity
 \begin{equation}\label{cmnfmn}
  c_n^{(m)} = \sum_{k=0}^m { m \choose k } f_n^{(k)} \, .
 \end{equation}
 Now, by inverting this formula, we reobtain (\ref{fmncmn}).
 Viceversa, we can obtain (\ref{cmnfmn}) by inverting (\ref{fmncmn}).
\end{remark}

\begin{proposition}
 The generating series for the numbers $ f_n^{(m)} $ is
 \begin{equation}\label{series-fn}
  f^{(m)}(x) = \sum_{k=0}^m { m \choose k } (-1)^{m-k} c^{(k)}(x)
             = \sum_{k=0}^m { m \choose k } (-1)^{m-k} \frac{(1-x)^k}{2(1-x)^k-1}  \, .
 \end{equation}
\end{proposition}
\begin{proof}
 This is an immediate consequence of identity (\ref{fmncmn}).
\end{proof}

\begin{proposition}
 For $ n \geq 1 \,$, the numbers $ f_n^{(m)} $ satisfy
 a homogeneous linear recurrence with constant coefficients of order $ { m+1 \choose 2 } \,$.
\end{proposition}
\begin{proof}
 Immediate consequence of the fact that the rational series (\ref{series-fn}) has the form
 \begin{equation}\label{gffmn}
  f^{(m)}(x) = \frac{x^m F_m(x)}{(1-2x)(1-4x+2x^2)\cdots(2(1-x)^m-1)}
 \end{equation}
 where $ F_m(x) $ is a polynomial with degree (less than or) equal to $ { m \choose 2 } \,$.
\end{proof}

\begin{remark}
 The recurrence satisfied by the numbers $ f_n^{(m)} $
 can be deduced from the denominator of series (\ref{gffmn}).
 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)} = 6 f_{n+2}^{(2)} - 10 f_{n+1}^{(2)} + 4 f_n^{(2)} \, . $$
 Similarly, for $ m = 3 \,$, we have the series
 $$ f^{(3)}(x) = \frac{13 x^3 - 24 x^4 + 16 x^5 - 4 x^6}{1 - 12 x + 52 x^2 - 102 x^3 + 96 x^4 - 44 x^5 + 8 x^6} $$
 and hence the recurrence
 $$
  f_{n+6}^{(3)} = 12 f_{n+5}^{(3)} - 52 f_{n+4}^{(3)} + 102 f_{n+3}^{(3)} - 96 f_{n+2}^{(3)} + 44 f_{n+1}^{(3)} - 8 f_n^{(3)} \, .
 $$
\end{remark}

\begin{proposition}
 The numbers $ f_n^{(m)} $ have the following explicit expression
 \begin{equation}\label{explicitfmn}
  f_n^{(m)} = \sum_{\rho\in\PP^m \atop |\rho|=n}
  \sum_{k \geq 0} \sum_{i=0}^k { k \choose i } \mchoose{k-i}{r_1} \cdots \mchoose{k-i}{r_m} (-1)^i \, ,
 \end{equation}
 where $ \PP $ is the set of all positive integers.
\end{proposition}
\begin{proof}
 Since $ f_n^{(m)} $ counts all $m$-compositions with non-zero row-sums, we have
 $$
  f_n^{(m)} = \sum_{k \geq 0} \sum_{(r_1,\ldots,r_m)\in\PP^m \atop r_1+\cdots+r_m=n} c_k^{(m)}(r_1,\ldots,r_m)
            = \sum_{k \geq 0} \sum_{\rho\in\PP^m \atop |\rho|=n} c_k^{(m)}(\rho)
 $$
 where $ \rho = (r_1,\ldots,r_m) $ and $ |\rho|=r_1+\cdots+r_m \,$.
 Hence, by (\ref{cmkrho}), we have at once (\ref{explicitfmn}).
\end{proof}

\begin{table}
 $$
 \footnotesize
 \begin{array}{|c|ccccccccccc|}
  \hline
     n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\
  \hline
   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 \\
   %m=7 &   &   &   &    &     &      &       &  47293 & 2075948 \\
   %m=8 &   &   &   &    &     &      &       &        &  545835 \\
  \hline
 \end{array}
 $$
 \caption{The numbers $ f_n^{(m)} \,$.}
 \label{table-fnm}
\end{table}

Let $ f_{nk}^{(m)} $ be the number of all $m$-compositions, without zero rows, of $ n $ of length $ k \,$.
\begin{proposition}
 The numbers $ f_{nk}^{(m)} $ admit the explicit expression
 \begin{equation}\label{fmnk-formula}
  f_{nk}^{(m)} = \sum_{i=0}^m \sum_{j=0}^k { m \choose i } { k \choose j } \mchoose{(m-i)(k-j)}{n} (-1)^{i+j} \, .
 \end{equation}
\end{proposition}
\begin{proof}
 Let $ A_{ij} $ be the set of all matrices $ M \in \MM_{mk}(\NN) $ 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)} = \left| \bigcap_{(i,j)\in[m]\times[k]} A'_{ij} \right|
  = \sum_{I \subseteq [m] \atop J \subseteq [k]} (-1)^{|I|+|J|} \left| \bigcap_{i \in I \atop j \in J} A_{ij} \right| .
 $$
 Since the intersection $ \bigcap_{i \in I,\, j \in 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 (\ref{fmnk-formula}) follows at once.
\end{proof}

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.
\begin{proposition}
 The numbers $ f_{nk}^{(m)} $ can be expressed as
 \begin{equation}\label{fmnk-Sformula}
  f_{nk}^{(m)} = \frac{m!k!}{n!} \sum_{h=0}^n { n \brack h } { h \brace m } { h \brace k } \, .
 \end{equation}
 Similarly, the numbers $ f_n^{(m)} $ can be expressed as
 \begin{equation}\label{fmn-Sformula}
  f_n^{(m)} = \frac{m!}{n!} \sum_{k=m}^n { n \brack k } { k \brace m } t_k \, .
 \end{equation}
\end{proposition}
\begin{proof}
 By using (\ref{risingExpansion}), identity (\ref{fmnk-formula}) can be rewritten as
 $$
  f_{nk}^{(m)} = \frac{1}{n!} \sum_{h=0}^n { n \brack h }
  \sum_{i=0}^m { m \choose i } (m-i)^h (-1)^i \sum_{j=0}^k { k \choose j } (k-j)^h (-1)^j \, .
 $$
 Now, by (\ref{surjFzId}), we have (\ref{fmnk-Sformula}).
 Finally, using the fact that $ f_n^{(m)} = \sum_{k=0}^n f_{nk}^{(m)} $
 and identities (\ref{formula-tn}) and (\ref{fmnk-Sformula}),
 we have at once identity (\ref{fmn-Sformula}).
\end{proof}

Clearly, $ f_n^{(m)} = 0 $ whenever $ n < m \,$. In particular, we have
$$ f_n^{(n)} = t_n \, , \qquad 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 \emph{preferential arrangement} is a set partition in which the blocks are linearly ordered \cite{Gross,Stanley,Wilf},
with a given preferential arrangement $ \pi = (B_1, \ldots, B_k) $ of an $n$-set $ X $
we can always associate the matrix $ M $
having as columns the characteristic vectors of the blocks of $ \pi \,$.
For instance, the preferential arrangement $ \pi = ( \{2,3\}, \{1,5\}, \{4\} ) $
of the set $ X = \{ 1, 2, 3, 4, 5 \} $ corresponds to the matrix
$$
 M = \begin{bmatrix}
      0 & 1 & 0 \\
      1 & 0 & 0 \\
      1 & 0 & 0 \\
      0 & 0 & 1 \\
      0 & 1 & 0 \\
     \end{bmatrix}.
$$
So, if $ \pi $ 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 $ \sigma(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{remark}
 Another kind of matrix compositions are \emph{packed matrices} \cite{DuchampHivertThibon},
 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 $ \sigma(M) = n \,$.
 These numbers form sequence \seqnum{A120733} in \cite{sloane}, and, by (\ref{fmn-Sformula}), can be expressed as
 $$ b_n = \sum_{m=0}^n f^{(m)}_n = \frac{1}{n!} \sum_{k=0}^n { n \brack k } t_k^2 \, . $$
\end{remark}

\section{Matrix compositions of Carlitz type}

We say that an $m$-composition is of \emph{Carlitz type} when no two adjacent columns are equal.
For $ m = 1 \,$, we have the ordinary \emph{Carlitz compositions} \cite{Carlitz}
(see also \cite{CarlitzII,LouchardProdinger,KnopfmacherProdinger} and \cite{CorteelHitczenko}).
Let $ z_n^{(m)} $ be the number of all $m$-composition of $ n $ of Carlitz type.
For $ m = 1 $ we have sequence \seqnum{A003242} in \cite{sloane},
while for $ m \geq 2 $ we have new sequences (see Table \ref{table-znm}).
\begin{table}
 $$
 \footnotesize
 \begin{array}{|c|ccccccccccc|}
  \hline
     n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\
  \hline
   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 \\
  \hline
 \end{array}
 $$
 \caption{The numbers $ z_n^{(m)} \,$.}
 \label{table-znm}
\end{table}

\begin{proposition}
 The generating series of the numbers $ z_n^{(m)} $ is
 \begin{equation}\label{zseries}
  z^{(m)}(x) = \sum_{n \geq 0} z_n^{(m)}\; x^n
             = \frac{1}{\displaystyle 1-\sum_{k \geq 1} \Mchoose{m}{k} \frac{x^k}{1+x^k}} \, ,
 \end{equation}
 or, equivalently,
 \begin{equation}\label{zseries2}
  z^{(m)}(x) = \frac{1}{\displaystyle 1+\sum_{k \geq 1} (-1)^k \frac{1-(1-x^k)^m}{(1-x^k)^m}}
             = \frac{1}{\displaystyle 1+\sum_{k \geq 1} (-1)^k h^{(m)}(x^k)} \, .
 \end{equation}
\end{proposition}
\begin{proof}
 Let $ x_\mu $ be an indeterminate marking a column of an $m$-matrix
 equivalent to a multiset $ \mu \in \MM^{(m)}_{\ne 0} \,$,
 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)}_\mu(X) $ be the generating series for the set of all $m$-compositions of Carlitz type
 whose last column corresponds to the multiset $ \mu \,$.
 Then we have at once the linear system
 $$
  \begin{cases}
   \displaystyle z^{(m)}(X) = 1 + \sum_{\mu \in \MM^{(m)}_{\ne 0}} z^{(m)}_\mu(X) \\
   z^{(m)}_\mu(X) = \left( z^{(m)}(X) - z^{(m)}_\mu(X) \right) x_\mu \qquad \forall\; \mu \in \MM^{(m)}_{\ne 0}
  \end{cases}
 $$
 from which
 $$
  z^{(m)}_\mu(X) = \frac{x_\mu}{1+x_\mu}\; z^{(m)}(X)
  \qquad\textrm{and}\qquad
  z^{(m)}(X) = \frac{1}{\displaystyle 1-\sum_{\mu \in \MM^{(m)}_{\ne 0}} \frac{x_\mu}{1+x_\mu}} \, .
 $$
 Now, to obtain (\ref{zseries}) it is sufficient to substitute $ x_\mu $ with $ x^{\ord(\mu)} $
 in $ z^{(m)}(X) \,$.

 Finally, (\ref{zseries2}) can be obtained with the same argument used in \cite{Carlitz} by Carlitz,
 or simply by rewriting in a suitable way the series at the denominator of (\ref{zseries}).
\end{proof}

\begin{proposition}
 The numbers $ z_n^{(m)} $ can be expressed as
 \begin{equation}\label{formula-zn}
  z_n^{(m)} = \sum_{k\geq 0} \sum_{\alpha, \beta \in \PP^k \atop \alpha \cdot \beta=n} \Mchoose{m}{\alpha} (-1)^{|\beta|-k} \, .
 \end{equation}
 where, for every $ \alpha = (a_1, \ldots, a_k) $ and $ \beta = (b_1, \ldots, b_k) \,$,
 $ \alpha \cdot \beta = a_1 b_1 + \cdots + a_k b_k \,$, $\; | \beta | = b_1 + \cdots + b_k $
 and $ \Mchoose{m}{\alpha} = \Mchoose{m}{a_1} \ldots \Mchoose{m}{a_k} \,$.
\end{proposition}
\begin{proof}
 {From} (\ref{zseries}), we have
 \begin{eqnarray*}
  z^{(m)}(x)
  & = & \sum_{k\geq 0} \left( \sum_{n\geq 1} \Mchoose{m}{n} \frac{x^n}{1+x^n} \right)^{\!\!k} \\
  & = & \sum_{k\geq 0} \sum_{a_1\geq 1}
        \mchoose{m}{a_1} \frac{x^{a_1}}{1+x^{a_1}} \cdots \sum_{a_k\geq 1} \mchoose{m}{a_k} \frac{x^{a_k}}{1+x^{a_k}} \\
  & = & \sum_{k\geq 0} \sum_{a_1, \ldots, a_k\geq 1} \mchoose{m}{a_1} \ldots \mchoose{m}{a_k}
        \frac{x^{a_1}}{1+x^{a_1}} \cdots \frac{x^{a_k}}{1+x^{a_k}}\\
  & = & \sum_{k\geq 0} \sum_{a_1, \ldots, a_k\geq 1 \atop b_1, \ldots, b_k\geq 1} \mchoose{m}{a_1} \ldots \mchoose{m}{a_k}
       (-1)^{b_1 + \cdots + b_k - k} x^{a_1b_1 + \cdots + a_kb_k} \\
  & = & \sum_{n\geq 0} \left(\sum_{k\geq 0} \sum_{\alpha, \beta \in \NN_0^k \atop \alpha \cdot \beta=n} \Mchoose{m}{\alpha} (-1)^{|\beta|-k}\right) x^n
 \end{eqnarray*}
% that is
% $$
%  z^{(m)}(x) = \sum_{n\geq 0}
%  \left(
%   \sum_{k\geq 0} \sum_{\alpha, \beta \in \NN_0^k \atop \alpha \cdot \beta=n} \Mchoose{m}{\alpha} (-1)^{|\beta|-k}
%  \right) x^n \, .
% $$
 Hence, we have (\ref{formula-zn}).
\end{proof}

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
\begin{equation}\label{zg-rel}
 z_n^{(m)} = \sum_{k=0}^m { m \choose k } g_n^{(k)}
 \qquad \textrm{and} \qquad
 g_n^{(m)} = \sum_{k=0}^m { m \choose k } (-1)^{m-k} z_n^{(k)} \, .
\end{equation}

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 \,$.

\begin{table}
 $$
 \footnotesize
 \begin{array}{|c|ccccccccccc|}
  \hline
     n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\
  \hline
   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 \\
   %m=7 &   &   &   &    &     &      &       &  47293 & 1894032 \\
   %m=8 &   &   &   &    &     &      &       &        &  545835 \\
  \hline
 \end{array}
 $$
 \caption{The numbers $ g_n^{(m)} \,$.}
 \label{table-gnm}
\end{table}

\section{Matrix compositions with palindromic rows}

An ordinary composition is \emph{palindromic} when its elements are the same
in the given or in the reverse order \cite{ChinnHeubach,ChinnHeubach2,HoggattBicknell,MerliniUnciniVerri}.
Here, we say that an $m$-composition is palindromic when all its rows are palindromic.
For instance,
$$
 M =
 \begin{bmatrix}
  1 & 2 & 1 &  2 &   1 \\
  2 & 0 & 3 &  0 &   2 \\
  0 & 0 & 1 &  0 &   0 \\
  3 & 1 & 1 &  1 &   3 \\
 \end{bmatrix}
$$
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 \ref{table-pnm}).
\begin{table}
 $$
 \footnotesize
 \begin{array}{|c|ccccccccccc|}
  \hline
    n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ % & 11
  \hline
   m=0 & 1 & 0 &  0 &  0 &   0 &   0 &    0 &    0 &     0 &     0 &      0 \\ % &      0
   m=1 & 1 & 1 &  2 &  2 &   4 &   4 &    8 &    8 &    16 &    16 &     32 \\ % &     32
   m=2 & 1 & 2 &  5 &  8 &  18 &  28 &   62 &   96 &   212 &   328 &    724 \\ % &   1120
   m=3 & 1 & 3 &  9 & 19 &  48 &  96 &  236 &  468 &  1146 &  2270 &   5556 \\ % &  11004
   m=4 & 1 & 4 & 14 & 36 & 101 & 240 &  648 & 1520 &  4082 &  9560 &  25660 \\ % &  60088
   m=5 & 1 & 5 & 20 & 60 & 185 & 501 & 1470 & 3910 & 11390 & 30230 &  88002 \\ % & 233530
   m=6 & 1 & 6 & 27 & 92 & 309 & 930 & 2939 & 8640 & 27048 & 79280 & 247968 \\ % & 726672
  \hline
 \end{array}
 $$
 \caption{The numbers $ p_n^{(m)} \,$.}
 \label{table-pnm}
\end{table}
\begin{proposition}
 The generating series for the palindromic $m$-compositions is
 \begin{equation}\label{series-pn}
  p^{(m)}(x) = \sum_{n \geq 0} p_n^{(m)}\; x^n = \frac{(1+x)^m}{2(1-x^2)^m-1} \, .
 \end{equation}
 In particular, the numbers $ p_n^{(m)} $ can be expressed as
 \begin{equation}\label{formula-pn}
  p_n^{(m)} = \sum_{k=0}^{\lfloor n/2 \rfloor} \mchoose{m}{n-2k} c_k^{(m)} \, .
 \end{equation}
\end{proposition}
\begin{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 | \mathbf{v} | M_s ] \,$,
 where $ M $ is an arbitrary $m$-composition,
 $ M_s $ is the specular $m$-composition obtained from $ M $ by reversing every row
 and $ \mathbf{v} $ is an arbitrary non-zero column vector. Hence
 $$ p^{(m)}(x) = c^{(m)}(x^2) + \left[\frac{1}{(1-x)^m}-1\right] c^{(m)}(x^2) = \frac{c^{(m)}(x^2)}{(1-x)^m} \, , $$
 that is (\ref{series-pn}). Finally, identity (\ref{formula-pn})
 can be obtained by expanding the series on the right-hand side of the above equations.
\end{proof}

Now, let $ q_n^{(m)} $ be the number of all $m$-compositions of $ n $ with palindromic non-zero rows
(see Table \ref{table-qnm}).
With arguments similar to those used in the case of ordinary $m$-compositions, we have
\begin{equation}\label{pq-rel}
 p_n^{(m)} = \sum_{k=0}^m { m \choose k } q_n^{(k)}
 \qquad \textrm{and} \qquad
 q_n^{(m)} = \sum_{k=0}^m { m \choose k } (-1)^{m-k} p_n^{(k)} \, .
\end{equation}

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 \,$.

\begin{table}
 $$
 \footnotesize
 \begin{array}{|c|ccccccccccc|}
  \hline
   m / n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\
  \hline
   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 \\
   %m=7 &   &   &   &   &    &    &    &   1 &  14 &  140 \\
   %m=8 &   &   &   &   &    &    &    &     &   1 &   16 \\
   %m=9 &   &   &   &   &    &    &    &     &     &    1 \\
  \hline
 \end{array}
 $$
 \caption{The numbers $ q_n^{(m)} \,$.}
 \label{table-qnm}
\end{table}

\section{Matrices generated by $m$-compositions}

Identities (\ref{fmncmn}), (\ref{cmnfmn}), (\ref{zg-rel}) and (\ref{pq-rel}) can be reformulated in terms of matrices.
In particular, we will consider the following pairs of infinite matrices.
\begin{enumerate}
 \item
  The matrix $ C = [ c_n^{(m)} ]_{m,n \geq 0} $ generated by $m$-compositions (see Table \ref{table-cnm}),
  and the the upper triangular matrix $ F = [ f_n^{(m)} ]_{m,n \geq 0} $
  generated by $m$-compositions without zero rows (see Table \ref{table-fnm}).
 \item
  The matrix $ Z = [ z_n^{(m)} ]_{m,n \geq 0} $ generated by $m$-compositions of Carlitz type
  (see Table \ref{table-znm}),
  and the upper triangular matrix $ G = [ g_n^{(m)} ]_{m,n \geq 0} $
  generated by $m$-compositions of Carlitz type without zero rows (see Table \ref{table-gnm}).
 \item
  The matrix $ P = [ p_n^{(m)} ]_{m,n \geq 0} $ generated by $m$-compositions with palindromic rows
  (see Table \ref{table-pnm}),
  and the upper triangular matrix $ Q = [ q_n^{(m)} ]_{m,n \geq 0} $
  generated by $m$-compositions with palindromic rows without zero rows (see Table \ref{table-qnm}).
\end{enumerate}

Finally, we also need the ordinary binomial matrix $ B = [ { m \choose n } ]_{m,n \geq 0} \,$.
Moreover, if $ X = [ x_{ij} ]_{i,j\geq0} $ if an infinite matrix,
then we can always consider the partial matrices $ X_k = [ x_{ij} ]_{i,j=0}^k \,$, for every $ k \in \NN \,$.
\begin{proposition}\label{prop-LU-C}
 We have the following LU-factorizations over $ \NN \,$: $\; C = B F \,$, $\; Z = B G \,$, $\; P = B Q \,$.
 Similarly, $ C_k = B_k F_k \,$, $ Z_k = B_k G_k \,$, $ P_k = B_k Q_k \,$, for every $\; k \in \NN \,$.
\end{proposition}

\begin{proposition}
 For every $ k \in \NN \,$, we have $ \det C_k = \det Z_k = t_0 t_1 \cdots t_k $ and $ \det P_k = 1 \,$.
\end{proposition}
\begin{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 \in \NN \,$,
 the factorizations in Proposition \ref{prop-LU-C} and Binet's theorem imply at once the stated identities.
\end{proof}

\section{Final remarks}

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

\paragraph{$L$-convex polyominoes.}
As remarked in the introduction,
$2$-compositions have been introduced in \cite{CastiglioneFrosiniMunariniRestivoRinaldi}
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.

\paragraph{Labelled bargraphs.}
The simple correspondence between $m$-compositions and labelled bargraphs with degree at most $ m $
(considered in Subsection \ref{LabbeledBargraphsSec}) suggests to study some particular subclasses of
matrix compositions arising in a very natural way as subclasses of bargraphs, such as the following ones.
\begin{enumerate}
 \item
  The class of bargraphs having all the $ m $ labels in each column (Figure~\ref{bargraph4}(a)),
  corresponding to the set of $m$-compositions containing no $0$'s.
%  The generating function of such objects is:
%  $$ 1 + \frac{\left( \frac{x}{1-x} \right) ^m}{1- \left( \frac{x}{1-x} \right) ^m}
%  = \frac{1}{1-\left( \frac{x}{1-x} \right ) ^m } \,; $$

  \begin{figure}[htb]
  \centerline{\hbox{\psfig{figure=bargraph4.eps,width=4.5in,clip=}}} \caption{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$.} \label{bargraph4}
  \end{figure}
 \item
  The class of \emph{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 \ref{bargraph4}~(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 \emph{$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~\ref{bargraph4}~(b) corresponds to the following $3$-partition of $ 20 \,$:
  $$
   \begin{bmatrix}
    1 & 3 & 0 & 1 & 0 & 0 \\
    4 & 0 & 1 & 2 & 0 & 1 \\
    1 & 2 & 2 & 0 & 2 & 0 \\
   \end{bmatrix}.
  $$
 \item
  The class of \emph{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 \ref{bargraph4}(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 , \ldots,  c_k $ is unimodal.
\end{enumerate}
The problem of generating efficiently the \emph{$m$-partitions} has been studied in \cite{GrazziniMunariniPonetiRinaldi},
while the problem of enumerating labelled Ferrers diagrams and labelled
stacks has been solved in \cite{munabargraphs}, in a more general context.

\paragraph{$m$-colored compositions.}
Another interesting problem concerns the generalization to matrix compositions of the poset of ordinary
compositions considered by Bj\"{o}rner and Stanley~\cite{BjornerStanley}.
A first step in this direction has been made, independently, by Drake and Petersen in \cite{DrakePetersen},
where they introduced the \emph{$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 $ \alpha $ is an ordered tuple of ``colored'' positive integers,
that is $ \alpha = ( a_1 \omega^{s_1}, \ldots , a_k \omega^{s_k} ) \,$,
where the $ a_i$'s are positive integers, $ \omega $ is a primitive $m$-root of unity
and $ 0 \leq s_i \leq m-1 $ for each $ i = 1, \ldots, k \,$.
The $i$-th part of $ \alpha $ is $ a_i \omega^{s_i} $ and has color $ \omega^{s_i} \,$.
Moreover, $ \alpha $ is an $m$-colored composition of an integer number $ n $
when $ a_1 + \cdots + a_k = n \,$.
Hence an $m$-colored composition $ \alpha $ of a integer $ n $ is uniquely represented
by the $m$-composition $ M(\alpha) $ 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, \ldots, k \,$.
So, for instance, the $3$-colored composition $ \alpha = (2\omega,3,1,\omega^2,3\omega) $ of $ 10 $
is equivalent to the $3$-composition
$$
 M(\alpha) =
 \begin{bmatrix}
  0 & 3 & 1 & 0 & 0 \\
  2 & 0 & 0 & 0 & 3 \\
  0 & 0 & 0 & 1 & 0
 \end{bmatrix}.
$$
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.

\begin{thebibliography}{99}
 \bibitem{Andrews}
  G. E. Andrews,
  \emph{The Theory of Partitions},
  Encyclopedia of Mathemetics and its Applications,
  Addison-Wesley Publishing Company, Reading, Massachusetts, 1976.
 \bibitem{Andrews75}
  G. E. Andrews,
  The theory of compositions, II: Simon Newcom's problem,
  \emph{Utilitas Math.} \textbf{7} (1975), 33--54.
 \bibitem{Andrews76a}
  G. E. Andrews,
  The theory of compositions, I: The ordered factorizations of $n$ and a conjecture of C. Long,
  \emph{Canadian Math. Bull.} \textbf{18} (1976), 479--484.
 \bibitem{Andrews76b}
  G. E. Andrews,
  The theory of compositions, III: The MacMahon formula and the Stanton-Cowan numbers,
  \emph{Utilitas Math.} \textbf{9} (1976), 283--290.
 \bibitem{BergeronBousquetMelouDulucq}
  F. Bergeron, M. Bousquet-M{\'e}lou, and S. Dulucq,
  Standard paths in the composition poset,
  \emph{Ann. Sci. Math. Qu\'ebec} \textbf{19} (1995), 139--151.
 \bibitem{BergeronLabelleLeroux}
  F. Bergeron, G. Labelle, and P. Leroux,
  \emph{Combinatorial Species and Tree-like Structures},
  Encyclopedia of Mathematics and Its Applications \textbf{67}, G.-C. Rota editor,
  Cambridge University Press, Cambridge, 1998.
 \bibitem{BjornerSagan}
  A. Bj\"orner and B. Sagan,
  Rationality of the M\"obius function of a composition poset,
  \emph{Theoret. Comput. Sci.} \textbf{359} (2006), 282--298.
 \bibitem{BjornerStanley}
  A. Bj\"orner and R. Stanley,
  An analogue of Young's lattice for compositions,
  preprint at \emph{arXiv:math/0508043v4}.
 \bibitem{mbm2}
  M. Bousquet-M\'elou,
  A method for the enumeration of various classes of column-convex polygons,
  \emph{Discrete Math.} \textbf{154} (1996), 1--25.
 \bibitem{BMR}
  M. Bousquet-M\'elou and A. Rechnitzer,
  The site-perimeter of bargraphs,
  \emph{Adv. in Appl. Math.} \textbf{31} (2003), 86--112.
 \bibitem{Carlitz}
  L. Carlitz,
  Restricted compositions,
  \emph{Fibonacci Quart.} \textbf{14} (1976), 254--264.
 \bibitem{CarlitzE}
  L. Carlitz,
  Enumeration of compositions by rises, falls and levels.
  \emph{Math. Nachr.} \textbf{77} (1977), 361--371.
 \bibitem{CarlitzII}
  L. Carlitz,
  Restricted compositions. II,
  \emph{Fibonacci Quart.} \textbf{17} (1979), 321--328.
 \bibitem{ChinnHeubach}
  P. Chinn and S. Heubach,
  Compositions of $n$ with no occurrence of $k$,
  \emph{Proceedings of the Thirty-Fourth Southeastern International Conference on Combinatorics, Graph Theory and Computing}.
  \emph{Congr. Numer.} \textbf{164} (2003), 33--51.
 \bibitem{ChinnHeubach2}
  P. Chinn and S. Heubach,
  Integer sequences related to compositions without 2's,
  \emph{J. Integer Seq.} \textbf{6} (2003). % Journal of Integer Sequences
 \bibitem{CastiglioneFrosiniMunariniRestivoRinaldi}
  G. Castiglione, A. Frosini, E. Munarini, A. Restivo, and S. Rinaldi,
  Combinatorial aspects of $L$-convex polyominoes,
  \emph{Europ. J. Comb.} \textbf{28} (2007), 1724--1741.
 \bibitem{Comtet}
  L. Comtet,
  \emph{Advanced Combinatorics},
  Reidel, Dordrecht-Holland, Boston, 1974.
 \bibitem{CorteelHitczenko}
  S. Corteel and P. Hitczenko,
  Generalizations of Carlitz compositions,
  \emph{J. Integer Seq.} \textbf{10} (2007), Article 07.8.8, 13 pp. (electronic).
 \bibitem{DrakePetersen}
  B. Drake and T. K. Petersen,
  \emph{The $m$-colored composition poset},
  %Proceedings of FPSAC'06, Formal Power Series and Algebraic Combinatorics 2006, San Diego.
  \emph{Electron. J. Combin.} \textbf{14} (2007), Research Paper 23, 14 pp. (electronic).
 \bibitem{DuchampHivertThibon}
  G. Duchamp, F. Hivert, and J.-Y. Thibon,
  Noncommutative symmetric functions VI: Free quasi-symmetric functions and related algebras,
  \emph{Internat. J. Alg. Comp.} \textbf{12} (2002), 671--717.
 \bibitem{FrosiniRinaldi}
  A. Frosini and S. Rinaldi,
  On the sequence \seqnum{A079500} and its combinatorial interpretations,
  \emph{J. Integer Seq.} \textbf{9} (2006), Article 06.3.1, 13 pp. (electronic).
  % Journal of Integer Sequences
 \bibitem{GrahamKnuthPatashnik}
  R. L. Graham, D. E. Knuth, and O. Patashnik,
  \emph{Concrete Mathematics},
  Addison-Wesley, Reading, Massachusetts, 1989.
 \bibitem{GrazziniMunariniPonetiRinaldi}
  E. Grazzini, E. Munarini, M. Poneti, and S. Rinaldi,
  m-compositions and m-partitions: exhaustive generation and Gray code,
  \emph{Pure Math. Appl.} \textbf{17} (2006), 111--121.
% \bibitem{GrazziniMunariniPonetiRinaldi}
%  E. Grazzini, E. Munarini, M. Poneti, and S. Rinaldi,
%  \emph{On the generation of $m$-compositions and $m$-partitions},
%  Proceedings of GASCom and Bijective Combinatorics 2006, Dijon, 12--23.
 \bibitem{Gross}
  O. A. Gross,
  Preferential arrangements,
  \emph{Amer. Math. Monthly} \textbf{69} (1962), 4--8.
 \bibitem{HeubachMansour04}
  S. Heubach and T. Mansour,
  Compositions of $n$ with parts in a set,
  \emph{Proceedings of the Thirty-Fifth Southeastern International Conference on Combinatorics, Graph Theory and Computing}.
  \emph{Congr. Numer.} \textbf{168} (2004), 127--143.
 \bibitem{HeubachMansour05}
  S. Heubach and T. Mansour,
  Counting rises, levels, and drops in compositions,
  \emph{Integers} \textbf{5} (2005), \textbf{A11}, 24 pp. (electronic).
 \bibitem{HoggattBicknell}
  V. E. Hoggatt, Jr. and  M. Bicknell,
  Palindromic compositions,
  \emph{Fibonacci Quart.} \textbf{13} (1975), 350--356.
 \bibitem{Joyal}
  A. Joyal,
  Une th\'eorie combinatoire des s\'eries formelles,
  \emph{Adv. in Math.} \textbf{42} (1981), 1--82.
 \bibitem{KnopfmacherProdinger}
  A. Knopfmacher and H. Prodinger,
  On Carlitz compositions,
  \emph{European J. Combin.} \textbf{19} (1998), 579--589.
 \bibitem{KnopfmacherRobbins}
  A. Knopfmacher and N. Robbins,
  Compositions with parts constrained by the leading summand,
  \emph{Ars Combinatorica} \textbf{76} (2005), 287--295.
 \bibitem{LinRui}
  Z. Lin and H. Rui,
  Cyclotomic $Q$-Schur algebras and Schur-Weyl duality.
  Representations of algebraic groups, quantum groups, and Lie algebras, 133--155,
  \emph{Contemp. Math.}, \textbf{413}, Amer. Math. Soc., Providence, RI, 2006.
 \bibitem{Louchard}
  G. Louchard,
  Matrix compositions: a probabilistic approach,
  \emph{Proceedings of GASCom and Bijective Combinatorics 2008}, Bibbiena, Italy, 159--170.
 \bibitem{LouchardProdinger}
  G. Louchard and H. Prodinger,
  Probabilistic analysis of Carlitz compositions,
  \emph{Discrete Math. Theor. Comput. Sci.} \textbf{5} (2002), 71--95 (electronic).
 \bibitem{MacMahon1}
  P. A. MacMahon,
  Memoir on the theory of the compositions of numbers,
  \emph{Phil. Trans. Royal Soc.} \textbf{184} (1894), 835--901.
 \bibitem{MacMahon2}
  P. A. MacMahon,
  Second memoir on the compositions of numbers,
  \emph{Phil. Trans. Royal Soc.} \textbf{207} (1908), 65--134.
 \bibitem{MacMahon3}
  P. A. MacMahon,
  \emph{Combinatory Analysis},
  vol. 1, Cambridge Univerity Press, Cambridge 1915
  (reprinted: Chelsea, New York 1960).
 \bibitem{MerliniUnciniVerri}
  D. Merlini, F. Uncini, and C. Verri,
  A unified approach to the study of general and palindromic compositions,
  \emph{Integers} \textbf{4} (2004), A23, 26 pp. (electronic).
 \bibitem{munabargraphs}
  E. Munarini,
  Column enriched bargraphs,
  preprint.
 \bibitem{OP}
  A. L. Owczarek and T. Prellberg,
  Exact solution of the discrete (1+1)-dimensional SOS model with field and surface interactions,
  \emph{J. Stat. Phys.} \textbf{70} (1993), 1175--1194.
 \bibitem{PB}
  T. Prellberg and R. Brak,
  Critical exponents from non-linear functional equations for partially directed cluster models,
  \emph{J. Stat. Phys.} \textbf{78} (1995), 701--730.
 \bibitem{Riordan}
  J. Riordan,
  \emph{An Introduction to Combinatorial Analysis},
  Dover Publications, 2002.
 \bibitem{SaganVatter}
  B. Sagan and V. R. Vatter,
  The M\"obius function of a composition poset,
  \emph{J. Algebraic Combin.} \textbf{24} (2006), 117--136.
 \bibitem{sloane}
  N. J. A. Sloane,
  \emph{On-Line Encyclopedia of Integer Sequences}, published electronically at
  {\tt http://www.research.att.com/\~{}njas/sequences/}.
 \bibitem{Snellman}
  J. Snellman,
  Saturated chains in composition posets,
  preprint availeble at \texttt{arXiv:math.CO/0505262}.
 \bibitem{Snellman2}
  J. Snellman,
  Standard paths in another composition poset,
  \emph{Electron. J. Combin.} \textbf{11} (1) (2004), Research Paper 76, 8 pp. (electronic).
 \bibitem{Stanley}
  R. P. Stanley,
  \emph{Enumerative Combinatorics},
  Volume 1, Cambridge Studies in Advanced Mathematics \textbf{49},
  Cambridge University Press, Cambridge, 1997.
 \bibitem{Wilf}
  H. S. Wilf,
  \emph{Generatingfunctionology},
  Academic Press, Boston, MA, 1990.
\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2000 {\it Mathematics Subject Classification}:
Primary 05A17; Secondary 05A15.\\

\noindent \emph{Keywords: } 
compositions, multisets, Cassini identity, Carlitz compositions,
palindromic compositions, preferential arrangements, bargraphs,
Stirling number, enumeration.

\bigskip
\hrule
\bigskip

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

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received July 25 2008;
revised version received  June 16 2009.
Published in {\it Journal of Integer Sequences}, June 20 2009.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}