% 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}
\specs{P51}{20(3)}{2013}

\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{\bf Chains of Length 2 in\\ Fillings of Layer  Polyominoes }
\author{Mitch Phillipson \qquad  Catherine H. Yan \qquad 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 16, 2013}{Sep 26, 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}  

