% revised April 7, 2013 for presentation. Can not wait for Jean. It has been in her hand since middle Feb, no comments. % submitted to E-JC on April 10, 2013. Get report in the end of July. Revise accordingly on Sep. 5. % add Mitch for he contributed in Section 5 , proof-read by Mitch 9/14/13 \documentclass[12pt]{article} \usepackage{e-jc} \usepackage{amsmath,amsthm,amssymb} %\usepackage{amstext,amsbsy} %\usepackage{epsfig,multicol} %\usepackage{color} \usepackage{tikz} \usepackage{graphicx} %\usepackage{subfigure} % use this command to create hyperlinks (optional and recommended) \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} % use these commands for typesetting doi and arXiv references in the bibliography \newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}} \newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}} % all overfull boxes must be fixed; % i.e. there must be no text protruding into the margins %% The lines between the two rows of %'s are more or less compulsory. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %\makeatother \pagestyle{plain} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %Page Size % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % No more paper size for E-JC %\setlength{\oddsidemargin}{0.0in} % %\setlength{\evensidemargin}{0.0in}% %\setlength{\textwidth}{6.5in} % %\setlength{\parskip}{1.2ex} % %\setlength{\textheight}{9in} % %\setlength{\topmargin}{-0.6in} % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % declare theorem-like environments \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{fact}[theorem]{Fact} \newtheorem{observation}[theorem]{Observation} \newtheorem{claim}[theorem]{Claim} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{open}[theorem]{Open Problem} \newtheorem{problem}[theorem]{Problem} \newtheorem{question}[theorem]{Question} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \newtheorem{note}[theorem]{Note} % From the following are mine own commands \def\dotcircle{\mathinner{12Ge\hbox{.}}} \def\pf{\noindent{\it Proof.} } \def\sol{\noindent{\it Solution.} } %\def\rem{\noindent{\it Remark.} } \def\qed{\nopagebreak\hfill{\rule{4pt}{7pt}}\medbreak} \def \se {\mathrm{se}} \def \ne {\mathrm{ne}} \def \neB {\mathrm{ne}^\Box} \def \seB {\mathrm{se}^\Box} \def \mne {\mathrm{maxne}} \def \al {\mathrm{al}} \def \inv {\mathrm{inv}} \def \asc {\mathrm{coinv}} \def \F {\mathbf{F}} \def \s {\mathbf{s}} \def \bve {\mathbf{e}} \def \ve {\varepsilon} \def \cros {\mathrm{cros}} \def \nest {\mathrm{nest}} %\newcommand {\auc} {\mathrm{auc}} %\newcommand {\buc} {\mathrm{buc}} %\newcommand {\ce} {\mathrm{ce}} \def \M {\mathcal{M}} \def \N {\mathcal{N}} \def \R {\mathcal{R}} \def \B {\mathcal{B}} \def \L {\mathcal{L}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \title{Chains of Length 2 in Fillings of Layer Polyominoes } \author{Mitch Phillipson, Catherine H. Yan and Jean Yeh \\ \small Department of Mathematics \\ [-0.8ex] \small Texas A\&M University \\[-0.8ex] \small College Station, Texas, U.S.A. \\ \small \tt \{phillipson,cyan,jeanyeh\}@math.tamu.edu } %\date{} % \date{\dateline{submission date}{acceptance date}\\ % \small Mathematics Subject Classifications: comma separated list of % MSC codes available from http://www.ams.org/mathscinet/freeTools.html} \date{\dateline{Apr 11, 2013}{Sep 12, 2013}\\ \small Mathematics Subject Classification: 05A15, 05B50, 05E10 } \begin{document} \maketitle \begin{abstract} The symmetry of the joint distribution of the numbers of crossings and nestings of length $2$ has been observed in many combinatorial structures, including permutations, matchings, set partitions, linked partitions, and certain families of graphs. These results have been unified in the larger context of enumeration of northeast and southeast chains of length $2$ in $01$-fillings of moon polyominoes. In this paper we extend this symmetry to fillings of a more general family --layer polyominoes, which are intersection-free and row-convex, but not necessarily column-convex. %The family of layer polyominoes are closed under permutations of rows. Our main result is that the joint distribution of the numbers of northeast and southeast chains of length $2$ over $01$-fillings is symmetric and invariant under an arbitrary permutation of rows. % keywords are optional \bigskip\noindent \textbf{Keywords:} chains of length 2, polyomino, symmetric distributions \end{abstract} \section{Introduction} % background, definition Recently there have been many interesting results on the combinatorics of crossings and nestings over discrete structures. In particular, it is observed that the numbers of crossings and nestings of length 2 often have a symmetric distribution. The first examples are the classical permutation statistics that count the numbers of \emph{inversions} and \emph{coinversions}. Another example comes from complete matchings, which are partitions of the set $\{1,2,\dots, 2n\}$ into $n$ blocks of size 2. In a matching, two blocks $(i_1, j_1)$ and $(i_2, j_2)$ form a \emph{crossing} if $i_1 < i_2< j_1 < j_2$; they form a \emph{nesting} if $i_1 < i_2 < j_2 < j_1$. The symmetry of the joint distribution of crossings and nestings over complete matchings follows from a bijection of de Sainte-Catherine \cite{deSC}, who also found the generating function for the number of crossings (or nestings). This result was extended to set partitions by Kasraoui and Zeng \cite{Kasra06}, to linked set partitions by Chen, Wu and Yan \cite{CWY}, and to a certain diagram associated with permutations by Corteel \cite{Corteel07}. Klazar \cite{klazar}, and Poznanovikj and Yan \cite{PY09} studied further the distributions of crossings and nestings over the generating trees of matchings and set partitions, respectively. Kasraoui unified the symmetry of crossings and nestings in \cite{Kasra08} by using the model of fillings of moon polyominoes, where a moon polyomino is a collection of cells in $\mathbb{Z}^2$ that are convex and intersection-free, (see Section 2 for exact definitions). Crossings and nestings become northeast and southeast chains of length 2 in fillings of polyominoes. Kasraoui proved that the statistic $(\ne, \se)$, the numbers of northeast and southeast chains of length $2$, has a symmetric joint distribution over the set of $01$-fillings of moon polyominoes where either every row has at most one $1$, or every column has at most one $1$. In both cases, the joint distribution of $(\ne, \se)$ can be expressed as a product of $(p,q)$-Gaussian coefficients. This symmetry was further strengthened in \cite{CWYY} which showed that the northeast and southeast chains can be mixed according to the positions of the $1$-cells in a chain, yet the new statistics still have the same joint distribution as $(\ne, \se)$. From the bi-variate generating function of $(\ne, \se)$ one notes that these statistics (and their mixed variants) are invariant under permutations of rows and columns of the underlying polyomino, provided that the resulting polyomino is still convex and intersection-free. Such an invariant property also appears in other combinatorial statistics of fillings of moon polyominoes, for example, in the sizes of longest northeast chains and southeast chains \cite{Jon05,JW07,Rubey}, and in the major index for $01$-fillings of moon polyominoes \cite{CPYY}. The motivation of the present paper is to understand this invariant property for the pair $(\ne, \se)$. To keep the convexity, rows (or columns) of a moon polyomino can not be permuted arbitrarily. It is natural to ask whether there is a larger family of polyominoes that allows a free permutation of rows while preserving the distribution of $(\ne, \se)$ over $01$-fillings. As observed by Kasraoui \cite{Kasra08}, the condition of intersection-free is necessary. In this paper we propose the notion of \emph{layer polyominoes}, which are polyominoes that are intersection-free and row-convex, but not necessarily column-convex. The family of layer polyominoes is closed under permutations of rows. In fillings of layer polyominoes the northeast and southeast chains are still well-defined. Our main result is that over all $01$-fillings of a layer polyomino where every row has at most one $1$, or every column has at most one $1$, the distribution of $(ne, se)$ depends only on the sets of the rows, but not how the rows are arranged. The paper is organized as follows. Section 2 contains necessary notation and the main result that the distribution of $(\ne, \se)$ is invariant under the action of the symmetric group $\mathfrak{S}_n$ on the rows of the underlying layer polyomino. Then we give new proofs for the symmetry of the mixed statistics for fillings of moon polyominoes, and describe how to obtain the joint distribution of $(\ne, \se)$ over 01-fillings of a layer polyomino. This is the content of Sections 3 and 4. In Section 5 we prove the symmetric distribution of a variation of NE/SE chains. We conclude the paper with some comments and counterexamples to a few seemingly natural generalizations. \section{Northeast and southeast chains in layer polyominoes } We begin by giving necessary notations in the language of fillings of polyominoes. A \textit{polyomino} is a finite subset of $\mathbb{Z}^2$, where every element of $\mathbb{Z}^2$ is represented by a square cell. The polyomino is \textit{row-convex} (\emph{column-convex}) if its intersection with any row (column) of $\mathbb{Z}^2$ is connected. It is \textit{convex} if it is both row-convex and column convex. A polyomino is said to be \textit{intersection-free} if every two rows are comparable, i.e., the column-coordinates of one row form a subset of those of the other row. It is easily checked that this is equivalent to saying that every two columns are comparable. \begin{definition} A polyomino is called a \emph{moon polyomino} if it is convex and intersection-free; it is called a \emph{layer polyomino} if it is row-convex and intersection-free, but not necessarily column-convex. \end{definition} The term of ``moon polyomino" was first introduced by Jonsson \cite{Jon05} in the study of generalized triangulations and diagonal-free subsets of polyominoes. Jonsson also suggested a family of \emph{stalactite polyominoes}, which are column-convex, intersection-free, and the columns are aligned on the top. By definition, a moon polyomino is a layer polyomino whose rows are arranged in a unimodal order; while a stalactite polyomino, after a $90^o$ rotation, becomes a layer polyomino that is aligned on the left (or right). Figure \ref{polyomino} shows a moon polyomino and a general layer polyomino. We remark that all the results in this paper apply to polyominoes which are intersection-free and column-convex, but not necessarily row-convex. \begin{figure}[ht] \begin{center} \begin{tikzpicture}[scale=0.5] \draw[line width=0.7pt](2,0)--(4,0)--(4,6)--(2,6)--(2,0) (3,0)--(3,6) (1,1)--(5,1)--(5,4)--(0,4)--(0,2)--(5,2) (1,1)--(1,5)--(4,5) (0,3)--(5,3) (10,0)--(15,0)--(15,2)--(11,2)--(11,0) (10,0)--(10,1)--(15,1) (12,0)--(12,6)--(14,6)--(14,0) (13,0)--(13,6) (10,4)--(10,5)--(15,5)--(15,4)--(10,4) (11,5)--(11,3)--(14,3); \end{tikzpicture} \caption{A moon polyomino and a layer polyomino} \label{polyomino} \end{center} \end{figure} Given a layer polyomino $\mathcal {L}$, we assign $0$ or $1$ to each cell of $\mathcal {M}$ so that there is at most one $1$ in each column. Throughout this paper we will simply use the term \emph{filling} to denote such $01$-fillings. In a filling a cell is empty if it is assigned $0$, and is a $1$-cell otherwise. We label the rows from top to bottom, and the columns from left to right. The cell $(i,j)$ refers to the cell lying in the $i$-th row and the $j$-th column. A $2 \times 2$ submatrix $S$ of $\mathcal{L}$ is a set of four cells in $\mathcal{L}$ with the coordinates \begin{eqnarray} \label{matrix} S=\{(i_1, j_1), (i_1, j_2), (i_2, j_1), (i_2, j_2) \in \L: 1 \leq i_1 < i_2 , 1 \leq j_1 < j_2 \}. \end{eqnarray} Note that if $S$ is a submatrix of $\L$, then all the cells $\{ (i_1, k), (i_2, k): j_1 \leq k \leq j_2 \}$ are also in $\L$; if furthermore $\L$ is a moon polyomino, then the rectangle $\{ (l,k): i_1 \leq l \leq i_2, j_1 \leq k\leq j_2\}$ is contained in $\L$. A \emph{northeast (NE) chain} of length 2 in a filling $L$ consists of a $2 \times 2$ submatrix $S$ as in \eqref{matrix} where $(i_1, j_2)$ and $ (i_2, j_1)$ are $1$-cells. There is no constraint on the filling of the other two cells. Similarly, a \emph{southeast (SE) chain} of length 2 consists of a submatrix $S$ where $(i_1, j_1)$ and $ (i_2, j_2)$ are $1$-cells. In both cases we say that the submatrix $S$ is the \emph{support} of the chain. Unless otherwise specified, all the chains in this paper are of length 2. The numbers of NE-chains and SE-chains of $L$ are denoted by $\ne(L)$ and $\se(L)$, respectively. \begin{example} \emph{Figure \ref{filling} shows a $01$-filling of a layer polyomino, where $a,b,c,d,e,f$ are $1$-cells. This filling has four NE-chains $\{ad, bd, cd, ef\}$, and two SE-chains $\{ df, de\}$ .} \end{example} \begin{figure}[ht] \begin{center} \begin{tikzpicture}[scale=0.5] \draw[line width=0.7pt](0,0)--(7,0)--(7,1)--(0,1)--(0,0) (1,0)--(1,1) (2,0)--(2,2)--(7,2)--(7,1) (6,0)--(6,2) (4,0)--(4,6) (3,0)--(3,6)--(5,6)--(5,0) (5,3)--(2,3)--(2,5) (1,4)--(1,5) (0,4)--(0,5)--(7,5)--(7,4)--(0,4) (6,4)--(6,5); \node at (0.5,0.5){$a$}; \node at (2.5,3.5){$b$}; \node at (3.5,2.5){$c$}; \node at (4.5,4.5){$d$}; \node at (5.5,0.5){$e$}; \node at (6.5,1.5){$f$}; \end{tikzpicture} \caption{A filling of a layer polyomino} \label{filling} \end{center} \end{figure} Assume a polyomino $\mathcal{L}$ has $n$ rows and $m$ columns. Let $\s=(s_1,\ldots,s_n) \in \mathbb{N}^n$ and $\bve=(\ve_1, \dots, \ve_m) \in \{0,1\}^m$ with \[ \sum_{i=1}^n s_i = \sum_{j=1}^m \ve_j. \] We denote by $\mathbf{F}(\mathcal{L}, \mathbf{s}, \mathbf{e})$ the set of fillings $L$ of $\mathcal {L}$ such that the $i$-th row has exactly $s_i$ $1$'s, and the $j$-th column has exactly $\ve_j$ $1$'s, for $ 1 \leq i \leq n$ and $1\leq j\leq m$. For example, the filling in Figure \ref{filling} has $\s=(0,1,1,1,1,2)$ and $\bve=(1,0,1,1,1,1,1)$. Our main result is that the distribution of $(\ne, \se)$ is invariant under any permutation of rows of the underlying layer polyomino. \begin{theorem} \label{main} Let $\mathcal{L}$ be a layer polyomino with rows $R_1, ..., R_n$ from top to bottom. For a permutation $\sigma \in \mathfrak{S}_n$, let $\mathcal{L'}=\sigma(\mathcal{L})$ be the layer polyomino whose rows are $R_{\sigma(1)}, \dots, R_{\sigma(n)}$, and $\s' = \sigma(\s)=(s_{\sigma(1)}, \dots, s_{\sigma(n)})$. Then \[ \sum_{L\in \mathbf{F}(\mathcal{L},\s,\bve)} p^{\ne(L)} q^{\se(L)} = \sum_{L'\in \mathbf{F}(\mathcal{L}',\s',\bve)} p^{\ne(L')} q^{\se(L')}. \] \end{theorem} \pf It is sufficient to prove Theorem \ref{main} for adjacent transpositions, that is, when $\sigma=(k, k+1)$ where $k\in \{1, \dots, n-1\}$. Explicitly, let $\mathcal{L}'$ be the layer polyomino obtained from $\mathcal{L}$ by exchanging the rows $R_k$ and $R_{k+1}$. We construct a bijection \[ \phi : \mathbf{F}(\mathcal{L},\s,\bve) \rightarrow \mathbf{F}(\mathcal{L}',\s',\bve) \] such that $\ne(L)=\ne(\phi(L))$ and $\se(L)=\se(\phi(L))$ for every $L \in \mathbf{F}(\mathcal{L},\s,\bve)$. %Without loss of generality, assume that $|R_k| \geq |R_{k+1}|$. That is, the column-coordinates of cells in $R_k$ %cover those of cells in $R_{k+1}$. Let $\R$ be the largest rectangle with two rows that is contained in $R_k \cup R_{k+1}$. For a filling $L$ of $\mathcal{L}$, we define $L'=\phi(L)$ by the following steps. \begin{enumerate} \item Any $1$ of $L$ in $\L - (R_k \cup R_{k+1})$ stays in the same cell. \item Any $1$ of $L$ in the cell $(i, r)$ where $(i, r) \in (R_k \cup R_{k+1}) -\R$ moves to the position $(\sigma(i), r)$ in the polyomino $\mathcal{L}'$. \item For the $1$'s in the cells in $\R$, let $\R' \subseteq \R$ consist of the non-empty columns of $L \cap \R$. All the cells in $\R-\R'$ remain empty in $L'$. Assume $\R'$ contains $l$ columns. Identify fillings of $\R'$ with binary words $(w_1\cdots w_l) \in \{0,1\}^l$ by letting $w_i=0$ if the $1$-cell in the $i$-th column of $\R'$ is in row $R_k$; otherwise $w_i=1$. Let $w(L)=(w_1\cdots w_l)$ be the word corresponding to the filling $L \cap \R'$. Then the filling of $L'$ on $\R'$ is the one given by the word $(u_1\dots u_l)$, where $u_i= 1-w_{l+1-i}$. That is, $(u_1\dots u_l)$ is obtained from $w(L)$ by first reversing the word, then exchanging $0$'s with $1$'s. \end{enumerate} See Figure \ref{ex-phi} for an example of Step 3, where the rectangle $\R$ is indicated by black lines, and $\R'$ contains the unshaded cells in $\R$. We have $w(L)=(0,1,0,0)$, and $w(L')= (1,1,0,1)$. \begin{figure}[ht] \begin{center} \begin{tikzpicture}[scale=0.5] \path[fill=yellow] (3,1) rectangle (4,3); \draw[line width=0.7pt](0,0)--(8,0)--(8,1)--(0,1)--(0,0) (1,0)--(1,3)--(6,3)--(6,0) (1,3)--(0,3)--(0,2)--(8,2)--(8,3)--(6,3)--(6,5)--(2,5)--(2,4)--(6,4) (1,0)--(1,3) (2,0)--(2,3) (3,0)--(3,5) (4,0)--(4,5) (5,0)--(5,5) (7,0)--(7,1) (7,2)--(7,3); \draw[line width=1.4pt](1,1)--(1,3)--(6,3)--(6,1)--(1,1) ; \node at (1.5,2.5){$1$}; \node at (2.5,1.5){$1$}; \node at (4.5,2.5){$1$}; \node at (5.5,2.5){$1$}; \node at (7.5,2.5){$1$}; \draw [->] (10,3)--(13,3); \node at (11.5,3.5){$\phi$}; \path[fill=yellow](18,1) rectangle (19,3); \draw[line width=0.7pt](15,0)--(23,0)--(23,2)--(15,2)--(15,0) (16,0)--(16,3)--(21,3)--(21,0) (17,0)--(17,3) (18,0)--(18,5)--(21,5)--(21,3) (19,0)--(19,5) (20,0)--(20,5) (18,5)--(17,5)--(17,4)--(21,4) (22,0)--(22,2) (15,1)--(23,1); \node at (16.5,1.5){$1$}; \node at (17.5,1.5){$1$}; \node at (19.5,2.5){$1$}; \node at (20.5,1.5){$1$}; \node at (22.5,1.5){$1$}; \draw[line width=1.4pt](16,1)--(16,3)--(21,3)--(21,1)--(16,1); \end{tikzpicture} \end{center} \caption{Step 3 of $\phi$} \label{ex-phi} \end{figure} \noindent \textbf{Claim: $\ne(L)=\ne(L')$ and $\se(L)=\se(L')$}. \noindent \emph{Proof of the claim.} It is clear that $L' \in \mathbf{F}(\mathcal{L}',\s',\bve)$. We prove the first equation only. The second one can be treated similarly. %Let $\{(i_1, j_1),(i_2, j_2)\}$ be two $1$-cells in $L$ that form an northeast chain. %There are three cases. First note that any NE-chain formed by two $1$-cells outside $R_k \cup R_{k+1}$ is not changed. Next we consider the NE-chains with exactly one $1$-cell in $R_k \cup R_{k+1}$. Let $X=(a,b)$ be a cell of $\L$ outside $R_k \cup R_{k+1}$. An NE-chain formed by $X$ and $Y=(i,r) \in R_k \cup R_{k+1}-\R$ in $L$ is replaced by the NE-chain with $1$-cells $X$ and $(\sigma(i),r)$ in $L'$. For the NE-chains in $L$ formed by $X$ and $1$-cells in $\R$, let $C_b$ be the column of $X$. There are two possibilities. \begin{enumerate} \item $C_b \cap \R =\emptyset$. Without loss of generality, assume $|R_k| \geq |R_{k+1}|$. Then the number of NE-chains formed by $X$ and $1$-cells in $\R$ is $0$ unless $(k,b) \in L$, in which case the number equals the number of $1$s in $\R \cap R_k$. In $\L'$, row $R_k$ is moved to the row $k+1$, the cell $(k,b)$ is moved to $(k+1, b)$, and $L'$ has the same number of $1$'s in $\R \cap R_{k+1}$ as that of $L$ in $\R \cap R_k$. \item $C_b \cap \R \neq \emptyset$. Then the number of NE-chains formed by $X$ and $1$-cells in $\R$ equals the number of columns in \begin{eqnarray*} \left\{ \begin{array}{ll} \{ C_t \cap \R': (a, t) \text{ a cell in the underlying polyomino, } t < b\} & \text{ if $a < k$} , \\ \{ C_t \cap \R': (a,t) \text{ a cell in the underlying polyomino, } t > b \} & \text{ if $a > k+1$}. \end{array} \right. \end{eqnarray*} In both cases, this number remains same in $L$ and $L'$. \end{enumerate} Now we consider the rows $R_k \cup R_{k+1}$. Let $w(L)$ be the word defined as in Step 3. Then the number of NE-chains formed by two $1$-cells in $R_k \cup R_{k+1}$ is exactly the number of inversions of $w(L)$. But for any sequence $w_1w_2\dots w_n\in \{0,1\}^n$, \[ \mathrm{inv}(w_1w_2 \dots w_l) = \mathrm{inv}(u_1u_2\dots u_l) \qquad \text{ if } u_i=1-w_{l+1-i}. \] Hence there is an equal number of NE-chains of this type in $L$ and $L'$. Combining the above cases, we have $\ne(L)=\ne(L')$. %The equation $\se(L)=\se(L')$ can be proved similarly. \qed %*************************************************** \begin{corollary} \label{symmetry} The joint distribution of $(\ne(L), \se(L))$ is symmetric, that is, \[ \sum_{L\in \mathbf{F}(\mathcal{L}, \s, \bve)} p^{\ne(L)} q^{\se(L)} = \sum_{L\in \mathbf{F}(\mathcal{L},\s,\bve)} p^{\se(L)} q^{\ne(L)}. \] \end{corollary} \pf Let $\tilde \L$ be the polyomino obtained by reversing the rows of $\L$, that is, $\tilde \L=\sigma(\L)$ where $\sigma=n \cdots 21$. For any filling $L$ of $\L$, let $\tilde L$ be obtained from $L$ by keeping every $1$ in the same cell while re-arranging rows from $\L$ to $\tilde \L$. Then $\ne(\tilde L) = \se(L)$, $\se(\tilde L)=\ne(L)$ and the symmetry follows from Theorem \ref{main}. \qed We remark that Corollary \ref{symmetry} implies immediately the symmetry of the distribution of $(\ne, \se)$ over moon polyominoes, and that the bijection given here is different from Kasraoui's \cite{Kasra08}. In addition to the set $\mathbf{F}(\mathcal{L},\s,\bve)$, we can also consider $01$-fillings of a layer polyomino with arbitrary column sum, but every row has at most one $1$. Explicitly, let $\mathcal{L}$ be a layer polyomino with $n$ rows and $m$ columns. Given $\bve=(\ve_1, \dots, \ve_n) \in \{0,1\}^n$, $\s=(s_1,\ldots,s_m) \in \mathbb{N}^m$ with \[ \sum_{i=1}^n \ve_i = \sum_{j=1}^m s_j, \] let $\mathbf{F}^c(\mathcal{L},\bve,\s)$ be the set of fillings of $\mathcal {L}$ with the row-sum $\bve$ and column-sum $\s$. We have \begin{theorem} \label{main2} Let $\mathcal{L}$ be a layer polyomino with rows $R_1, ..., R_n$ from top to bottom. For a permutation $\sigma \in \mathfrak{S}_n$, let $\mathcal{L}'=\sigma(\mathcal{L})$ be the layer polyomino whose rows are $R_{\sigma(1)}, \dots, R_{\sigma(n)}$, and $\bve' = \sigma(\bve)=(\ve_{\sigma(1)}, \dots, \ve_{\sigma(n)})$. Then \[ \sum_{L\in \mathbf{F}^c(\mathcal{L},\bve,\s)} p^{\ne(L)} q^{\se(L)} = \sum_{L'\in \mathbf{F}^c(\mathcal{L}',\bve',\s)} p^{\ne(L')} q^{\se(L')}. \] \end{theorem} \pf Again we prove that the equation holds for any adjacent transposition $\sigma=(k,k+1)$ by constructing a bijection $\phi^c: \mathbf{F}^c(\mathcal{L},\bve,\s) \rightarrow \mathbf{F}^c(\mathcal{L}',\bve',\s)$ that preserves the statistic $(\ne, \se)$. The map $\phi^c$ is essentially the same as $\phi$, but it can be described in a much simpler way since for fillings in $\mathbf{F}^c(\mathcal{L},\bve,\s)$ every row has at most one $1$. Again let $\R$ be the largest rectangle with two rows that is contained in $R_k \cup R_{k+1}$. Let $L$ be a filling in $\mathcal{F}^c(\mathcal{L},\bve,\s)$. Then $L'=\phi^c(L)$ is the filling of $\mathbf{F}^c(\mathcal{L}',\bve',\s)$ obtained from $L$ by the following steps. \begin{description} \item[(1)] Any $1$ in a cell $(i,j)$ with $i \notin \{k, k+1\}$ stays in the same cell; \item[(2)] Any $1$ in a cell $(i,j) \in (R_k \cup R_{k+1})-\R$ moves to the cell $(\sigma(i), j)$. \item[(3)] If there is only one $1$-cell in $\R$, say $(i,j)$, then $(\sigma(i), j)$ becomes a $1$-cell in $L'$. \\ Otherwise (i.e., there are two $1$-cells in $\R$), the fillings $L$ and $L'$ agree on $\R$. \end{description} The proof that $\phi^c$ preserves $(\ne, \se)$ is similar to that of Theorem \ref{main}, and is omitted here. \qed \vspace{.5cm} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Mixed statistics in fillings of moon polyominoes} %% %% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% There is a stronger symmetry between the northeast and southeast chains of length 2 in fillings of moon polyominoes. In \cite{CWYY} Chen et al. introduced four families of mixed statistics with respect to a bipartition of rows or columns of the underlying moon polyomino, and proved that the symmetric joint distribution holds for each family of mixed statistics. In this section we explain such a symmetry for moon polyominoes from Theorems \ref{main} and \ref{main2}. %We will discuss the top-mixed statistics only. Other families of mixed-statistics can be treated in a similar way. Let $S$ be a subset of rows of a moon polyomino $\M$. An NE/SE chain is called a \emph{top $S$-NE/SE chain} if its top $1$-cell is in $S$; Similarly, it is a \emph{bottom $S$-NE/SE chain} if the lower $1$-cell of the chain is in $S$. Let $\bar{S}=\M \setminus S$ be the complement of $S$. Given a filling $M\in\mathbf{F}(\mathcal{M},\s, \bve)$, define the \emph{top-mixed statistic $\alpha(S;M)$} and the \emph{bottom-mixed statistic $\beta(S;M)$ with respect to $S$} as \begin{eqnarray*} &&\alpha(S;M)=\#\{ \text{top } S\mbox{-NE chains of}~M\}+\#\{\text{top } \bar{S} \mbox{-SE chains of}~M\}, \\[3pt] &&\beta(S; M)=\#\{ \text{bottom } S\mbox{-NE chains of}~M\}+\#\{\text{bottom } \bar{S} \mbox{-SE chains of}~M\}. \end{eqnarray*} Analogously one defines the left-mixed statistic $\gamma(T;M)$ and right-mixed statistic $\delta(T;M)$ with respect to a subset $T$ of columns. The main result of \cite{CWYY} can be stated as follows: Let $\lambda(A; M)$ be any of the four statistics $\alpha(S;M)$, $\beta(S; M)$, $\gamma(T; M)$, $\delta(T; M)$, then the joint distribution of the pair $(\lambda(A;M), \lambda(\bar A; M))$ over $\mathbf{F}(\M, \s, \bve)$ is symmetric and independent of the subsets $S, T$. In particular, the joint distribution is the same as the distribution of $(\ne(M), \se(M))$. We show that the stable distribution of mixed statistics can be derived from results in Section 2. We discuss the case of top-mixed statistics only. Other mixed-statistics can be treated similarly. In a moon polyomino $\M$, assume the rows in $S$ are $R_{i_1} , R_{i_2}, \dots, R_{i_s}$, and rows not in $S$ are $R_{j_1}, R_{j_2}, \dots, R_{j_t}$, where $i_1 < i_2 < \cdots < i_s$, $j_1 < j_2 < \dots < j_t$, and $s+t=n$. Given a filling $M$ of $\mathcal{M}$, let $L$ be the filling of a layer polyomino $\mathcal{L}(S)$ obtained from $M$ by rearranging the rows of $\mathcal{M}$ together with the filling in the order $R_{i_1}, R_{i_2},\dots, R_{i_s}, R_{j_t}, \dots, R_{j_2}, R_{j_1}$. See Figure \ref{mixed-figure} for an illustration, where the rows in $S$ are shaded in the moon polyomino $\M$, and the right-hand side labels indicate how the rows are rearranged. \begin{figure}[ht] \begin{center} \begin{tikzpicture}[line width=0.7pt,scale=0.5] \path[fill=yellow] (4,6) rectangle (7,7); \path[fill=yellow] (1,3) rectangle (8,4); \path[fill=yellow] (3,0) rectangle (7,1); \draw (1,2)--(1,4)--(8,4)--(8,2)--(1,2)(1,3)--(8,3) (2,2)--(2,5)--(7,5) (3,0)--(3,6)--(7,6)--(7,0)--(3,0) (3,1)--(7,1) (4,0)--(4,7)--(7,7)--(7,6) (5,0)--(5,7) (6,0)--(6,7); \node at (0,0.5){$R_7$}; \node at (0,1.5){$R_6$}; \node at (0,2.5){$R_5$}; \node at (0,3.5){$R_4$}; \node at (0,4.5){$R_3$}; \node at (0,5.5){$R_2$}; \node at (0,6.5){$R_1$}; \node at (1.5,3.5 ) {$1$}; \node at (3.5, 5.5) {$1$}; \node at (4.5 , 0.5) {$1$}; \node at (5.5 ,2.5 ) {$1$}; \node at (6.5 ,6.5 ) {$1$}; \node at (7.5 , 3.5) {$1$}; \draw [->] (10,3)--(12,3); \draw (14,6)--(14,5)--(21,5)--(21,6)--(14,6) (14,2)--(14,3)--(21,3)--(21,2)--(14,2) (16,6)--(16,0)--(20,0)--(20,7)--(17,7)--(17,0) (18,0)--(18,7) (19,0)--(19,7) (16,4)--(20,4) (20,1)--(15,1)--(15,3) (15,5)--(15,6) ; \node at (22,0.5){$R_2$}; \node at (22,1.5){$R_3$}; \node at (22,2.5){$R_5$}; \node at (22,3.5){$R_6$}; \node at (22,4.5){$R_7$}; \node at (22,5.5){$R_4$}; \node at (22,6.5){$R_1$}; \node at (14.5,5.5 ) {$1$}; \node at (16.5, 0.5) {$1$}; \node at (17.5 , 4.5) {$1$}; \node at (18.5 ,2.5 ) {$1$}; \node at (19.5 ,6.5 ) {$1$}; \node at (20.5 , 5.5) {$1$}; \end{tikzpicture} \caption{Top-mixed statistics in $\M$ and NE-chains in $\L(S)$} \label{mixed-figure} \end{center} \end{figure} \begin{proposition} \label{MtoL} $\alpha(S;M) = \ne(L)$ and $\alpha(\bar{S};M) = \se(L)$. \end{proposition} \pf We compare the chains in the fillings $M$ and $L$. For any chain that is counted by $\alpha(S;M)$, it is either a top $S$-NE chain or a top $\bar{S}$-SE chain of $M$. Assume the two $1$-cells in the chain are $A$ and $B$, where $A$ is the one on the top. \begin{enumerate} \item If it is a top $S$-NE chain of $M$, then $A \in S$. Note that for any row $R_i \in S$ and a row $R_k$ with $k >i$ in $\M$, $R_i$ stays above $R_k$ in $\mathcal{L}(S)$. Hence $A$ and $B$ still form an NE-chain in $L$. \item If it is a top $\bar{S}$-SE chain of $M$, then $A \in \mathcal{M} \setminus S$. For any row $R_j \in \mathcal{M} \setminus S$ and a row $R_k$ with $k > j$ in $\M$, $R_j$ is moved below $R_k$ in $\mathcal{L}(S)$. Hence any top $\bar{S}$-SE chain of $M$ becomes an NE-chain of $L$. \end{enumerate} Similarly we see that top $\bar{S}$-NE chains and top $S$-SE chains of $M$ become SE-chains of $L$. This proves the claim. \qed Proposition \ref{MtoL} implies that the distribution of $(\alpha(S; M), \alpha(\bar{S};M))$ is the same as the distribution of $(\ne, \se)$ over fillings of $\L(S)$, where $\L(S)$ has the same set of rows as $\M$. By Theorem \ref{main} and Corollary \ref{symmetry}, this distribution is symmetric and independent of $S$. % Section 4: short summary on how to get the generating function %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Formula for the symmetric generating function} %% %% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Let $F_{\L}(p,q)$ be the joint distribution of $(\ne, \se)$ over the set $\mathbf{F}(\mathcal{L},\s,\bve)$, that is, \[ F_{\L}(p,q)= \sum_{L\in \mathbf{F}(\mathcal{L},\s,\bve)} p^{\ne(L)} q^{\se(L)}. \] We discuss briefly how to get the explicit formula of $F_{\L}(p,q)$ for a layer polyomino $\L$. There are two approaches. The first one is to transform the layer polyomino $\L$ to a moon polyomino by a permutation of rows, then apply Theorem 2.2 of Kasraoui's \cite{Kasra08} which expressed the distribution of $(\ne, \se)$ for fillings of moon polyominoes as a product of $(p,q)$-Gaussian coefficients. Alternatively, using Theorems \ref{main} and \ref{main2}, we can transform the layer polyomino $\L$ to a Ferrers diagram (partition shape) by first rearranging the rows from longest to shortest, then rearranging the columns from large to small, see Figure \ref{to-Ferrers} for an illustration. This reduces the problem to computing the distribution of $(\ne, \se)$ over $01$-fillings of a Ferrers shape, which, by a bijection of de Mier \cite{deMier}, is equivalent to the enumeration of crossings and nestings of length 2 over linked partitions. The latter has been studied and explicit formula was given in \cite[Theorem 3.5]{CWY}. This in turn provides a new proof for Kasraoui's formula for $01$-fillings of moon polyominoes. %In this section we explain how to use the above theorems to get the symmetric joint generating function of $(\ne, \se)$ %over $\mathcal{F}(\mathcal{L},\s,\bve)$. %We would transform the underlying layer polyomino to a Ferrers shape with the same row lengths and column lengths, %and then show that the problem is equivalent to a known result for which the explicit formula is given in \cite{CWY}. % %Given a layer polyomino $\mathcal{L}$, let $\mathcal{L}_1$ be the polyomino obtained from $\mathcal{L}$ by %rearranging the rows from longest to shortest. Assume $\mathcal{L}_1=\alpha(\mathcal{L})$ %here $\alpha$ is a permutation of rows. By Theorem \ref{main}, %\begin{eqnarray} \label{step1} %\sum_{L\in \mathbf{F}(\mathcal{L},\s,\bve)} p^{\ne(L)} q^{\se(L)} %= \sum_{L_1\in \mathbf{F}(\mathcal{L}_1, \alpha(\s),\bve)} p^{\ne(L_1)} q^{\se(L_1)}. %\end{eqnarray} %Next, we rearrange the columns of $\mathcal{L}_1$ from large to small to form $\mathcal{L}_2$. Let %$\beta$ be the column permutation from $\mathcal{L}_1$ to $\mathcal{L}_2$. Then by Theorem \ref{main2} %(applying it to the $90^\circ$ rotation of $\mathcal{L}_1$) we have %\begin{eqnarray} \label{step2} %\sum_{L_1\in \mathbf{F}(\mathcal{L}_1, \alpha(\s),\bve)} p^{\ne(L_1)} q^{\se(L_1)} %= \sum_{L_2\in \mathbf{F}(\mathcal{L}_2, \alpha(\s),\beta(\bve))} p^{\ne(L_2)} q^{\se(L_2)}. %\end{eqnarray} %Hence it is enough to compute the distribution of $(\ne, \se)$ over $\mathcal{L}_2$. %Note that $\mathcal{L}_2$ is a Ferrers diagram (partition shape) with the same sets of row lengths and column %lengths as $\mathcal{L}$. %Figure \ref{to-Ferrers} shows the transformation from $\mathcal{L} \rightarrow \mathcal{L}_1 \rightarrow %\mathcal{L}_2$. \begin{figure}[ht] \begin{center} \begin{tikzpicture}[scale=0.4] \draw[line width=0.7pt](0,0)--(8,0)--(8,1)--(0,1)--(0,0) (1,0)--(1,3)--(6,3)--(6,0) (1,3)--(0,3)--(0,2)--(8,2)--(8,3)--(6,3)--(6,5)--(2,5)--(2,4)--(6,4) (1,0)--(1,3) (2,0)--(2,3) (3,0)--(3,5) (4,0)--(4,5) (5,0)--(5,5) (7,0)--(7,1) (7,2)--(7,3); \draw [->](10,3)--(12,3) ; \draw[line width=0.7pt](14,5)--(14,3)--(22,3)--(22,5)--(14,5) (14,4)--(22,4) (15,5)--(15,2)--(20,2)--(20,5) (21,5)--(21,3) (16,5)--(16,1)--(20,1) (20,2)--(20,0)--(17,0)--(17,5) (18,0)--(18,5) (19,0)--(19,5); \draw[->](24,3)--(26,3); \draw [line width=0.7pt](28,5)--(36,5)--(36,3)--(28,3)--(28,5) (28,4)--(36,4) (28,4)--(28,0)-- (31,0)--(31,5) (29,0)--(29,5) (30,0)--(30,5) (28,1)--(32,1)--(32,5) (28,2)--(33,2)--(33,5) (35,3)--(35,5) (34,3)--(34,5); \end{tikzpicture} \caption{Transformation from layer polyomino to a Ferrers diagram. } \label{to-Ferrers} \end{center} \end{figure} %It is first observed by de Mier \cite{deMier} that fillings of %Ferrers shapes with prescribed row and column sums are in one-to-one %correspondence with loop-less graphs on $[n]$ with given %\emph{left-right degree sequence}. In a graph $G$ on $[n]$, the left %(resp. right) degree of a vertex $i$ is the number of edges that %join $i$ to a vertex $j$ with $j < i$ (resp. $j >i$). The %left-right degree sequence of $G$ is the sequence $(l_i, r_i)_{1 %\leq i \leq n}$, where $l_i$ is the left-degree of $i$ and $r_i$ is %the right degree of $i$. In particular, if in each pair $(l_i, %r_i)$, either $l_i$ or $r_i$ is 0, the graph is called a %\emph{left-right graph}. A bijection is described by de Mier in %\cite[Section 3]{deMier} between the fillings of Ferrers shapes to left-right graphs, %under which the NE/SE-chains in a filling become nestings %and crossings formed by two edges in a graph. %Using de Mier's bijection, fillings of the Ferrers diagram $\L_2$ with given row-sum %$\alpha(\s) \in \mathbb{N}^n$ and column-sum $\beta(\bve) \in \{0,1\}^m$ %become graphs on the vertex set $[n+m]$ where for each vertex, the left-right %degree is either $(0, \alpha(\s)_i)$ or $(\beta(\bve)_j, 0)$. Note that %the left degree of any vertex is either 0 or 1. %Such graphs have been studied in \cite{CWY} under the name %\emph{linked partitions}. The bi-variate generating function of crossings and nestings %in linked partitions has been given in \cite[Theorem 3.5]{CWY}. %Translating to fillings of $\mathcal{L}_2$, we obtain a product formula in terms of $(p,q)$-Gaussian %coefficients, which covers Kasraoui's result for moon polyominoes \cite{Kasra08}. %To describe the formula, recall that the $p,q$-integer $[r]_{p,q}$ is given by %\[ %[r]_{p,q} = \frac{p^r-q^r}{p-q} = p^{r-1} + p^{r-2}q + \cdots +pq^{r-2} +q^{r-1}, %\] %and the $p,q$-factorial $[r]_{p,q}!$ is defined as $[r]_{p,q}!= %\prod_{i=1}^r [i]_{p,q}$. %The $p,q$-Gaussian coefficient is %\[ %\genfrac[]{0pt}{}{n}{s}_{p,q} % = \frac{[n]_{p,q} ! }{ [s]_{p,q}! [n-s]_{p,q}! }. %\] %Then %\begin{theorem} %\begin{eqnarray} \label{formula} %F_{\mathcal{L}}(p,q)= % F_{\mathcal{L}_2}(p,q) % \sum_{G\in LP_{n+m}(S(\mathcal{L}_2),T(\mathcal{L}_2))} p^{\cros_2(G)}q^{\nest_2(G)} %= \prod_{i=1}^n \genfrac[]{0pt}{}{h(i)}{s_i}_{p,q}, %\end{eqnarray} %where $s_i$ are entries of the row-sum vector $\s$, and %$h(i)$'s are integers determined by the row lengths of $\mathcal{L}$ and the vectors $\s, \bve$. %\end{theorem} %The explicit values of $h(i)$'s and the complete description of the bijection between fillings of Ferrers %diagrams and %linked partitions are given in \cite[Section 4.2]{WangYan}, and hence not repeated here. We remark that in \cite{WangYan} the authors provided another way to transform the enumeration of $(\ne, \se)$ over fillings of moon polyominoes to those of a Ferrers diagram. The idea is to associate with a moon polyomino $\M$ a charge function $C: \M \rightarrow \{\pm 1\}$ which induces a sign on the NE/SE-chains of length 2, and then prove that the numbers of positive and negative chains have a stable distribution which is independent of the charge function. The connection between charge functions and layer polyominoes is currently under investigation. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{A variation of NE/SE chains} % % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% In this section we consider a variation of the NE/SE chains of length 2 in fillings of layer polyominoes. Let $\L$ be a layer polyomino and $L$ a 01-filling of $\L$. For an NE/SE chain with the support \[ S=\{ (i_1, j_1), (i_1, j_2), (i_2, j_1), (i_2, j_2) \in \L: 1 \leq i_1 < i_2, 1 \leq j_1 < j_2 \}, \] we say that it is a \emph{strong} chain if the whole rectangle $\{ (l, k): i_1 \leq l \leq i_2, j_1 \leq k \leq j_2\}$ is also contained in $\L$. For example, in the filling of Figure \ref{filling}, there are three strong NE-chains $\{bd, cd, ef\}$, and no strong SE-chains. On the other hand, for moon polyominoes any NE/SE chain is strong. Denote by $\neB(L)$ and $\seB(L)$ the numbers of strong NE-chains and strong SE-chains of $L$ respectively. It is easy to see that for a general layer polyomino, the distribution of $(\neB, \seB)$ is not preserved under permutations of rows, and not necessarily equal to the distribution of $(\ne,\se)$. Nevertheless, we prove that the distribution of $(\neB, \seB)$ is still symmetric over fillings in $\mathbf{F}(\L, \s, \bve)$. \begin{theorem} \label{strong} The statistic $(\neB, \seB)$ has a symmetric joint distribution over the set $\mathbf{F}(\L, \s, \bve)$, where $\s=(s_1, \dots, s_n)\in \mathbb{N}^n$ and $\bve=(\epsilon_1, \dots, \epsilon_m) \in \{0,1\}^m$. That is, \begin{eqnarray} \label{square-ne} \sum_{L\in \mathbf{F}(\mathcal{L}, \s, \bve)} p^{\neB(L)} q^{\seB(L)} = \sum_{L\in \mathbf{F}(\mathcal{L},\s,\bve)} p^{\seB(L)} q^{\neB(L)}. \end{eqnarray} \end{theorem} \pf We prove by induction on $n$, the number of rows of $\L$. For $n=1, 2$ the claim is true since every layer polyomino of no more than two rows is a moon polyomino, and hence $(\neB, \seB)$ coincides with $(\ne, \se)$. Assume the claim is true for all layer polyominoes with less than $n$ rows, and with arbitrary row sum in $\mathbb{N}$ and column sum in $\{0, 1\}$. Let $\L$ be a layer polyomino with $n$ rows and $m$ columns, $\s=(s_1, \dots, s_n)\in \mathbb{N}^n$, and $\bve=(\epsilon_1, \dots, \epsilon_m) \in \{0,1\}^m$. We shall prove the theorem for $\L$. First we need some notations. Let $R_i$ be a row of $\L$ with maximal number of cells. If there are more than one such rows, take the one with maximal index. Among $R_{i-1}$ and $R_{i+1}$, pick the one with more cells. Without loss of generality, we assume that it is $R_{i-1}$. Let $\R$ be the maximal rectangle of two rows that is contained in $R_{i-1} \cup R_i$, %that is, if $R_{i-1}= \{ (i-1, t): a \leq t \leq b\}$, then $\R =\{(i-1, t), (i,t): a \leq t \leq b\}$. and let $\mathcal{T}=R_i -\R$. For $L \in \mathbf{F}(\mathcal{L}, \s, \bve)$, let \[ \Gamma(L) =\{ L' \in \mathbf{F}(\mathcal{L}, \s, \bve): \text{ $L'$ and $L$ agree on $\mathcal{T}$} \}. \] We shall prove the following equation for arbitrary $L$, which then implies \eqref{square-ne}: \begin{eqnarray} \label{gamma} \sum_{L'\in \Gamma(L)} p^{\neB(L')} q^{\seB(L')} = \sum_{L'\in \Gamma(L)} p^{\seB(L')} q^{\neB(L')}. \end{eqnarray} Assume in all fillings of $\Gamma(L)$, there are $k$ $1$-cells in $\mathcal{T}$ in columns $t_1, t_2, \dots, t_k$. These $1$-cells do not appear in any strong NE/SE chains. Hence removing $\mathcal{T}$ from $\L$ does not change $(\neB, \seB)$ for any filling. Let $\L_1=\L-\mathcal{T}$, $\s_1=(s_1, \dots, s_{i-1}, s_i-k, s_{i+1}, \dots, s_n)$ and $\bve_1$ be obtained from $\bve$ by changing $\epsilon_{t_1}, \dots, \epsilon_{t_k}$ from $1$ to $0$. Then the map \begin{eqnarray*} \pi: \Gamma(L) &\rightarrow & \mathbf{F}(\L_1, \s_1, \bve_1) \\ L' & \rightarrow & L' \text{ restricted to } \L_1 \end{eqnarray*} is a bijection that preserves the statistic $(\neB, \seB)$. Define $\L_2$ with $n-1$ rows $(R_1, \dots, R_{i-1}, R_{i+1}, \dots, R_n)$, $\s_2=(s_1, \dots, s_{i-2}, s_{i-1} +s_i-k, s_{i+1}, \dots, s_n)$ and $\bve_2=\bve_1$. Let $\rho: \mathbf{F}(\L_1, \s_1, \bve_1) \rightarrow \mathbf{F}(\L_2, \s_2, \bve_2)$ by defined as follows. For $L_1 \in \mathbf{F}(\L_1, \s_1, \bve_1)$ perform the following operations. \begin{enumerate} \item Move all $1$s from row $i$ into row $i-1$ preserving their column, \item Delete row $i$, \item Shift rows $i+1,i+2, \dots, n$ up one, so row $R_i$ becomes $R_{j-1}$ for $j=i+1, i+2, \dots, n$. \end{enumerate} The map $\rho$ is surjective, but not injective. In fact for any $L_2 \in \mathbf{F}(\L_2, \s_2, \bve_2)$, there are $\binom{s_{i-1}+s_i-k}{s_{i-1}}$ fillings in $\mathbf{F}(\L_1, \s_1, \bve_1)$ that map to it. This is obtained by splitting the $s_{i-1}+s_i-k$ $1$-cells in the $(i-1)$st row of $\L_2$ into two subsets of sizes $s_{i-1}$ and $s_i-k$. Thus \[ \sum_{L_1 \in \mathbf{F}(\L_1,\s_1, \bve_1: \rho(L_1)=L_2 } p^{\neB(L_1)} q^{\seB(L_1)} = p^{\neB(L_2)}q^{\seB(L_2)} \genfrac[]{0pt}{}{s_{i-1}+s_i-k}{s_{i-1}}_{p,q} , \] where \[ \genfrac[]{0pt}{}{n}{s}_{p,q} = \frac{[n]_{p,q} ! }{ [s]_{p,q}! [n-s]_{p,q}! }. \] is the $(p,q)$-Gaussian coefficient with the $(p,q)$-integers $[n]_{p,q} = p^{n-1}+p^{n-2}q+ \cdots + pq^{n-2} +q^{n-1}$ and $(p,q)$-factorial $[n]_{p,q}! = \prod_{i=1}^n [i]_{p,q}$. It follows that \begin{eqnarray*} \sum_{L' \in \Gamma(L)} p^{\neB(L')} q^{\seB(L')} & =& \sum_{L_1 \in \mathbf{F}(\L_1, \s_1, \bve_1)} p^{\neB(L)} q^{\seB(L)} \\ & =& \genfrac[]{0pt}{}{s_{i-1}+s_i-k}{s_{i-1}}_{p,q} \cdot \sum_{L_2 \in \mathbf{F}(\L_2, \s_2, \bve_2)} p^{\neB(L)} q^{\seB(L)}. \end{eqnarray*} Equation \eqref{gamma} follows from the inductive hypothesis on $\mathbf{F}(\L_2, \s_2, \bve_2)$. \qed % ***************************************% \section{Concluding remarks} % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% We conclude this paper with some comments and counterexamples to a few seemingly natural generalizations of Theorem \ref{main} and \ref{main2}. %\subsection{Natural generalizations} First, it was observed by Kasraoui \cite{Kasra08} that with no restrictions on the row sum or the column sum, the joint distribution of the statistics $(\ne, \se)$ is not symmetric over \emph{arbitrary} 01-fillings of moon polyominoes, and hence layer polyominoes. A similar problem can be considered for $\mathbb{N}$-fillings, i.e., each cell $(i,j)$ of the polyomino is assigned a non-negative integer $n_{i,j}$. For a submatrix $S$ as in \eqref{matrix} in the polyomino, it contributes $n_{i_2,j_1} n_{i_1,j_2}$ NE-chains, and $n_{i_1,j_1}n_{i_2,j_2}$ SE-chains. It is natural to ask whether the joint distribution of $(\ne, \se)$ is symmetric over arbitrary $\mathbb{N}$-fillings with a fixed total sum of entries. The answer is negative, as shown by the following counterexample. \begin{example} Consider the Ferrers diagram of shape $(3,3,2)$ and $\mathbb{N}$-fillings with sum of entries equal to 5. We compute the number of fillings with $\ne=6$ or $\se=6$. It is easy to check that to get six NE-chains or six SE-chains, the set of entries in the fillings must be $(3,2)$, $(2, 2,1)$, or $(2,1,1,1)$. With the entries $(3, 2)$, there are ten fillings with $\ne=6$ and ten with $\se=6$; With the entries $(2,2,1)$, there are six fillings with $\ne=6$ and six with $\se=6$; while with the entries $(2,1,1,1)$, there is one filling with $\se=6$ (see Figure \ref{n-filling}), but none with $\ne=6$. \end{example} \begin{figure}[ht] \begin{center} \begin{tikzpicture}[line width=0.7pt,scale=0.5] \draw (0,0)--(2,0)--(2,3)--(0,3)--(0,0) (0,1)--(3,1)--(3,3)--(2,3) (0,2)--(3,2)(1,0)--(1,3); \node at (0.5,2.5){$2$}; \node at (1.5,1.5){$1$}; \node at (2.5,1.5){$1$}; \node at (1.5,0.5){$1$}; %\draw (5,0)--(7,0)--(7,3)--(5,3)--(5,0) (5,1)--(8,1)--(8,3)--(7,3) (5,2)--(8,2)(6,0)--(6,3); %\node at (5.5,2.5){$2$}; \node at (6.5,1.5){$1$}; \node at (6.5,0.5) {$1$}; %\draw (10,0)--(12,0)--(12,3)--(10,3)--(10,0) (10,1)--(13,1)--(13,3)--(12,3) (10,2)--(13,2)(11,0)--(11,3); %\node at (10.5,2.5) {$2$}; \node at (11.5, 0.5){$1$}; \node at (12.5,1.5){$1$}; %\draw (15,0)--(17,0)--(17,3)--(15,3)--(15,0) (15,1)--(18,1)--(18,3)--(17,3) (15,2)--(18,2)(16,0)--(16,3); %\node at (15.5,1.5) {$1$}; \node at (16.5,1.5){$1$}; \node at (17.5,2.5){$2$}; %\draw (20,0)--(22,0)--(22,3)--(20,3)--(20,0) (20,1)--(23,1)--(23,3)--(22,3) (20,2)--(23,2)(21,0)--(21,3); %\node at (20.5,0.5){$1$}; \node at (20.5, 1.5){$1$}; \node at (21.5,2.5){$2$}; \end{tikzpicture} \caption{$\mathbb{N}$-fillings with entries $(2,1,1,1)$ and six SE-chains} \label{n-filling} \end{center} \end{figure} Notice that the difference between a moon polyomino and a layer polyomino is that the latter is only required to be row-convex, but not necessary column-convex. Another natural question is whether we can get rid of the convexity completely? That is, for an arbitrary intersection-free polyomino, whether the pair $(\ne, \se)$ is symmetric or preserved under permutation of rows. Example \ref{ex3} gives a negative answer. \begin{example} \label{ex3} The left polyomino $\L$ in Figure \ref{not-convex} is intersection-free but not row-convex nor column-convex. (The cell at the 3rd row and 2nd column does not belong to $\L$. ) Consider 01-filings $L$ such that every row has exactly one $1$, and the column sum is $(2,1,1)$. There are six possible 01-fillings. We obtain that $\sum_{L} p^{\ne(L)} q^{\se(L)} =p^3+3p^2q+2q^3$. On the other hand, the right polyomino $\L'$ is obtained from the left one by exchanging the middle two rows, for which we have $\sum_{L'} p^{\ne(L')} q^{\se(L')} = p^3+2p^2q+2pq^2+q^3$. \begin{figure}[ht] \begin{center} \begin{tikzpicture}[scale=0.5] \path [fill=gray] (1,2) rectangle (2,3); \draw[line width=0.7pt](0,1)--(0,5)--(1,5)--(1,1) (2,1)--(2,5)--(3,5)--(3,1) (0,4)--(3,4) (0,3)--(3,3) (0,2)--(3,2)(0,1)--(3,1); \node at (1.5, 0){$\L$}; \draw[line width=0.7pt] (7,1)--(7,5)--(8,5)--(8,1)(7,4)--(8,4) (9,4)--(10,4) (7,1)--(10,1)--(10,5)--(9,5)--(9,1) (7,2)--(10,2) (7,3)--(10,3); \node at (8.5, 0){$\L'$}; \end{tikzpicture} \caption{Non-convex polyomino} \label{not-convex} \end{center} \end{figure} \end{example} Kasraoui also provided examples \cite[Sec.6]{Kasra08} showing that the distribution of $(\ne, \se)$ may not be symmetric if the polyomino is convex but not intersection-free. %\subsection{A variation of NE/SE chains} %\subsection{Maximal NE/SE chains} Finally we consider the length of maximal NE-chains in a filling. A $k$-NE chain in a filling $L$ on $\L$ is a $k \times k$ submatrix consisting of cells $\{ (i_s, j_t) \in \L : 1 \leq s,t \leq k, i_1 < i_2 < \cdots < i_k, \text{ and } j_1 < j_2 < \cdots < j_k\}$ such that the cells $(i_r, j_r)$ are filled with $1$ for $r=1, \dots, k$. Let $\mne(L)$ be the maximal $k$ such that $L$ contains a $k$-NE chain. The statistic $\mne(L)$ has been studied for fillings of Ferrers diagrams, stack polyominoes, and moon polyominoes, for example, see \cite{CDDSY, deMier06, deMier, Jon05, JW07, Krattenthaler, Rubey}. In particular, \cite{Rubey} showed that in $01$-fillings of a moon polyomino with given row sum, (but no constraints on the column sum), the distribution of $\mne$ depends only on the set of columns, but not how the columns are arranged. The proofs of \cite{Rubey} imply that in $01$-fillings of a moon polyomino where every row and every column has at most one $1$, the distribution of $\mne$ depends only on the set of rows (or columns). This is not true for layer polyominoes. We found two polyominoes, shown in Example \ref{max-ne}, that differ by exchanging the position of two adjacent rows, yet the distributions of the length of the longest NE-chains are different. \begin{example} \label{max-ne} In the following two layer polyominoes, consider the 01-fillings where every row and every column has exactly one $1$. We obtained the following generating function for the statistic $\mne$: For the left polyomino $\L_1$, $\sum_{L_1} p^{\mne(L_1)} = p + 37p^2 + 31p^3 + 3p^4$, while for the right polyomino $\L_2$, $\sum_{L_2} p^{\mne(L_2)} = p + 36 p^2 +32 p^3+3 p^4.$ \begin{center} \begin{tikzpicture}[line width=0.7pt,scale=0.5] \draw (5,2)--(0,2)--(0,0)--(5,0)--(5,5)--(0,5)--(0,4)--(5,4) (1,0)--(1,5) (2,0)--(2,5) (3,0)--(3,5) (4,0)--(4,5) (0,1)--(5,1) (1,3)--(5,3) ; \draw (10,0)--(15,0)--(15,5)--(11,5)--(11,0) (10,0)--(10,2)--(15,2) (15,3)--(10,3)--(10,4)--(15,4) (10,1)--(15,1) (12,0)--(12,5) (13,0)--(13,5) (14,0)--(14,5) ; \node at (2.5,-1) {$\L_1$}; \node at (12.5, -1) {$\L_2$}; \end{tikzpicture} \end{center} Furthermore, for $\L_1$, $\sum_{L_1} p^{\mathrm{maxse}(L_1)} = p + 36 p^2 +32 p^3+3 p^4$ where $\mathrm{maxse}(L)$ is the maximal $k$ such that $L$ contains a $k$-SE chain. Hence in general layer polyominoes $\mne$ and $\mathrm{maxse}$ do not have the same distribution. \end{example} \section*{Acknowledgments} This publication was made possible by NPRP grant \#[5-101-1-025] from the Qatar National Research Fund (a member of Qatar Foundation). The statements made herein are solely the responsibility of the authors. The authors would like to thank an anonymous referee for carefully reading the manuscript and for giving many valuable comments and suggestions which substantially helped improving the quality of the paper. In particular, the variation of NE/SE chains studied in Section 5 was suggested by the referee. % \bibliographystyle{plain} % \bibliography{myBibFile} % If you use BibTeX to create a bibliography % then copy and past the contents of your .bbl file into your .tex file \begin{thebibliography}{10} \bibitem{CDDSY} W. Y. C. Chen, E. Y. P. Deng, R. R. X. Du, R. P. Stanley and C. H. Yan, Crossings and nestings of matchings and partitions, Trans. Amer. Math. Soc. 359 (2007) 1555--1575. \bibitem{CWYY} W.Y.C Chen, A. Y. Z. Wang, C.H.Yan and A. F. Y. Zhao. Mixed statistics on $01$-fillings of moon polyominoes, SIAM J. Discrete Math. 24 (2010) no. 4, 1272--1290. \bibitem{CWY} W. Y. C. Chen, S. Y. Wu and C. H. Yan, Linked partitions and linked cycles, European J. Combin. 29 (2008) 1408--1426. \bibitem{CPYY} W. Y. C. Chen, S. Poznanovi\'{c}, C. H. Yan and A. L. B. Yang, Major index for $01$-fillings of moon polyominoes, J. Combin. Theory, Ser. A. Vol. 117 (2010), no.8, 1058--1081. \bibitem{Corteel07} S. Corteel. Crossings and alignments of permutations. Adv. Appl. Math. 38(2007), 149--163. \bibitem{deMier06} A. de Mier, On the symmetry of the distribution of crossings and nestings in graphs, Electron. J. Combin. 13 (2006), N21. \bibitem{deMier} A. de Mier, $k$-noncrossing and $k$-nonnesting graphs and fillings of Ferrers diagrams, Combinatorica 27 (2007) 699--720. \bibitem{deSC} M. de Sainte-Catherine, Couplages et Pfaffiens en Combinatoire, Physique et Informatique, Ph.D. Thesis, University of Bordeaux I, Talence, France, 1983. \bibitem{Jon05} J. Jonsson, Generalized triangulations and diagonal-free subsets of stack polyominoes, J. Combin. Theory Ser. A 112 (2005), 117--142. \bibitem{JW07} J. Jonsson and V. Welker. \newblock A spherical initial ideal for {P}faffians. \newblock {\em Illinois J. Math.} 51(4):1397--1407, 2007. \bibitem{Kasra08} A. Kasraoui, Ascents and descents in 01-fillings of moon polyominoes, European J. Combin. 31 (2010), no.1, 87--105 \bibitem{Kasra06} A. Kasraoui and J. Zeng, Distributions of crossings, nestings and alignments of two edges in matchings and partitions, Electron. J. Combin. 13 (2006) R33. \bibitem{klazar} M. Klazar, On identities concerning the numbers of crossings and nestings of two edges in matchings, SIAM J. Discrete Math. 20 (2006) 960--976. \bibitem{Krattenthaler} C. Krattenthaler, Growth diagrams, and increasing and decreasing chains in fillings of Ferrers shapes, Adv. in Appl. Math. 37 (2006), 404--431. \bibitem{PY09} S. Poznanovi\'{c}, C. H. Yan, Crossings and nestings of two edges in set partitions, SIAM J. Discrete Math. 23 (2009), no.2, 787--804. \bibitem{Rubey} M. Rubey, Increasing and decreasing sequences in fillings of moon polyominoes, Adv. in Appl. Math. 47 (2011), 57--87. \bibitem{WangYan} A.Y.Z. Wang and C.H. Yan, Positive and negative chains in charged moon polyominoes. Adv. in Appl. Math. 51 (2013), 467--482. \end{thebibliography} \end{document}