%&latex %will accept 10pt 11pt or 12 pt in following line %\renewcommand{\baselinestretch}{1.3} sets the interline spacing at %generous double-spacing \documentclass[12pt]{article} \marginparwidth 0pt \oddsidemargin 0pt \evensidemargin 0pt \marginparsep 0pt \topmargin 0pt \textwidth 6.3in \textheight 8.5in \headsep -3mm \parskip = 3mm %\setstretch{1.5} \usepackage{pstricks,pst-node} %\usepackage{pathlatex} %\usepackage{psfig} %\usepackage{epsfig} \usepackage{amsmath,amsthm} \usepackage{amssymb} %\usepackage{mathabx} \usepackage{color} \usepackage{xspace} % load hyperref last \usepackage[colorlinks=true, linkcolor=purple1, filecolor=brown, citecolor=blue]{hyperref} \definecolor{gray1}{rgb}{0.5,0.5,0.5} \definecolor{black}{rgb}{0,0,0} \definecolor{purple1}{rgb}{0.2,0,0.4} \def\gray1{\textcolor{gray1} } \def\f{\ensuremath{F}\xspace} \def\ff{\ensuremath{F}\xspace} \def\gg{\ensuremath{g}\xspace} \def\h{\ensuremath{h}\xspace} \def\ps{\ensuremath{\Psi}\xspace} \def\ph{\ensuremath{h}\xspace} \renewcommand{\baselinestretch}{1.3} \def\g{\ensuremath{\mathcal G}\xspace} \def\afp{a fragmented permutation\xspace} \def\fps{fragmented permutations\xspace} \def\s{s-partition\xspace} \def\ss{s-partitions\xspace} \def\z{x} \def\t{y} \def\red{\textcolor{red} } \def\blue{\textcolor{black} } \def\v{\vert} \def\ep{\epsilon} \def\a{\ensuremath{\mathcal A}\xspace} \def\b{\ensuremath{\mathcal B}\xspace} \def\fcal{\ensuremath{\mathcal F}\xspace} \def\q{\ensuremath{\mathcal F}\xspace} \def\g{\ensuremath{\mathcal G}\xspace} \def\n{\ensuremath{\mathcal N}\xspace} \def\p{\ensuremath{\mathcal P}\xspace} \def\i{\ensuremath{\mathcal I}\xspace} \def\gf{generating function\xspace} \def\mbf#1{\mathchoice{\hbox{\boldmath $\displaystyle #1$}} {\hbox{\boldmath $\textstyle #1$}} {\hbox{\boldmath $\scriptstyle #1$}} {\hbox{\boldmath $\scriptscriptstyle #1$}}} % mathboldface %path-generating code courtesy of Christian Krattenthaler %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %Input-Datei zum Erzeugen von Gitterpunktwegen.% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %LaTeX-Version% %%%%%%%%%%%%%%% %entering a path: % \Pfad(x-coordinate of starting point,y-coordinate of final %point),path % as 1-2-3-4-word\endPfad %(1=step in x-direction, 2=step in y-direction, 3=upward diagonal step, 4=downward diagonal step) % %entering a dotted path: % \SPfad(x-coordinate of starting point,y-coordinate of starting point),path % as 1-2-3-4-word\endSPfad %(1=step in x-direction (E), 2=step in y-direction (N), 3=upward diagonal step, 4=downward diagonal step) %(5=step EEN, 6=step EES, 7=step EEEN, 8=step EEES) %coordinate-axes: % \Koordinatenachsen(length of positive x-axes, length of positive %y-axes)(length of negative x-axes, length of negative y-axes) %The length of negative axes are entered as negative numbers. % %lattice: % \Gitter(number of points in positive x-direction, number of points %in positive y-direction)(number of points in negative x-direction, %number of points in negative y-direction) % %diagonal lines: % \Diagonale(x-coordinate of SW-most point,y-coordinate of SW-most point)length of the projection on the x-axes % %antidiagonal lines: % \AntiDiagonale(x-coordinate of NW-most point,y-coordinate of NW-most point)length of the projection on the x-axes % %labelling of points: % \Label[location?]{[label]}(x-coordinate,y-coordinate) %where: % [location?]=\l,\lo,\lu,\r,\ro,\ru,\o,\u %and l=left, r=right, u=bottom, o=top. %In addition, if by \Einheit?cm the basic unit is changed, there exist %\llo,\loo,\llu,\luu,\rro,\roo,\rru,\ruu. % %The basic unit can be changed by entering % \Einheit=?cm %The default is \Einheit=0.5cm. % %The thickness of the paths can be changed by entering % \PfadDicke{?cm} %The default is \PfadDicke=1pt. % %The following point sizes are available: %\DuennPunkt, \NormalPunkt, \DickPunkt. Syntax: % \DickPunkt(x-coordinate,y-coordinate), etc. % %Besides, a circle is available by \Kreis. Syntax: % \Kreis(x-coordinate,y-coordinate) % \catcode`\@=11 \font\tenln = line10 \font\tenlnw = linew10 \thicklines \newskip\Einheit \Einheit=.6cm \newcount\xcoord \newcount\ycoord \newdimen\xdim \newdimen\ydim \newdimen\PfadD@cke \newdimen\Pfadd@cke \PfadD@cke2pt \Pfadd@cke0.3pt \def\PfadDicke#1{\PfadD@cke#1 \divide\PfadD@cke by2 \Pfadd@cke\PfadD@cke \multiply\PfadD@cke by2} \long\def\LOOP#1\REPEAT{\def\BODY{#1}\ITERATE} \def\ITERATE{\BODY \let\next\ITERATE \else\let\next\relax\fi \next} \let\REPEAT=\fi \def\Punkt{\hbox{\raise-2pt\hbox to0pt{\hss\scriptsize$\bullet$\hss}}} \def\DuennPunkt(#1,#2){\unskip \raise#2 \Einheit\hbox to0pt{\hskip#1 \Einheit \raise-1.5pt\hbox to0pt{\hss\tiny$\bullet$\hss}\hss}} \def\NormalPunkt(#1,#2){\unskip \raise#2 \Einheit\hbox to0pt{\hskip#1 \Einheit \raise-3pt\hbox to0pt{\hss\large$\bullet$\hss}\hss}} \def\DickPunkt(#1,#2){\unskip \raise#2 \Einheit\hbox to0pt{\hskip#1 \Einheit \raise-4pt\hbox to0pt{\hss\Large$\bullet$\hss}\hss}} \def\Kreis(#1,#2){\unskip \raise#2 \Einheit\hbox to0pt{\hskip#1 \Einheit \raise-4pt\hbox to0pt{\hss\Large$\circ$\hss}\hss}} \def\Diagonale(#1,#2)#3{\unskip\leavevmode \xcoord#1\relax \ycoord#2\relax \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit \unitlength\Einheit \line(1,1){#3}\hss}} \def\AntiDiagonale(#1,#2)#3{\unskip\leavevmode \xcoord#1\relax \ycoord#2\relax \advance\xcoord by -0.05\relax \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit \unitlength\Einheit \line(1,-1){#3}\hss}} \def\Pfad(#1,#2),#3\endPfad{\unskip\leavevmode \xcoord#1 \ycoord#2 \thicklines\ZeichnePfad#3\endPfad\thinlines} \def\ZeichnePfad#1{\ifx#1\endPfad\let\next\relax \else\let\next\ZeichnePfad \ifnum#1=1 \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit \vrule height\Pfadd@cke width1 \Einheit depth\Pfadd@cke\hss}% \advance\xcoord by 1 \else\ifnum#1=2 \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit \unitlength\Einheit \line(0,1){1}\hss} \advance\xcoord by 0 \advance\ycoord by 1 \else\ifnum#1=3 \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit \unitlength\Einheit \line(1,1){1}\hss} \advance\xcoord by 1 \advance\ycoord by 1 \else\ifnum#1=4 \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit \unitlength\Einheit \line(1,-1){1}\hss} \advance\xcoord by 1 \advance\ycoord by -1 \else\ifnum#1=5 \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit \unitlength\Einheit \line(2,1){2}\hss} \advance\xcoord by 2 \advance\ycoord by 1 \else\ifnum#1=6 \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit \unitlength\Einheit \line(2,-1){2}\hss} \advance\xcoord by 2 \advance\ycoord by -1 \else\ifnum#1=7 \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit \unitlength\Einheit \line(3,1){3}\hss} \advance\xcoord by 3 \advance\ycoord by 1 \else\ifnum#1=8 \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit \unitlength\Einheit \line(3,-1){3}\hss} \advance\xcoord by 3 \advance\ycoord by -1 \fi\fi\fi\fi\fi\fi\fi\fi \fi\next} \def\hSSchritt{\leavevmode\raise-.4pt\hbox to0pt{\hss.\hss}\hskip.2\Einheit \raise-.4pt\hbox to0pt{\hss.\hss}\hskip.2\Einheit \raise-.4pt\hbox to0pt{\hss.\hss}\hskip.2\Einheit \raise-.4pt\hbox to0pt{\hss.\hss}\hskip.2\Einheit \raise-.4pt\hbox to0pt{\hss.\hss}\hskip.2\Einheit} \def\vSSchritt{\vbox{\baselineskip.2\Einheit\lineskiplimit0pt \hbox{.}\hbox{.}\hbox{.}\hbox{.}\hbox{.}}} \def\DSSchritt{\leavevmode\raise-.4pt\hbox to0pt{% \hbox to0pt{\hss.\hss}\hskip.2\Einheit \raise.2\Einheit\hbox to0pt{\hss.\hss}\hskip.2\Einheit \raise.4\Einheit\hbox to0pt{\hss.\hss}\hskip.2\Einheit \raise.6\Einheit\hbox to0pt{\hss.\hss}\hskip.2\Einheit \raise.8\Einheit\hbox to0pt{\hss.\hss}\hss}} \def\dSSchritt{\leavevmode\raise-.4pt\hbox to0pt{% \hbox to0pt{\hss.\hss}\hskip.2\Einheit \raise-.2\Einheit\hbox to0pt{\hss.\hss}\hskip.2\Einheit \raise-.4\Einheit\hbox to0pt{\hss.\hss}\hskip.2\Einheit \raise-.6\Einheit\hbox to0pt{\hss.\hss}\hskip.2\Einheit \raise-.8\Einheit\hbox to0pt{\hss.\hss}\hss}} \def\SPfad(#1,#2),#3\endSPfad{\unskip\leavevmode \xcoord#1 \ycoord#2 \ZeichneSPfad#3\endSPfad} \def\ZeichneSPfad#1{\ifx#1\endSPfad\let\next\relax \else\let\next\ZeichneSPfad \ifnum#1=1 \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit \hSSchritt\hss}% \advance\xcoord by 1 \else\ifnum#1=2 \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit \hbox{\hskip-2pt \vSSchritt}\hss}% \advance\ycoord by 1 \else\ifnum#1=3 \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit \DSSchritt\hss} \advance\xcoord by 1 \advance\ycoord by 1 \else\ifnum#1=4 \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit \dSSchritt\hss} \advance\xcoord by 1 \advance\ycoord by -1 \fi\fi\fi\fi \fi\next} \def\Koordinatenachsen(#1,#2){\unskip \hbox to0pt{\hskip-.5pt\vrule height#2 \Einheit width.5pt depth1 \Einheit}% \hbox to0pt{\hskip-1 \Einheit \xcoord#1 \advance\xcoord by1 \vrule height0.25pt width\xcoord \Einheit depth0.25pt\hss}} \def\Koordinatenachsen(#1,#2)(#3,#4){\unskip \hbox to0pt{\hskip-.5pt \ycoord-#4 \advance\ycoord by1 \vrule height#2 \Einheit width.5pt depth\ycoord \Einheit}% \hbox to0pt{\hskip-1 \Einheit \hskip#3\Einheit \xcoord#1 \advance\xcoord by1 \advance\xcoord by-#3 \vrule height0.25pt width\xcoord \Einheit depth0.25pt\hss}} \def\Gitter(#1,#2){\unskip \xcoord0 \ycoord0 \leavevmode \LOOP\ifnum\ycoord<#2 \loop\ifnum\xcoord<#1 \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit\Punkt\hss}% \advance\xcoord by1 \repeat \xcoord0 \advance\ycoord by1 \REPEAT} \def\Gitter(#1,#2)(#3,#4){\unskip \xcoord#3 \ycoord#4 \leavevmode \LOOP\ifnum\ycoord<#2 \loop\ifnum\xcoord<#1 \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit\Punkt\hss}% \advance\xcoord by1 \repeat \xcoord#3 \advance\ycoord by1 \REPEAT} \def\Label#1#2(#3,#4){\unskip \xdim#3 \Einheit \ydim#4 \Einheit \def\lo{\advance\xdim by-.5 \Einheit \advance\ydim by.5 \Einheit}% \def\llo{\advance\xdim by-.25cm \advance\ydim by.5 \Einheit}% \def\loo{\advance\xdim by-.5 \Einheit \advance\ydim by.25cm}% %NEW DEF \O := \OX \def\o{\advance\ydim by.25cm}% \def\ro{\advance\xdim by.5 \Einheit \advance\ydim by.5 \Einheit}% \def\rro{\advance\xdim by.25cm \advance\ydim by.5 \Einheit}% \def\roo{\advance\xdim by.5 \Einheit \advance\ydim by.25cm}% \def\l{\advance\xdim by-.30cm}% \def\r{\advance\xdim by.30cm}% \def\lu{\advance\xdim by-.5 \Einheit \advance\ydim by-.6 \Einheit}% \def\llu{\advance\xdim by-.25cm \advance\ydim by-.6 \Einheit}% \def\luu{\advance\xdim by-.5 \Einheit \advance\ydim by-.30cm}% \def\u{\advance\ydim by-.30cm}% \def\ru{\advance\xdim by.5 \Einheit \advance\ydim by-.6 \Einheit}% \def\rru{\advance\xdim by.25cm \advance\ydim by-.6 \Einheit}% \def\ruu{\advance\xdim by.5 \Einheit \advance\ydim by-.30cm}% #1\raise\ydim\hbox to0pt{\hskip\xdim \vbox to0pt{\vss\hbox to0pt{\hss$#2$\hss}\vss}\hss}% } \catcode`\@=12 \begin{document} \newtheorem{theorem}{Theorem} \newtheorem{defn}[theorem]{Definition} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{prop}[theorem]{Proposition} \newtheorem{cor}[theorem]{Corollary} \newtheorem{conj}[theorem]{Conjecture} \newtheorem*{mainthm}{Main Theorem} \newtheorem*{gnrl}{Main Theorem Generalized} %\vspace*{-5mm} \begin{center} {\Large The Run Transform \\ } \vspace{10mm} % \begingroup \renewcommand\thefootnote{\fcalnsymbol{footnote}} \begin{tabular}{l@{\hspace{3em}}l} David Callan & Emeric Deutsch \\[1mm] Department of Statistics & Department of Mathematics\\[-1mm] University of Wisconsin-Madison & Polytechnic Institute of NYU\\[-1mm] Madison, WI \ 53706 & Brooklyn, NY 11201 \\[1mm] {\small {\tt callan@stat.wisc.edu}} & {\small {\tt emericdeutsch@msn.com}} \end{tabular} \endgroup %\vspace{5mm} %December 13, 2011 \end{center} \begin{abstract} We consider the transform from sequences to triangular arrays defined in terms of generating functions by $f(x) \rightarrow \frac{1-x}{1-xy} f\big(\frac{x(1-x)}{1-xy}\big)$. We establish a criterion for the transform of a nonnegative sequence to be nonnegative, and we show the transform counts certain classes of lattice paths by number of so-called pyramid ascents and certain classes of partitions into sets of lists (blocks) by number of blocks that consist of increasing consecutive integers. \end{abstract} \section{Introduction} \vspace*{-2mm} We investigate the transform $\Phi$ defined on formal power series $f(x)$ by \[ \Phi\big(f(x)\big) := \frac{1-x}{1-xy}\: f\!\left(\frac{x\,(1-x)}{1-xy}\right). \] Following Herbert Wilf's dictum, ``A generating function is a clothesline on which we hang up a sequence of numbers for display'' \cite[Chapter 1]{wilf}, we will use sequences/arrays and their generating functions interchangeably. Thus the transform $\Phi$ is also defined for sequences $(a_{n})_{n\ge 0}$. It turns out that the transform is closely related to the Catalan numbers and there is a nice combinatorial interpretation for the transform of the size-counting sequence for various classes of partitions into sets of lists (blocks) and various classes of lattice paths of upsteps $U$, flatsteps $F$, and downsteps $D$. In the former case, the transform counts partitions by number of runs, where a \emph{run}, also known as an \emph{adjacent block} \cite{adj}, is a block that consists of increasing consecutive integers. In the latter case it counts lattice paths by number of pyramid ascents, where an \emph{ascent} is a maximal subpath of the form $U^{k},\ k\ge 1$, a \emph{pyramid} is a maximal subpath of the form $U^{k}D^{k}, k\ge 1$, and a \emph{pyramid ascent} is an ascent that is the first half of a pyramid. For example, among the four ascents of $UUDUUDUUDDDUDD$, only the last two ($UU$ and $U$) are pyramid ascents. Because of the interpretation in terms of runs, and for brevity, we will call $\Phi$ the \emph{run transform}. In Section \ref{catconv} we review the Catalan numbers and two of their interpretations, and in Section 3 we establish some basic properties of the run transform and give a criterion for the run transform of a nonnegative sequence to also be nonnegative. Section 4 gives interpretations of the run transform of the Catalan numbers in terms of both Dyck paths and noncrossing partitions, the basis for subsequent generalizations. Section 5 generalizes to paths of $j$-upsteps $(j,j)$ and downsteps $(1,-1)$. Section 6 recalls the notion of a set-of-lists partition, \s for short, introduces the notion of a run-closed family of \ss and proves that if $f(\z)$ is the \gf by size of a run-closed family $\fcal$ of \ss, then the run transform of $f(\z)$ counts $\fcal$ by size and number of runs. Section 7 generalizes this result. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % % defines the basis of a run-closed family %of \fps % % and shows that, in the case of a singleton (one-element) basis, % % the distribution of runs depends only on the size of this element, and not on its actual blocks. % % Section 9 finds the distribution of runs for the run-closed family % % $\fcal_{k}$ with singleton basis $(k,k-1,\ldots ,1)$, and completes the proof % % of the key result. % % % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Section 8 considers the transform for paths of upsteps, flatsteps, and downsteps and Section 9 presents a conjecture. Sequences in The On-Line Encyclopedia of Integer Sequences (OEIS) \cite{oeis}, are referred to by their six-digit A-numbers. \section{Review of the Catalan numbers, Dyck paths, and noncrossing partitions}\vspace*{-5mm}\label{catconv} The Catalan numbers (sequence \htmladdnormallink{A000108}{http://oeis.org/A000108} in OEIS) are intimately related to the run transform $\Phi$; so let us recall some facts and fix some notation for them and for two of their interpretations. The \gf for the Catalan numbers $C_{n}=\frac{1}{n+1}\binom{2n}{n}=\binom{2n}{n}-\binom{2n}{n-1}$ is $C(x)=(1-\sqrt{1-4x})/(2x)$. The Catalan convolution matrix is defined by $C=\left(\binom{2j-i}{j-i} - \binom{2j-i}{j-i-1} \right)_{i,j\ge 0}$ and its inverse is given by $C^{-1}= \left((-1)^{j-i}\binom{i+1}{j-i}\right)_{i,j\ge 0}$ \cite[p. 137]{convolution}. The first few rows and columns are shown. \[ C= \left(\begin{array}{cccccccc} 1 & 1 & 2 & 5 & 14 & 42 & 132 & \ldots \\ & 1 & 2 & 5 & 14 & 42 & 132 & \ldots \\ & & 1 & 3 & 9 & 28 & 90 & \ldots \\ & & & 1 & 4 & 14 & 48 & \ldots \\ & & & & 1 & 5 & 20 & \ldots \\ & & & & & 1 & 6 & \ldots \\ & & & & & & 1 & \ldots \\ & & & & & & & \ddots \end{array}\right),\quad C^{-1}= \left(\begin{array}{cccccccc} 1 & -1 & 0 & 0 & 0 & 0 & 0 & \ldots \\ & 1 & -2 & 1 & 0 & 0 & 0 & \ldots \\ & & 1 & -3 & 3 & -1 & 0 & \ldots \\ & & & 1 & -4 & 6 & -4 & \ldots \\ & & & & 1 & -5 & 10 & \ldots \\ & & & & & 1 & -6 & \ldots \\ & & & & & & 1 & \ldots \\ & & & & & & & \ddots \end{array}\right) \] Thus the top row (row 0) of $C$, the Catalan numbers, has \gf $C(x)$. It is well known that the entries of $C$ count nonnegative lattice paths. Specifically, define a $U$-$D$ path to be a lattice path of \emph{upsteps} $U=(1,1)$ and \emph{downsteps} $D=(1,-1)$ (not necessarily starting at the origin). Let $\n_{mn}\ (=\n_{m,n})$ denote the set of $U$-$D$ paths consisting of $n$ upsteps and $m+n$ downsteps that never dip below ground level, the horizontal line through the terminal vertex. The size of a $U$-$D$ path is its number of downsteps. Then $\v\,\n_{mn}\,\v = C_{mn}$. Set $\n_{m}:=\bigcup_{n\ge 0}\n_{mn}$. A \emph{Dyck} path is a member of $\n_{0}$. It is also well known (see, e.g., \cite[Remark 5]{woan} or \cite{tedford}) that row $m$ of $C$, starting at the diagonal entry, is the $(m+1)$-fold convolution of the top row. Hence, the \gf for $\n_{m}$ by size is $x^{m}C(x)^{m+1}$, and, with $\mathbf{x}$ defined to be the column vector $(1,x,x^{2},\ldots)^{\,t}$ where the superscript $t$ denotes transpose, we have the matrix-vector product \begin{equation}\label{matvec} C\,\mathbf{x}=(C(x),\:xC(x)^{2},\:x^{2}C(x)^{3},\:\ldots)^{\,t}. \end{equation} We define $C(x,y)$ to be $\Phi\big(C(x)\big)$. Thus \begin{equation}\label{ctz} C(x,y)=\frac{1-\sqrt{1-4\,\frac{\textrm{{\small $x\,(1-x)$}}}{\textrm{{\small $1-xy$}}}}}{2x}. \end{equation} The \emph{matching step} of a given step in a Dyck path is the other end-step of the shortest Dyck subpath containing the given step as an end-step. Ascents (and pyramid ascents) were defined in the Introduction and, analogously, a \emph{descent} is a maximal subpath of the form $D^{k},\ k\ge 1$. %An \emph{ascent} is a maximal sequence of contiguous upsteps, and similarly %for a \emph{descent}. %A \emph{pyramid} in a path is a maximal subpath of the form %$U^{k}D^{k}$ with $k\ge 1$. %A \emph{pyramid} ascent is an ascent in which the matching %steps of its steps all belong to the same descent, equivalently, the %descent immediately following the ascent is at least as long as the %ascent (and so the ascent is the first half of a pyramid). A nonempty Dyck path decomposes (at its returns to ground level) into \emph{components}, each of which is a \emph{primitive} Dyck path---a nonempty Dyck path whose only return to ground level is at the end. There is a well known bijection from Dyck paths to noncrossing partitions, whose origin we have been unable to trace.. Traverse the Dyck path from left to right and number the down steps from 1 to $n$. Give the same labels to the matching up steps. The numbers on the ascents form the blocks of the partition. We will call this the standard bijection. Under the standard bijection, pyramid ascents in the Dyck path become runs in the noncrossing partition. \section{Basic properties and a criterion for nonnegativity} \vspace*{-5mm} We will use $F(x,y)$ for $\Phi\big(f(x)\big)$ to show the dependency on both variables. Clearly, $F(x,1)=f(x)$ and so the row sums of the run transform give the original sequence. The run transform $\Phi$ is linear, \[ \Phi\big(\alpha f(x)+\beta g(x)\big)= \alpha \Phi\big(f(x)\big)+\beta \Phi\big(g(x)\big), \] and has a multiplicativity property, \[ \Phi\big(xf(x)g(x)\big)=x\Phi\big(f(x)\big)\Phi\big(g(x)\big). \] More generally, \[ \Phi\big(x^{i-1}f_{1}(x)f_{2}(x)\cdots f_{i}(x)\big)=x^{i-1}\Phi\big(f_{1}(x)\big) \Phi\big(f_{2}(x)\big)\cdots \Phi\big(f_{i}(x)\big). \] In particular, for $i=k+1$ and $f=f_{1}=f_{2}=\cdots ,$ \[ \Phi\big(x^{k}f(x)^{k+1}\big)=x^{k}\Phi\big(f(x)\big)^{k+1}. \] From this fact, together with linearity, we obtain \begin{lemma} \label{prop1} For an arbitrary sequence $(a_{k})_{k\ge 0}$ and formal power series $f(x)$, \[ \Phi\left(\sum_{k\ge 0}a_{k}x^{k}f(x)^{k+1}\right)= \sum_{k\ge 0}a_{k}x^{k}\Phi\big(f(x)\big)^{k+1}. \] \end{lemma} %\qed \begin{prop} \label{em} Let $\mathbf{a}=(a_{k})_{k\ge 0}$ be an arbitrary sequence. Then its run transform is \[ \sum_{k\ge 0}b_{k}x^{k}C(x,y)^{k+1}, \] where $\mathbf{b}=(b_{k})_{k\ge 0}$ is defined by $\mathbf{b}=\mathbf{a}\,C^{-1}$. \end{prop} Proof. The defining relation $\mathbf{b}=\mathbf{a}\,C^{-1}$ yields $\mathbf{a}=\mathbf{b}\,C$ and, after multiplication by the column vector $\mathbf{x}$, \[ \mathbf{a}\,\mathbf{x}=\mathbf{b}\,C\,\mathbf{x}. \] Making use of (\ref{matvec}), this matrix identity translates into \[ \sum_{k\ge 0}a_{k}x^{k}=\sum_{k\ge 0}b_{k}x^{k}C(x)^{k+1}. \] Now apply Lemma \ref{prop1} with $f(x)=C(x)$. \qed \begin{prop} For a nonnegative sequence $\mathbf{a}=(a_{k})_{k\ge 0}$, its run transform is nonnegative if and only if the sequence $\mathbf{x}:=\mathbf{a}\,C^{-1}$ is nonnegative. \end{prop} Proof. We have $C(x,0)=(1-x)C\big(x(1-x)\big)=1$ and it follows from Proposition \ref{em} that column 0 of the run transform, given by $F(x,0)$, is (the transpose of) $\mathbf{x}$. So the condition is certainly necessary. Sufficiency will follow if we know that each power of $C(x,y)$ is the \gf of a nonnegative array. For $C(x,y)$ itself, nonnegativity follows from a combinatorial interpretation in terms of decorated forests \cite[Section 9]{lcoforest} or from Proposition \ref{pyrascDyck} below, but we can also give an analytic proof as follows. Say $(u_{i,j})_{i\ge 0,\ 0\le j \le i}$ is the array of coefficients for $C(x,y)$. We have the identity $(2xC(x,y)-1)^{2}=1-4x(1-x)/(1-xy)$, leading to \[ xC(x,y)^{2}=C(x,y)-\frac{1-x}{1-xy}. \] Picking out coefficients leads to a recurrence for $u_{i,j}:\ u_{0,0} = 1$, and \[ u_{n,k} = \begin{cases} \sum_{i=0}^{n-1}\sum_{j=0}^{n}u_{i,j}u_{n-1-i,n-j} +1, & \textrm{ if $1\le k \le n$;} \\ \sum_{i=0}^{n-1}\sum_{j=0}^{n-1}u_{i,j}u_{n-1-i,n-1-j} -1, & \textrm{ if $0\le k = n-1$;} \\ \sum_{i=0}^{n-1}\sum_{j=0}^{k}u_{i,j}u_{n-1-i,k-j}, & \textrm{ if $0\le k \le n-2$,} \end{cases} \] from which it is easy to see that $u_{i,j}$ is nonnegative, the $-1$ in the middle equality notwithstanding. Finally, it is easy to check that nonnegativity of $C(x,y)$ implies nonnegativity of all its powers. \qed \section{The run transform of the Catalan numbers} \begin{lemma}\label{pyrascDyck} The run transform $C(x,y)$ of the Catalan number \gf $C(x)$ counts Dyck paths by size and number of pyramid ascents, equivalently, noncrossing partitions by size and number of runs. \end{lemma} Proof. Let $F(x,y)$ denote the \gf for Dyck paths by size and number of pyramid ascents. A Dyck path $P$ is either empty or has the decomposition $P=U^{r}DP_{1}DP_{2}D\cdots DP_{r}$ for some $r\ge1$, where the $P_{i}$ are Dyck paths. Each pyramid ascent in $P_{1},\ldots ,P_{r}$ is a pyramid ascent in $P$ and, if $P_{1},\ldots ,P_{r-1}$ are all empty paths, then the first ascent of $P$ is also a pyramid ascent, contributing a $y$ factor. We thus obtain \[ F=1+\sum_{r\ge 1}x^{r}\big(y+F^{r-1}-1\big)F \] which leads at once to \[ xF^{2}-F+\frac{1-x}{1-xy} = 0, \] an equation whose solution is $F(x,y)=C(x,y)$. \qed Recall that $\n_{k}$ is the set of nonnegative $U$-$D$ paths with $k$ more downsteps than upsteps. \begin{theorem} The run transform of the \gf for $\n_{k}$ by size counts $\n_{k}$ by size and number of pyramid ascents. \end{theorem} Proof. A path in $\n_{k}$ decomposes as $P_{1}DP_{2}D\cdots P_{k}DP_{k+1}$ with each $P_{i}$ a Dyck path. The statistics size and number of pyramid ascents are additive over this decomposition. So one multiplies the generating functions given by Proposition \ref{pyrascDyck}, and the \gf for $\n_{k}$ by size and number of pyramid ascents is $x^{k}C(x,y)^{k+1}$. By Lemma \ref{prop1}, the run transform of $x^{k}C(x)^{k+1}$ is $x^{k}C(x,y)^{k+1}$. \qed In subsequent sections we generalize this result in 3 ways: (i) from Dyck paths to %$U^{j}-D$ paths, where a $U^{j}-D$ path is a $U$-$D$ paths in which each ascent has length divisible by $j$, %equivalently, a path consisting of $j$-upsteps $(j,j)$ and downsteps, (ii) from Dyck paths to $U-F-D$ paths, where flatsteps $F=(1,0)$ are allowed, (iii) from noncrossing partitions to run-closed families of \ss, defined in Section \ref{runclosed} below. \section[U\^{}\{j\}-D paths]{$\mbf{U^{j}}$-$\mbf{D}$ paths} \vspace*{-5mm} Fix a positive integer $j$. A \emph{$j$-Dyck} path is a Dyck path in which each ascent has length divisible by $j$. Equivalently, it can be viewed as a nonnegative lattice path of so-called $j$-upsteps $(j,j)$ and (ordinary) downsteps $(1,-1)$. Its \emph{size} is the number of $j$-upsteps, equivalently, (number of downsteps)$/j$. A \emph{$j$-nice} pyramid ascent is one that ends at height $\equiv 0$ (mod $j$). \begin{lemma}\label{jud} The run transform of the \gf for $j$-Dyck paths by size is the \gf for $j$-Dyck paths by size and number of pyramid ascents. \end{lemma} Proof. Let $\ff_{0}(x,y)$ denote the \gf for $j$-Dyck paths with $x$ marking size and $y$ marking the number of $j$-nice pyramid ascents. To find an equation for $\ff_{0}(x,y)$, it is convenient to introduce the \gf $\ff_{i}(x,y)$, $i$ an integer, for the number of pyramid ascents that end at height $\equiv i$ (mod $j$). Set $\ff = \ff_{0}\ff_{1}\cdots \ff_{j-1}$. A nonempty $j$-Dyck path $P$ has a decomposition as illustrated for $j=3$ and $r=2$ where $r$ is the number of initial $j$-upsteps, and the $P_{i}$'s are all $j$-Dyck paths (possibly empty). \Einheit=0.5cm \[ \Pfad(-12,0),3333334\endPfad \Pfad(-3,5),4\endPfad \Pfad(0,4),4\endPfad \Pfad(3,3),4\endPfad \Pfad(6,2),4\endPfad \Pfad(9,1),4\endPfad \SPfad(-12,0),111111111111111111111111\endSPfad \Label\o{P_{1}}(-4,5) \Label\o{P_{2}}(-1,4) \Label\o{P_{3}}(2,3) \Label\o{P_{4}}(5,2) \Label\o{P_{5}}(8,1) \Label\o{P_{6}}(11,0) \DuennPunkt(-11,1) \DuennPunkt(-10,2) \DuennPunkt(-8,4) \DuennPunkt(-7,5) \NormalPunkt(-12,0) \NormalPunkt(-9,3) \NormalPunkt(-6,6) \NormalPunkt(-5,5) \NormalPunkt(-3,5) \NormalPunkt(-2,4) \NormalPunkt(0,4) \NormalPunkt(1,3) \NormalPunkt(3,3) \NormalPunkt(4,2) \NormalPunkt(6,2) \NormalPunkt(7,1) \NormalPunkt(9,1) \NormalPunkt(10,0) \NormalPunkt(12,0) \Label\u{\textrm{A $j$-Dyck path with $j=3$}}(0,-1) \] \noindent In general, the decomposition is \[ U^{jr}DP_{1}DP_{2}\cdots DP_{jr}, \] for some $r\ge 1$. To obtain an expression for $\ff_{0}$ from this decomposition, $P_{1}$ contributes $\ff_{1}$ because it starts at height $\equiv -1$ mod $j$, $P_{2}$ contributes $\ff_{2},\ldots, P_{j}$ contributes $\ff_{0}$, $P_{j+1}$ contributes $\ff_{1}$, and so on, cyclically. And if $P_{1},P_{2},\ldots ,P_{jr-1}$ are all empty, the first ascent of $P$ is a pyramid ascent. Splitting into the two cases where $P_{1},P_{2},\ldots ,P_{jr-1}$ are all empty or not, we thus obtain \[ \ff_{0}=1+\sum_{r\ge 1}x^{r}\big(y+\ff_{1}\ff_{2}\cdots \ff_{j-1}\ff^{r-1}-1\big)\ff_{0} \] which simplifies to \begin{equation}\label{f0} \ff_{0}=1+(y-1)\ff_{0} \frac{x}{1-x} +\frac{x\ff}{1-x\ff}. \end{equation} For $i\not\equiv 0$ (mod $j$), there is no need to split into cases. We find $\ff_{i}=1+x\ff + x^{2}\ff^{2}+\cdots $, leading to \begin{equation}\label{fi} \hspace*{50mm} \ff_{i}=\frac{1}{1-x\ff} \hspace*{30mm}\textrm{ for $i\not\equiv 0$ (mod $j$).} \end{equation} Eliminating $f$ from (\ref{f0}) and (\ref{fi}), we obtain \begin{equation} \hspace*{40mm} \ff_{i}(x,y)=\frac{1-xy}{1-x}\ff_{0}(x,y)\hspace*{20mm}\textrm{ for $i\not\equiv 0$ (mod $j$).} \label{fij} \end{equation} Hence, \[ \ff=\left(\frac{1-xy}{1-x}\right)^{j-1}\ff_{0}^{j} \] and (\ref{f0}) becomes, after further simplification \begin{equation} (1-x)^{j}-(1-x)^{j-1}(1-xy)\ff_{0} + x(1-xy)^{j}\ff_{0}^{j+1}=0. \label{eq:definej} \end{equation} From (\ref{eq:definej}), $f(x):=\ff_{0}(x,1)$ has defining equation $1-f+xf^{j+1}=0$, and the run transform of $f(x)$ satisfies (\ref{eq:definej}). Hence the run transform of $f(x)$ is $\ff_{0}(x,y)$. \qed Now fix nonnegative integers $m$ and $d$. A $(j,m,d)$-$U$-$D$ path is a path of $j$-upsteps and downsteps that starts (for convenience) at $(0,m)$, has lowest point at level $-d$, and ends on the $x$-axis. A $(j,0,0)$-$U$-$D$ path is just a $j$-Dyck path. The size of a $(j,m,d)$-$U$-$D$ path is $\lfloor \textrm{(number of downsteps)}/j \rfloor$, and so it is convenient to express $m$ as $jk+\ell$ with $0\le \ell \le j-1$. \begin{theorem}\label{jmdUD} The run transform of the \gf for $(j,m,d)$-$U$-$D$ paths by size is the \gf for $(j,m,d)$-$U$-$D$ paths by size and number of pyramid ascents. \end{theorem} Proof. Let $G(x,y)$ denote the \gf for $(j,m,d)$-$U$-$D$ paths with $x$ marking size and $y$ marking the number of $j$-nice pyramid ascents. A $(j,m,d)$-$U$-$D$ path has the decomposition: \begin{equation} P_{0}\,D\,P_{1}\,D\,P_{2}\,\ldots\, D\,P_{m+d}\,U^{j}\,P_{m+d-1}'\,U^{j}\,P_{m+d-2}'\, \ldots \,U^{j}\,P_{m}'. \label{decomp} \end{equation} where the $P_{i}$ and the $P_{i}'$ are all $j$-Dyck paths. If a $P_{i}'$ begins with a pyramid, the pyramid is killed by the immediately preceding $U^{j}$. This necessitates introducing the \gf $H(x,y)$ for $j$-Dyck paths that begin with a pyramid: \[ H(x,y)=\sum_{i\ge 1}x^{i}y\ff_{0} =\frac{xy}{1-x}\ff_{0}. \] %Set $\ph_{0}(t,z)=\frac{1-tz}{1-z}\ff_{0}(t,z)$. The decomposition (\ref{decomp}) together with (\ref{fij}) yields \begin{eqnarray*} G(x,y) & = & x^{k+d}\ff_{-m}\,\ldots\,\ff_{-1}\,\ff_{0}\, \ff_{1}\,\ff_{2}\,\ldots\,\ff_{jd}\left(\frac{H}{y}+\ff_{0}-H\right) \\ & = & x^{k+d}\ff_{0}^{k+d+1}\ff_{1}^{m-k+(j-1)d} \left(\frac{1-xy}{1-x}\ff_{0}\right)^{d} \\ & = & x^{k+d} \left(\frac{1-xy}{1-x}\right)^{m-k+jd}\ff_{0}^{m+1+(j+1)d}. \end{eqnarray*} Hence $g(x):=G(x,1)=x^{k+d}\ff_{0}(x,1)^{m+1+(j+1)d}$ is the \gf for $(j,m,d)$-$U$-$D$ paths by size. The run transform of $g(x)$ is \begin{eqnarray*} \frac{1-x}{1-xy}\,g\left(\frac{x(1-x)}{1-xy}\right) & = & \frac{1-x}{1-xy} \left(\frac{x(1-x)}{1-xy}\right)^{k+d} \ff_{0}\Big(\frac{x(1-x)}{1-xy},1\Big)^{m+1+(j+1)d} \\ & = & x^{k+d}\left(\frac{1-xy}{1-x}\right)^{m+jd-k} \left(\frac{1-x}{1-xy}\, \ff_{0}\Big(\frac{x(1-x)}{1-xy},1\Big)\right)^{m+1+(j+1)d} \\ & = & x^{k+d}\left(\frac{1-xy}{1-x}\right)^{m+jd-k} \ff_{0}(x,y)^{m+1+(j+1)d} \\ & = & G(x,y), \end{eqnarray*} the next to last equality using the fact that the run transform of $\ff_{0}(x,1)$ is $\ff_{0}(x,y)$ (Lemma \ref{jud}). \qed \section{Run-closed families of \ss}\label{runclosed} \vspace*{-5mm} A \emph{set-of-lists} partition, or \emph{\s} for short, also known as a \emph{fragmented permutation} \cite[p.\,125]{flaj09}, is a partition $\pi$ of a set $S$ into a set of lists. The size of $\pi$, denoted $\v\, \pi \,\v$, is $\v\, S \, \v$. An \s is \emph{standard} if its support set is an initial segment of the positive integers. We use the familiar term \emph{blocks} for the lists in an \s, and we always arrange the blocks in increasing order of their first entry. Recall that a run is a block that consists of consecutive integers in increasing order. Thus the \s $3\,8\,1\,/\,4\,5\,6\,/\,7\,2\,/\, 9$ has size 9 and four blocks, two of which are runs, $4\,5\,6$ and 9. A permutation can be viewed as an \s via its disjoint cycle decomposition; for definiteness, we define a \emph{cycle} to be a list whose smallest entry occurs first. To \emph{delete} a run from a standard \s means to remove it and standardize what remains (replace smallest entry by 1, second smallest by 2, and so on). Thus deleting the run 23 from 178/23/465/9 yields 156/243/7. To \emph{insert} a run $i+1,\,\ldots, i+j$ into a standard \s $\pi$ means to increment by $j$ all elements of $\pi$ that exceed $i$ and adjoin $i+1,i+2,\ldots i+j$ as a new block. The result will be a standard \s provided $0 \le i \le \v\, \pi \,\v$. For example, inserting the run 456 into 15/342 yields 18/372/456. When runs are successively deleted from an \s, the order of deletion is immaterial and the result is always the same run-free \s. For 178/23/465/9, the result is 156/243. Let $\p$ denote the set of all standard \ss, including the empty one $\ep$. \begin{defn} A \emph{run-closed} family %$\fcal$ of \ss is a subset of \p that is closed under insertion and deletion of runs. \end{defn} To present a few examples of run-closed families, let us recall some terminology and facts for ordinary set partitions. A set partition is an \s in which each block is an increasing list $u_{1}k$. Then the run-deletion sequences of \ss in $\fcal(n)$, as specified by $(a_{i})_{i=1}^{r}$ and $(\ell_{i})_{i=1}^{r}$, are characterized by the following conditions: \[ \begin{array}{l} \textrm{\emph{$r\ge 1$ and all $a$'s and $\ell$'s are positive integers}}, \\ k+\ell_{1}+\ell_{2}+\ldots +\ell_{r}=n, \\ a_{1}k$ (it is obviously true for $n=k$). Since the characterization of the run-deletion sequences for $\g_{1}(n)$ makes no reference to $\pi_{1}$ other than through its size, this equality follows from two observations: \vspace*{-2mm} (i) members of $\g_{i}(n)$ are in one-to-one correspondence with their run-deletion sequences, $i=1,2$. \vspace*{-2mm} (ii) the set of run-deletion sequences for $\g_{1}(n)$ is \emph{identical} with that for $\g_{2}(n)$: both sets are characterized by the conditions of Proposition \ref{charRunDeletion}. \qed %\newpage Now we consider a canonical singleton basis of each size $k$, say the one-block \s $k,k-1,\ldots,2,1$ (the empty \s if $k=0$), and let $\fcal_{k}$ denote the run-closed family generated by it. A technical difficulty arises if $k=1$ because the only \s of size 1 is the one-block \s, (1), which is a run. (A workaround would be to color it red, maintain the color when runs are inserted---inserting 12 into \red{1} yields 12/\red{3}---and declare that red entries are not to be considered runs.) By Corollary \ref{f0NC}, $\fcal_{0}$ is the family of noncrossing ordinary partitions, and $\fcal_{k}$ can be characterized for general $k$: it consists of the noncrossing \ss in which (i) all blocks are increasing except for one block of length $k$ which is decreasing and (ii) this decreasing block is not covered by entries in another block, in other words, there is no increasing block containing integers $a