%% if you are submitting an initial manuscript then you should have submission as an option here
%% if you are submitting a revised manuscript then you should have revision as an option here
%% otherwise options taken by the article class will be accepted
\documentclass[finalversion]{FPSAC2020}
\articlenumber{26}%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

%% note that the class file already loads {amsmath, amsthm, amssymb}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Our additions: 
\usepackage{tikz,color,enumerate}
\usetikzlibrary{decorations.pathmorphing}
%\usepackage[backref]{hyperref}
 
 \theoremstyle{plain}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{conjecture}[theorem]{Conjecture}  

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}   
\newtheorem{remark}[theorem]{Remark}  

\newcommand\G{\mathcal{GD}}
\newcommand\DP{\mathcal D}
\newcommand\B{\mathcal B}
\renewcommand\P{\mathcal P}
\newcommand\UB{\mathcal U}
\newcommand\M{\mathcal M}
\newcommand\GM{\mathcal{GM}}
\newcommand\WQ{\mathcal{W}}
\def\bij{\phi}
\def\bijw{\omega}
\DeclareMathOperator\ds{ds}
\DeclareMathOperator\da{da}
\DeclareMathOperator\dsh{ds\ulcorner}
\renewcommand\sp{\operatorname{sp}}
\DeclareMathOperator\hm{hm}
\newcommand\Cat{C}
\newcommand\ul{\underline}
\newcommand\ol{\overline}
\renewcommand\SS{\mathcal S}
\newcommand\sv{\operatorname{sv}}
\newcommand\ret{\operatorname{ret}}
\newcommand{\card}[1]{{\lvert #1 \rvert}} 	% cardinality
\newcommand\pho{\operatorname{ph}_1}
\newcommand\NE{\textnormal{NE}}
\newcommand\NW{\textnormal{NW}}
\newcommand\SE{\textnormal{SE}}
\newcommand\SW{\textnormal{SW}}

\def\U{-- ++(1,1) circle(1.2pt)}
\def\D{-- ++(1,-1) circle(1.2pt)}
\def\H{-- ++(1,0) circle(1.2pt)}
\def\drawHtwo{\draw[very thick,decorate,decoration={snake,amplitude=.3mm,segment length=1mm}] (last)-- ++(1,0) coordinate(last);}
\def\u{-- ++(.2,.2) circle(0.2pt)}
\def\d{-- ++(.2,-.2) circle(0.2pt)}
\def\h{-- ++(.2,0) circle(0.2pt)}
\def\N{-- ++(0,1) circle(1.2pt)}
\def\S{-- ++(0,-1) circle(1.2pt)}
\def\W{-- ++(-1,0)}

\newcommand{\todo}[1]{\mbox{}{\sf\color{red}[#1]}\marginpar{\color{red}\Large$*$}}
\newcommand{\remove}[1]{}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% END

%% define your title in the usual way
\title[Measuring symmetry in lattice paths and partitions]{Measuring symmetry in lattice paths and partitions}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author{Sergi Elizalde\thanks{\href{mailto:sergi.elizalde@dartmouth.edu}{sergi.elizalde@dartmouth.edu}.}\addressmark{1}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Department of Mathematics, Dartmouth College, Hanover, NH, USA}

%% put the date of submission here
\received{\today}

%% leave this blank until submitting a revised version
%\revised{}

%% put your English abstract here, or comment this out if you don't have one yet
%% please don't use custom commands in your abstract / resume, as these will be displayed online
%% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year)
\abstract{We introduce the notion of {\em degree of symmetry} for lattice paths and related combinatorial objects. The degree of symmetry measures how symmetric an object is, usually ranging from zero (completely asymmetric) to its size (completely symmetric).
We study the behavior of this statistic on Dyck paths and grand Dyck paths, where the symmetry is given by reflection along a vertical line through their midpoint; partitions, where the  symmetry is given by conjugation; and certain compositions interpreted as bargraphs.
We find expressions for the generating functions for these objects with respect to their degree of symmetry, and their semilength or semiperimeter. The generating functions are algebraic in most cases, with the notable exception of Dyck paths, for which we apply techniques from walks in the plane to find a functional equation for the generating function, and conjecture that it is D-finite but not algebraic.}

%% put your French abstract here, or comment this out if you don't have one
%\resume{\lipsum[2]}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{symmetry, lattice path, Dyck path, partition, composition, D-finite}

%% you can include your bibliography however you want, but using an external .bib file is STRONGLY RECOMMENDED and will make the editor's life much easier
%% regardless of how you do it, please use numerical citations, ie. [xx, yy] in the text

%% this sample uses biblatex, which (among other things) takes care of URLs in a more flexible way than bibtex
%% but you can use bibtex if you want

\addbibresource{fpsac.bib}
%% note the \printbibliography command at the end of the file which goes with these biblatex commands

 

\begin{document}

\maketitle
%% note that you DO NOT have to put your abstract here -- it is generated by \maketitle and the \abstract and \resume commands above



\section{Introduction}

For combinatorial objects with a standard reflection operation, it is natural to study the subset of those that are {\em symmetric}, that is, invariant under such reflection. Examples of symmetric combinatorial objects include symmetric Dyck paths~\cite{deng_riordan_2015} and grand Dyck paths, self-conjugate partitions~\cite[Proposition 1.8.4]{stanley_enumerative_1997}, palindromic compositions~\cite{hoggatt_palindromic_1975}, and symmetric binary trees, all of which have been considered.

In this abstract we refine the concept of symmetric objects by introducing a type of combinatorial statistic that we call the {\em degree of symmetry}, which measures how close the object is to being symmetric. The notion of degree of symmetry, suggested by
Emeric Deutsch (personal communication, March 2018) appears to be new. In some instances, it is related to other statistics studied in the literature, such as the number of {\em centered tunnels} in Dyck paths (introduced in~\cite{elizalde_simple_2003}) or the number of transpositions in permutations.

Let us start by defining the degree of symmetry of certain lattice paths. 
Let $\G_n$ be the set of all lattice paths in the plane with up-steps $U=(1,1)$ and down-steps $D=(1,-1)$ from $(0,0)$ to $(2n,0)$.
These are called {\em grand Dyck paths} (also referred to as {\em free Dyck paths} or {\em bridges} in the literature), and $n$ is called the {\em semilength}. Let $\DP_n$ be the subset of those that do not go below the $x$-axis. These are called {\em Dyck paths}. We use the notation $[n]=\{1,2,\dots,n\}$.

Given a path $P\in\G_n$, we view its steps as segments in the plane, which we denote by $\bar{p}_1,\bar{p}_2,\dots,\bar{p}_{2n}$ from left to right. For example, $\bar{p}_1$ has endpoints $(0,0)$ and $(1,\pm 1)$, and $\bar{p}_{2n}$ has endpoints $(2n-1,\pm1)$ and $(2n,0)$. For $i\in[n]$, we say that $P$ is symmetric in position $i$ 
(or that $\bar{p}_i$ is a {\em symmetric step}) if $\bar{p}_i$ and $\bar{p}_{2n+1-i}$ are mirror images of each other with respect to the reflection along the vertical line $x=n$. 
We define the {\em degree of symmetry} of $P$, denoted by $\ds(P)$, as the number of $i\in[n]$ such that $P$ is symmetric in position $i$.
See \cref{fig:symD} for an example.

\begin{figure}[htb]
\centering
%\begin{tikzpicture}[scale=0.55]
 %    \draw[dotted](-1,0)--(15,0);
  %   \draw[dotted](0,-3)--(0,2);
   %  \draw[dashed,thick](7,-3)--(7,2);
    % \draw[thick,blue](0,0) circle(1.2pt) \D\D\U\U\U\D\D\U\U\D\U\D\D\U;
    % \draw[red,ultra thick](0,0)--(1,-1);
    % \draw[red,ultra thick](4,0)--(5,1)--(7,-1)--(9,1)--(10,0);  
    % \draw[red,ultra thick](13,-1)--(14,0);     
    %\end{tikzpicture}\medskip
    %
   \begin{tikzpicture}[scale=0.55] 
     \draw[dotted](-1,0)--(23,0);
     \draw[dotted](0,-3)--(0,2);
     \draw[dashed,thick](11,-3)--(11,2);
     \draw[thick,blue](0,0) circle(1.2pt) \U\D\D\U\D\U\U\D\U\D\U  \D\D\D\U\U\D\U\U\D\D\U;
     \draw[red,ultra thick](4,0)--(5,-1)--(6,0) (10,0)--(11,1)--(12,0) (16,0)--(17,-1)--(18,0);
    \end{tikzpicture}
   \caption{A grand Dyck path with degree of symmetry 3. The symmetric steps and their mirror images are highlighted in red.}\label{fig:symD}
\end{figure}


In \cref{sec:GD} we find an expression for the generating function of grand Dyck paths with respect to semilength and degree of symmetry. 
\cref{sec:Dyck} deals with the analogous problem for Dyck paths, which is significantly harder. Using bijections for walks in the quarter plane, we derive a functional equation for the corresponding generating function.
\cref{sec:partitions} focuses on the degree of symmetry of partitions and certain unimodal compositions, giving generating functions with respect to a few possible definitions of size and degree of symmetry. The proofs of most results in this extended abstract are omitted or only sketched.

\section{Grand Dyck paths}\label{sec:GD}

For grand Dyck paths we obtain a surprisingly simple generating function. 

\begin{theorem} \label{thm:sym_G} The generating function for grand Dyck paths with respect to their degree of symmetry is
$$\sum_{n\ge0} \sum_{P\in\G_n} s^{\ds(P)} z^n = \frac{1}{2(1-s)z + \sqrt{1-4z}}.$$
\end{theorem}

The proof of this result relies on a bijection to another kind of lattice paths. 
A {\em bicolored grand Motzkin path} starts at the origin, ends on the $x$-axis, 
and can have steps $U=(1,1)$, $D=(1,-1)$, and horizontal steps $(1,0)$ of two kinds (or colors), denoted by $H_1$ and $H_2$. 
If such a path does not go below the $x$-axis, it is called a {\em bicolored Motzkin path}.
Denote by $\GM^2$ the set of bicolored grand Motzkin paths, and by $\M^2$ the set of bicolored Motzkin paths. We often identify a path with its sequence of steps.
For a path $M\in\GM^2$, let $u(M)$ denote its number of $U$ steps (which also equals its number $d(M)$ of $D$ steps), and define $h_1(M)$ and $h_2(M)$ analogously.
Additionally, let $h_1^0(M)$ denote the number of $H_1$ steps of $M$ on the $x$-axis, and define $h_2^0(M)$ similarly.

Define the {\em length} of a path $M$ to be its total number of steps, which we denote by $|M|$. Let $\M^2_n\subset\M^2$ and $\GM^2_n\subset\GM^2$ denote the subsets consisting of paths of length $n$ in each case.
Let $G(x,y,s_1,s_2)=\sum_{M\in\GM^2} x^{d(M)+h_1(M)} y^{u(M)+h_2(M)} s_1^{h_1^0(M)} s_2^{h_2^0(M)}$.

\begin{lemma}\label{lem:2Motzkin}\label{lem:grand2Motzkin}
We have
$$G(x,y,s_1,s_2)=\frac{1}{(1-s_1)x+(1-s_2)y+\sqrt{(1-x-y)^2-4xy}}.$$
\end{lemma}

To prove \cref{thm:sym_G}, given $P\in\G_n$, construct two paths as follows. Let $P_L$ denote the left half of $P$, and let $P_R$ be the path obtained by reflecting the right half of $P$ along the vertical line $x=n$. Note that $P_L$ and $P_R$ are paths with steps $U$ and $D$ from $(0,0)$ to some common endpoint on the line $x=n$. Denote the $i$th step of $P_L$ by $\bar{\ell}_i$ when viewed as a segment in the plane, and let $\ell_i\in\{U,D\}$ be the direction of this step. Define $\bar{r}_i$ and $r_i$ similarly for the path $P_R$. 

Next we describe a bijection $\bij$ from $\G_n$ to $\GM^2_n$; see \cref{fig:pairs2Motzkin} for an example.
For $P\in\G_n$ with the above notation, let $\bij(P)\in\GM^2_n$ be the path whose $i$th step is equal to 
$$\begin{cases} U & \text{ if } \ell_i=U \text{ and }r_i=D,\\
D & \text{ if } \ell_i=D \text{ and }r_i=U,\\
H_1 & \text{ if } \ell_i=r_i=D,\\
H_2 & \text{ if } \ell_i=r_i=U.
\end{cases}$$


\begin{figure}[htb]
\centering
    \begin{tikzpicture}[scale=0.5]
     \draw[dotted](-1,0)--(23,0);
     \draw[dotted](0,-2)--(0,2);
     \draw[dashed,thick](11,-2)--(11,2);
    \draw[olive,very thick,dashed](0,0) circle (1.2pt)  \D\U\U\D\D\U\D\D\U\U\U;
    \draw[blue,very thick](0,0) circle (1.2pt) \U\D\D\U\D\U\U\D\U\D\U coordinate(last);
    \draw[blue] (last) \D\D\D\U\U\D\U\U\D\D\U;
    \draw[olive] (.5,-1.5) node {$P_R$};
    \draw[blue] (.5,1.5) node {$P_L$};
    \draw (5.5,-2.5) node  {$\downarrow\bij$};
    \begin{scope}[shift={(0,-5)}]
      \draw[dotted](-1,0)--(12,0);
     \draw[dotted](0,-2)--(0,2);
    \draw[very thick](0,0) circle (1.2pt)  \U\D\D\U\H coordinate(last);
     \drawHtwo
    \draw[very thick](last) circle (1.2pt) \U\H coordinate(last);
    \drawHtwo 
    \draw[very thick](last) circle (1.2pt) \D coordinate(last);
    \drawHtwo
    \draw[very thick](last) circle (1.2pt);
    \draw (.5,1.5) node {$M$};
    \end{scope}
    \end{tikzpicture}
   \caption{The bijection $\bij:\G_n\to\GM^2_n$. The path $P\in\G_n$ is drawn in blue, and its reflected right half $P_R$ is drawn in olive color with dahes. The steps $H_2$ in $\bij(P)$ are drawn with wavy lines.}\label{fig:pairs2Motzkin}
\end{figure}


\begin{lemma}\label{lem:bij_properties}
The map $\bij:\G_n\to\GM^2_n$ is a bijection with the property that, if $M=\bij(P)$, then $\ds(P)=h_1^0(M)+h_2^0(M)$.
\end{lemma}

\begin{proof}[Proof of \cref{thm:sym_G}]
Combining \cref{lem:bij_properties,lem:grand2Motzkin},
\[
\sum_{n\ge0} \sum_{P\in\G_n} s^{\ds(P)} z^n  = \sum_{M\in\GM^2} s^{h_1^0(M)+h_2^0(M)} z^{|M|} = G(z,z,s,s)=\frac{1}{2(1-s)z+\sqrt{1-4z}}.
\]
\end{proof}


When $P_L$ lies strictly above $P_R$ (except at their common endpoints), the pair $(P_L,P_R)$ is called a {\em parallelogram polyomino} \cite{polya_number_1969}, and its semiperimeter is defined to be the length of either of the two paths. It is well known that parallelogram polyominos of semiperimeter $n$ are counted by the Catalan number $C_{n-1}$. This also follows follows from our bijection and \cref{lem:2Motzkin}.

An alternative measure of the symmetry of a grand Dyck path is its {\em number of symmetric vertices}, that is, vertices in the first half of the path that are mirror images of vertices in the second half. We do not consider the midpoint itself as a symmetric vertex. Denote by $\sv(P)$ the number of symmetric vertices of the path $P\in\G_n$, and let 
\[
 \Cat(z)=\sum_{n\ge0} C_n z^n = \frac{1-\sqrt{1-4z}}{2z}. 
 \]

\begin{theorem} \label{thm:sv_G} The generating function for grand Dyck paths with respect to their number of symmetric vertices is
\[
\sum_{n\ge0} \sum_{P\in\G_n} v^{\sv(P)} z^n = \frac{1}{1-2vzC(z)}=\frac{1}{1-v + v\sqrt{1-4z}}.
\]
\end{theorem}


For $P\in\G_n$, denote by $\ret(P)$ the number of returns of $P$ to the $x$-axis.
It is easy to see that the generating function in \cref{thm:sv_G} also enumerates grand Dyck paths with respect to this statistic; see~\cite[A108747]{sloane_-line_nodate}. The following result also has a bijective proof.

\begin{corollary}
The statistics $\sv$ and $\ret$ are equidistributed on $\G_n$; that is, for all $n,k\ge0$,
\[
|\{P\in\G_n:\sv(P)=k\}|=|\{P\in\G_n:\ret(P)=k\}|.
\]
\end{corollary}


\section{Dyck paths}\label{sec:Dyck}

Let
$$D(s,z)=\sum_{n\ge0} \sum_{P\in\DP_{n}} s^{\ds(P)} z^n$$
denote the generating function for Dyck paths with respect to their degree of symmetry. % and their semilength.
In contrast to the simplicity of the generating function in \cref{thm:sym_G} for grand Dyck paths, the generating function $D(s,z)$ is unwieldy. 
We will first rephrase the problem in terms of walks in the plane, and then apply some transformations on the walks that will allow us to obtain a functional equation for a refinement of $D(s,z)$.

Let $\WQ^1_n$ denote the set of walks in the first quadrant $\{(x,y):x,y\ge0\}$ starting at the origin, ending on the diagonal $y=x$, and having $n$ steps in $\{\NE,\NW,\SE,\SW\}$, where we use the notation $\NE=(1,1)$, $\NW=(-1,1)$, $\SE=(1,-1)$, $\SW=(-1,-1)$.

We start by describing a standard bijection $\bijw:\DP_n\to\WQ^1_n$, which, in a similar form, has been used in~\cite{elizalde_bijections_2015,gouyou-beauchamps_chemins_1986,lladser_walks_2010}. 
Given $P\in\DP_n$, first define two paths as in \cref{sec:GD}: $P_L$ is the left half of $P$, and $P_R$ is the path obtained by reflecting the right half of $P$ along the vertical line $x=n$. Denote the $i$th step of $P_L,P_R$ by $\ell_i,r_i\in\{U,D\}$, respectively.
Now let $\bijw(P)\in\WQ^1_n$ be the walk whose $i$th step is equal to 
$$\begin{cases} 
\NE & \text{ if } \ell_i=r_i=U,\\
\NW & \text{ if } \ell_i=U \text{ and }r_i=D,\\
\SE & \text{ if } \ell_i=D \text{ and }r_i=U,\\
\SW & \text{ if } \ell_i=r_i=D.\\
\end{cases}$$

Under this bijection, symmetric steps of $P$, which correspond to common steps of $P_L$ and $P_R$, become steps of $\bijw(P)$ lying entirely on the diagonal $y=x$.
%Thus, $D(s,z)$ is the generating function for walks in $WQ^1_n$ where 
%steps on the diagonal have weight $s$ if we define the weight of a 
An equation for the generating function of walks with a variable keeping track of the number of such steps would be troublesome, since it would contain a term corresponding to walks ending on the diagonal $y=x$, which would involve taking diagonals of generating functions.

To circumvent this problem, we modify the walks so that the steps that we need to keep track of lie on the boundary of the region.
Folding walks in $\WQ^1_n$ along the diagonal $y=x$ (reflecting the steps above the diagonal onto steps below it), we obtain walks in the first octant $\{(x,y):x\ge y\ge0\}$. In order not to lose information while folding, we allow the resulting walks in the octant to use two colors for steps $\SE$ leaving the diagonal. These colors keep track of whether the portion of the walk between the colored step and the next return to the diagonal was above or below the diagonal on the original quadrant walk. We obtain a bijection between $\WQ^1_n$ and the set $\WQ^2_n$ of walks in the first octant starting at the origin, ending on the diagonal $y=x$, having $n$ steps in $\{\NE,\NW,\SE,\SW\}$, and where steps $\SE$ leaving the diagonal $y=x$ can have two colors. 


Next we apply the linear transformation $(x,y)\mapsto(y,\frac{x-y}{2})$ from the first octant to the first quadrant. This transformation gives a bijection between $\WQ^2_n$ and the set $\WQ^3_n$ of walks in the first quadrant starting at the origin, ending on the $x$-axis, having $n$ steps in $\{E,W,\NW,\SE\}$ (denoting $E=(1,0)$ and $W=(-1,0)$), and where steps $\NW$ leaving the $x$-axis can have 2 colors. Under this bijection, steps of walks in $\WQ^2_n$ lying on the diagonal become steps of walks in $\WQ^3_n$ lying on the $x$-axis. \cref{tab:WQ} summarizes the above sequence of bijections from $\DP_n$ to $\WQ^3_n$. 
It follows that $D(s,z)$ is the generating function for walks in $\WQ^3_n$ where $z$ marks the length and $s$ marks the number of steps on the $x$-axis. 


\begin{table}[htb]
\resizebox{\columnwidth}{!}{
\begin{tabular}{r||c|c|c|c}
 & $\DP_n$ &  $\WQ^1_n$ & $\WQ^2_n$ & $\WQ^3_n$ \\ \hline\hline
walks in & first octant & first quadrant & first octant & first quadrant\\ \hline
allowed steps & $U=\NE,D=\SE$ & $\NE,\NW,\SE,\SW$ & $\NE,\NW,\SE,\SW$ & $E,W,\NW,\SE$\\ \hline
length & $2n$ & $n$ & $n$ & $n$ \\ \hline
ending on & $x$-axis & diagonal & diagonal & $x$-axis \\ \hline
2 colors for & & & $\SE$ leaving diagonal & $\NW$ leaving $x$-axis \\ \hline
$\ds$ counts & symmetric steps & steps on diagonal & steps on diagonal & steps on $x$-axis
\end{tabular}
}
\caption{A summary of the bijections between Dyck paths and walks.}
\label{tab:WQ}
\end{table}


To enumerate walks in $\WQ^3_n$, we consider more general walks where any endpoint is allowed.
Let $W(x,y,s,z)$ be the generating function where the coefficient of $x^i y^j s^k z^n$ is the number of walks in the first quadrant with $n$ steps in $\{E,W,\NW,\SE\}$, starting at the origin, ending at $(i,j)$, having $k$ steps entirely on the $x$-axis, and where steps $\NW$ leaving the $x$-axis can have 2 colors. 
By considering the different possibilities for the last step of the walk, we obtain the following functional equation for $W(x,y):=W(x,y,s,z)$.
\begin{align*}
W(x,y)=& \ 1+z\left(x+\frac{1}{x}+\frac{x}{y}+\frac{y}{x}\right)W(x,y) - z \left(\frac{1}{x}+\frac{y}{x}\right)W(0,y) - z\, \frac{x}{y} W(x,0) & \\
& + z\, \frac{y}{x} \left(W(x,0)-W(0,0)\right) + z\, (s-1) \left(x+\frac{1}{x}\right)W(x,0) - z\, (s-1) \frac{1}{x} W(0,0).
\end{align*}


\begin{theorem}\label{thm:symDyck}
The generating function for Dyck paths with respect to the statistic $\ds$ is\linebreak $D(s,z)=W(1,0,s,z)$, where $W(x,y):=W(x,y,s,z)$ satisfies the functional equation
\begin{multline*} \left(xy-z(y+x^2)(1+y)\right)W(x,y)=xy-zy(1+y)W(0,y)\\
+z\left(y^2-x^2+(s-1)y(x^2+1)\right)W(x,0)-zy(y+s-1)W(0,0).
\end{multline*}
\end{theorem}

Even though we have been unable to solve this functional equation using the kernel method, the equation suggests that the generating function $D(s,z)=W(1,0,s,z)$ is D-finite. Computations by Alin Bostan (personal communication, July 2019) using \cref{thm:symDyck} have led to the following conjecture.
%s obtained a fifth order linear differential equation with polynomial coefficients with maximum degree 27 in $z$, which is conjecturally satisfied by $D(s,z)$. 

\begin{conjecture}
The generating function $D(s,z)$ is $D$-finite in $z$ but not algebraic. Specifically, it satisfies
a linear differential equation of order 5 with polynomial coefficients of maximum degree~$27$.
\end{conjecture}

The coefficients of $s^kz^n$ for small values of $k$ and $n$ in the generating functions from \cref{thm:sym_G,thm:symDyck} are given in \cref{tab1}.


\begin{table}[h]
\centering
\begin{tabular}{c@{\qquad}c}
$\card{\{P \in \G_n: \ds(P) = k\}}$ & $\card{\{P \in \DP_n: \ds(P) = k\}}$ \smallskip \\
\begin{tabular}{c||r|r|r|r|r|r|r|r|} 
% \hline
 $n \setminus k$ & 0& 1 & 2 & 3 & 4 & 5 & 6\\ 
\hline\hline
1& 0&2 & & & & &   \\
\hline
2&2 &0 &4 & & & & \\
\hline
3&4 &8 &0 & 8 & & & \\
\hline
4&14 &16 &24 & 0 & 16 & & \\
\hline
5& 44 & 64 & 48 & 64 & 0 & 32 & \\
\hline
6& 148 & 208 & 216 & 128 & 160 & 0 & 64 \\
\hline
\end{tabular}
&
\begin{tabular}{c||r|r|r|r|r|r|r|} 
% \hline
 $n \setminus k$ & 1 & 2 & 3 & 4 & 5 & 6 \\ 
\hline\hline
1& 1& & & & &    \\
\hline
2&0 &2 & & & & \\
\hline
3& 2 &0 &3 & & & \\
\hline
4&2 &6 &0 & 6  & & \\
\hline
5& 8 & 8 & 16 & 0 & 10 &  \\
\hline
6& 16 & 32 & 24 & 40 & 0 & 20  \\
\hline
%7& 52 & 84 & 108 & 60 & 90 & 0 & 35 \\
%\hline
\end{tabular}
\end{tabular}
\caption{The number of grand Dyck paths (left, see \cref{thm:sym_G}) and Dyck paths (right, see \cref{thm:symDyck}) of semilength $n\le 6$ with a given degree of symmetry.}
\label{tab1}
\end{table}

Note the surprising contrast between the simple algebraic generating function for grand Dyck paths in \cref{thm:sym_G} and the complicated one for Dyck paths in \cref{thm:symDyck}. 

\remove{To understand this difference, consider an easier path statistic: the height of the midpoint of a path $P$, denoted by $\hm(P)$. Note that the first half of $P$ ends at $(n,\hm(P))$.
The number of paths with steps $U$ and $D$ from $(0,0)$ to $(n,b)$ not going below the $x$-axis is the ballot number 
$$B_{n,b}=\binom{n}{\frac{n-b}{2}}-\binom{n}{\frac{n-b}{2}-1}=\frac{2b+2}{n+b+2}\binom{n}{\frac{n-b}{2}}$$
if $n-b$ is even and $0\le b\le n$, and $B_{n,b}=0$ otherwise.
The corresponding generating function is 
\begin{equation}\label{eq:Bob}\sum_{n,b\ge0} B_{n,b} y^bz^n=\frac{2}{1-2yz+\sqrt{1-4z^2}}=\frac{C(z^2)}{1-yzC(z^2)}.
\end{equation} 

Then, the generating function of Dyck paths with respect to the height of their midpoint is
 $$H(y,z)=\sum_{n\ge0}\sum_{P\in\DP_n}y^{\hm(P)}z^n=\sum_{n,b\ge0} B_{n,b}^2 y^{b}z^n.$$
However, this generating function is not algebraic, since the coefficients of $H(0,z)=\sum_{m\ge0}C_m^2 z^{2m}$ grow asymptotically as $C_m^2\sim \frac{16^m}{m^3\pi}$, which is not a possible asymptotic behavior for coefficients of an algebraic generating function (see~\cite{jungen_sur_1931}). 
%The coefficients of $H(y,z)$ do not appear in~\cite{sloane_-line_nodate}. 
Using \eqref{eq:Bob}, we can express $H(y,z)$ as a diagonal of an algebraic generating function, as 
$$H(y,z)=\text{diag}_{z_1,z_2}^z \frac{C(z_1^2)C(z_2^2)}{1-yz_1z_2C(z_1^2)C(z_2^2)},$$
which implies by~\cite{lipshitz_diagonal_1988} that $H(y,z)$ is D-finite .

On the other hand, the enumeration of grand Dyck paths with respect to the height of their midpoint is straightforward.

\begin{proposition}\label{prop:hm_G} The generating function for grand Dyck paths with respect to the height of their midpoint is
%$$\sum_{n\ge0}\sum_{P\in\G_n}y^{\hm(P)}z^n=\frac{y}{\sqrt{y^2-2v(1+y^2)z+(1-y^2)^2z^2}}.$$
\begin{equation}\label{eq:hm_G}
\sum_{n\ge0}\sum_{P\in\G_n}y^{\hm(P)}z^n=\frac{1}{\sqrt{(1-yz-\frac{z}{y})^2-4z^2}}=\sum_{n\ge0}\sum_{k=0}^n \binom{n}{k}^2 y^{n-2k}z^n.
\end{equation}
\end{proposition}

The algebraicity of this generating function can be explained because it is the diagonal of a rational generating function; see \cite[Theorem 6.3.3]{stanley_enumerative_1999}. Indeed, counting left halves of grand Dyck paths according to their ending height, we obtain 
$$\sum_{n\ge0}\sum_{k=0}^n \binom{n}{k} y^{n-2k}z^n=\frac{1}{1-(y+\frac{1}{y})z}.$$
}

\remove{
Finally, we remark that the method used to prove \cref{thm:sym_G} and \cref{prop:hm_G} also gives a common generalization of the two generating functions, namely
$$\sum_{n\ge0}\sum_{P\in\G_n}s^{\ds(P)}y^{\hm(P)}z^n=\frac{1}{(1-s)(y+\frac{1}{y})z+\sqrt{(1-yz-\frac{z}{y})^2-4z^2}}.$$
}


\section{Partitions}\label{sec:partitions}

Let $\P$ denote the set of integer partitions, that is, sequences $\lambda=(\lambda_1,\lambda_2,\dots,\lambda_k)$ where $k\ge0$ and $\lambda_1\ge\lambda_2\ge\dots\ge\lambda_k\ge1$.  We draw the Young diagram of $\lambda$ in English notation, by arranging boxes (unit squares) into $k$ left-justified rows, where the $i$th row from the top has $\lambda_i$ boxes for each $i$.
%The {\em area} of $\lambda$ is $\lambda_1+\lambda_2+\dots+\lambda_k$, and its {\em semiperimeter} is $\lambda_1+k$.
The {\em conjugate} of $\lambda$, denoted by $\lambda'$, is the partition defined by $\lambda'_i=|\{j:\lambda_j\ge i\}|$ for $1\le i\le \lambda_1$. The Young diagram of $\lambda'$ is obtained by transposing the Young diagram of $\lambda$.


Each one of the following subsections considers a different measure of the symmetry of a partition. The first one views partitions inside a square and relates them to grand Dyck paths. The second one is perhaps the most natural measure of symmetry: the number of parts that equal the corresponding part in the conjugate partition. The third measure involves a decomposition of partitions into diagonal hooks.


\subsection{Partitions inside a square}

Let $\P^\Box_n\subset\P$ be the set of partitions $\lambda=(\lambda_1,\lambda_2,\dots,\lambda_k)$ with $k\le n$ and $\lambda_1\le n$. These can be thought of as partitions whose Young diagram fits inside an $n\times n$ square. 
For such $\lambda\in \P^\Box_n$, let $\tilde\lambda=(\lambda_1,\lambda_2,\dots,\lambda_k,0,\dots,0)$ denote the sequence of length $n$ obtained by appending $n-k$ zeros to $\lambda$. 
Let $\tilde\lambda'$ be the sequence of length $n$ obtained by conjugating $\tilde\lambda$, that is, $\tilde\lambda'_i=|\{j:\tilde\lambda_j\ge i\}|$ for $1\le i\le n$. 

Viewing $\lambda$ as a partition inside a square, one can define the following measure of symmetry, where the zeros in $\tilde\lambda$ are allowed to contribute. Let
$$\ds^\Box_n(\lambda)=|\{i\in [n]:\tilde\lambda_i=\tilde\lambda'_i\}|.$$ For example, if $\lambda=(5,4,4,2,1,1)$,
then $\ds^\Box_6(\lambda)=2$ but $\ds^\Box_7(\lambda)=3$, since in the second case, $\tilde\lambda=(5,4,4,2,1,1,0)$ and $\tilde\lambda'=(6,4,3,3,1,0,0)$ coincide in positions $2$, $5$, and $7$. 


To relate partitions inside a square and grand Dyck paths, we define a straightforward bijection $\partial_n:\P^\Box_n\to\G_n$ by
$\partial_n(\lambda)=D^{\tilde\lambda_n}UD^{\tilde\lambda_{n-1}-\tilde\lambda_n}UD^{\tilde\lambda_{n-2}-\tilde\lambda_{n-1}}U\dots D^{\tilde\lambda_{1}-\tilde\lambda_{2}}UD^{n-\tilde\lambda_{1}}$.

This bijection can be visualized by placing the Young diagram of $\lambda$ inside an $n\times n$ square (aligned with the top and left edges), reading the south-east boundary of the diagram from the south-west corner of the square to the north-east corner, and then translating north steps to $U$ steps and east steps to $D$ steps. 
The following is a consequence of \cref{thm:sym_G}.

\begin{corollary} \label{cor:sym_P} 
The generating function for partitions whose Young diagram fits inside a square with respect to the side length of the square and the statistic $\ds^\Box_n$ is
$$\sum_{n\ge0} \sum_{\lambda\in\P^\Box_n} s^{\ds^\Box_n(\lambda)} z^n = \frac{1}{2(1-s)z + \sqrt{1-4z}}.$$
\end{corollary}



\subsection{Symmetry by self-conjugate parts}

Another notion of symmetry, which we call simply the degree of symmetry of $\lambda\in\P$, is defined as $$\ds(\lambda)=|\{i:\lambda_i=\lambda'_i\}|,$$ 
that is, the number of parts of $\lambda$ that equal the corresponding parts of its conjugate.
For example, if $\lambda=(5,4,4,2,1,1)$, then $\ds(\lambda)=2$ because $\lambda_2=\lambda'_2=4$ and $\lambda_5=\lambda'_5=1$, but $\lambda_i\ne\lambda'_i$ for every other $i$ for which these quantities are defined.

The following is a consequence of \cref{cor:sym_P} and the fact that $\ds^\Box_m(\lambda)=\ds(\lambda)$ when $m=\max\{\lambda_1,\lambda'_1\}$.

\begin{corollary}
The generating function for partitions with respect to the side length of the smallest square containing their Young diagram and their degree of symmetry is
$$\sum_{\lambda\in\P} s^{\ds(\lambda)} z^{\max\{\lambda_1,\lambda'_1\}} = \frac{1-sz}{2(1-s)z + \sqrt{1-4z}}.$$
\end{corollary}

For $\lambda\in\P$, let $\sp(\lambda)=\lambda_1+\lambda'_1$ denote the semiperimeter of its Young diagram.

\begin{theorem}\label{thm:Psp}
The generating function for partitions with respect to their semiperimeter and their degree of symmetry is
\begin{equation}\label{eq:Psp}\sum_{\lambda\in\P} s^{\ds(\lambda)} z^{\sp(\lambda)} =1+\frac{z^2\left((1-s)(1-2z)-\sqrt{1-4z^2}\right)}{(2z-1)\left(2(1-s)z^2+\sqrt{1-4z^2}\right)}.
\end{equation}
\end{theorem}


It is interesting to note that, while the generating function for partitions by semi\-perimeter is rational, namely $\frac{z^2}{1-2z}$ (setting $s=1$ in \eqref{eq:Psp}, the generating function by semiperimeter and degree of symmetry is not. 



\subsection{Symmetry by self-conjugate hooks}

Next we consider a third notion of symmetry for partitions. As in~\cite{barnabei_descent_2014}, the boxes in the Young diagram of $\lambda\in\P$ can be decomposed into {\em diagonal hooks} as follows: the first hook is the largest hook, consisting of the first row and the first column; the second hook is the largest hook after the first hook has been removed, and so on. The number of hooks in this decomposition equals the largest $\delta$ such that $\lambda_\delta\ge \delta$ (also known as the side length of Durfee square of $\lambda$).  Let $\dsh(\lambda)$ be the number of diagonal hooks in the Young diagram of $\lambda$ that are self-conjugate, that is, they have the same number of boxes in the row than in the column. For example, the partition $\lambda=(4,4,3,2,1)$ in \cref{fig:psi} has two symmetric diagonal hooks, and so $\dsh(\lambda)=2$, whereas $\ds(\lambda)=3$.

\begin{proposition}
The generating functions for partitions with respect to the statistic $\dsh$ and the side length of any (in the first formula) or the smallest (in the second formula) square containing their Young diagram are 
\begin{align*}\sum_{n\ge0} \sum_{\lambda\in\P^\Box_n} s^{\dsh(\lambda)} z^n & = \frac{1}{(1-s)z + \sqrt{1-4z}}, \\
\sum_{\lambda\in\P} s^{\dsh(\lambda)} z^{\max\{\lambda_1,\lambda'_1\}} & = \frac{1-z}{(1-s)z + \sqrt{1-4z}}.
\end{align*}
%$$\sum_{n\ge0} \sum_{\lambda\in\P^\Box_n} s^{\dsh(\lambda)} z^n  = \frac{1}{(1-s)z + \sqrt{1-4z}}, \quad 
%\sum_{\lambda\in\P} s^{\dsh(\lambda)} z^{\max\{\lambda_1,\lambda'_1\}} = \frac{1-z}{(1-s)z + \sqrt{1-4z}}.$$
\end{proposition}


For $P\in\G_n$, denote by $\pho(P)$ the number of peaks of $P$ at height $1$, that is, occurrences of $UD$ whose middle vertex  has $y$-coordinate equal to 1.

\begin{corollary}
For $n,k\ge0$,
$$|\{\lambda\in\P^\Box_n:\dsh(P)=k\}|=|\{P\in\G_n:\pho(P)=k\}|.$$
\end{corollary}


\begin{proof}
Consider the following bijection $\psi:\P^\Box_n\to\G_n$, which is also used in \cite[Lemma 3.5]{barnabei_descent_2014}. Given
$\lambda\in\P^\Box_n$, let $\delta$ be the number of hooks in its diagonal hook decomposition described above. For $1\le i\le \delta$, let $a_i$ (resp. $\ell_i$) denote the arm length (resp. leg length) of the $i$-th diagonal hook, defined as the number of boxes in the top row (resp. left column) of the hook, not including the corner box. Let
$$\psi(\lambda)=D^{a_\delta}U^{\ell_\delta+1}D^{a_{\delta-1}-a_\delta}U^{\ell_{\delta-1}-\ell_\delta}%D^{a_{\delta-2}-a_{\delta-1}}U^{\ell_{\delta-2}-\ell_{\delta-1}}
\dots D^{a_{1}-a_2}U^{\ell_{1}-\ell_2}D^{n-a_1}U^{n-1-\ell_1}.$$
Then $\dsh(\lambda)=\pho(\psi(\lambda))$. Indeed, the peaks of $\psi(\lambda)$ occur at heights $1+\ell_\delta-a_\delta, 1+\ell_{\delta-1}-a_{\delta-1},
\dots, 1+\ell_1-a_1$, and so $\pho(\psi(\lambda))=|\{i:a_i=\ell_i\}|=\dsh(\lambda)$. \cref{fig:psi} shows an example of this construction.
\end{proof}

\begin{figure}[htb]
\centering
    \begin{tikzpicture}[scale=0.5]
      \draw (0,-5) rectangle (5,0);
      \draw[fill=yellow!70] (0,-5) rectangle (1,0);
      \draw[fill=yellow!70] (1,-1) rectangle (4,0);
      \draw[fill=blue!25] (1,-4) rectangle (2,-1);
      \draw[fill=blue!25] (2,-2) rectangle (4,-1);
      \draw[fill=green!30] (2,-3) rectangle (3,-2);
      \draw (0,-5) grid (1,0);
      \draw (1,-1) grid (4,0);
      \draw (1,-4) grid (2,-1);
      \draw (2,-2) grid (4,-1);
      \draw (2,-3) grid (3,-2);
      \draw[dashed,thin] (0,0)--(3,-3);
   \end{tikzpicture}\quad
 \begin{tikzpicture}[scale=0.55] 
 	\draw (-2,0) node[above] {$\psi$};
 	\draw (-2,0) node {$\rightarrow$};
     \draw[dotted](-1,0)--(11,0);
     \draw[dotted](0,-2)--(0,2);
     \draw[thick,blue](0,0) circle(1.2pt) \U\D\D\U\U\D\U\U\D\D;
     \foreach \x in {1,5}{ \draw[orange,ultra thick] (\x,1) circle(.15);} 
    \end{tikzpicture}
  \caption{The bijection $\psi$ applied to $\lambda=(4,4,3,2,1)\in\P^\Box_5$. Here $\delta=3$, $a_1=3$, $\ell_1=4$,  
$a_2=\ell_2=2$, $a_3=\ell_3=0$. The peaks at height $1$ in $\phi(\lambda)$ are highlighted in orange.}\label{fig:psi}
\end{figure}



\subsection{Unimodal compositions}\label{sec:unimodal}

A composition is a sequence of positive integers $(a_1,a_2,\dots,a_k)$ for some $k\ge1$.
Its degree of symmetry is the number of indices $i\le k/2$ such that $a_i=a_{k+1-i}$.
Similarly to how partitions are represented as Young diagrams, compositions can be represented as {\em bargraphs}, by arranging boxes (unit squares) into $k$ bottom-justified columns, where column $i$ from the left has $a_i$ boxes for each $i$; see \cref{fig:bargraph} for an example.
Bargraphs have been studied in the literature as a special case of column-convex polyominoes (see e.g. \cite{bousquet-melou_site-perimeter_2003,prellberg_critical_1995}), and they are used in statistical physics to model polymers.

A bargraph can be identified with the lattice path determined by its upper boundary, namely, a self-avoiding path with steps $N=(0,1)$, $E=(1,0)$ and $S=(0,-1)$ starting at the origin and returning to the $x$-axis only at the end. 
For a bargraph $B$, let $e(B)$ and $n(b)$ denote its number of $E$ and $N$ steps, respectively. The semiperimeter of $B$ is defined as $\sp(B)=e(B)+n(B)$, 
%and its area is $a_1+\dots+a_k$, where the $a_i$ are the column heights. 
and its degree of symmetry is defined as the degree of symmetry of the composition determined by its column heights, and denoted by $\ds(B)$.

Interpreting partitions as weakly decreasing compositions, it is natural to consider the related notion of unimodal compositions; equivalently, unimodal bargraphs. Let $\UB$ denote the set of {\em unimodal bargraphs} with a centered maximum, defined as those whose column heights satisfy $1\le a_1\le \dots\le a_{\left\lfloor (k+1)/2 \right\rfloor}$ and 
$a_{\left\lceil (k+1)/2 \right\rceil}\ge \dots\ge a_{k}\ge1$. 

\begin{figure}[htb]
\centering
    \begin{tikzpicture}[scale=0.7]
      \draw[thin,dotted](0,0)--(8,0);
     \draw[dashed,thick](4,-.5)--(4,4.5);
     \draw[thick] (0,0) circle(1.2pt)  \N\H\H\N\H\N\H\N\H\S\S\H\H\S\H\S; 
     \draw[red,ultra thick] (0,1)--(1,1) (2,2)--(3,2) (5,2)--(6,2) (7,1)--(8,1);
\end{tikzpicture}
\caption{A unimodal bargraph $B$ with $\ds(B)=2$, $e(B)=8$ and $n(B)=4$, corresponding to the composition $(1,1,2,3,4,2,2,1)$.}
\label{fig:bargraph}
\end{figure}


\begin{theorem}\label{thm:UB}
The generating function for unimodal bargraphs with a centered maximum with respect to their degree of symmetry is
$$\sum_{B\in\UB}s^{\ds(B)}x^{e(B)}y^{n(B)}=\frac{y(1+x-y)}{(1-s)x^2+\sqrt{((x+1)^2-y)((x-1)^2-y)}}-y.$$
\end{theorem}



For partitions and compositions (represented as Young diagrams and bargraphs, respectively), a natural measure of size other than the semiperimeter is the sum of the entries (equivalently, the area). Whereas the generating function for compositions by area and degree of symmetry is straightforward, the corresponding generating functions for partitions and unimodal compositions are not known.


%% if you use biblatex then this generates the bibliography
%% if you use some other method then remove this and do it your own way
\printbibliography

\end{document}

