%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% This is fpsac18MusikerrhoBRev.tex, extended abstract by Gregg Musiker & Tom Roby
%%%% Revised version after getting reviewer's comments
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% 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]{FPSAC2018}
\articlenumber{37}
%% 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}

%%% We've already defined ours below
% \newtheorem{thm}{Theorem}
% \newtheorem{lem}{Lemma}

\usepackage{lipsum}

%% define your title in the usual way
%\title[Optional shorter title]{Something to do with math}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\title{A formula for birational rowmotion on rectangles}
%\title[A Path Formula for Birational Rowmotion]{A Path formula for birational rowmotion on the
%product of two chains (Extended abstract)}
%\author[G. Musiker]{Gregg Musiker}
%\address{University of Minnesota\\ Minneapolis, MN}
%\email{musiker@math.umn.edu}

%\author[T. Roby]{Tom Roby}
%\address{University of Connecticut\\Storrs, CT 06269-1009}
%\email{tom.roby@uconn.edu}


\author{
Gregg
Musiker\thanks{\href{mailto:musiker@math.umn.edu}{musiker@math.umn.edu}.
Partially supported by NSF Grant DMS-1362980.}\addressmark{1}
\and 
Tom Roby\thanks{\href{mailto:tom.roby@uconn.edu}{tom.roby@uconn.edu}}\addressmark{2}
}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
% \author[Optional shorter names]{
% Longer names me \thanks{\href{mailto:hello@world.c}{hello@world.c}. Longer names me was partially 
%                   supported by Grant 2017.11.14.$\partial$\;supp.}
% \addressmark{1}, 
% \and 
% you\addressmark{2}} 



%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Department of Mathematics, University of Minnesota, Minneapolis, 55455  USA\\
\addressmark{2}Department of Mathematics, University of Connecticut, Storrs, 06269-1009 USA}

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

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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
				      %%% PACKAGES %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% EVERY LATEX PACKAGE SHOULD HAVE: next three from Mike LaCroix: 
%%% FIX TEX ENGINE BUGS: There are some problems with the TeX engine that cannot legally 
%%% be fixed for software licensing reasons. This fixes them.
\usepackage{fixltx2e}

%%% Optical right justification and multi-width letters
\usepackage{microtype}

%%% MAKE LIGATURES CUT-AND-PASTE-ABLE This makes things, like ligatures, copyable
%%\input{glyphtounicode} \pdfgentounicode=1

%%%%% ^^^^EVERY LATEX PACKAGE SHOULD HAVE THE THREE ABOVE ^^^^

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
		 %%% PACKAGES IN (MOSTLY) ALPHABETICAL ORDER (BY THEME) %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

  
%%% AMS MATH PACKAGESVarious AMS packages for math; (maybe unecessary with 'amsart' class);
%%% NOT NEEDED WITH THE FPSAC CLS
% \usepackage{amsfonts}
% \usepackage{amsmath}
% \usepackage{amssymb}
% \usepackage{amsthm}

%%% ANIMATIONS: To get animations like those written by Mike LaCroix's; 
\usepackage{animate}

%%% ARRAYS & TABLES:: More flexible arrays and tables: 
\usepackage{array}
%%% TR: Added 18.Aug.2015 to created text colums that don't insist on right-justification; 
\newcolumntype{L}[1]{>{\raggedright\let\newline\\\arraybackslash\hspace{0pt}}p{#1}}

%%% For the longtable environment, which allows split tables over multiple pages (may need
%%% to run LaTeX multiple times\dots 
\usepackage{longtable}

%%% BLACKBOARD BOLD EXTENSION: To get blackboard bold for numerals, etc. 
\usepackage{bbm}
%%% I like using this for indicator functions; 
\newcommand{\II}{\mathbbm 1}

%%% CAPTIONS: For fine-tuning captions, e.g., centering them 
\usepackage[justification=centering,labelfont=bf]{caption}

%%% For color, better than the "color" package; 
\usepackage[dvipsnames]{xcolor}

\usepackage{comment}

%% These are standard colors for white background; 
\newcommand{\cred}[1]{{\color{red}#1}}
\newcommand{\cblu}[1]{{\color{blue}#1}}
\newcommand{\cpurp}[1]{{\color{violet}#1}}
\newcommand{\cgrn}[1]{{\color{OliveGreen}#1}}
\newcommand{\cvio}[1]{{\color{violet}#1}}

%%% DOUBLESPACINGFor doublespacing, etc. provides "\singlespacing",
%%% "\onehalfspacing", "\doublespacing" or "\setstretch{<factor>}" 
%%% Also \begin/end{doublespace} AND \begin{spacing}{1.7}...\end{spacing}
\usepackage{setspace}

%%% EXTENDED TeX: so as to not run out of memory (particularly with TIKZ, etc.);
\usepackage{etex}

%%% ENUMERATE For special enumeration specifications (thanks to Joe Chen)
\usepackage{enumitem}

%% FANCY HEADERS: This allows for fancy headers and footers if use command below.  Set
%% \pagestyle to "plain" if prefer the simpler look (just page numbers); 
%%%% THESE ARE ALSO PART OF THE FPSAC STYLE
% \usepackage{fancyhdr}
% \headheight=14pt
% %\pagestyle{plain}
% \pagestyle{fancy}

%%% GRAPHICS: Sample code below; works with jpg, pdf, etc., but not tiff;
\usepackage{graphicx}
% \begin{center}
% \includegraphics[width=4.7in]{graphics.jpg}
% \end{center}

%%% For adding program listings with ``lstlisting'' env; 
\usepackage{listings}

%%% FONTS FROM TeXBook: Fonts from the "Manual", i.e., TeXbook, e.g.,  \dbend sign
\usepackage{manfnt}

%%% To get a nice ``parallel summation'' symbol?? ENDED UP with parallel inside
% \usepackage{mathabx}

% \makeatletter
% \newcommand\incircbin
% {%
%   \mathpalette\@incircbin
% }
% \newcommand\@incircbin[2]
% {%
%   \mathbin%
%   {%
%     \ooalign{\hidewidth$#1#2$\hidewidth\crcr$#1\ovoid$}%
%   }%
% }
% \newcommand{\oeq}{\incircbin{=}}
% \newcommand{\sumpar}{\large \incircbin{\small \parallel}}
% \makeatother

\newcommand{\myparallel}{{\mkern3mu\vphantom{\perp}\vrule height 6pt width 0.8pt depth 0pt\mkern2mu\vrule
height 6pt  width 0.8pt depth 0pt\mkern3mu}}
\DeclareMathOperator*{\foo}{\scalerel*{\maltese}{\sum}}
\DeclareMathOperator*{\barr}{\scalerel*{\maltese}{\textstyle\sum}}
\usepackage{scalerel}
\DeclareMathOperator*{\sumpar}{\scalerel*{\maltese}{\sum}}
\def\parallelsum{\mathop{\rm \maltese}}
\def\parallel{\parallelsum} 
%%\def\sumpar{\kern 0.5em {\myparallel} \kern -2.2em \sum }

%%% FRACTIONS NON-VERTICALLY: Makes fractions in form a/b instead of purely vertical; 
\usepackage{nicefrac}

%%% TEXT POSITION
%%% To get absolute or relative positioning of a block of text or
%%% figure on a page. Useful for posets; see manual online. 
\usepackage{textpos}

%%% To get circled variables in some diagrams. 
\usepackage{tikz} 
\newcommand*\ncirc[1]{\tikz[baseline=(char.base)]{
            \node[shape=circle,draw,inner sep=1.2pt] (char) {#1};}} 
%%% INSTEAD OF CIRCLING, UNDERLING LOOKS BETTER, TAKES LESS SPACE
\def\ncirc{\uline}

%%% TRAM Creates ``tram'' environment for highlighting text w/tiny backgrd dots
%%% Many people don't have this package, so leave commented out unless
%%% needed. 
%\usepackage{tram}

%%% STRIKE OUT TEXT For striking out text using \sout{} command;
\usepackage[normalem]{ulem}

%%% TODO NOTES for Collaborators comments; 
 \usepackage{todonotes}
\definecolor{bananamania}{rgb}{0.98, 0.91, 0.71}
\definecolor{apricot}{rgb}{0.98, 0.81, 0.69}
% \newcommand{\twr}[1]{\todo{\fcolorbox{red}{bananamania}{\color{Blue}TWRV: #1}}}
% \newcommand{\malc}[1]{\todo{\fcolorbox{red}{Apricot}{\color{Blue}MALC: #1}}}
\newcommand{\twr}[1]{\todo[size=\tiny, linecolor=orange, backgroundcolor=blue!20!white,
 bordercolor=red]{\it TWR: #1}}
\newcommand{\gjm}[1]{\todo[size=\tiny, linecolor=blue, backgroundcolor=green!20!white,
 bordercolor=red]{\it Gregg: #1}}
%\newcommand{\malc}[1]{\def\baselinestretch{0.5}\todo{\tiny \it MALC: #1}}
 %%% UNCOMMENT BELOW TO ELIMINATE THE NOTES
 %\long\def\authornote#1{\relax}

%%% URL & REFERENCING COMMANDS, including for DOI and arXiv; 
% \usepackage{url}
% %%% Referencing commands (from Darij) 
% \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue,
%  pdfauthor={Tom Roby}]{hyperref}
% %\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
 \newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}

%%% XY package For simple drawing of diagrams, posets: 
\usepackage[all]{xy}

%%% For NODES in POSETS (with XY) \newmoon, etc. Also \hexagon
\usepackage{wasysym}
\def\lpreg{\hexagon}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% Defines various math operators and other notation I use frequently %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% Random Variables
%\def\mchoose{{\left(\atopwithdelims()\right)}}
\def \bangle{ \atopwithdelims \langle \rangle}
\def\Bern{\mathop{\rm Bern}}
\def\Bin{\mathop{\rm Bin}}
\def\Cov{\mathop{\rm Cov}}
\def\EE{\mathop{{}\mathbb{E}}}
\def\Exp{\mathop{\rm Exp}}
\def\Geom{\mathop{\rm Geom}}
\def\NBin{\mathop{\rm NBin}}
\def\NormDist{\mathop{\mathcal{N}}}
\def\One{\mathop{{}\mathbbm{1}}}
\def\PP{\mathop{{}\mathbb{P}}}
\def\Pois{\mathop{\rm Pois}}
\def\Rot{\mathop{\rm Rot}}
\def\SD{\mathop{\rm SD}}
\def\SS{\S\!\S} 
\def\TE{\exists}
\def\Unif{\mathop{\rm Unif}}
\def\Var{\mathop{\rm Var}}
\def\amaj{\mathop{\rm{amaj}}}
\def\bc#1#2{\left(\kern -2pt{#1\atop #2} \kern -2pt\right)}
\def\bfit#1{{\textit{\textbf{#1}}}}
\def\bij{\;\longleftrightarrow\;}
\def\bull{\noindent $\bullet$\kern 4pt}
\def\clickq{\textbf{ClickQuest:  }}
\def\degrees{$^{\circ}$}
\def\det{\mathop{\rm det}}
\def\eset{\emptyset}
\def\gcd{\mathop{\rm GCD}}
\def\inv{\mathop{\rm inv}}
\def\lcm{\mathop{\rm LCM}}
\def\mchoose{\atopwithdelims\langle \rangle}
\def\multiset#1#2{\ensuremath{\left(\kern-.3em\left(\genfrac{}{}{0pt}{}{#1}{#2}\right)\kern-.3em\right)}}
\def\onlyif{\quad \Longleftarrow \quad }
\def\partitions{\vdash}
\def\rk{\mathop{\rm rk}}
\def\spec{\mathop{\rm spec}}
\def\tr{\mathop{\rm tr}}
\def\type{\mathop{\rm type}}
\def\vol{\mathop{\rm vol}}
\def\zz{\mathbb}
%
%%% Above are TeX-style with \def; Below with LaTeX-style \newcommand
%
\newcommand{\chk}{{\sc \bf X }}
%\newcommand{\divides}{\mid }
\newcommand{\given}{\,\vert \,}
\newcommand{\leg}[2]{\left(\frac{#1}{#2}\right) }
%
%
%%% MOST OF THE ONES BELOW ARE TAKEN OR MODIFIED FROM KEITH'S\dots 
%
%%%General 
\newcommand{\Zn}[1]{\mathbb{Z}/#1\mathbb{Z}}
\newcommand{\Znx}[1]{(\mathbb{Z}/#1\mathbb{Z})^\times}
\newcommand{\X}{\times} 
\newcommand{\set}[2]{\left\{#1 : #2\right\}}          
\newcommand{\sett}[1]{\left\{#1\right\}}                
\newcommand{\nonempty}{\neq\varnothing}
\newcommand{\ds}{\displaystyle}
\newcommand{\abs}[1]{\left| {#1} \right|}
\newcommand{\qedbox}{\rule{2mm}{2mm}}
\newcommand{\aand}{\qquad\hbox{and}\qquad}
\newcommand{\e}{\varepsilon}
\newcommand{\tto}{\rightrightarrows}
\newcommand{\gs}{\geqslant}
\newcommand{\ls}{\leqslant}
%
\renewcommand{\qedsymbol}{\qedbox}
\renewcommand{\tilde}{\widetilde}
\renewcommand{\hat}{\widehat}
\newcommand{\norm}[1]{\left\| #1 \right\|}
\newcommand{\md}[3]{#1\equiv#2\;(\mathrm{mod}\;#3)}     
\newcommand{\gen}[1]{\left\langle #1 \right\rangle}
\newcommand{\zero}{\boldsymbol{0}}
%
\newcommand{\dist}{\operatorname{dist}}
\newcommand{\esssup}{\operatorname{ess\:sup}}
\newcommand{\id}{\operatorname{id}}
\newcommand{\card}{\operatorname{card}}
\renewcommand{\Re}{\operatorname{Re}}
\renewcommand{\Im}{\operatorname{Im}}
%
\newcommand{\dmu}{\:\mathrm{d}\mu}
\newcommand{\dm}{\:\mathrm{d}m}
\newcommand{\dx}{\:\mathrm{d}x}
\newcommand{\dt}{\:\mathrm{d}t}
\newcommand{\dz}{\:\mathrm{d}z}
\newcommand{\dtheta}{\:\mathrm{d}\theta}
\newcommand{\dw}{\:\mathrm{d}w}

%%%Algebra
\newcommand{\Sym}{\operatorname {Sym}}
\newcommand{\Stab}{\operatorname {Stab}}
\newcommand{\M}{\operatorname{M}}
\newcommand{\GL}{\operatorname{GL}}
\newcommand{\SL}{\operatorname{SL}}
\newcommand{\Heis}{\operatorname{Heis}}
\newcommand{\Aff}{\operatorname{Aff}}
\newcommand{\Aut}{\operatorname{Aut}}
\newcommand{\image}{\operatorname{im}}
\newcommand{\Syl}[2]{\operatorname{\emph{Syl}}_{#1}\left(#2\right)}
\newcommand{\Hom}{\operatorname{Hom}}
\newcommand{\Tor}{\operatorname{Tor}}
\newcommand{\Gal}{\operatorname{Gal}}
\newcommand{\ch}{\operatorname{ch}}
\newcommand{\rad}{\operatorname{rad}}
\newcommand{\iso}{\cong}
\newcommand{\normal}{\unlhd}
\newcommand{\semi}{\rtimes}
\newcommand{\Nm}{\operatorname {N}}
\newcommand{\Tr}{\operatorname {Tr}}
\newcommand{\disc}{\operatorname {disc}}
%

%%% With amsthm package, creates environments for nicely formatted,
%%% labeled, and numbered propositions, etc. 
%%% Default {\bf Boldface} title, with italicized  statements; 
\newtheorem{thm}{Theorem}[section]
\newtheorem{claim}[thm]{Claim}
\newtheorem{conj}[thm]{Conjecture}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{lemma}[thm]{Lemma}
\newtheorem{observ}[thm]{Observation}
\newtheorem{open}[thm]{Open Problem}
\newtheorem{prob}[thm]{Problem}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{quest}[thm]{Question}
% Gregg's:
\newtheorem{theorem}[thm]{Theorem}
\newtheorem{example}[thm]{Example}
%\newtheorem{lemma}[thm]{Lemma}
%\newtheorem{claim}[thm]{Claim}
%\newtheorem{remark}[thm]{Remark}
\newtheorem{proposition}[thm]{Proposition}
\newtheorem{corollary}[thm]{Corollary}
\newtheorem{conjecture}[thm]{Conjecture}
\newtheorem{definition}[thm]{Definition}
\newtheorem{problem}[thm]{Problem}
\newtheorem{question}[thm]{Question}
%%% Boldface titles, but text remains Roman
\theoremstyle{definition}
\newtheorem{eg}[thm]{Example}
\newtheorem{defn}[thm]{Definition}
\newtheorem{fact}[thm]{Fact}
%%% Italicized titles, text remains Roman. 
\theoremstyle{remark}
\newtheorem{remark}[thm]{Remark}
\newtheorem{rem}[thm]{Remark}
\newtheorem{note}[thm]{Note}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
	  %%% Perfectly good macros from plain.tex that I want to keep using, %%%
	  %%%	   despite AMS*TeX's dismissive deprecation\dots              %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% We make @ signs act like letters, temporarily, to avoid conflict
%%% between user names and internal control sequences of plain format.
\catcode`@=11
\def\m@th{\mathsurround\z@}
\def\cases#1{\left\{\,\vcenter{\normalbaselines\m@th
    \ialign{$##\hfil$&\quad##\hfil\crcr#1\crcr}}\right.}
\def\matrix#1{\null\,\vcenter{\normalbaselines\m@th
    \ialign{\hfil$##$\hfil&&\quad\hfil$##$\hfil\crcr
      \mathstrut\crcr\noalign{\kern-\baselineskip}
      #1\crcr\mathstrut\crcr\noalign{\kern-\baselineskip}}}\,}
\def\pmatrix#1{\left(\matrix{#1}\right)}
\def\bmatrix#1{\left[\matrix{#1}\right]}
\def\hang{\hangindent 24pt}
\def\d@nger{\medbreak\begingroup\clubpenalty=10000
  \def\par{\endgraf\endgroup\medbreak} %
  \noindent\hang\hangafter=-2
  \hbox to0pt{\hskip-\hangindent\dbend\hfill}}
\outer\def\danger{\d@nger}
%|\def\dd@nger{\medbreak\begingroup\clubpenalty=10000|
%|  \def\par{\endgraf\endgroup\medbreak} \noindent\hang\hangafter=-2|
%|  \hbox to0pt{\hskip-\hangindent\dbend\kern1pt\dbend\hfill}\ninepoint}|
%|\outer\def\ddanger{\dd@nger}|
\def\enddanger{\endgraf\endgroup} % omits the \medbreak

\catcode`@=12 % at signs are no longer letters
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
	     %%% Various single alphanumeric characters in crazy math fonts %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
%%% Symbols for number systems
\newcommand{\FF}{\mathbb F}
\newcommand{\KK}{\mathbb K}
\newcommand{\ZZ}{\mathbb Z}
\newcommand{\RR}{\mathbb R}
\newcommand{\QQ}{\mathbb Q}
\newcommand{\CC}{\mathbb C}
\newcommand{\NN}{\mathbb N}
%
%%%Euler Script Characters
\newcommand{\esa}{\EuScript{A}}
\newcommand{\esb}{\EuScript{B}}
\newcommand{\esc}{\EuScript{C}}
\newcommand{\esd}{\EuScript{D}}
\newcommand{\ese}{\EuScript{E}}
\newcommand{\esf}{\EuScript{F}}
\newcommand{\esg}{\EuScript{G}}
\newcommand{\esh}{\EuScript{H}}
\newcommand{\esi}{\EuScript{I}}
\newcommand{\esj}{\EuScript{J}}
\newcommand{\esk}{\EuScript{K}}
\newcommand{\esl}{\EuScript{L}}
\newcommand{\esm}{\EuScript{M}}
\newcommand{\esn}{\EuScript{N}}
\newcommand{\eso}{\EuScript{O}}
\newcommand{\esp}{\EuScript{P}}
\newcommand{\esq}{\EuScript{Q}}
\newcommand{\esr}{\EuScript{R}}
\newcommand{\ess}{\EuScript{S}}
\newcommand{\est}{\EuScript{T}}
\newcommand{\esu}{\EuScript{U}}
\newcommand{\esv}{\EuScript{V}}
\newcommand{\esw}{\EuScript{W}}
\newcommand{\esx}{\EuScript{X}}
\newcommand{\esy}{\EuScript{Y}}
\newcommand{\esz}{\EuScript{Z}}

%%%Calligraphic Characters
\newcommand{\calA}{\mathcal{A}}
\newcommand{\calB}{\mathcal{B}}
\newcommand{\calC}{\mathcal{C}}
\newcommand{\calD}{\mathcal{D}}
\newcommand{\calE}{\mathcal{E}}
\newcommand{\calF}{\mathcal{F}}
\newcommand{\calG}{\mathcal{G}}
\newcommand{\calH}{\mathcal{H}}
\newcommand{\calI}{\mathcal{I}}
\newcommand{\calJ}{\mathcal{J}}
\newcommand{\calK}{\mathcal{K}}
\newcommand{\calL}{\mathcal{L}}
\newcommand{\calM}{\mathcal{M}}
\newcommand{\calN}{\mathcal{N}}
\newcommand{\calO}{\mathcal{O}}
\newcommand{\calP}{\mathcal{P}}
\newcommand{\calQ}{\mathcal{Q}}
\newcommand{\calR}{\mathcal{R}}
\newcommand{\calS}{\mathcal{S}}
\newcommand{\calT}{\mathcal{T}}
\newcommand{\calU}{\mathcal{U}}
\newcommand{\calV}{\mathcal{V}}
\newcommand{\calW}{\mathcal{W}}
\newcommand{\calX}{\mathcal{X}}
\newcommand{\calY}{\mathcal{Y}}
\newcommand{\calZ}{\mathcal{Z}}

%%%Gothic Characters
\newcommand{\fraka}{\mathfrak{a}}
\newcommand{\frakb}{\mathfrak{b}}
\newcommand{\frakc}{\mathfrak{c}}
\newcommand{\frakd}{\mathfrak{d}}
\newcommand{\frake}{\mathfrak{e}}
\newcommand{\frakf}{\mathfrak{f}}
\newcommand{\frakg}{\mathfrak{g}}
\newcommand{\frakh}{\mathfrak{h}}
\newcommand{\fraki}{\mathfrak{i}}
\newcommand{\frakj}{\mathfrak{j}}
\newcommand{\frakk}{\mathfrak{k}}
\newcommand{\frakl}{\mathfrak{l}}
\newcommand{\frakm}{\mathfrak{m}}
\newcommand{\frakn}{\mathfrak{n}}
\newcommand{\frako}{\mathfrak{o}}
\newcommand{\frakp}{\mathfrak{p}}
\newcommand{\frakq}{\mathfrak{q}}
\newcommand{\frakr}{\mathfrak{r}}
\newcommand{\fraks}{\mathfrak{s}}
\newcommand{\frakt}{\mathfrak{t}}
\newcommand{\fraku}{\mathfrak{u}}
\newcommand{\frakv}{\mathfrak{v}}
\newcommand{\frakw}{\mathfrak{w}}
\newcommand{\frakx}{\mathfrak{x}}
\newcommand{\fraky}{\mathfrak{y}}
\newcommand{\frakz}{\mathfrak{z}}

\newcommand{\frakA}{\mathfrak{A}}
\newcommand{\frakB}{\mathfrak{B}}
\newcommand{\frakC}{\mathfrak{C}}
\newcommand{\frakD}{\mathfrak{D}}
\newcommand{\frakE}{\mathfrak{E}}
\newcommand{\frakF}{\mathfrak{F}}
\newcommand{\frakG}{\mathfrak{G}}
\newcommand{\frakH}{\mathfrak{H}}
\newcommand{\frakI}{\mathfrak{I}}
\newcommand{\frakJ}{\mathfrak{J}}
\newcommand{\frakK}{\mathfrak{K}}
\newcommand{\frakL}{\mathfrak{L}}
\newcommand{\frakM}{\mathfrak{M}}
\newcommand{\frakN}{\mathfrak{N}}
\newcommand{\frakO}{\mathfrak{O}}
\newcommand{\frakP}{\mathfrak{P}}
\newcommand{\frakQ}{\mathfrak{Q}}
\newcommand{\frakR}{\mathfrak{R}}
\newcommand{\frakS}{\mathfrak{S}}
\newcommand{\frakT}{\mathfrak{T}}
\newcommand{\frakU}{\mathfrak{U}}
\newcommand{\frakV}{\mathfrak{V}}
\newcommand{\frakW}{\mathfrak{W}}
\newcommand{\frakX}{\mathfrak{X}}
\newcommand{\frakY}{\mathfrak{Y}}
\newcommand{\frakZ}{\mathfrak{Z}}

%%%Lowercase Bold Letters
\newcommand{\bfa}{\mathbf{a}}
\newcommand{\bfb}{\mathbf{b}}
\newcommand{\bfc}{\mathbf{c}}
\newcommand{\bfd}{\mathbf{d}}
\newcommand{\bfe}{\mathbf{e}}
\newcommand{\bff}{\mathbf{f}}
\newcommand{\bfg}{\mathbf{g}}
\newcommand{\bfh}{\mathbf{h}}
\newcommand{\bfi}{\mathbf{i}}
\newcommand{\bfj}{\mathbf{j}}
\newcommand{\bfk}{\mathbf{k}}
\newcommand{\bfl}{\mathbf{l}}
\newcommand{\bfm}{\mathbf{m}}
\newcommand{\bfn}{\mathbf{n}}
\newcommand{\bfo}{\mathbf{o}}
\newcommand{\bfp}{\mathbf{p}}
\newcommand{\bfq}{\mathbf{q}}
\newcommand{\bfr}{\mathbf{r}}
\newcommand{\bfs}{\mathbf{s}}
\newcommand{\bft}{\mathbf{t}}
\newcommand{\bfu}{\mathbf{u}}
\newcommand{\bfv}{\mathbf{v}}
\newcommand{\bfw}{\mathbf{w}}
\newcommand{\bfx}{\mathbf{x}}
\newcommand{\bfy}{\mathbf{y}}
\newcommand{\bfz}{\mathbf{z}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
			 %%% MACROS PARTICULAR TO THIS DOCUMENT %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\whP}{{\widehat{P}}}
\newcommand{\rowmotion}{\rho}
\newcommand{\iscovered}{\lessdot}
\newcommand{\covers}{\gtrdot}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 			     %%% BACK TO FPSAC BOILERPLATE %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

 
%% 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 give a formula in terms of families of non-intersecting lattice paths for iterated
actions of the \textit{birational rowmotion} map on a product of two chains, equivalently a rectangle.  This allows us
to give a much simpler direct proof of the key fact that the period of this map on a product of
chains of lengths $r$ and $s$ is $r+s+2$ (first proved by D.~Grinberg and the second
author) as well as other consequences, as explained in~\cite{MR18}.
%\cblu{as well as other consequences in~\cite{MR18}.}

% \textit{Birational rowmotion} is an action on the space of assignments of rational functions
% to the elements of a finite partially-ordered set (poset).  It is lifted from the
% well-studied \textit{rowmotion} map on order ideals (equivariantly on antichains) of a poset
% $P$~\cite{brouwer-schrijver, CF95,Pan09,PR13,RuSh12,RuWa15+,SW12}, which when iterated on
% special posets, has unexpectedly nice properties in terms of periodicity, cyclic sieving,
% and homomesy (statistics whose averages over each orbit are constant)~\cite{PR13}.
% In this context, rowmotion appears to be related to Auslander-Reiter translation on certain
% quivers~\cite{Yil17}, and birational rowmotion to $Y$-systems of type $AA$ described in
% Zamolodchikov periodicity~\cite[Section 4.4]{Rob16}. 
}

%% 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{
birational rowmotion, 
dynamical algebraic combinatorics,
%homomesy, 
periodicity
%toggling, 
}

%% 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
\usepackage[backend=bibtex]{biblatex}
\addbibresource{37-Musiker-Roby.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{A section}

% \lipsum[3]

% \begin{equation}\label{eqn:eq1}
% \int_0^\infty \exp(-x)dx = 1.
% \end{equation}

% \begin{lem}\label{lem:lem1}
% \lipsum[11]
% \end{lem}

% \lipsum[10]

% \begin{figure}
% \centering
% \includegraphics[width=0.5\textwidth]{plot}
% \caption{A plot of a function.}
% \label{fig:plot}
% \end{figure}

% \subsection{A subsection}

% \lipsum[5]

% \begin{align*}
% 1 + 1 + 1 &= 2 + 1 \\ &= 3.
% \end{align*}

% \subsubsection{A subsubsection}

% \lipsum[17]

% Here is a citation~\cite{greenwade93} with URL. Here is another
% citation~\cite{MR4}, which is the earliest-numbered Math Review with a
% functioning DOI: MR0000004. Finally, a reference to
% equation~\eqref{eqn:eq1}. And a reference to Figure~\ref{fig:plot}.

% \acknowledgements{\lipsum[20]}

%% 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

\section{Introduction}

% We give a formula in terms of families of non-intersecting lattice paths for iterated
% actions of the \textit{birational rowmotion} map $\rho_{B}$ (defined below) on a product of two chains.
% This allow us to give a direct and significantly simpler proof that $\rho_{B}$ is periodic,
% with the same period as ordinary (combinatorial) rowmotion, from which it is lifted.  

Birational rowmotion is an action on the space of assignments of rational functions to the
elements of a finite partially-ordered set (poset).  It is lifted from the well-studied
\textit{rowmotion} map on order ideals 
(equivariantly on antichains) of a poset $P$~\cite{brouwer-schrijver,
CF95,Pan09,PR13,RuWa15+,SW12}, which when iterated on special posets has unexpected % unexpectedly 
nice properties in terms of periodicity, cyclic sieving, and homomesy.  Rowmotion is first lifted to a piecewise-linear
action of the \textit{order polytope}~\cite{Stan86} of $P$, i.e., $\{f:P\rightarrow [0,1]: f
\text{ is order preserving}\}$.   This is then detropicalized (a.k.a.\ ``geometricized'') to
a birational map, as detailed in~\cite{EiPr13,EiPr14}.  Theorems proven at the birational
level generally imply their corresponding theorems at the piecewise-linear, and then  the
combinatorial level, but not vice-versa.  For example, the only proof available as of this
writing that piecewise-linear rowmotion is periodic uses the corresponding result for
birational rowmotion.  

Rowmotion appears to behave particularly nicely for posets associated with representations
of finite-dimensional Lie algebras, e.g., root posets and minuscule posets. Armstrong,
Stump, and Thomas proved a conjecture of Panyushev~\cite[Conjecture 2.1(iii)]{Pan09} that antichain-cardinality is a homomesic
with respect to rowmotion action on antichains of root posets, i.e., for every orbit $\calO$, the value
$\frac{1}{\#\calO}\sum_{A\in \calO} \#A$ is a constant, independent of $\calO$.  This was
one of the first explicit statements of a type later isolated by Propp and the second author
as the \textbf{homomesy phenomenon} \cite{PR13}.  

Iterating birational rowmotion also displays interesting and unexpected dynamics for
certain ``nice'' posets, particularly rectangular ones (i.e., $P=[0,r]\times [0,s]$, the
product of two finite chains).  The order of birational rowmotion is (unexpectedly) the same is that
for ordinary rowmotion, namely $r+s+2$, a fact whose first
proof~\cite[Theorem 30]{GrRo15} was
nontrivial.  Here ordinary rowmotion appears to be related to Auslander--Reiten translation on certain
quivers~\cite{Yil17}, and birational rowmotion to $Y$-systems of type $A_m \times A_n$ described in
Zamolodchikov periodicity~\cite[Section 4.4]{Rob16} and to the recent notion of \emph{$R$-systems}~\cite{GaPy17}.
The orbits of these actions have natural \textit{homomesic}
statistics~\cite{PR13,EiPr13,EiPr14}. 
%, though that is not our focus here. 
In \cite{MR18}, we show an instance of birational file homomesy, generalizing a
combinatorial result of \cite{PR13}. 

Proofs of periodicity and homomesy tend to be rather indirect, and often involve
finding an equivariant bijection between rowmotion and an action that is easier to
understand, or at least already better understood.  
% At the combinatorial level rowmotion
% can be equivariantly bijected to cyclic rotation of bitstrings via the Stanley-Thomas
%word~\cite[Section 7]{PR13}.  
For birational rowmotion, Grinberg and the second author
parameterize poset labelings by ratios of determinants, then show periodicity via certain 
Pl\"ucker relations (overcoming a number of technical hurdles)~\cite{GrRo15}.  The formula
via non-intersecting lattice paths in this paper gives a more direct proof.

The paper is organized as follows.  In Section~2 we give basic definitions, state our main
result (Theorem~\ref{thm:main}), and give an extended illustrative example; we also prove as
corollaries the main results of \cite{GrRo15}, namely the periodicity and reciprocity of birational
rowmotion.  In Section~3, we outline the proof of our main theorem, leaving details for the arXiv preprint~\cite{MR18}.
Further results, i.e., birational file homomesy, also appear therein.
%In Section~3 we outline a proof by way of some colorful combinatorial
%bijections for pairs of NILPs, \cblu{similar to~\cite{FuKl01}.} Details are in the arXiv preprint~\cite{MR18}.

The initial impetus for this paper came when the authors were both at a workshop on
``Dynamical Algebraic Combinatorics'' hosted by the American Institute of Mathematics (AIM)
in March~2015. We are grateful for AIM's hospitality that week, as well as for helpful
conversations with Max Glick, Darij Grinberg, Christian Krattenthaler, James Propp, Pasha
Pylyavskyy, and Richard Stanley. 
Computations of birational rowmotion programmed by Grinberg in SageMath~\cite{sage} were of
enormous assistance in helping us discover the main formula. 

\section{Definitions and main result}

% Birational rowmotion can be defined for any
% labeling of the elements of a finite poset by elements of a field.  The original motivation for
% considering this came from work of Einstein and Propp~\cite{EiPr13, EiPr14}, which explained
% how to lift the notion of \textbf{toggles}: first from the combinatorial setting to the
% piecewise-linear setting, and second from the piecewise-linear setting to the birational
% setting via ``detropicalization''.  This allowed them to define piecewise-linear and
% birational analogues of rowmotion, which they wished to study from the standpoint of
% homomesy, whose traditional definition requires a periodic action.  So they were eager to
% have a proof of periodicity, which was first supplied in~\cite{GrRo15}.  Another exposition
% of these ideas and further background can be found 
% in~\cite[Section 4]{Rob16}.  For basic information and notation about posets, we direct the reader
% to~\cite[Chapter 3]{Stan11}.  

\begin{definition}\label{def:bitoggle}
Let $P$ be any finite poset, and let $\whP$ be $P$ with an additional global maximum (denoted
$\hat 1 $) and an additional global minimum (denoted $\hat 0 $) adjoined.  
Let $\KK$ be any field, and $f\in \KK^{\whP}$ be any $\KK$-labeling of $\whP$.
We define the \textbf{birational toggle} 
$T_{v}:\mathbb{K}^{\widehat{P}}\dashrightarrow\mathbb{K}^{\widehat{P}}$
at $v\in P$ by
$$
(T_{v} f) (y) = f(y) \mathrm{~~~~}\text{if} \mathrm{~~~~} y \not = v;  \mathrm{~~~~}
(T_{v} f) (y) = \dfrac{1}{f\left(  v\right)  }\cdot\dfrac{\sum\limits_{\substack{w\in
\widehat{P};\\w\lessdot v}}f\left(  w\right)  }{\sum\limits_{\substack{z\in
\widehat{P};\\z\gtrdot v}}\dfrac{1}{f\left(  z\right)  }}
\mathrm{~~~~}\text{if} \mathrm{~~~~} y = v; 
$$
%\begin{equation}
%\left(  T_{v}f\right)  \left(  y\right)  =\left\{
%\begin{array}{cc}
%f\left(  y\right)  ,\ \ \ \ \ \ \ \ \ \ & \text{if }y\neq v;\\[8pt]
% & \\
%\dfrac{1}{f\left(  v\right)  }\cdot\dfrac{\sum\limits_{\substack{w\in
%\widehat{P};\\w\lessdot v}}f\left(  w\right)  }{\sum\limits_{\substack{z\in
%\widehat{P};\\z\gtrdot v}}\dfrac{1}{f\left(  z\right)  }}
%,\ \ \ \ \ \ \ \ \ \ & \text{if }y=v
%\nonumber
%\end{array}
%\right.
%\end{equation}
for all $y \in \whP$.
Note that this rational map $T_{v}$ is
well-defined, because the right-hand side is
well-defined on a Zariski-dense open subset of $\mathbb{K}^{\widehat{P}}$.
%Finally, we define \textbf{birational rowmotion} by $\rowmotion_{B}: = T_{v_{1}}T_{v_{2}}\dots
%T_{v_{n}}: \KK^{\whP}\dashrightarrow \KK^{\whP}$, where $v_{1},v_{2},\dotsc ,v_{n}$ is any
%linear extension of $P$. (``Togging at each element of $P$ from top to bottom.'')   
\end{definition}

The toggle map $T_{v}$ changes only the label of the poset at $v$, and does this by 
(a) \emph{inverting} the label at $v$, (b) multiplying by the \emph{sum} of the labels
at vertices \emph{covered by} $v$, and (c) multiplying by the \emph{parallel sum} of
the labels at vertices \emph{covering} $v$. Because toggles in the tropical category involve
both the operations of $\min$ and $\max$, one of these is lifted to $+$ and the other to
the (associative) parallel sum operation $\parallel$, defined by
$a\parallel b : = \frac{1}{\frac{1}{a}+\frac{1}{b}}$ (when $a,b\neq 0$ and $a\neq -b$).    
%
\textbf{Birational Rowmotion}
$\rowmotion_{B}$ is then defined as 
$\rowmotion_{B}: = T_{v_{1}}T_{v_{2}}\dots T_{v_{n}}: \KK^{\whP}\dashrightarrow \KK^{\whP}$ where $v_{1},v_{2},\dotsc ,v_{n}$ is any linear extension of $P$, i.e., by togging at each element of $P$ from top to bottom, as for ordinary rowmotion.

%Birational rowmotion $\rowmotion_{B}$ is then defined, as for ordinary rowmotion,  by
%toggling once at every element from top to bottom. (Some authors define rowmotion by toggling from bottom to
%top, yielding the inverse of our map.)  

The main result of our paper is a formula in terms of families of non-intersecting lattice
paths for the $k$th iteration, $\rho_{B}^{k}$ of birational rowmotion on the product of two
chains. For our purposes, it is more convenient to initially coordinatize our poset $P$ as
$[0,r]\times [0,s]$ (where $[0,n] = \{0,1,2,\dots, n\}$), with minimal element $(0,0)$, maximal element $(r,s)$ and covering relations: 
$(i,j) \lessdot (k,\ell)$ if and only if (1) $i=k$ and $\ell  = j +1$ or (2) $j=\ell$ and $k
= i+1$. We then initially assign the generic label $x_{ij}$ (a.k.a.\ $x_{i,j}$) to the element $(i,j)$, and the
label 1 to the elements $\hat{0}$ and $\hat{1}$.  No essential generality is lost by
assigning 1 to the elements of $\whP -P$ (a ``reduced
labeling'')~\cite[Section 4]{GrRo15} or
\cite[Section 4]{EiPr13}, but it simplifies our formulae and figures, which will generally just
display the labelings of $P$ itself, not of $\whP$.  

\begin{eg}\label{eg:Hasse}
The Hasse diagram of $P = [0,2]\times [0,3]$ is shown on the left, and the generic initial
labeling $f$ of $\whP$ is shown on the right.  
\vspace{-1em}
\[
\xymatrixrowsep{0.4pc}\xymatrixcolsep{0.08pc}\xymatrix{
&&& & (2,3) \ar@{-}[rd] \ar@{-}[ld] & \\
&&& (2,2) \ar@{-}[rd] \ar@{-}[ld] & & (1,3) \ar@{-}[ld] \ar@{-}[rd]\\
P=&&(2,1) \ar@{-}[rd] \ar@{-}[ld] & & (1,2) \ar@{-}[ld] \ar@{-}[rd] && (0,3) \ar@{-}[ld] & \\
&(2,0)  \ar@{-}[rd] && (1,1) \ar@{-}[rd] \ar@{-}[ld] & & (0,2) \ar@{-}[ld] && && && f=\\ 
&& (1,0)  \ar@{-}[rd] && (0,1) \ar@{-}[ld] & &\\
&&& (0,0)
}
\xymatrixrowsep{0.4pc}\xymatrixcolsep{0.10pc}\xymatrix{
&&& 1 \ar@{-}[d] \\ 
&& & x_{23} \ar@{-}[rd] \ar@{-}[ld] & \\
&& x_{22} \ar@{-}[rd] \ar@{-}[ld] & & x_{13} \ar@{-}[ld] \ar@{-}[rd]\\
&x_{21} \ar@{-}[rd] \ar@{-}[ld] & & x_{12} \ar@{-}[ld] \ar@{-}[rd] && x_{03} \ar@{-}[ld] & \\
x_{20}  \ar@{-}[rd] && x_{11} \ar@{-}[rd] \ar@{-}[ld] & & x_{02} \ar@{-}[ld] && \\ 
& x_{10}  \ar@{-}[rd] && x_{01} \ar@{-}[ld] & &\\
&& x_{00} \ar@{-}[d]\\ 
&& 1
}
\]
\end{eg}

\vspace{-2em}
\begin{eg}
Consider the $4$-element poset $P:= \left\{  0,1\right\}  \times\left\{
0,1\right\}  $, i.e., the product of two chains of length one, with the subscript-avoiding
labeling shown below.  
%
Then $f$ and the output of toggling $f$ at the top element $(1,1)$ of $P$ are
as follows:
\[
\xymatrixrowsep{0.6pc}\xymatrixcolsep{0.20pc}\xymatrix{
& &1\ar@{-}[d] & \\
& & z \ar@{-}[rd] \ar@{-}[ld] & \\
f = \ & x \ar@{-}[rd] & & y \ar@{-}[ld] \\
& & w \ar@{-}[d] \\
& & 1 & 
} 
\qquad  \qquad \raisebox{-55pt}{$\rightsquigarrow$} \qquad \qquad 
\xymatrixrowsep{0.5pc}\xymatrixcolsep{0.20pc}\xymatrix{
& &1\ar@{-}[d] & \\
& & {\color{red} \frac{\left(x+y\right)}{z}} \ar@{-}[rd] \ar@{-}[ld] & \\
T_{\left(  1,1\right)  } f = \ & x \ar@{-}[rd] & & y \ar@{-}[ld] \\
& & w \ar@{-}[d] & \\
& & 1 &
}
\]
Since the labels at $\hat{0}$ and $\hat{1}$ never vary, we suppress displaying them in all future examples
of birational rowmotion. (They are still involved in the computations.)   
Computing successively $T_{\left(  0,1\right)
}T_{\left(  1,1\right)  }f$, then
$T_{\left(  1,0\right)  }T_{\left(  0,1\right)  }T_{\left(  1,1\right)
}f$, and %finally 
$\rho_{B}f=T_{\left(  0,0\right)  }T_{\left(  1,0\right)  }T_{\left(  0,1\right)
}T_{\left(  1,1\right)  }f$ gives: 
\[
\xymatrixrowsep{0.9pc}\xymatrixcolsep{0.20pc}\xymatrix{
& & \frac{\left(x+y\right)}{z} \ar@{-}[rd] \ar@{-}[ld] & \\
\ & x \ar@{-}[rd] & & {\color{red} \frac{\left(x+y\right)w}{yz}} \ar@{-}[ld] \\
& & w  & ,\\
}
\quad 
\xymatrixrowsep{0.9pc}\xymatrixcolsep{0.20pc}\xymatrix{
& & \frac{\left(x+y\right)}{z} \ar@{-}[rd] \ar@{-}[ld] & \\
& {\color{red} \frac{\left(x+y\right)w}{xz}} \ar@{-}[rd] & & \frac{\left(x+y\right)w}{yz} \ar@{-}[ld] \quad \text{ and}\\
& & w  & ,\\
}\quad 
\xymatrixrowsep{0.9pc}\xymatrixcolsep{0.20pc}\xymatrix{
& & \frac{\left(x+y\right)}{z} \ar@{-}[rd] \ar@{-}[ld] & \\
& \frac{\left(x+y\right)w}{xz} \ar@{-}[rd] & & \frac{\left(x+y\right)w}{yz} ~~~~~. \ar@{-}[ld] \\
& & {\color{red} \frac{1}{z}}  & \\
}
\]
By repeating this
procedure (or just substituting the labels of $\rho_{B}f$ obtained as variables), we
can compute the iterated maps $\rho_{B}$, $\rho_{B}^{2}f$, $\rho_{B}^{3}f, \dots $ obtaining
\begin{align*}
&
\xymatrixrowsep{0.1pc}\xymatrixcolsep{0.10pc}
\xymatrix{ & \frac{\left(x+y\right)}{z} \ar@{-}[rd] \ar@{-}[ld] & \\ 
 \frac{\left(x+y\right)w}{xz} \ar@{-}[rd] & & \frac{\left(x+y\right)w}{yz} \ar@{-}[ld] \\ 
 & \frac{1}{z}  & ,}\ \ \ \ \ \ \ \ \ \ 
\xymatrixrowsep{0.1pc}\xymatrixcolsep{0.10pc}
%\xymatrixrowsep{0.9pc}\xymatrixcolsep{0.20pc}
\xymatrix{ & \frac{\left(x+y\right)w}{xy} \ar@{-}[rd] \ar@{-}[ld] & \\   
 \frac{1}{y} \ar@{-}[rd] & & \frac{1}{x} \ar@{-}[ld] \\ 
& \frac{z}{x+y}  & ,}
&
\xymatrixrowsep{0.1pc}\xymatrixcolsep{0.10pc}
%\xymatrixrowsep{0.9pc}\xymatrixcolsep{0.20pc}
\xymatrix{ &
\frac{1}{w} \ar@{-}[rd] \ar@{-}[ld] & \\ 
 \frac{yz}{\left(x+y\right)w}
\ar@{-}[rd] & & \frac{xz}{\left(x+y\right)w} \ar@{-}[ld] \\ 
 & \frac{xy}{\left(x+y\right)w}& ,}\ \ \ \ \ \ \ \ \ \
\xymatrixrowsep{0.1pc}\xymatrixcolsep{0.10pc}
%\xymatrixrowsep{0.9pc}\xymatrixcolsep{0.20pc}
\xymatrix{ & z
\ar@{-}[rd] \ar@{-}[ld] & \\
 x \ar@{-}[rd] & & y \ar@{-}[ld] \\ 
& w  & .}
\end{align*}  
Notice that $\rho_B^{4}f=f$, which generalizes to $\rho_{B}^{r+s+2}f=f$ for $P=[0,r]\times
[0,s]$ (Corollary~\ref{cor:periodicity}). 
More subtly, as one iterates $\rho_{B}$, the labels at certain poset elements are reciprocals
of others occuring earlier at the antipodal position in the poset $P$.  (See
Corollary~\ref{cor:reciprocity}.) 
% For example,   
% %the values 
% $\left(  \rho_Bf\right)  \left(  \left(  0,0\right)  \right)  = 1/f(1,1)$,
% $\left(  \rho_B^{2}f\right)  \left(  \left(  0,1\right)  \right) = 1/f(1,0) $, $\left(
% \rho_B^{2}f\right)  \left(  \left(  1,0\right)  \right) = 1/f(0,1)  $, $\left(
% \rho_B^{3}f\right)  \left(  \left(  1,1\right)  \right) = 1/f(0,0)  $, and these induce further 
% relations such as 
% $\left(  \rho_B^{2}f\right)  \left(  \left(  0,0\right)  \right) = 1/\left(  \rho_Bf\right)  \left(  \left(  1,1\right)  \right)$.
% % each have the form $\dfrac{1}{f\left(  v\right)  }$ for some $v\in P$. 
% This \textquotedblleft reciprocity\textquotedblright\ phenomenon turns out to
% generalize to arbitrary rectangular posets~\cite[Theorem~32]{GrRo15}.  
 

\end{eg}



\subsection{Our Main Result: A lattice-path formula for birational rowmotion}

% Here we state our main result, Theorem~\ref{thm:main}.  It gives a formula for any iteration
% of $\rho_{B}$ on a product of two chains, as a 
% ratio of polynomials in $A$-variables (simple fractions of the $x_{ij}$'s), where each
% monomial corresponds to a family of non-interesecting lattice paths. 
% As a corollary, we give a simpler
% and more direct proof that the period of this map on a product of chains of lengths
% $r$ and $s$ is $r+s+2$ and that it satisfies the reciprocity exemplified by the previous
% example.  Each of these results was first proved by D.~Grinberg and the second author~\cite[Thm.~30,
% Thm~32]{GrRo15}, inspired by Volkov's proof of the ``rectangular'' (type-$AA$) Zamolodchikov
% conjecture for $Y$-systems~\cite{Volk06}.  The basic idea is to construct ``Grassmannian
% parameterizations'' of generic labellings of such a poset by matrices, which can then be
% used to track iterations of the map.  Both the proof in \cite{GrRo15} and here rely on
% Pl\"ucker-like lemmas in their individual contexts.  

A simple change of variables in the initial labeling greatly facilitates our ability to write
our formula.  Let 
\begin{equation}\label{eq:Aij}
A_{ij} := \frac{\sum_{z\lessdot (i,j)} x_{z}}{x_{(i,j)}}=\frac{x_{i,j-1} + x_{i-1,j}}{x_{ij}}, 
\end{equation}
where we set $A_{i0} = \frac{x_{i-1,0}}{x_{i,0}}$, $A_{0j} = \frac{x_{0,j-1}}{x_{0,j}}$ 
%and $x_{i,j}=0$ for $(i,j)\not \in P$ 
and $A_{00} = \frac{1}{x_{00}}$ (working in
$\whP$). 

We define a \textbf{lattice path of length $\mathbf{k}$} within $P=[0,r]\times [0,s]$ to be
a sequence $v_{1}, v_{2}, \dotsc , v_{k}$ of elements of $P$ such that each difference of
successive elements $v_{i}-v_{i-1}$ is either $(1,0)$ or $(0,1)$ for each $i\in [k]$.  We call
a collection of lattice paths \textbf{non-intersecting} if no two of them share a common
vertex.  We will frequently abbreviate \textbf{non-intersecting lattice paths} as
\textbf{NILP}. 

\begin{defn}\label{def:phi}
Given a triple $(k,m,n)\in \NN^{3}$ (where $\NN$ denotes the nonnegative integers
$\{0,1,2,\dots \}$) with $k\leq \min \{r-m, s-n \}+1$, we define 
a polynomial $\varphi_k(m,n)$ in terms of the $A_{ij}$'s as follows: 

1) Let $\bigvee_{(m,n)} :=\{(u,v): (u,v)\geq (m,n)\}$ be the \emph{principal order
filter at $(m,n)$} in $P$, which is isomorphic to $[r-m]\times [s-n]$.  Set
$\lpreg_{(m,n)}^{k} : = \{(u,v)\in \bigvee_{(m,n)}: 
m+n+k-1\leq u+v\leq r+s-k+1 \}$, the \emph{rank-selected
subposet} consisting of all elements in $\bigvee_{(m,n)}$ whose rank (within
$\bigvee_{(m,n)}$) is at least $(k-1)$ and whose corank is at least $(k-1)$.  

2) More specifically, let $s_1, s_2, \dots, s_k$ be the $k$ minimal elements and
$t_1, t_2, \dots, t_k$ be the $k$ maximal elements of $\lpreg_{(m,n)}^{k}$,
i.e.,  $s_{\ell } = (m+k-\ell ,n+\ell-1 )$ and $t_{\ell } = \left(r-\ell +1,s-k+\ell
\right)$ for $\ell  \in [k]$.  (When $k=0$, there are no 
$s_{\ell}$'s or $t_{\ell}$'s.)  Our condition that $k\leq \min \{r-m, s-n \}+1$ insures that
these points all lie within $\lpreg_{(m,n)}^{k}$.  

3) Let $S_k(m,n)$ be the set of families of NILPs in $\lpreg_{(m,n)}^{k}$ 
from $\{s_1,s_2,\dots, s_k\}$ to $\{t_1,t_2,\dots, t_k\}$.  We let $\calL = \{L_1,L_2,\dots, 
L_k \}\in S_{k}(m,n)$ denote such a family.

4) Define 
\begin{equation}\label{eq:phi}
\varphi_k(m,n) : = \sum_{ \calL  \in S_{k}(m,n)}
\hspace{2em}\prod_{\stackrel{(i,j) \in \lpreg_{(m,n)}^{k}}{(i,j) \not \in L_1 \cup L_2 \cup \dots \cup
L_k}} A_{ij}. 
\end{equation}

5) Finally, set $[\alpha ]_{+} : = \max \{ \alpha ,0 \}$ and let $\mu^{(a,b)}$ be the transformation
that takes a 
rational function in $\{A_{u,v}\}$ and simply shifts each index in 
each factor of each term: $A_{u,v}\mapsto A_{u-a,v-b}$.
\end{defn}

% \begin{defn}\label{def:phi}
% Given a triple $(k,m,n)\in \NN^{3}$ (where $\NN$ denotes the nonnegative integers
% $\{0,1,2,\dots \}$), we define 
% a polynomial ${\varphi_k(m,n)}$ % \varphi can't be bolded
%  in terms of the $A_{ij}$'s as follows: 

% 1) Let $\bigvee_{(m,n)} :=\{(u,v): (u,v)\geq (m,n)\}$ be the \emph{principal order
% filter at $(m,n)$} in $P$, and set $\lpreg_{(m,n)}^{k} : = \{(u,v)\in \bigvee_{(m,n)}:
% m+n+k-1\leq u+v\leq r+s-k+1 \}$, the \emph{rank-selected
% subposet}, consisting of all elements in $\bigvee_{(m,n)}$ whose rank (within
% $\bigvee_{(m,n)}$) is at least $k-1$ and whose corank is at most $k-1$.  

% 2) More specifically, let $s_1, s_2, \dots, s_k$ be the $k$ minimal elements and
% $t_1, t_2, \dots, t_k$ be the $k$ maximal elements of $\lpreg_{(m,n)}^{k}$,
% i.e.,  $s_{\ell } = (m+k-\ell ,n+\ell-1 )$ and $t_{\ell } = \left(r-\ell +1,s-k+\ell
% \right)$ for $\ell  \in [k]$.  (When $k=0$, there are no 
% $s_{\ell}$'s or $t_{\ell}$'s.) 

% 3) Let $S_k(m,n)$ be the set of all $k$-tuples of NILPs in $\lpreg_{(m,n)}^{k}$ 
% from $\{s_1,s_2,\dots, s_k\}$ to $\{t_1,t_2,\dots, t_k\}$.  We let $\calL = (L_1,L_2,\dots 
% L_k)\in S_{k}^{k}(m,n)$ denote a $k$-tuple of such lattice paths. 

% 4) Define 
% \begin{equation}\label{eq:phi}
% \varphi_k(m,n) : = \sum_{ \calL  \in S_{k}^{k}(m,n)}
% \hspace{2em}\prod_{\stackrel{(i,j) \in \lpreg_{(m,n)}^{k}}{(i,j) \not \in L_1 \cup L_2 \cup \dots \cup
% L_k}} A_{ij}. 
% \end{equation}

% 5) Finally, set $[\alpha ]_{+} : = \max \{ \alpha ,0 \}$ and let $\mu^{(a,b)}$ be the operator
% that takes a 
% rational function in $\{A_{(u,v)}\}$ and %simply 
% shifts each index in 
% each factor of each term: $A_{(u,v)}\mapsto A_{(u-a,v-b)}$
% % \footnote{{\color{red}DOUBLE-CHECK THIS TRANSLATION IS CORRECT WITH NEW CONVENTION - or -
% % update later formulas so that this $\mu^{(a,b)}$-shift can be rewritten as
% % $(u,v)-(a,b)$.}}.   
% \end{defn}


We are now ready to state our main result.

% \begin{theorem}\label{thm:main}
% [OLD] Apply $\rho_B$ to the top $t$ ranks of $P$ (where $t < \min(r,s)$) followed by an
% application of $\rho_B$ to the top $(t-1)$ ranks and iterating so that we apply $\rho_B$ to
% fewer and fewer of the topmost ranks as we proceed.  After $(k+1)$ such applications of
% $\rho_B$ to the elements of the top $(t-k)$ ranks of $P$ (and further applications to the
% lower ranks), we let $\rho_B^k(i,j)$ denote the rational function associated to the poset
% element $(i,j)$.  We obtain the following formula for $\rho_B^{k+1}(i,j)$: 
% $$\rho_B^k(i,j) = \frac{\varphi_k(i+k,j+k)}{\varphi_{k+1}(i+k,j+k)}$$ where 
% $\varphi_k(m,n)$ is the sum defined above.  
% \end{theorem}

\begin{theorem}\label{thm:main} Fix $k\in [0, r+s+1]$, and let
$\rho_B^{k+1}(i,j)$ denote the rational function in $\KK[x_{u,v}]$ associated to the poset element $(i,j)$
after $(k+1)$ applications of the birational rowmotion map to the generic initial labeling
of $P = [0,r] \times [0,s]$.  
Set $M = [k-i]_+ + [k-j]_+$.  We obtain the following formula for $\rho_B^{k+1}(i,j)$: 

\bfit{(a)}  When $M\leq k$:

\begin{equation}\label{eq:main1}
\rho_B^{k+1}(i,j) = \mu^{([k-j]_+,
[k-i]_+)}\left(\frac{\varphi_{k-M}(i-k+M,j-k+M)}{\varphi_{k-M+1}(i-k+M,j-k+M)}\right)
\end{equation}

where $\varphi_t(v,w)$ and $\mu^{(a,b)}$ are as defined in 4) and 5) of Definition~\ref{def:phi}.  

\bfit{(b)} When $M \geq k$: 
%, (i.e., $i+j<k$) 
%% and $k<r+s+2$: 
\[
\rho_{B}^{k+1}(i,j) = 1/\rho_{B}^{k-i-j}(r-i, s-j)
\]
where $\rho_{B}^{k-i-j}(r-i,s-j)$ is well-defined by part (a). 
\end{theorem}
Note that these formulas agree when $M=k$. 
% \begin{rem}
% Note that our formulae in (a) and (b) agree when $M=k$, as we will see as part of
% Claim~\ref{claim:Mk}.  Additionally, we see 
% that the formula $\rho_{B}^{k-i-j}(r-i,s-j)$ satisfies the hypotheses for part (a) as
% follows: First by letting $K = k-i-j-1$, $I = r-i$ and $J=s-j$, we see that the formula $\rho_{B}^{k-i-j}(r-i,s-j) = \rho_B^{K+1}(I,J)$ is well-defined by part (a) if $[K-I]_+ + [K-J]_+ \leq K$.  Second, we assume that $(K-I)$ or $(K-J)$ are both positive, because this inequality holds automatically if one or both of 
% $(K-I)$ or $(K-J)$ are negative.  Then the only way the hypothesis would fail is if 
% $(K-I) + (K-J) > K$, i.e., 
% $$(k-i-j-1) - (r-i) + (k-i-j-1) - (s-j) = 2k - r - s - 2 - i - j > k - i - j -1.$$ But that implies that $k > r + s + 1$, contracting our assumption $k \in [0,r+s+1]$.
% \end{rem}
%
Since on $P = [0,r]\times [0,s]$ we have $\rho_{B}^{r+s+2+d} = \rho_{B}^{d}$ by
periodicity (Corollary~\ref{cor:periodicity}), this gives a formula for \textbf{all}
iterations of the birational rowmotion map on $P$.
%
In the ``generic'' case where shifting $(i,j)\mapsto (i-k, j-k)$ (straight down by $2k$ ranks)
still gives a point in $P$, we get the following simpler formula.  
% (which we discovered
% first and then generalized to the main theorem).  
\begin{cor}\label{cor:noShiftMain}
\begin{equation}\label{eq:noShift}
\text{For }k\leq \min \{ i,j\},\  \rho_B^{k+1}(i,j) = \frac{\varphi_{k}(i-k,j-k)}{\varphi_{k+1}(i-k,j-k)}
\end{equation}

\end{cor}


\begin{figure}[htb]
\caption{The six lattice paths (shown in \cred{red}) involved in computing $\varphi_{1}(1,0)$ in $[0,3]\times
[0,2]$. Corresponding $A$-variable subscripts are underlined in \cgrn{\ncirc{green}}.}
%Elements shown in \cgrn{green} are the subscripts of the corresponding $A$-variables.}
\label{fig:6LP}
\[
% \xymatrixrowsep{0.4pc}\xymatrixcolsep{0.18pc}\xymatrix{
% &&\cred{32} \ar@{-}[rd] \ar@{-}@[red][ld]\\
% &\cred{31}\ar@{-}[rd] \ar@{-}@[red][ld]&& \cgrn{22} \ar@{-}[rd] \ar@{-}[ld]\\
% \cred{30}\ar@{-}@[red][rd] &&\cgrn{21} \ar@{-}[rd] \ar@{-}[ld] & & \cgrn{12} \ar@{-}[ld] \ar@{-}[rd]\\
% &\cred{20}  \ar@{-}@[red][rd] && \cgrn{11} \ar@{-}[rd] \ar@{-}[ld] & & 02 \ar@{-}[ld]\\ 
% && \cred{10}  \ar@{-}[rd] && 01 \ar@{-}[ld]\\
% &&& 00
% }
\xymatrixrowsep{0.1pc}\xymatrixcolsep{0.09pc}\xymatrix{
&&\cred{32} \ar@{-}[rd] \ar@{-}@[red][ld]\\
&\cred{31}\ar@{-}[rd] \ar@{-}@[red][ld]&& {\cgrn{\ncirc{22}}} \ar@{-}[rd] \ar@{-}[ld]\\
\cred{30}\ar@{-}@[red][rd] &&\cgrn{\ncirc{21}} \ar@{-}[rd] \ar@{-}[ld] & & \cgrn{\ncirc{12}} \ar@{-}[ld] \ar@{-}[rd]\\
&\cred{20}  \ar@{-}@[red][rd] && \cgrn{\ncirc{11}} \ar@{-}[rd] \ar@{-}[ld] & & 02 \ar@{-}[ld]\\ 
&& \cred{10}  \ar@{-}[rd] && 01 \ar@{-}[ld]\\
&&& 00
}
\qquad 
\xymatrixrowsep{0.1pc}\xymatrixcolsep{0.09pc}\xymatrix{
&&\cred{32} \ar@{-}[rd] \ar@{-}@[red][ld]\\
&\cred{31}\ar@{-}@[red][rd] \ar@{-}[ld]&& \cgrn{\ncirc{22}} \ar@{-}[rd] \ar@{-}[ld]\\
\cgrn{\ncirc{30}}\ar@{-}[rd] &&\cred{21} \ar@{-}[rd] \ar@{-}@[red][ld] & & \cgrn{\ncirc{12}} \ar@{-}[ld] \ar@{-}[rd]\\
&\cred{20}  \ar@{-}@[red][rd] && \cgrn{\ncirc{11}} \ar@{-}[rd] \ar@{-}[ld] & & 02 \ar@{-}[ld]\\ 
&& \cred{10}  \ar@{-}[rd] && 01 \ar@{-}[ld]\\
&&& 00
}
\qquad 
\xymatrixrowsep{0.1pc}\xymatrixcolsep{0.09pc}\xymatrix{
&&\cred{32} \ar@{-}@[red][rd] \ar@{-}[ld]\\
&\cgrn{\ncirc{31}}\ar@{-}[rd] \ar@{-}[ld]&& \cred{22} \ar@{-}[rd] \ar@{-}@[red][ld]\\
\cgrn{\ncirc{30}}\ar@{-}[rd] &&\cred{21} \ar@{-}[rd] \ar@{-}@[red][ld] & & \cgrn{\ncirc{12}} \ar@{-}[ld] \ar@{-}[rd]\\
&\cred{20}  \ar@{-}@[red][rd] && \cgrn{\ncirc{11}} \ar@{-}[rd] \ar@{-}[ld] & & 02 \ar@{-}[ld]\\ 
&& \cred{10}  \ar@{-}[rd] && 01 \ar@{-}[ld]\\
&&& 00
}
\]
\[
\xymatrixrowsep{0.1pc}\xymatrixcolsep{0.09pc}\xymatrix{
&&\cred{32} \ar@{-}[rd] \ar@{-}@[red][ld]\\
&\cred{31}\ar@{-}@[red][rd] \ar@{-}[ld]&& \cgrn{\ncirc{22}} \ar@{-}[rd] \ar@{-}[ld]\\
\cgrn{\ncirc{30}}\ar@{-}[rd] &&\cred{21} \ar@{-}@[red][rd] \ar@{-}[ld] & & \cgrn{\ncirc{12}} \ar@{-}[ld] \ar@{-}[rd]\\
&\cgrn{\ncirc{20}}  \ar@{-}[rd] && \cred{11} \ar@{-}[rd] \ar@{-}@[red][ld] & & 02 \ar@{-}[ld]\\ 
&& \cred{10}  \ar@{-}[rd] && 01 \ar@{-}[ld]\\
&&& 00
}
\qquad 
\xymatrixrowsep{0.1pc}\xymatrixcolsep{0.09pc}\xymatrix{
&&\cred{32} \ar@{-}@[red][rd] \ar@{-}[ld]\\
&\cgrn{\ncirc{31}}\ar@{-}[rd] \ar@{-}[ld]&& \cred{22} \ar@{-}[rd] \ar@{-}@[red][ld]\\
\cgrn{\ncirc{30}}\ar@{-}[rd] &&\cred{21} \ar@{-}@[red][rd] \ar@{-}[ld] & & \cgrn{\ncirc{12}} \ar@{-}[ld] \ar@{-}[rd]\\
&\cgrn{\ncirc{20}}  \ar@{-}[rd] && \cred{11} \ar@{-}[rd] \ar@{-}@[red][ld] & & 02 \ar@{-}[ld]\\ 
&& \cred{10}  \ar@{-}[rd] && 01 \ar@{-}[ld]\\
&&& 00
}
\qquad 
\xymatrixrowsep{0.1pc}\xymatrixcolsep{0.09pc}\xymatrix{
&&\cred{32} \ar@{-}@[red][rd] \ar@{-}[ld]\\
&\cgrn{\ncirc{31}}\ar@{-}[rd] \ar@{-}[ld]&& \cred{22} \ar@{-}@[red][rd] \ar@{-}[ld]\\
\cgrn{\ncirc{30}}\ar@{-}[rd] &&\cgrn{\ncirc{21}} \ar@{-}[rd] \ar@{-}[ld] & & \cred{12} \ar@{-}@[red][ld] \ar@{-}[rd]\\
&\cgrn{\ncirc{20}}  \ar@{-}[rd] && \cred{11} \ar@{-}[rd] \ar@{-}@[red][ld] & & 02 \ar@{-}[ld]\\ 
&& \cred{10}  \ar@{-}[rd] && 01 \ar@{-}[ld]\\
&&& 00
}
\]
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%% FIGURE OF PAIRS OF LP %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{figure}[h]
\caption{The three pairs of lattice paths (shown in \cred{red} and \cblu{blue}) used for computing $\varphi_{2}(1,0)$ in $[0,3]\times
[0,2]$.  $A$-variable subscripts are circled in \cgrn{green}.}
%\caption{The three pairs of lattice paths (shown in in \cred{red} and \cblu{blue}) involved in computing $\varphi_{2}(1,0)$ in $[0,3]\times
%[0,2]$. Elements shown in \cgrn{green} are the subscripts of the corresponding $A$-variables.}
\label{fig:3LP}
\[
\xymatrixrowsep{0.4pc}\xymatrixcolsep{0.18pc}\xymatrix{
&&32 \ar@{-}[rd] \ar@{-}[ld]\\
&\cred{31}\ar@{-}[rd] \ar@{-}@[red][ld]&& \cblu{22} \ar@{-}[rd] \ar@{-}@[blue][ld]\\
\cred{30}\ar@{-}@[red][rd] &&\cblu{21} \ar@{-}@[blue][rd] \ar@{-}[ld] & & \cgrn{\ncirc{12}} \ar@{-}[ld] \ar@{-}[rd]\\
&\cred{20}  \ar@{-}[rd] && \cblu{11} \ar@{-}[rd] \ar@{-}[ld] & & 02 \ar@{-}[ld]\\ 
&& 10  \ar@{-}[rd] && 01 \ar@{-}[ld]\\
&&& 00
}
\qquad 
\xymatrixrowsep{0.4pc}\xymatrixcolsep{0.18pc}\xymatrix{
&&32 \ar@{-}[rd] \ar@{-}[ld]\\
&\cred{31}\ar@{-}[rd] \ar@{-}@[red][ld]&& \cblu{22} \ar@{-}@[blue][rd] \ar@{-}[ld]\\
\cred{30}\ar@{-}@[red][rd] &&\cgrn{\ncirc{21}} \ar@{-}[rd] \ar@{-}[ld] & & \cblu{12} \ar@{-}@[blue][ld] \ar@{-}[rd]\\
&\cred{20}  \ar@{-}[rd] && \cblu{11} \ar@{-}[rd] \ar@{-}[ld] & & 02 \ar@{-}[ld]\\ 
&& 10  \ar@{-}[rd] && 01 \ar@{-}[ld]\\
&&& 00
}
\qquad 
\xymatrixrowsep{0.4pc}\xymatrixcolsep{0.18pc}\xymatrix{
&&32 \ar@{-}[rd] \ar@{-}[ld]\\
&\cred{31}\ar@{-}@[red][rd] \ar@{-}[ld]&& \cblu{22} \ar@{-}@[blue][rd] \ar@{-}[ld]\\
\cgrn{\ncirc{30}}\ar@{-}[rd] &&\cred{21} \ar@{-}[rd] \ar@{-}@[red][ld] & & \cblu{12} \ar@{-}@[blue][ld] \ar@{-}[rd]\\
&\cred{20}  \ar@{-}[rd] && \cblu{11} \ar@{-}[rd] \ar@{-}[ld] & & 02 \ar@{-}[ld]\\ 
&& 10  \ar@{-}[rd] && 01 \ar@{-}[ld]\\
&&& 00
}
\qquad 
\]
\end{figure}
 


\begin{eg}\label{eg:main}
We use Theorem \ref{thm:main} %our main theorem 
to compute $\rho_{B}^{k+1}(2,1)$ for
$P = [0,3]\times [0,2]$ for $k=0,1,2, \dots,6.$ Periodicity kicks in for $k\geq 6$.  %every $k\in \NN$.  
Here $r=3, s=2, i=2$, and $j=1$ throughout.   

\textbf{\bull When} $\mathbf{k=0}$, $M=0$ and we get 
$\ds 
\rho_{B}^{1}(2,1) = \frac{\varphi_{0}(2,1)}{\varphi_{1}(2,1)} =
\frac{A_{21}A_{22}A_{31}A_{32}}{A_{22}+A_{31}}.
$ 
In general
$\varphi_{0}(i,j)=\prod_{(m,n)\geq (i,j)}A_{m,n}$, the product of all the $A$-variables in
the order filter  $\bigvee_{(i,j)}$.  
% (In this situation there are no endpoints to possibly shorten
% the interval and no lattice paths to remove
% factors from the product.)  

\textbf{\bull When} $\mathbf{k=1}$, we still have $M = 0$, and $\ds \rho_{B}^{2}(2,1) = \frac{\varphi_{1}(1,0)}{\varphi_{2}(1,0)} = $
\[
{\textstyle
\frac{A_{11}A_{12}A_{21}A_{22} + A_{11}A_{12}A_{22}A_{30} + A_{11}A_{12}A_{30}A_{31} + 
A_{12}A_{20}A_{22}A_{30} + A_{12}A_{20}A_{30}A_{31} + A_{20}A_{21}A_{30}A_{31}}
	{A_{12}+A_{21} + A_{30}}.
}
\]
For the numerator, $s_{1}= (1,0)$, $t_{1}=(3,2)$, and there are six lattice paths from $s_{1}$ to $t_{1}$,
each of which covers 5 elements and leaves 4 uncovered (Figure~\ref{fig:6LP}).  For the
denominator, $s_{1} = (2,0)$, $s_{2}= (1,1)$, $t_{1}=(3,1)$, and $t_{2}=(2,2)$, and each pair
of lattice paths leaves exactly one element uncovered (Figure~\ref{fig:3LP}). 

\textbf{\bull When} $\mathbf{k=2}$, we get $M=[2-2]_{+} + [2-1]_{+} = 1 \leq 2=k$.  So by part (a)
of the main theorem we have 
\[
\ds \rho_{B}^{3}(2,1) = \mu^{(1,0)}\left[ \frac{\varphi_{1}(1,0)}{\varphi_{2}(1,0)} \right] = 
    \text{(just shifting indices in the $k=1$ formula)}
\]
\[
{\textstyle
\frac{A_{01}A_{02}A_{11}A_{12} + A_{01}A_{02}A_{12}A_{20} + A_{01}A_{02}A_{20}A_{21} + 
A_{02}A_{10}A_{12}A_{20} + A_{02}A_{10}A_{20}A_{21} + A_{10}A_{11}A_{20}A_{21}}
	{A_{02}+A_{11} + A_{20}}.
}
\]

\textbf{\bull When} $\mathbf{k=3}$, we get $M=[3-2]_{+} + [3-1]_{+} = 3 =k$. Therefore, 
\[
\rho_{B}^{4}(2,1) = \mu^{(2,1)}\left[ \frac{\varphi_{0}(2,1)}{\varphi_{1}(2,1)} \right] =
\mu^{(2,1)}\left[ \frac{A_{21}A_{22}A_{31}A_{32}}{A_{22}+A_{31}} \right] 
 = \frac{A_{00}A_{01}A_{10}A_{11}}{A_{01}+A_{10}}.
\] 
We can also use part (b) of the main theorem to get 
$\ds 
\rho_{B}^{4}(2,1) = 1/\rho_{B}^{3-2-1}(3-2, 2-1) = 1/\rho_{B}^{0}(1,1) = \frac{1}{x_{11}}. 
$
The equality between these two expressions is easily checked. 

% $$
% \frac{A_{00}A_{01}A_{10}A_{11}}{A_{01}+A_{10}} = \frac{\frac{1}{x_{00}} 
% \frac{x_{00}}{x_{01}} \frac{x_{00}}{x_{10}} \frac{x_{01} + x_{10}}{x_{11}}
% }{\frac{x_{00}}{x_{01}} + \frac{x_{00}}{x_{10}}} =  \frac{1}{x_{11}}.$$  

\textbf{\bull When} $\mathbf{k=4}$, we get $M=[4-2]_{+} + [4-1]_{+} = 5 > k$. Therefore, 
by part (b) of the main theorem, then part (a),
\[
\rho_{B}^{5}(2,1) = 1/\rho_{B}^{4-2-1}(3-2, 2-1) = 1/\rho_{B}^{1}(1,1)
= \frac{\varphi_{1}(1,1)} {\varphi_{0}(1,1)} = \frac{A_{12}A_{22}+A_{12}A_{31}+A_{21}A_{31}}{A_{11}A_{12}A_{21}A_{22}A_{31}A_{32}}. 
\]
% Each term in the numerator is associated with one of the three lattice paths from $(1,1)$ to
% $(3,2)$ in $P$, while the denominator is just the product of all $A$-variables in the
% principal order filter $\bigvee{(1,1)}$. 

\textbf{\bull When} $\mathbf{k=5}$, we get $M=[5-2]_{+} + [5-1]_{+} = 7 > k$. Therefore, 
%by part (b) of the main theorem, then part (a),
\[
\textstyle
\rho_{B}^{6}(2,1) = 1/\rho_{B}^{5-2-1}(1, 1) = 1/\rho_{B}^{2}(1,1)
= \frac{\varphi_{2}(0,0)} {\varphi_{1}(0,0)} 
%= \frac{1}{A_{12}A_{22}+A_{12}A_{31}+A_{21}A_{31}}.
\scriptstyle = \frac{A_{02}A_{12}+A_{02}A_{21}+A_{11}A_{21}+A_{30}A_{02}+A_{30}A_{11}+A_{30}A_{20}}
	{\text{A sum of 10 degree-6 monomials in $A_{ij}$}}.
\]
% The numerator here represents the empty product, since the unique (unordered) pair of
% lattice paths from $s_{1}= (2,1)$ and $s_{2}= (1,2)$ to $t_{1}=(3,1)$ and $t_{2}=(2,2)$
% covers \textbf{all} elements of $\lpreg_{(1,1)}^{2}$.  The denominator here is the same as the numerator of the previous case. 

\textbf{\bull When} $\mathbf{k=6}$, we get $M=[6-2]_{+} + [6-1]_{+} = 9 > k$. Therefore, 
%by part (b) of the main theorem, then part (a),
\[
\rho_{B}^{7}(2,1) = 1/\rho_{B}^{6-2-1}(3-2, 2-1) = 1/\rho_{B}^{3}(1,1)
=  \mu^{(1,1)} \left[ \frac{ \varphi_1(1,1)}{\varphi_0(1,1)} \right] 
\]
\[
= \mu^{(1,1)} \left[ \frac{A_{12}A_{22} + A_{12}A_{31} + A_{21}A_{31}}
{A_{11}A_{11}A_{21}A_{22}A_{31}A_{32}}  \right] 
= \frac{A_{01}A_{11} + A_{01}A_{20} + A_{10}A_{20}}
{A_{00}A_{01}A_{10}A_{11}A_{20}A_{21}} = x_{21}
%\frac{\varphi_{2}(1,1)} {\varphi_{1}(1,1)} = \frac{1}{A_{12}A_{22}+A_{12}A_{13}+A_{21}A_{31}}.
\]
% We will later see that this last equality is an application of Claim \ref{claim:Mk}, but one can also
% deduce this by plugging in $A_{00} = 1/x_{00}, A_{10} = x_{00}/x_{10}, A_{01} = x_{00}/x_{01}, A_{11} = (x_{10}+x_{01})/x_{11}, A_{20} = x_{10}/x_{20},$ and 
% $A_{21} = (x_{20}+x_{11})/x_{21}$.  
Notice that periodicity also kicks in for this case and $\rho_B^7(2,1) = \rho_B^0(2,1) = x_{21}$.
%using $(r+s+2) = 7$.

%\textbf{\bull When} $\mathbf{k\geq 6}$, we get by periodicity that $\rho_{B}^{k+1}(i,j)=\rho_{B}^{g}$, where 
%$g=k+1 \bmod 7$ has already been computed above.  

\end{eg}

As corollaries of Theorem~\ref{thm:main}, we get the main two theorems on birational rowmotion on a
product of two chains (by applying part (b) once or twice).  

\begin{corollary}[{\cite[Theorem~30]{GrRo15}}]\label{cor:periodicity}
The birational rowmotion map $\rho_{B}$ on the product of two chains $P=[0,r]\times [0,s]$
is periodic, with period $r+s+2$.  
\end{corollary}
% \begin{proof}
% Apply part (b) of the main theorem twice, first with $k=r+s+1$, then with $k=(r-i)+(s-j)$
% (checking in each case that $M\geq k$) to obtain 
% \[
% \rho_{B}^{r+s+2}(i,j) = 1/\rho_{B}^{r+s+1-i-j}(r-i, s-j) = 1/\frac{1}{\rho_{B}^{0}(i,j)} =
% \rho_{B}^{0}(i,j). 
% \]
% \end{proof}


\begin{corollary}[{\cite[Theorem~32]{GrRo15}}]\label{cor:reciprocity}
The birational rowmotion map $\rho_{B}$ on the product of two chains $P=[0,r]\times [0,s]$
satisfies the following reciprocity: 
$\rho_{B}^{i+j+1} = 1/\rho_{B}^{0}(r-i,s-j) = \frac{1}{x_{r-i,s-j}}$.
\end{corollary}

% \begin{proof}
% This is the special case $k=i+j$ in Theorem~\ref{thm:main} (b). 
% \end{proof}


\section{Proof of Main Theorem}

There is only space here to outline the main ideas of the proof of Theorem~\ref{thm:main},
which is a complicated triple induction on $i$, $j$, and $k$. We start with $k=0$ and work
our way down the poset from the upper boundary, then repeat with $k=1$, etc. 
The key ingredients are a Pl\"ucker-like recurrence relation for the $\varphi_{k}$'s,
Lemma~\ref{lem:bounce}, and a 
generalization thereof (omitted herein)
that includes the shifting $\mu^{(i,j)}$'s, but whose proof can be reduced to
it.   We prove Lemma~\ref{lem:bounce} using a
colorful combinatorial bijection on pairs of $k$-tuples of NILPs, which we later learned is similar to those in~\cite{FuKl01} for Schur functions identities. 


% We first prove the result for the special case when $k=0$, 
% % where we re-express our
% % formulas in terms of $x_{ij}$'s more compactly in terms of the $A_{ij}$'s.
% % After that we prove the result 
% then for larger $k$ by induction working from the top of the
% poset. We will often need to distinguish those elements on the \textbf{upper boundary} of
% $P$, namely $\{(i,j): i=\bfr  \text{ or } j=\bfs \}$, each of which is covered by exactly
% one element in $\whP$. All other elements of $P$ are covered by exactly two elements.  

% As an initial case, at the top element $(\bfr ,\bfs )$ (bolded to help the reader
% keep track of which variables are ``fixed'' in the formulae below) of $P$ we obtain 
% \[
% \rho_B^1(\bfr ,\bfs ) = \frac{x_{\bfr ,\bfs -1} + x_{\bfr -1,
% \bfs }}{x_{\bfr , \bfs }} = A_{\bfr \bfs }  
% \]
% where the first equality is
% by definition of birational rowmotion (a single toggle), and the second by definition 
% of $A_{ij}$ (Equation~\ref{eq:Aij}). 

% Second, for any element $(\bfr, j)$ 
% %%of the upper-left boundary sufficiently close to the top (i.e., with $j$ sufficiently large), 
% with $1\leq j\leq s$,
% we assume by induction that $\rho_B^1(\bfr ,j) = \prod_{c=j}^{\bfs }
% A_{\bfr ,c}$.  Then  
% \[
% \rho_B^1(\bfr ,j-1) = \frac{(x_{\bfr ,j-2}+x_{\bfr -1,j-1})(\rho_B^1(\bfr ,j))}{x_{\bfr ,j-1}} = \left(\frac{x_{\bfr ,j-2}+x_{\bfr -1,j-1}}{x_{\bfr ,j-1}}\right)\left(\prod_{c=j}^{\bfs }A_{\bfr ,c}\right) = \prod_{c=j-1}^{\bfs } A_{\bfr ,c},
% \]
% by definition of $A_{\bfr ,j-1}$ and using the definition of birational rowmotion in the case where only a single
% element covers it.   By symmetry we get a
% formula for all (upper boundary) elements covered by a single element: 
% \begin{equation}\label{eq:k=1;1cover}
% \rho_B^1(\bfr ,j) = \prod_{c=j}^{\bfs } A_{\bfr ,c}, \text{ for } j\in [0,s] 
% \qquad \text{ and } \qquad 
% \rho_B^1(i,\bfs ) = \prod_{c=i}^{\bfr } A_{c, \bfs }, \text{ for } i\in [0,r]. 
% \end{equation}
% Note that this agrees with Theorem~\ref{thm:main} as follows.  Here $k=0$ forces $M=0$
% and the shift operator $\mu^{(0,0)}$ acts trivially.  Thus, Equation~\ref{eq:main1} reduces to 
% \[
% \rho_{B}^{1}(i,j) = \frac{\varphi_{0}(i,j)}{\varphi_{1}(i,j)}. 
% \]
% The numerator is simply $\prod_{(u,v)\geq (i,j)} A_{(u,v)}$, since the defining summation of
% $\varphi_{0}(i,j)$ has only a single term, namely the empty tuple of lattice paths, and each
% element of $\lpreg_{(i,j)}^{k} = \bigvee_{(i,j)}$ contributes one factor $A_{ij}$ to that term's product.  The
% denominator, $\varphi_{1}(i,j)$ for $i=\bfr $ or $j=\bfs $, equals $1$ because
% there is a unique lattice path from $(i,j)$ to $(\bfr , \bfs) $ covering the entire
% order filter $\bigvee_{(i,j)}$; thus, the summation consists of a single term, which is the
% empty product, i.e., 1. 
% % \twr{It seemed important here to spell out our degenerate conventions and help the reader
% % work through the notation, though I see we mention it similarly at the end of the sections\dots }

% All other elements $(i,j)$ of the poset are covered by exactly two elements.  In the case
% that $(i,j)$ also covers (exactly) two elements, we obtain
% \[
% \rho_B^1(i,j) = \left(\frac{x_{i,j-1} + x_{i-1,j}}{x_{ij}}\right) \cdot \left( \rho_B^1(i,j+1) \parallel \rho_B^1(i+1,j)\right) 
% = A_{ij} \cdot \left( \rho_B^1(i,j+1) \parallel \rho_B^1(i+1,j)\right).
% \]

% Recall that $a \parallel b$ denotes the parallel sum $\frac{1}{\frac{1}{a} + \frac{1}{b}}$.

% \begin{rem} In the case that $(i,j)$ covers a single element of $P$, i.e., $i=0$ or $j=0$, recall that we defined $A_{i0}$, $A_{0j}$, and $A_{00}$ accordingly (see right after Equation~\ref{eq:Aij}).  Thus,
% %Recall that by definition %(see Equation~\ref{eq:Aij}) 
% %when $(i,j)$ covers a single element of $P$, i.e., $i=0$ or $j=0$ (but not both), we defined $A_{i,0} = \frac{x_{i-1,0}}{x_{i,0}}$ and $A_{0j} = \frac{x_{0,j-1}}{x_{0,j}}$.  For the smallest element $A_{0,0} = \frac{1}{x_{0,0}}$.  Thus,
% \begin{equation}\label{eqn:2covers}
% \rho_B^1(i,j) = A_{ij} \cdot \left( \rho_B^1(i,j+1) \parallel \rho_B^1(i+1,j)\right)
% \end{equation}
% holds for 
% for all $(i,j)$ covered by two elements (regardless of how many elements $(i,j)$ covers). 
% \end{rem}

% We claim that by induction (as long as $I+J > i+j$) that 
% \[
% \rho_B^1(I,J) =
% \frac{1}{\sum_{\mathrm{~paths}~L} \frac{1}{\prod_{(p,q)\in P} A_{pq}}}
%  = \sumpar_{\text{paths}~L} \prod_{(p,q)\in L} A_{pq},
% \] where the sum is
% over paths $L$ from the point $(I,J)$ up to the point $(\bfr ,\bfs )$.  (Here the large symbol $\sumpar$
% denotes \emph{parallel summation}, the analogue of $\sum$ for parallel sums, which is
% well-defined since $\parallel$ is associative and commutative.)  

% In particular, in the special case of $\rho_B^1(\bfr ,j)$, there is a unique such path
% and its weight is $\prod_{c=j}^{\bfs } A_{\bfr ,c}$ agreeing with the computation
% above.  (By symmetry, we obtain 
% $\rho_B^1(i,\bfs ) = \prod_{c=i}^{\bfr } A_{c,\bfs }$ as well.)  Then inductively, 

% \begin{align*}
% \rho_B^1(i,j) &= A_{ij}  \cdot \left( \sumpar_{\mathrm{~paths}~L~\text{from}~(i,j+1)}\prod_{(p,q)\in L} A_{pq} \ \ \  \parallel \sumpar_{\mathrm{~paths}~L~\text{from}~(i+1,j)}\prod_{(p,q)\in L} A_{pq} \right)\\ 
% &= \sumpar_{\mathrm{~paths}~L~\text{from}~(i,j)}\prod_{(p,q)\in L} A_{pq},
% \end{align*}
% simply because every path from $(i,j)$  to $(\bfr , \bfs )$ must go either through
% $(i,j+1)$ or $(i+1,j)$, and the $A_{ij}$ term distributes through.  
% We finish the $k=0$ case by remarking that 
% \begin{equation} \label{eq:k0} \rho_B^1(i,j) = \sumpar_{\mathrm{~paths}~L~\text{from}~(i,j)}\prod_{(p,q)\in L} A_{pq} = \frac{1}{\sum_{\mathrm{~paths}~L~\text{from}~(i,j)} \frac{1}{\prod_{(p,q)\in L} A_{pq}}}\end{equation}
% $$= \frac{\varphi_0(i,j)}{\sum_{\mathrm{~paths}~L~\text{from}~(i,j)} \prod_{(p,q)\not\in L} A_{pq}} = \frac{\varphi_0(i,j)}{\varphi_1(i,j)},$$
% where the second line comes from multiplying top and bottom by $\varphi_0(i,j)
% =\prod_{(u,v)\geq (i,j)} A_{uv}$.  This
% agrees with part (a) of our main theorem, where $k=0$ implies $[k-i]_{+} = [k-j]_{+} = M = 0$.  




% We continue our proof by induction, starting by proving the case of $k=1$ on the upper
% boundary.  Then for each such $k$, we move downward through the entire rectangular poset by
% induction and then start again with a proof for the case of $(k+1)$ for the upper boundary.
% To accomplish this proof we first verify two recurrence relations (Lemmas \ref{lem:bounce} %
% and \ref{lem:genBounce}) that will be used for the induction step.  Both of these results
% are proven via combinatorial bijections.  Even though Lemma \ref{lem:bounce} looks like a
% special case, %we will see how this result will imply Lemma \ref{lem:genBounce} and then
% Theorem \ref{thm:main} by verifying the recurrence %that is used in our induction.
 

\begin{lemma} \label{lem:bounce} For $1 \leq k\leq \min \{ i,j \}$ we have the Pl\"ucker-like relation
\begin{align}
\begin{split}
\varphi_k(i-k,j-k) \varphi_{k-1}(i-k+1,j-k+1) &= \varphi_k(i-k+1,j-k) \varphi_{k-1}(i-k,j-k+1)\\ 
&+ \varphi_k(i-k,j-k+1) \varphi_{k-1}(i-k+1,j-k).
\end{split}
\end{align}
\end{lemma}

% Since this statement involves pairs of families of \textbf{non-intersecting lattice-paths},
% abbreviated below to \textbf{NILPs}, we prove it via a colorful combinatorial bijection.

\begin{proof}
The definition of $\varphi_{k}$ (Equation~\eqref{eq:phi}) involves summing 
monomials in the $A_{ij}$'s, with each term corresponding to the elements left uncovered by a
$k$-tuple of NILPs.  So a term on the left-hand side of the Lemma
is represented by a pair of NILPs $(\cblu{\calB}, \cred{\calR})$ 
offset from one another by one rank.  Example~\ref{eg:bouncePaths} gives an example to
illustrate both this and the bijection below.  
Specifically, the lower NILPs $\cblu{\calB}$, whose endpoints are marked with $\cblu{\circ}$,
represents a monomial from $\varphi_{k}(i-k,j-k)$, 
and the upper NILPs $\cred{\calR}$, whose endpoints are marked by $\cred{\times}$, represents one
from $\varphi_{k-1}(i-k+1,j-k+1)$.  Our goal is to transform this pair into a pair of NILPs
counted by one of the terms on the right-hand-side of Lemma~\ref{lem:bounce}.  

Starting at each bottom $\cblu{\circ}$ (lowest points in $\cblu{\calB}$), we create two \textbf{bounce
paths} and $(k-2)$ \textbf{twigs} as follows.  From the leftmost
$\cblu{\circ}$ on the bottom, move up blue edges until encountering a vertex with a downward red
edge.  Then move down red edges until encountering a vertex with an upward blue edge.
Continue in this way, reversing directions whenever possible and only traversing unused
edges, until a terminal vertex is reached.  (No such path can terminate at an internal
vertex, since any edge by which one enters must be paired with a possible exit.)  Do the same procedure starting from the 
rightmost $\cblu{\circ}$ on the bottom.  We refer to both of these paths as \textbf{bounce paths}.

%Any such path that starts at $\cblu{\circ}$ along the bottom and ends at a point $\cred{\times}$ also along the bottom is called 
%a \textbf{bounce path}.  


%%% TR: Here's some earlier language that maybe we are ditching now? 
% Since we reverse directions along bounce paths in a systematic way, we always follow blue edges upward and red edges downward.  It follows that one of these two bounce paths end at the top of the interval and at an $\cblu{\circ}$ and the other bounce path ends at the bottom of the interval ends at a $\cred{\times}$.  We call the bounce path starting at a bottom $\cblu{\circ}$ and ending at a top $\cblu{\circ}$ a \textbf{vertical bounce path}.  We will refer to the other path as a \textbf{bottom bounce path}.

Since we reverse directions along bounce paths in a systematic way, we always follow blue edges upward and red edges downward.  
%
%
%Because there are $k$ paths in $\cblu{\calB}$ but only $(k-1)$ paths in $\cred{\calR}$, there will be exactly one additional path that starts at an $\cblu{\circ}$ along the bottom, changes directions whenever possible (as defined above), but then ends at an $\cblu{\circ}$ along the top.  The set consisting of $(k-1)$ bounce paths and this one non-bounce path exhausts all possible paths starting and ending at the lower endpoints of $\cblu{\calB}$ and $\cred{\calR}$.
%
In addition to these two bounce paths, the $(k-2)$ $\cblu{\circ}$'s in the interior of the
bottom immediately connect to a $\cred{\times}$ in the rank second from the bottom.  We
refer to these blue edges as {\bf twigs}.  Since the twigs cover all but $1$ of the $(k-2)$
$\cred{\times}$'s, only one of the two bounce paths may return to the bottom of the poset
ending with a segment of downward red edges.   
%
Furthermore the $(k-1)$ red paths, starting from the $\cred{\times}$'s at the top, intersect $(k-1)$ of the $k$ topmost $\cblu{\circ}$'s, leaving only  $1$  $\cblu{\circ}$ untouched.  Notice % Note that a bounce path can only end at the top of the poset if it does not meet a red path that it can follow downward.
%
%Furthermore, if both bounce paths ended at the top of the poset, ending by following the blue edges upward, there would not be enough room for the non-intersecting lattice paths between them.
%
%
It follows that one of these two bounce paths ends at the top of the interval, at the
$\cblu{\circ}$ on top untouched by the red paths, and the other bounce path ends at the
bottom of the interval, at the $\cred{\times}$ on the bottom not covered by a twig.  We call the former %bounce path ending at the top
%a bottom $\cblu{\circ}$ and ending at a top $\cblu{\circ}$ 
a \textbf{vertical bounce path} and the latter a
%.  We refer to the other path, the one that returns to the bottom, as a 
\textbf{horizontal bounce path}.  
%(Note that in the case that all blue paths point northeast (resp. northwest) starting from the bottom   $\cblu{\circ}$'s, the horizontal bounce path turns out to be a twig as well.  The remainder of our procedure is consistent whether or not we treat this as a twig or as a horizontal bounce path.)  

We proceed by interchanging the colors of the edges along the horizontal bounce path, along all the twigs, and swap the $\cred{\times}$ and $\cblu{\circ}$ endpoints at the bottom, while leaving the remaining edges of $\cblu{\calB} \cup \cred{\calR}$ unchanged (also leaving the colors of the vertical bounce path unchanged).  
%
We then truncate the vertical bounce path by deleting the bottommost edge.  These transformations result in a new pair of lattice path families which we denote as $(\cblu{\calB}', \cred{\calR}')$.
%
%This will leave $(k-1)$ red paths from the bottom to the top of the interval, and
%one blue path from the bottom to the penultimate rank of the interval.  Truncate the bottom edge
%of the latter, so that it becomes one of $k$ blue paths.    
%
The bottom endpoints %new lower endpoint
for $\cblu{\calB}'$ will be one step either to the northeast or northwest %left or right 
of the original ones, indicating
respectively whether it is contributing to the first or second summand on the right-hand-side of
Lemma~\ref{lem:bounce}.  The %lower 
bottom endpoints of $\cred{\calR}'$ are skewed in the other
direction, i.e., the southwest or the southeast, respectively.   
 
Furthermore, if lattice paths $L_B \in \cblu{\calB}$ and $L_R \in \cred{\calR}$ did not
originally intersect, then their edges would not lie along any bounce path.  Consequently,
$L_B$ would be a lattice path again in $\cblu{\calB}'$ unchanged,
%\footnote{With the small exception of possibly truncating the bottommost leftmost or rightmost edge.  However, even
%this change would not affect intersections.},
and the same is true for $L_R$ in
$\cred{\calR}'$.  They would again not intersect.  On the other hand, if $L_B$ and $L_R$ did
originally intersect, then they could meet along a bounce path.  Being part of larger NILPs,
$L_B$ would not intersect any path in $\cblu{\calB}$ and $L_R$ would not intersect any path
in $\cred{\calR}$. Swapping colors of individual edges along $L_B$ and $L_R$ might break
this intersection-free property, but since all colors of edges along a horizontal bounce
path are swapped simultaneously, we ensure that each collection of paths, $\cblu{\calB}'$
and $\cred{\calR}'$, is still intersection-free.

%Starting at each bottom $\cblu{\circ}$ (lowest points in $\cblu{\calB}$), we create \textbf{bounce
%paths} as follows.  Move up blue edges until enountering a vertex with a downward red
%edge.  Then move down red edges until encountering a vertex with an upward blue edge.
%Continue in this way, reversing directions whenever possible and only traversing unused
%edges, until a terminal vertex is reached.  (No such path can terminate at an internal
%vertex; any edge by which one enters must be paired with a possible exit.)  Any such
%path that starts at $\cblu{\circ}$ along the bottom and ends at a point $\cred{\times}$ also along the bottom is called 
%a \textbf{bounce path}.  
%
%%{\color{red}Is this exposition clear enough?  Is it clear that the resulting configurations after color swaps will indeed be two NILP families?  Should we say more about the local neighborhood of intersections with two red edges in and two blue edges out (possibly with violet double edges)?}
%
%%{\color{red}ADD MORE/DIFFERENT DETAILS HERE?  OUTLINE IDEA OF PROOF THAT WE WANT TO ESSENTIALLY SWAP BOTTOM-MOST TWO ROWS WHICH MEANS SWAPPING COLORS EMANATING FROM THOSE BOTTOM POINTS BUT WITHOUT CREATING MONOCHROMATIC INTERSECTIONS.  BUT INTERSECTIONS (EITHER CROSSINGS OR KISSINGS) ALWAYS HAVE BLUE AND RED FROM BELOW AND BLUE AND RED FROM ABOVE (INCLUDING PURPLE DOUBLE EDGES) AND THIS PROPERTY PRESERVED WHEN COLORS OF ALL EDGES IN BOUNCE PATH ARE SWITCHED.  MAKE IT CLEARER WHY SWITCHING THE COLORS OF BOUNCE PATHS CAN'T MAKE NEW MONOCHROMATIC INTERSECTIONS AND SUCCEEDS IN SWITCHING BOTTOMS OF PATHS.  
%
%%Our method .... }
%
%Since we reverse directions along bounce paths in a systematic way, we always follow blue edges upward and red edges downward.  It follows that any bounce path ending at the top of the interval must end at an $\cblu{\circ}$ and any bounce path ending at the bottom of the interval ends at a $\cred{\times}$.  
%Because there are $k$ paths in $\cblu{\calB}$ but only $(k-1)$ paths in $\cred{\calR}$, there will be exactly one additional path that starts at an $\cblu{\circ}$ along the bottom, changes directions whenever possible (as defined above), but then ends at an $\cblu{\circ}$ along the top.  The set consisting of $(k-1)$ bounce paths and this one non-bounce path exhausts all possible paths starting and ending at the lower endpoints of $\cblu{\calB}$ and $\cred{\calR}$.
%
%%  Using the bounce paths, the remaining $(k-1)$ $\cblu{\circ}$'s along the bottom are matched up in a $1$-to-$1$ correspondence to the $(k-1)$ $\cred{\times}$'s along the bottom.
%
%Now interchange the colors of the edges along each of the $(k-1)$ bounce paths, and swap the $\cred{\times}$ and $\cblu{\circ}$ endpoints at
%the bottom, while leaving the remaining edges of $\cblu{\calB} \cup \cred{\calR}$ unchanged.  This will leave $(k-1)$ red paths from the bottom to the top of the interval, and
%one blue path from the bottom to the penultimate rank of the interval.  Truncate the bottom edge
%of the latter, so that it becomes one of $k$ blue paths.    The new lower endpoint
%for $\cblu{\calB}'$ will be either to the left or right of the original ones, indicating
%respectively whether it is counting the first or second summand on the right-hand-side of
%Lemma~\ref{lem:bounce}.  The lower endpoints of $\cred{\calR}'$ will be skewed the other
%direction.   
% 
%Furthermore, if lattice paths $L_B \in \cblu{\calB}$ and $L_R \in \cred{\calR}$ did not originally intersect, then their edges would not lie along any bounce path.  Consequently, $L_B$ would be a lattice path again in $\cblu{\calB}'$ unchanged\footnote{With the small exception of possibly truncated the bottommost leftmost or rightmost edge.  However, even this change would not effect intersections.}, and the same for $L_R$ in $\cred{\calR}'$.  They would again not intersect.  On the other hand, if $L_B$ and $L_R$ did originally intersect, then they would meet along a bounce path.  Being part of larger NILPs, $L_B$ would not intersect any path in $\cblu{\calB}$ and $L_R$ would not intersect any path in $\cred{\calR}$. Swapping colors of individual edges along $L_B$ and $L_R$ might break this intersection-free property, but since all edges along a bounce path are swapped simultaneously, we ensure that the $\cblu{\calB}'$ and $\cred{\calR}'$ are both still intersection-free.

Hence, the result is a new pair of NILPs $(\cblu{\calB}', \cred{\calR}')$ with the lower
endpoints of $\cblu{\calB}'$ on the second rank from the bottom of the interval skewed left
(resp.~right) while the lower endpoints of $\cred{\calR}'$ are on the bottom rank of the
interval and skewed right (resp.~left).  By construction, this map is well-defined, and
$\cblu{\calB}'$ is a collection of $k$ lattice paths from $\cblu{\circ}$'s to
$\cblu{\circ}$'s, and  $\cred{\calR}'$ is a collection of $(k-1)$ lattice paths from
$\cred{\times}$'s to $\cred{\times}$'s. 
Thus the new pair represents a pair of monomials ``counted'' by
$\varphi_k(i-k,j-k+1) \varphi_{k-1}(i-k+1,j-k)$ in the former case, and ``counted'' by
$\varphi_k(i-k+1,j-k) \varphi_{k-1}(i-k,j-k+1)$ in the latter.
Finally this procedure is clearly reversible, giving the desired bijection.
\end{proof}
\begin{eg}\label{eg:bouncePaths}
Let $k=5$, and consider the following pair of tuples of lattice paths, $(\cblu{\calB}, \cred{\calR})$ 
(shown below left in (\cblu{blue}, \cred{red}) in $\lpreg_{(i-5,j-5)}^{5}\cup
\lpreg_{(i-4,j-4)}^{4}$, with $r-i=s-j=2$. 
(Due to limitations of our drawing package, red edges are drawn as \cred{squiggles} and {\color{violet}violet} double edges 
represent one edge of each color.)  %We create bounce paths and twigs as shown above on the right. 
%(Double edges shown in {\color{violet}violet} are used 
%to represent one edge of each color because of limitations of our drawing package.)  
%We create bounce paths and twigs as shown below right. 
\[
\begin{array}{cc}
\xymatrixrowsep{0.3pc}\xymatrixcolsep{0.08pc}\xymatrix{
& & & & \cred{\times} \ar@{~}@[red][ld] & & \cred{\times} \ar@{~}@[red][rd] & & \cred{\times} \ar@{~}@[red][rd] & & \cred{\times} \ar@{~}@[red][rd] & & & & \\
& & & \cblu{\circ} \ar@{-}@[blue][ld] \ar@{~}@[red][rd] & & \cblu{\circ} \ar@{-}@[blue][ld] & & \cblu{\circ} \ar@{-}@[blue][ld] \ar@{~}@[red][rd] & & \cblu{\circ} \ar@{=}@[violet][rd] & & \cblu{\circ} \ar@{=}@[violet][rd] & & & \\
& & \bullet \ar@{-}@[blue][ld]  & & \bullet \ar@{~}@[red][ld]\ar@{-}@[blue][rd] & & \bullet \ar@{-}@[blue][rd] & & \bullet \ar@{~}@[red][ld] & & \bullet \ar@{~}@[red][ld] \ar@{-}@[blue][rd] & & \bullet  \ar@{~}@[red][ld] \ar@{-}@[blue][rd] & & \\
& \bullet \ar@{-}@[blue][ld] & & \bullet \ar@{~}@[red][rd] & & \bullet \ar@{-}@[blue][ld] & & \bullet \ar@{~}@[red][ld] \ar@{-}@[blue][rd]& & \bullet \ar@{~}@[red][rd]& & \bullet \ar@{-}@[blue][ld] \ar@{~}@[red][rd] & & \bullet \ar@{-}@[blue][rd] & \\
\bullet \ar@{-}@[blue][rd] & & \bullet  & & \bullet \ar@{~}@[red][ld] \ar@{-}@[blue][rd]& & \bullet \ar@{~}@[red][ld] & & \bullet \ar@{-}@[blue][rd] & & \bullet \ar@{~}@[red][ld]\ar@{-}@[blue][rd]& & \bullet \ar@{~}@[red][ld]& & \bullet \ar@{-}@[blue][ld] \\
& \bullet \ar@{-}@[blue][rd] & & \bullet \ar@{~}@[red][rd] & & \bullet \ar@{=}@[violet][rd] & & \bullet & & \bullet \ar@{=}@[violet][ld] & & \bullet \ar@{=}@[violet][ld] & & \bullet \ar@{-}@[blue][ld] & \\
& & \bullet \ar@{-}@[blue][rd] & & \cred{\times} & & \cred{\times} \ar@{-}@[blue][ld] & & \cred{\times} \ar@{-}@[blue][ld] & & \cred{\times} \ar@{-}@[blue][ld] & & \bullet \ar@{-}@[blue][ld] & & \\ 
& & & \cblu{\circ} & & \cblu{\circ} & & \cblu{\circ} & & \cblu{\circ} & & \cblu{\circ} & & &
}
&
\xymatrixrowsep{0.3pc}\xymatrixcolsep{0.08pc}\xymatrix{
& & & & \cred{\times} & & \cred{\times} & & \cred{\times} & & \cred{\times} & & & & \\
& & & \cblu{\circ} \ar@{<-}@[blue][ld] \ar@{-->}@[red][rd]& & \cblu{\circ} \ar@{<-}@[blue][ld] & & \cblu{\circ} & & \cblu{\circ} & & \cblu{\circ} & & & \\
& & \bullet \ar@{<-}@[blue][ld]  & & \bullet & & \bullet & & \bullet & & \bullet \ar@{-->}@[red][ld] \ar@{<-}@[blue][rd] & & \bullet  \ar@{-->}@[red][ld] \ar@{<-}@[blue][rd] & & \\
& \bullet \ar@{<-}@[blue][ld]  & & \bullet & & \bullet & & \bullet \ar@{-->}@[red][ld] \ar@{<-}@[blue][rd]& & \bullet \ar@{-->}@[red][rd]& & \bullet \ar@{<-}@[blue][ld] \ar@{-->}@[red][rd] & & \bullet \ar@{<-}@[blue][rd] & \\
\bullet \ar@{<-}@[blue][rd] & & \bullet  & & \bullet \ar@{-->}@[red][ld] \ar@{<-}@[blue][rd]& & \bullet \ar@{-->}@[red][ld] & & \bullet \ar@{<-}@[blue][rd] & & \bullet \ar@{-->}@[red][ld]\ar@{<-}@[blue][rd]& & \bullet \ar@{-->}@[red][ld] & & \bullet \ar@{<-}@[blue][ld] \\
& \bullet \ar@{<-}@[blue][rd] & & \bullet \ar@{-->}@[red][rd] & & \bullet & & \bullet & & \bullet & & \bullet & & \bullet \ar@{<-}@[blue][ld] & \\
& & \bullet \ar@{<-}@[blue][rd] & & \cred{\times} & & \cred{\times} \ar@{<-}@[blue][ld]  & & \cred{\times} \ar@{<-}@[blue][ld] & & \cred{\times} \ar@{<-}@[blue][ld] & & \bullet \ar@{<-}@[blue][ld] & & \\ 
& & & \cblu{\circ} & & \cblu{\circ} & & \cblu{\circ} & & \cblu{\circ} & & \cblu{\circ} & & &
}
\end{array}
\]

We create bounce paths and twigs as shown above on the right.
%
Notice %Note that 
the leftmost bounce path is vertical, i.e., it ends at the top, so its colors
remain the same.  We interchange the colors along the twigs and the rightmost bounce path,
which is horizontal. We then fill in the original edges (with their original colors) and
swap $\cred{\times}$ and $\cblu{\circ}$ at the bottom. 
\[
\begin{array}{cc}
\xymatrixrowsep{0.3pc}\xymatrixcolsep{0.07pc}\xymatrix{
& & & & \cred{\times} \ar@{~}@[red][ld]& & \cred{\times} \ar@{~}@[red][rd] & & \cred{\times} \ar@{~}@[red][rd] & & \cred{\times} \ar@{~}@[red][rd] & & & & \\
& & & \cblu{\circ} \ar@{-}@[blue][ld] \ar@{~}@[red][rd] & & \cblu{\circ} \ar@{-}@[blue][ld] & & \cblu{\circ} \ar@{-}@[blue][ld] \ar@{~}@[red][rd] & & \cblu{\circ} \ar@{=}@[violet][rd] & & \cblu{\circ} \ar@{=}@[violet][rd] & & & \\
& & \bullet \ar@{-}@[blue][ld]  & & \bullet \ar@{~}@[red][ld]\ar@{-}@[blue][rd] & & \bullet \ar@{-}@[blue][rd] & & \bullet \ar@{~}@[red][ld] & & \bullet \ar@{-}@[blue][ld] \ar@{~}@[red][rd] & & \bullet  \ar@{-}@[blue][ld] \ar@{~}@[red][rd] & & \\
& \bullet \ar@{-}@[blue][ld] & & \bullet \ar@{~}@[red][rd] & & \bullet \ar@{-}@[blue][ld] & & \bullet \ar@{-}@[blue][ld] \ar@{~}@[red][rd]& & \bullet \ar@{-}@[blue][rd]& & \bullet \ar@{~}@[red][ld] \ar@{-}@[blue][rd] & & \bullet \ar@{~}@[red][rd] & \\
\bullet \ar@{-}@[blue][rd] & & \bullet  & & \bullet \ar@{-}@[blue][ld] \ar@{~}@[red][rd]& & \bullet \ar@{-}@[blue][ld] & & \bullet \ar@{~}@[red][rd] & & \bullet \ar@{-}@[blue][ld]\ar@{~}@[red][rd]& & \bullet \ar@{-}@[blue][ld]& & \bullet \ar@{~}@[red][ld] \\
& \bullet \ar@{-}@[blue][rd] & & \bullet \ar@{-}@[blue][rd] & & \bullet \ar@{=}@[violet][rd] & & \bullet & & \bullet \ar@{=}@[violet][ld] & & \bullet \ar@{=}@[violet][ld] & & \bullet \ar@{~}@[red][ld] & \\
& & \bullet \ar@{-}@[blue][rd]& & \cblu{\circ} & & \cblu{\circ} \ar@{~}@[red][ld] & & \cblu{\circ} \ar@{~}@[red][ld] & & \cblu{\circ} \ar@{~}@[red][ld] & & \bullet \ar@{~}@[red][ld] & & \\
& & & \cred{\times}  & & \cred{\times} & & \cred{\times} & & \cred{\times} & & \cred{\times} & & & \\
}
%%% fifth picture added here
\xymatrixrowsep{0.3pc}\xymatrixcolsep{0.07pc}\xymatrix{
& & & & \cred{\times} \ar@{~}@[red][ld]& & \cred{\times} \ar@{~}@[red][rd] & & \cred{\times} \ar@{~}@[red][rd] & & \cred{\times} \ar@{~}@[red][rd] & & & & \\
& & & \cblu{\circ} \ar@{-}@[blue][ld] \ar@{~}@[red][rd] & & \cblu{\circ} \ar@{-}@[blue][ld] & & \cblu{\circ} \ar@{-}@[blue][ld] \ar@{~}@[red][rd] & & \cblu{\circ} \ar@{=}@[violet][rd] & & \cblu{\circ} \ar@{=}@[violet][rd] & & & \\
& & \bullet \ar@{-}@[blue][ld]  & & \bullet \ar@{~}@[red][ld]\ar@{-}@[blue][rd] & & \bullet \ar@{-}@[blue][rd] & & \bullet \ar@{~}@[red][ld] & & \bullet \ar@{-}@[blue][ld] \ar@{~}@[red][rd] & & \bullet  \ar@{-}@[blue][ld] \ar@{~}@[red][rd] & & \\
& \bullet \ar@{-}@[blue][ld] & & \bullet \ar@{~}@[red][rd] & & \bullet \ar@{-}@[blue][ld] & & \bullet \ar@{-}@[blue][ld] \ar@{~}@[red][rd]& & \bullet \ar@{-}@[blue][rd]& & \bullet \ar@{~}@[red][ld] \ar@{-}@[blue][rd] & & \bullet \ar@{~}@[red][rd] & \\
\bullet \ar@{-}@[blue][rd] & & \bullet  & & \bullet \ar@{-}@[blue][ld] \ar@{~}@[red][rd]& & \bullet \ar@{-}@[blue][ld] & & \bullet \ar@{~}@[red][rd] & & \bullet \ar@{-}@[blue][ld]\ar@{~}@[red][rd]& & \bullet \ar@{-}@[blue][ld]& & \bullet \ar@{~}@[red][ld] \\
& \bullet \ar@{-}@[blue][rd] & & \bullet \ar@{-}@[blue][rd] & & \bullet \ar@{=}@[violet][rd] & & \bullet & & \bullet \ar@{=}@[violet][ld] & & \bullet \ar@{=}@[violet][ld] & & \bullet \ar@{~}@[red][ld] & \\
& & \cblu{\circ} & & \cblu{\circ} & & \cblu{\circ} \ar@{~}@[red][ld] & & \cblu{\circ} \ar@{~}@[red][ld] & & \cblu{\circ} \ar@{~}@[red][ld] & & \bullet \ar@{~}@[red][ld] & & \\
& & & \bullet & & \cred{\times} & & \cred{\times} & & \cred{\times} & & \cred{\times} & & & \\
}
\end{array}
\]


%\begin{minipage}[t]{0.4\textwidth }
%Finally, we shorten the vertical bounce path by one edge, replacing $\cred{\times} \mapsto
%\bullet$ with $\bullet \mapsto \cblu{\circ}$ so that the new starting point of the blue path
%is at the same level as the other paths in 
%$\cblu{\calB'}$.  
%\end{minipage}
%%
%%\hskip -1in
%\begin{minipage}[t]{0.59\textwidth}
%\vskip -28pt
%\[
%\begin{array}{c}
%\xymatrixrowsep{0.3pc}\xymatrixcolsep{0.07pc}\xymatrix{
%& & & & \cred{\times} \ar@{~}@[red][ld]& & \cred{\times} \ar@{~}@[red][rd] & & \cred{\times} \ar@{~}@[red][rd] & & \cred{\times} \ar@{~}@[red][rd] & & & & \\
%& & & \cblu{\circ} \ar@{-}@[blue][ld] \ar@{~}@[red][rd] & & \cblu{\circ} \ar@{-}@[blue][ld] & & \cblu{\circ} \ar@{-}@[blue][ld] \ar@{~}@[red][rd] & & \cblu{\circ} \ar@{=}@[violet][rd] & & \cblu{\circ} \ar@{=}@[violet][rd] & & & \\
%& & \bullet \ar@{-}@[blue][ld]  & & \bullet \ar@{~}@[red][ld]\ar@{-}@[blue][rd] & & \bullet \ar@{-}@[blue][rd] & & \bullet \ar@{~}@[red][ld] & & \bullet \ar@{-}@[blue][ld] \ar@{~}@[red][rd] & & \bullet  \ar@{-}@[blue][ld] \ar@{~}@[red][rd] & & \\
%& \bullet \ar@{-}@[blue][ld] & & \bullet \ar@{~}@[red][rd] & & \bullet \ar@{-}@[blue][ld] & & \bullet \ar@{-}@[blue][ld] \ar@{~}@[red][rd]& & \bullet \ar@{-}@[blue][rd]& & \bullet \ar@{~}@[red][ld] \ar@{-}@[blue][rd] & & \bullet \ar@{~}[rd] & \\
%\bullet \ar@{-}@[blue][rd] & & \bullet  & & \bullet \ar@{-}@[blue][ld] \ar@{~}@[red][rd]& & \bullet \ar@{-}@[blue][ld] & & \bullet \ar@{~}@[red][rd] & & \bullet \ar@{-}@[blue][ld]\ar@{~}@[red][rd]& & \bullet \ar@{-}@[blue][ld]& & \bullet \ar@{~}@[red][ld] \\
%& \bullet \ar@{-}@[blue][rd] & & \bullet \ar@{-}@[blue][rd] & & \bullet \ar@{=}@[violet][rd] & & \bullet & & \bullet \ar@{=}@[violet][ld] & & \bullet \ar@{=}@[violet][ld] & & \bullet \ar@{~}@[red][ld] & \\
%& & \cblu{\circ} & & \cblu{\circ} & & \cblu{\circ} \ar@{~}@[red][ld] & & \cblu{\circ} \ar@{~}@[red][ld] & & \cblu{\circ} \ar@{~}@[red][ld] & & \bullet \ar@{~}@[red][ld] & & \\
%& & & \bullet & & \cred{\times} & & \cred{\times} & & \cred{\times} & & \cred{\times} & & & \\
%}
%\end{array}
%\]
%\end{minipage}

%
The last step simply shortens the vertical bounce path by one edge, replacing $\cred{\times} \cblu{\mapsto}
\bullet$ with $\bullet \mapsto \cblu{\circ}$. % so that the new starting point of the blue path
%is at the same level as the other paths in 
%$\cblu{\calB'}$.  
%
The result is a new pair of NILPs $(\cblu{\calB}', \cred{\calR}')$.  %In this example, the
The
lower endpoints of $\cblu{\calB}'$ are now ``skewed left'', representing a monomial in
$\varphi_{5}(i-4, j-5)$, while those of $\cred{\calR}'$ are ``skewed right'', 
representing a monomial in $\varphi_{4}(i-5, j-4)$.  %In other examples, the skewing will
%be opposite, giving a pair $(\cblu{\calB}', \cred{\calR}')$ corresponding to a pair of
%monomials counted by $\varphi_{5}(i-5, j-4)\varphi_{4}(i-4,j-5)$.  
\end{eg}

%{\color{blue} (CUT?)
%\bfit{After (now that?) this proof is clearly written with some pictures, we should be able to write the
%variant (or generalized) version of it with the shifts that we need to prove the general
%theorem. We expect this variant should reduce to the case already proven.
%\noindent 
%This lemma only applies to the case where $M\leq k$ ($M$ of main theorem), i.e., only works
%for part (a) of the main theorem.  Need examples for corner cases where $i$ or $j$ are close
%to $k$ or $k-1$.  Figure out what the expression turns into in these cases. 
%}}

Just as Lemma \ref{lem:bounce} is used to prove Theorem \ref{thm:main} (a), covering the cases when $0 \leq k \leq M$, we reduce the proof of Theorem \ref{thm:main} (b), i.e., $M \leq k \leq r + s + 1$, to the following claim.

\begin{claim} \label{claim:Mk}
Under the hypotheses of Theorem \ref{thm:main}, if $M=k$ (i.e., $i+j=k$)
then $$\rho_B^{k+1}(i,j) = \mu^{(i,j)} \left(\frac{\varphi_{0}(i,j)}{\varphi_{1}(i,j)}\right)
= \mu^{(i,j)} \rho_B^1(i,j) = \frac{1}{x_{r-i,s-j}}.$$ 
\end{claim}

\begin{proof} The first two equalities follow from Theorem \ref{thm:main} (a),
while we prove the last equality as follows.  Since the principal order filter
$\bigvee_{(i,j)}$ is isomorphic to the product of chains $[0,r-i]\times [0,r-j]$, we easily
reduce the claim to the case
%%% Not sure whether it's worth adding a picture here\dots TR
$i=j=k=0$, i.e., %it suffices to show the last equality of 
\[
\rho_B^1(0,0) = \frac{\varphi_{0}(0,0)}{\varphi_{1}(0,0)} =
\frac{\prod_{p=0}^r \prod_{q=0}^s A_{pq}}
{\sum_{ \calL  \in S_{1}(0,0)}
\hspace{2em}\prod_{\stackrel{(i,j) \in \lpreg_{(0,0)}^{1}}{(i,j) \not \in L_1}} A_{ij}. 
} = \frac{1}{x_{r,s}}. 
% {\sum_{\mathrm{paths~L~from~}(0,0) \in [0,r] \times
% [0,s]} \prod_{(p,q)\in L} A_{p,q}^{-1} }.
\] 
In this situation, our family of lattice %lattices 
paths reduces to a single lattice path $L_{1}$,
the numerator can be thought of as $\ds \prod_{(p,q)\in P}A_{pq}$, and $\lpreg_{(0,0)}^{1} =
P$ as well.  By clearing denominators and dividing through by the double-product) we
equivalently need to show %the following: 
%\begin{claim} \label{claim:00}
%\[
$\sum_{ \calL  \in S_{1}(0,0)}
\kern 1em \prod_{{(i,j) \in L_1}} A_{ij}^{-1} = x_{r,s}.$ 
% \sum_{\mathrm{paths~L~from~}(0,0) \in [0,r] \times
% [0,s]} \prod_{(p,q)\in L} A_{p,q}^{-1}  = x_{r,s}. 
%\]
%\end{claim}
%\textit{Proof.}
For the base case $s=0$, we get $P$ is a chain of length $r$ and the only lattice path %LP 
consists of
every element of $P$.  In this case $A_{i0} = \frac{x_{i,0}}{x_{i-1,0}}$ for $i\in [r]$, with
$A_{00} = x_{00}$, so the single summand is the telescoping product 
$
\frac{x_{0,0}}{1}\cdot \frac{x_{1,0}}{x_{0,0}}\cdot \frac{x_{2,0}}{x_{1,0}}\cdot 
\dotsb  \frac{x_{r,0}}{x_{r-1,0}} = x_{r,0}
$
as required.  Symmetrically, the claim also holds for $r=0$ and any $s$.  Now suppose that
$rs>0$ and 
the claim holds for every rectangular posets whose dimensions are strictly smaller than
$[0,r]\times [0,s]$.  Set $\frakL(p,q): = \{\text{lattice paths from } (0,0)\text{ to }
(p,q)\}$.   Any lattice path %LP 
from $(0,0)$ to $(r,s)$ must go through either $(r-1,s)$
or $(r,s-1)$.  Thus,
\begin{align*}
\sum_{ \calL  \in S_{1}(0,0)} \kern 1em \prod_{{(i,j) \in L_1}} A_{ij}^{-1} 
& = A_{r,s}^{-1} \sum_{L\in \frakL (r-1,s)} \kern 1em \prod_{{(i,j) \in L}} A_{ij}^{-1} 
    +A_{r,s}^{-1} \sum_{L\in \frakL (r,s-1)} \kern 1em \prod_{{(i,j) \in L}} A_{ij}^{-1}\\ 
& = A_{r,s}^{-1} (x_{r-1,s} + x_{r,s-1})  = x_{r,s}, 
\end{align*}
using the induction hypothesis and the definition of $A_{i,j}$.  %This finishes the proofs of
%both Claim~\ref{claim:00} and Claim~\ref{claim:Mk}.  
\end{proof}


\begin{comment}
The next lemma %\footnote{{\color{red}We might need to flesh out this exposition but perhaps have a pre-amble to Lemma 11 setting it up like this attempt.}} 
allows us to handle cases where shifting the point $(i,j)$ by $(-k,-k)$ lands
us outside of the poset $P$.  In such cases we shift the point back inside $P$ so
that the lattice paths are well defined, shifting the indices of
the $A$-variables accordingly.  %back to their correct values for rowmotion at that actual point.    
\begin{lemma}\label{lem:genBounce}
For $i,j,k$ such that $(i,j) \in [0,r]\times [0,s]$ and %$r+s+1 \geq k \geq [k-i]_+ + [k-j]_+$
$\left([k-i]_+ + [k-j]_+\right) \leq k \leq (r+s+1)$, we have the Pl\"ucker-like relation:
\begin{small}
$$\mu^{([k-j]_+,[k-i]_+)} \varphi_{k-M_{00}}(i-k+M_{00},j-k+M_{00})
~\mu^{([k-j-1]_+,[k-i-1]_+)} \varphi_{k-1-M_{11}}(i-k+1+M_{11},j-k+1+M_{11})$$
%
$$ = \mu^{([k-j]_+,[k-i-1]_+)} \varphi_{k-M_{10}}(i-k+1+M_{10},j-k+M_{10})  
~\mu^{([k-j-1]_+,[k-i]_+)} \varphi_{k-1-M_{01}}(i-k+M_{01},j-k+1+M_{01})$$
%
$$+ \mu^{([k-j-1]_+,[k-i]_+)} \varphi_{k-M_{01}}(i-k+M_{01},j-k+1+M_{01}) 
~\mu^{([k-j]_+, [k-i-1]_+)} \varphi_{k-1-M_{10}}(i-k+1+M_{10},j-k+M_{10}),$$
where $M_{00} = [k-i]_+ + [k-j]_+$, $M_{11} = [k-i-1]_+ + [k-j-1]_+$, $M_{01} = [k-i]_+ +
[k-j-1]_+$, and $M_{10} = [k-i-1]_+ + [k-j]_+$.  
\end{small}
     % \bfit{Why does my spacing look so much bigger than $$-version? align doesn't compress
     % horizontally when it runs out of room!  See
     % https://tex.stackexchange.com/questions/321/align-vs-equation?noredirect=1&lq=1 }
     % \begin{align*}
     % \begin{split}
     % \mu^{([k-i]_+,[k-j]_+)} \varphi_{k-M_{00}}(i-k+M_{00},j-k+M_{00})
     % ~\mu^{([k-i-1]_+,[k-j-1]_+)} \varphi_{k-1-M_{11}}(i-k+1+M_{11},j-k+1+M_{11})\\   
     %  = 
     % \mu^{([k-i]_+,[k-j-1]_+)} \varphi_{k-M_{01}}(i-k+M_{01},j-k+1+M_{01}) 
     % ~\mu^{([k-i-1]_+, [k-j]_+)} \varphi_{k-1-M_{10}}(i-k+1+M_{10},j-k+M_{10})\\  
     % ~+
     % \mu^{([k-i-1]_+,[k-j]_+)} \varphi_{k-M_{10}}(i-k+1+M_{10},j-k+M_{10})  
     % ~\mu^{([k-i]_+,[k-j-1]_+)} \varphi_{k-M_{01}}(i-k+M_{01},j-k+1+M_{01})
     % \end{split}
     % \end{align*}
\end{lemma}

This result includes Lemma \ref{lem:bounce} as a special case since  $1 \leq k\leq \min \{ i,j \}$ implies that $[k-i]_+ = [k-j]_+ = 0$ and therefore $\left([k-i]_+ + [k-j]_+\right) \leq k \leq (r+s+1)$ immediately holds.  We use Lemma \ref{lem:genBounce} to complete the proof of case (a) of Theorem \ref{thm:main}.  Part (b) is handled by a separate argument.
%As we will see later, this generalized Lemma allows us to complete the proof of case (a) of Theorem \ref{thm:main}.  Part (b) is handled by a separate argument.


\begin{proof} 
We prove this more general case by extending the domain where Lemma \ref{lem:bounce} holds and
then specializing to the case we need.  In particular, we extend the rectangular poset
$[0,r]\times [0,s]$ by embedding it inside $\{-r-s,-r-s+1,\dots, r-1, r\} \times
\{-r-s,-r-s+1,\dots, s-1,s\}$.
%$\{-r-s,-r-s+1,\dots, -1, 0,1,\dots, r\} \times \{-r-s,-r-s+1,\dots, -1, 0,1,\dots, s\}$.  
Inside of this larger rectangular poset, build the order filter with base $(i-k, j-k)$
noting that each or both of these coordinates could now be negative (and therefore would
have been outside the original $[0,r]\times [0,s]$ poset). 

Let $\Phi_k(i-k,j-k)$ denote the set of non-intersecting lattice-paths (NILPs) in this order filter.  Following Lemma \ref{lem:bounce}, we have a combinatorial bijection 
$$\Phi_k(i-k,j-k) \times \Phi_{k-1}(i-k+1,j-k+1) \to \Phi_k(i-k+1,j-k) \times \Phi_{k-1}(i-k,j-k+1)$$ 
$$\bigcup \Phi_k(i-k,j-k+1)\Phi_{k-1}(i-k+1,j-k)$$
where the right-hand-side is a disjoint union.

We let $\Phi_k(a,b)^{(c,d)}$ be shorthand for the subset of NILPs in the order filter based at point $(a,b)$ such that the lattice paths from $\{s_1,s_2,\dots, s_c\}$ to $\{t_1,t_2,\dots, t_c\}$ (ordered left-to-right in their respective ranks of $\{-r-s,-r-s+1,\dots, r\} \times \{-r-s,-r-s+1,\dots,s\}$) each traverse the leftmost possible route in the order filter and the lattice paths from $\{s_{k-d+1}, s_{k-d+2},\dots, s_{k}\}$ to $\{t_{k-d+1}, t_{k-d+2},\dots, t_{k}\}$ traverse the rightmost routes.  We refer to such NILPs as {\bf (c,d)-boundary hugging}.  This notation is well-defined whenever $k \geq c+d$.

%\footnote{{\color{red}DOUBLE-CHECK THAT THIS IS THE DEFINITION WE WANT.  MAYBE INSTEAD IS THE ALMOST LEFT-MOST AND RIGHT-MOST SO THAT THE BLUE AND RED LATTICE PATHS COINCIDE ALMOST ALL THE TIME ON THE LEFT AND RIGHT.}}.  This notation is well-defined whenever $k \geq c+d$.

Using this notation, we claim that the above restricts to a bijection 
\begin{eqnarray} \label{eq:restrictbounce} \Phi_k(i-k,j-k)^{([k-j]_+,[k-i]_+)} \times \Phi_{k-1}(i-k+1,j-k+1)^{([k-j-1]_+,[k-i-1]_+)} \to 
\\ \nonumber \Phi_k(i-k+1,j-k)^{([k-j]_+,[k-i-1]_+)}\times \Phi_{k-1}(i-k,j-k+1)^{([k-j-1]_+,[k-i]_+)} \\ 
\nonumber \bigcup
\Phi_k(i-k,j-k+1)^{([k-j-1]_+,[k-i]_+)}\Phi_{k-1}(i-k+1,j-k)^{([k-j]_+,[k-i-1]_+)}\end{eqnarray}
Note that we have assumed that $k \geq [k-i]_+ + [k-j]_+$, so all six of these sets are well-defined.

To see this, consider Figure \ref{fig:boundary-hugging} (a).  The leftmost and rightmost lattice paths in the pair of NILPs associated to $ \Phi_k(i-k,j-k)^{([k-j]_+,[k-i]_+)} \times \Phi_{k-1}(i-k+1,j-k+1)^{([k-j-1]_+,[k-i-1]_+)}$.  
%
%We illustrate the case where $[k-j]_+ = 3$ and $[k-i]_+ = 2$ so that we have $(3,2)$-boundary hugging blue paths and $(2,1)$-boundary hugging red paths.  
%
Without loss of generality, assume in our configuration that the {\bf horizontal bounce path} starts from the {\bf rightmost} $\cblu{\circ}$.  We hence swap the colors on the right but leave them unchanged on the left except for the twigs.  (If the horizontal bounce path starts from the leftmost $\cblu{\circ}$ instead, we use the mirror image.) 

After this swap, we have a configuration that has the form of Figure \ref{fig:boundary-hugging} (b).  
%
In particular the pattern of upward steps and downward steps starting from the bottom of the horizontal bounce path changes the colors of the rightmost boundary-hugging blue and red paths in a predictable way.  Furthermore, the horizontal bounce path cannot reach the leftmost $[k-j]_+$ boundary hugging blue paths since red steps are downward steps and cannot intersect the blue steps that are pointed down and to the left.  
%
%In particular, by analyzing the pattern of upward steps and downward steps of the horizontal bounce path, it follows that it is not possible for this bounce path to reach the leftmost $[k-j]_+$ blue paths nor leftmost $[k-j-1]_+$ red paths.
%
The resulting configuration after the swap corresponds to a pair of NILPs of the form 
$\Phi_k(i-k+1,j-k)^{([k-j]_+,[k-i-1]_+)}\times \Phi_{k-1}(i-k,j-k+1)^{([k-j-1]_+,[k-i]_+)}$.  %Continuing with our illustrated example, we would have 
%$(3,1)$-boundary hugging blue paths, which are left-justified, and $(2,2)$-boundary hugging red paths, which are right-justified.



%{\color{green}Starting with a pairs of NILPs, one in $\Phi_k(i-k,j-k)^{([k-j]_+,[k-i]_+)}$ and one in $\Phi_{k-1}(i-k+1,j-k+1)^{([k-j-1]_+,[k-i-1]_+)}$, we note that after excluding the very leftmost and very rightmost paths of $\Phi_k(i-k,j-k)^{([k-j]_+,[k-i]_+)}$ (which are disjoint\footnote{DOUBLE-CHECK-MIGHT-ACTUALLY NEED BOUNCING!!!} from any other path of  $\Phi_{k-1}(i-k+1,j-k+1)^{([k-j-1]_+,[k-i-1]_+)}$), the remaining $[k-i-1]_+$ leftmost paths of these two sets overlap and the same is true for the remaining $[k-j-1]_+$ rightmost paths.  Thus, when we apply the map by switching segments based on bounce paths, all $[k-i]_+ + [k-j]_+$ of the named paths are unchanged.  Hence, the right-hand-side of (\ref{eq:restrictbounce}) is indeed restricted as above.

%ACTUALLY THE PREVIOUS PARAGRAPH IS SLIGHTLY INCORRECT, INSTEAD: Either these leftmost paths or rightmost paths are disjoint from any other path of $\Phi_{k-1}(i-k+1,j-k+1)^{([k-j-1]_+,[k-i-1]_+)}$.  However, whichever way it goes, the collision will not create a bounce path and hence $\Phi_{k-1}(i-k+1,j-k+1)^{([k-j-1]_+,[k-i-1]_+)}$ and $\Phi_k(i-k,j-k)^{([k-j]_+,[k-i]_+)}$ are indeed unaffected except for an obvious transformation on the extreme left and right hand sides.}

Furthermore, because we have used boundary-hugging paths as constructed above, the only elements of this order filters left uncovered by any of these six sets of NILPs are elements that are in the original $[0,r]\times [0,s]$ poset, i.e., with nonnegative entries for both coordinates.  Consequently, the map defined by (\ref{eq:restrictbounce}) yields a weight-preserving-bijection after weighting NILPs $\mathcal{L}$ by the products of the $A_{cd}$'s for points $(c,d) \in [0,r]\times [0,s]$ left uncovered by $\mathcal{L}$.  
%
We end up associating the lattice paths in $\Phi_k(i-k,j-k)^{([k-j]_+,[k-i]_+)}$ to an order filter that has the element $(\bfr - [k-j]_+,\bfs-[k-i]_+)$ as its top (rather than $(\bfr,\bfs)$).  

We then obtain Lemma \ref{lem:genBounce} as written by translating the bottom and top of the order filter: Hence, for each $\epsilon_i,\epsilon_j \in \{0,1\}$, the subset
$\Phi_k(i-k+\epsilon_i,j-k+\epsilon_j)^{([k-j-\epsilon_j]_+,[k-i-\epsilon_i]_+)}$ has 
$$\mu^{([k-j-\epsilon_j]_+,[k-i-\epsilon_i]_+)} \varphi_{k-M_{\epsilon_i \epsilon_j}}(i-k+M_{\epsilon_i \epsilon_j},j-k+M_{\epsilon_i \epsilon_j})$$
as its generating function.
\end{proof}


%{ \color{red}DOUBLE-CHECK INDEXING IN THE ABOVE.  MIGHT HAVE SWITCHED I AND J COORDINATES IN SOME PLACES.}
 





\begin{figure}[h]
(a) \[
\begin{array}{c}
\xymatrixrowsep{0.9pc}\xymatrixcolsep{0.20pc}\xymatrix{
& & & & \cred{\times} \ar@{~}@[red][ld] & & \cred{\times} \ar@{~}@[red][ld] & & \cred{\times} \ar@{~}@[red][ld] & & \cred{\times} \ar@{~}@[red][ld] & & \cred{\times} \ar@{~}@[red][rd] & & \cred{\times} \ar@{~}@[red][rd] & & \cred{\times} \ar@{~}@[red][rd] & & & & \\
& & & \cblu{\circ} \ar@{=}@[violet][ld] & & \cblu{\circ} \ar@{=}@[violet][ld] & & \cblu{\circ} \ar@{-}@[blue][ld] \ar@{~}@[red][rd] & & \cblu{\circ} \ar@{-}@[blue][ld] \ar@{~}@[red][rd] & & \cblu{\circ} \ar@{-}@[blue][ld] & & \cblu{\circ} \ar@{~}@[red][ld] \ar@{-}@[blue][rd] & & \cblu{\circ} \ar@{=}@[violet][rd] & & \cblu{\circ} \ar@{=}@[violet][rd] & & & \\
& & \bullet \ar@{=}@[violet][ld]  & & \bullet \ar@{=}@[violet][ld]  & & \bullet \ar@{-}@[blue][ld]  & & \bullet \ar@{=}@[violet][rd]  & & \bullet \ar@{=}@[violet][rd] & & \bullet \ar@{~}@[red][rd] & & \bullet \ar@{-}@[blue][rd] & & \bullet \ar@{~}@[red][ld] \ar@{-}@[blue][rd] & & \bullet \ar@{=}@[violet][rd] & & \\
& \bullet \ar@{-}@[blue][ld]\ar@{~}@[red][rd]  & & \bullet \ar@{-}@[blue][ld]\ar@{~}@[red][rd]  & & \bullet \ar@{-}@[blue][ld] & & \bullet \ar@{-}@[white][ld] & & \bullet \ar@{~}@[red][ld] \ar@{-}@[blue][rd] & & \bullet \ar@{~}@[red][ld] \ar@{-}@[blue][rd] & & \bullet \ar@{~}@[red][rd] & & \bullet \ar@{-}@[blue][ld] \ar@{~}@[red][rd] & & \bullet \ar@{-}@[white][ld] \ar@{-}@[blue][rd] & & \bullet \ar@{~}@[red][ld] \ar@{-}@[blue][rd] & \\
\bullet \ar@{-}@[blue][rd] & & \bullet \ar@{=}@[violet][rd] & &  \bullet \ar@{=}@[violet][rd] & &  \bullet \ar@{-}@[white][rd] & & \bullet \ar@{~}@[red][ld]  & & \bullet \ar@{=}@[violet][ld] & & \bullet \ar@{-}@[blue][ld] & & \bullet \ar@{=}@[violet][ld] & & \bullet \ar@{~}@[red][ld]\ar@{-}@[white][rd]& & \bullet \ar@{=}@[violet][ld]& & \bullet \ar@{-}@[blue][ld] \\
& \bullet \ar@{-}@[blue][rd] & & \bullet \ar@{=}@[violet][rd] & & \bullet \ar@{=}@[violet][rd] & & \bullet \ar@{~}@[red][rd] & & \bullet \ar@{=}@[violet][rd] & & \bullet \ar@{-}@[blue][rd] & & \bullet \ar@{~}@[red][ld]\ar@{-}@[blue][rd] & & \bullet \ar@{~}@[red][ld] & & \bullet \ar@{=}@[violet][ld] & & \bullet \ar@{-}@[blue][ld] & \\
& & \bullet \ar@{-}@[blue][rd] & & \cred{\times}\ar@{-}@[blue][rd] & & \cred{\times}\ar@{-}@[blue][rd] & & \cred{\times} \ar@{-}@[white][ld] & & \cred{\times} \ar@{-}@[blue][ld] & & \cred{\times} \ar@{-}@[blue][ld] & & \cred{\times} \ar@{-}@[blue][ld] & & \cred{\times} \ar@{-}@[blue][ld] & & \bullet \ar@{-}@[blue][ld] & & \\ 
& & & \cblu{\circ} & & \cblu{\circ} & & \cblu{\circ} & & \cblu{\circ} & & \cblu{\circ} & & \cblu{\circ} & & \cblu{\circ} & & \cblu{\circ} & & &
}
\end{array}
\]


(b) \[
\begin{array}{c}
\xymatrixrowsep{0.9pc}\xymatrixcolsep{0.20pc}\xymatrix{
& & & & \cred{\times} \ar@{~}@[red][ld] & & \cred{\times} \ar@{~}@[red][ld] & & \cred{\times} \ar@{~}@[red][ld] & & \cred{\times} \ar@{~}@[red][ld] & & \cred{\times} \ar@{~}@[red][rd] & & \cred{\times} \ar@{~}@[red][rd] & & \cred{\times} \ar@{~}@[red][rd] & & & & \\
& & & \cblu{\circ} \ar@{=}@[violet][ld] & & \cblu{\circ} \ar@{=}@[violet][ld] & & \cblu{\circ} \ar@{-}@[blue][ld] \ar@{~}@[red][rd] & & \cblu{\circ} \ar@{-}@[blue][ld] \ar@{~}@[red][rd] & & \cblu{\circ} \ar@{-}@[blue][ld] & & \cblu{\circ} \ar@{->}@[blue][ld] \ar@{<--}@[red][rd] & & \cblu{\circ} \ar@{=}@[violet][rd] & & \cblu{\circ} \ar@{=}@[violet][rd] & & & \\
& & \bullet \ar@{=}@[violet][ld]  & & \bullet \ar@{=}@[violet][ld]  & & \bullet \ar@{-}@[blue][ld]  & & \bullet \ar@{=}@[violet][rd]  & & \bullet \ar@{=}@[violet][rd] & & \bullet \ar@{->}@[blue][rd] & & \bullet \ar@{<--}@[red][rd] & & \bullet \ar@{->}@[blue][ld] \ar@{<--}@[red][rd] & & \bullet \ar@{=}@[violet][rd] & & \\
& \bullet \ar@{-}@[blue][ld]\ar@{~}@[red][rd]  & & \bullet \ar@{-}@[blue][ld]\ar@{~}@[red][rd]  & & \bullet \ar@{-}@[blue][ld] & & \bullet \ar@{-}@[white][ld] & & \bullet \ar@{->}@[blue][ld] \ar@{<--}@[red][rd] & & \bullet \ar@{->}@[blue][ld] \ar@{<--}@[red][rd] & & \bullet \ar@{->}@[blue][rd] & & \bullet \ar@{<--}@[red][ld] \ar@{->}@[blue][rd] & & \bullet \ar@{-}@[white][ld] \ar@{<--}@[red][rd] & & \bullet \ar@{->}@[blue][ld] \ar@{<--}@[red][rd] & \\
\bullet \ar@{-}@[blue][rd] & & \bullet \ar@{=}@[violet][rd] & &  \bullet \ar@{=}@[violet][rd] & &  \bullet \ar@{-}@[white][rd] & & \bullet \ar@{->}@[blue][ld]  & & \bullet \ar@{=}@[violet][ld] & & \bullet \ar@{<--}@[red][ld] & & \bullet \ar@{=}@[violet][ld] & & \bullet \ar@{->}@[blue][ld]\ar@{-}@[white][rd]& & \bullet \ar@{=}@[violet][ld]& & \bullet \ar@{<--}@[red][ld] \\
& \bullet \ar@{-}@[blue][rd] & & \bullet \ar@{=}@[violet][rd] & & \bullet \ar@{=}@[violet][rd] & & \bullet \ar@{->}@[blue][rd] & & \bullet \ar@{=}@[violet][rd] & & \bullet \ar@{<--}@[red][rd] & & \bullet \ar@{->}@[blue][ld]\ar@{<--}@[red][rd] & & \bullet \ar@{->}@[blue][ld] & & \bullet \ar@{=}@[violet][ld] & & \bullet \ar@{<--}@[red][ld] & \\
& & \cblu{\circ}  & &\cblu{\circ}\ar@{-}@[red][rd] & &\cblu{\circ}\ar@{-}@[red][rd] & &\cblu{\circ} \ar@{-}@[white][ld] & &\cblu{\circ} \ar@{-}@[red][ld] & &\cblu{\circ} \ar@{-}@[red][ld] & &\cblu{\circ} \ar@{-}@[red][ld] & &\cblu{\circ} \ar@{-}@[red][ld] & & \bullet \ar@{<--}@[red][ld] & & \\ 
& & & \bullet  & &  \cred{\times} & &  \cred{\times} & &  \cred{\times} & &  \cred{\times} & &  \cred{\times} & &  \cred{\times} & &  \cred{\times} & & &
}
\end{array}
\]


%\[
%\begin{array}{c}
%\xymatrixrowsep{0.9pc}\xymatrixcolsep{0.20pc}\xymatrix{
%& & & & \cred{\times} \ar@{--}@[red][ld] & & \cred{\times} \ar@{--}@[red][ld] & & \cred{\times} \ar@{--}@[white][rd] & & \cred{\times} \ar@{--}@[white][rd] & & \cred{\times} \ar@{--}@[white][rd] & & \cred{\times} \ar@{--}@[white][rd] & & \cred{\times} \ar@{--}@[red][rd] & & & & \\
%& & & \cblu{\circ }\ar@{=}@[violet][ld] & & \cblu{\circ} \ar@{=}@[violet][ld] & & \cblu{\circ} \ar@{-}@[blue][ld] \ar@{--}@[white][rd] & & \cblu{\circ} \ar@{-}@[white][ld] \ar@{--}@[white][rd] & & \cblu{\circ} \ar@{-}@[white][ld] & & \cblu{\circ} \ar@{-}@[white][ld] \ar@{--}@[white][rd] & & \cblu{\circ} \ar@{--}@[red][rd] & & \cblu{\circ} \ar@{=}@[violet][rd] & & & \\
%& & \bullet \ar@{=}@[violet][ld]  & & \bullet \ar@{=}@[violet][ld]  & & \bullet \ar@{-}@[blue][ld]  & & \bullet \ar@{-}@[white][ld]  & & \bullet \ar@{--}@[white][ld]\ar@{-}@[white][rd] & & \bullet \ar@{-}@[white][rd] & & \bullet \ar@{--}@[white][ld] & & \bullet \ar@{--}@[red][rd] & & \bullet \ar@{=}@[violet][rd] & & \\
%& \bullet \ar@{-}@[blue][ld]\ar@{--}@[red][rd]  & & \bullet \ar@{-}@[blue][ld]\ar@{--}@[red][rd]  & & \bullet \ar@{-}@[blue][ld] & & \bullet \ar@{-}@[white][ld] & & \bullet \ar@{--}@[white][rd] & & \bullet \ar@{-}@[white][ld] & & \bullet \ar@{--}@[white][ld] \ar@{-}@[white][rd]& & \bullet \ar@{--}@[white][rd]& & \bullet \ar@{-}@[white][ld] \ar@{--}@[red][rd] & & \bullet \ar@{-}@[blue][ld] \ar@{--}@[red][rd] & \\
%\bullet \ar@{-}@[blue][rd] & & \bullet \ar@{=}@[violet][rd] & &  \bullet \ar@{=}@[violet][rd] & &  \bullet \ar@{-}@[white][rd] & & \bullet  & & \bullet \ar@{--}@[white][ld] \ar@{-}@[white][rd]& & \bullet \ar@{--}@[white][ld] & & \bullet \ar@{-}@[white][rd] & & \bullet \ar@{--}@[white][ld]\ar@{-}@[white][rd]& & \bullet \ar@{=}@[violet][ld]& & \bullet \ar@{--}@[red][ld] \\
%& \bullet \ar@{-}@[blue][rd] & & \bullet \ar@{=}@[violet][rd] & & \bullet \ar@{=}@[violet][rd] & & \bullet \ar@{-}@[white][rd] & & \bullet \ar@{--}@[white][rd] & & \bullet \ar@{=}@[white][rd] & & \bullet & & \bullet \ar@{=}@[white][ld] & & \bullet \ar@{=}@[violet][ld] & & \bullet \ar@{--}@[red][ld] & \\
%& & \cblu{\circ} \ar@{-}@[white][rd] & & \cblu{\circ}\ar@{--}@[red][rd] & & \cblu{\circ}\ar@{--}@[red][rd] & & \cblu{\circ} \ar@{-}@[white][ld] & & \cblu{\circ} \ar@{-}@[white][ld] & & \cblu{\circ} \ar@{-}@[white][ld] & & \cblu{\circ} \ar@{-}@[white][ld] & & \cblu{\circ} \ar@{--}@[red][ld] & & \bullet \ar@{--}@[red][ld] & & \\ 
%& & & \bullet & & \cred{\times} & & \cred{\times} & & \cred{\times} & & \cred{\times} & & \cred{\times} & & \cred{\times} & & \cred{\times} & & &
%}
%\end{array}
%\]

\caption{(a) Illustrating a pair of NILPs which are {\color{blue}$(3,2)$-boundary hugging} and {\color{red}$(2,1)$-boundary hugging}, respectively. (b) After applying our bijection, we have a {\color{blue}$(3,1)$-boundary-hugging NILP} and a {\color{red}$(2,2)$-boundary-hugging NILP}.}
\label{fig:boundary-hugging}
\end{figure}

\begin{eg}
We consider the NILPs illustrated in Figure \ref{fig:boundary-hugging} (a).  In this  case, $[k-j]_+ = 3$ and $[k-i]_+ = 2$ so that we have $(3,2)$-boundary hugging blue paths and $(2,1)$-boundary hugging red paths.  
%
In this example, the {\bf horizontal bounce path} starts from the {\bf rightmost} $\cblu{\circ}$ (as opposed to the leftmost $\cblu{\circ}$).
After swapping colors along the horizontal bounce path, we get the NILPs of Figure
\ref{fig:boundary-hugging} (b) with $(3,1)$-boundary hugging blue paths, which are
left-justified, and $(2,2)$-boundary hugging red paths, which are right-justified.  
\end{eg}



%{\color{red} 
%\begin{proof} Case 1) If $k \leq \min\{i,j\}$, then $[k-i]_+ = [k-i-1]_+ = [k-j]_+ = [k-j-1]_+ =0$, and Lemma \ref{lem:genBounce} follows from Lemma 
%\ref{lem:bounce} in this case.
%
%Case 2) Suppose that $i \leq k-1$, $j  \geq k$.  Then $[k-i]_+ = (k-i)$, $[k-i-1]_+ = (k-i-1)$, but $[k-j]_+ = [k-j-1]_+ =0$.
%Hence $M_{00} = (k-i) = M_{01} = (k-i)$, and $M_{11} = M_{10} = (k-i-1)$.  In this case, the statement of Lemma \ref{lem:genBounce} reduces to
%
%\begin{small}
%$$\mu^{(k-i,0)} \varphi_{i}(0,j-i)
%~\mu^{(k-i-1,0)} \varphi_{i}(0,j-i)
%%
% = \mu^{(k-i-1,0)} \varphi_{i+1}(0,j-i-1)  
%~\mu^{(k-i,0)} \varphi_{i-1}(0,j-i+1)$$
%%
%$$+ \mu^{(k-i,0)} \varphi_{i}(0,j-i+1) 
%~\mu^{(k-i-1, 0)} \varphi_{i}(0,j-i-1).$$
%\end{small}
%
%We note that this equation agrees with 
%$$\varphi_{k}(i-k, j-k) \varphi_{k-1}(i-k+1,j-k+1) =
%\varphi_k(i-k+1,j-k)\varphi_{k-1}(i-k,j-k+1)$$
%$$+ \varphi_{k}(i-k,j-k+1)\varphi_{k-1}(i-k+1,j-k)$$
%except that we shift the order filters to compensate for the fact that we are considering bottom points with negative $i$-coordinates and hence outside the poset.  We automatically adjoin forced non-intersecting lattice paths in the larger poset which naturally decreases the number of paths in the NILP and the shift in the order filter is incorporated into the $\mu$-translation.
%
%EXPLAIN THIS BETTER?  DRAW PICTURES??  IS IT POSSIBLE TO PROVE THIS DIRECTLY WITHOUT CONSIDERING THE PICTURE AS HANGING OUTSIDE THE POSET??
%
%OTHER CASES?
%\end{proof}
%
%
%\begin{proof}
%Case 1) If $k \leq \min\{i,j\}$, then $[k-i]_+ = [k-i-1]_+ = [k-j]_+ = [k-j-1]_+ =0$, and Lemma \ref{lem:genBounce} follows from Lemma 
%\ref{lem:bounce} in this case.
%
%\newpage
%
%Case 2) Suppose that $i=k-1$ and $j \geq k$.  Then $[k-i]_+ = 1$, but $[k-i-1]_+ = [k-j]_+ = [k-j-1]_+ =0$.  Hence $M_{00} = M_{01} = 1$ while $M_{11}=M_{10}=0$.  In this case, the statement of Lemma \ref{lem:genBounce} reduces to
%
%\begin{small}
%$$\mu^{(1,0)} \varphi_{k-1}(0,j-k+1)
%~\mu^{(0,0)} \varphi_{k-1}(0,j-k+1)
%%
%= \mu^{(0,0)} \varphi_{k}(0,j-k)  
%~\mu^{(1,0)} \varphi_{k-2}(0,j-k+2)$$
%%
%$$+ \mu^{(1,0)} \varphi_{k-1}(0,j-k+2) 
%~\mu^{(0, 0)} \varphi_{k-1}(0,j-k),$$
%..... .
%\end{small}
%
%
%Case 3) Suppose that $i < k-1$ and $j  \geq k$.  Then $[k-i]_+ = (k-i)$, $[k-i-1]_+ = (k-i-1)$, but $[k-j]_+ = [k-j-1]_+ =0$. 
%Hence $M_{00} = (k-i) = M_{01} = (k-i)$, and $M_{11} = M_{10} = (k-i-1)$.  In this case, the statement of Lemma \ref{lem:genBounce} reduces to
%
%\begin{small}
%$$\mu^{(k-i,0)} \varphi_{i}(0,j-i)
%~\mu^{(k-i-1,0)} \varphi_{i}(0,j-i)
%%
% = \mu^{(k-i-1,0)} \varphi_{i+1}(0,j-i-1)  
%~\mu^{(k-i,0)} \varphi_{i-1}(0,j-i+1)$$
%%
%$$+ \mu^{(k-i,0)} \varphi_{i}(0,j-i+1) 
%~\mu^{(k-i-1, 0)} \varphi_{i}(0,j-i-1),$$
%\end{small}
%
%NOTICE THAT CASE 2 IS IN FACT A SPECIAL CASE OF CASE 3. (i.e., let $i \leq k-1$)
%
%
%Case 4) Suppose that $i \leq k-1$ and $j \leq  k-1$.  Then $[k-i]_+ = (k-i)$, $[k-i-1]_+ = (k-i-1)$, $[k-j]_+ = (k-j)$, and $[k-j-1]_+ = (k-j-1)$. 
%Hence $M_{00} = 2k-i-j$, $M_{01} = M_{10} = 2k-i-j-1$, and $M_{11} = 2k-i-j-2$.  In this case, the statement of Lemma \ref{lem:genBounce} reduces to
%
%\begin{small}
%$$\mu^{(k-i,k-j)} \varphi_{i+j-k}(k-j,k-i)
%~\mu^{(k-i-1,k-j-1)} \varphi_{i+j-k+1}(k-j-1,k-i-1)$$
%%
%$$= \mu^{(k-i-1,k-j)} \varphi_{i+j-k+1}(k-j,k-i-1)  
%~\mu^{(k-i,k-j-1)} \varphi_{i+j-k}(k-j-1,k-i)$$
%%
%$$+ \mu^{(k-i,k-j-1)} \varphi_{i+j-k+1}(k-j-1,k-i) 
%~\mu^{(k-i-1, k-j)} \varphi_{i+j-k}(k-j,k-i-1),$$
%\end{small}
%
%Let $I = k-i-1 \geq 0$, $J = k -j-1 \geq 0$ in this case, which turns this identity into
%
%\begin{small}
%$$\mu^{(I+1,J+1)} \varphi_{k-I-J-2}(J+1,I+1)
%~\mu^{(I,J)} \varphi_{k-I-J-1}(J,I)$$
%%
%$$= \mu^{(I,J+1)} \varphi_{k-I-J-1}(J+1,I)  
%~\mu^{(I+1,J)} \varphi_{k-I-J-2}(J,I+1)$$
%%
%$$+ \mu^{(I+1,J)} \varphi_{k-I-J-1}(J,I+1) 
%~\mu^{(I, J+1)} \varphi_{k-I-J-2}(J+1,I),$$
%\end{small}
%
%
%
%NOTE: NEED $k \geq i + j$ FOR THIS TO BE CASE A OF THE MAIN THEOREM
%
%Other Cases....
%
%\end{proof}}

\vspace{-1em}

\subsection{Proof of Theorem \ref{thm:main} (a)}

We consider the off-boundary case where $(i,j)$ both covers and is covered by two elements
of $P$. 
  Under this hypothesis, we have the following identity by the definition of birational rowmotion:
$$\rho_B^{k+1}(i,j) = \frac{\bigg(\rho_B^k(i,j-1) + \rho_B^k(i-1,j)\bigg) \bigg( \rho_B^{k+1}(i+1,j) \parallel \rho_B^{k+1}(i,j+1) \bigg)}{\rho_B^k(i,j)}.$$
% where $$A \parallel  B = \frac{1}{\frac{1}{A}+\frac{1}{B}}$$
%for the points in the lattice that each have two parents and two children.

By induction on $k$, and the fact that we apply birational rowmotion from top to bottom, we can rewrite this formula as  
$$\frac{ \bigg(\frac{A}{B} + \frac{C}{D}\bigg) \bigg( 
\frac{B}{G} \parallel \frac{D}{H}\bigg)}{\frac{E}{F}} = 
\frac{ \bigg(\frac{A}{B} + \frac{C}{D}\bigg) \bigg( 
\frac{BD}{DG ~+~ BH}\bigg)}{\frac{E}{F}}$$
$$= \bigg(\frac{AD + BC}{BD}\bigg) \bigg( 
\frac{BD}{DG ~+~ BH}\bigg)\bigg(\frac{F}{E}\bigg) 
= \frac{D\frac{A}{E} + B\frac{C}{E}}{D\frac{G}{F} + B\frac{H}{F}} $$

where

$$A = \mu^{([k-j]_+,
[k-1-i]_+)}\varphi_{k-1-M_{10}}(i-k+1+M_{10},j-k+M_{10})$$

$$B = \mu^{([k-j]_+,
[k-1-i]_+)}\varphi_{k-M_{10}}(i-k+1+M_{10},j-k+M_{10})$$

$$C = \mu^{([k-1-j]_+,
[k-i]_+)}\varphi_{k-1-M_{01}}(i-k+M_{01},j-k+1+M_{01})$$

$$D = \mu^{([k-i]_+,
[k-1-j]_+)}\varphi_{k-M_{01}}(i-k+M_{01},j-k+1+M_{01})$$

$$E = \mu^{([k-1-j]_+,
[k-1-i]_+)}\varphi_{k-1-M_{11}}(i-k+1+M_{11},j-k+1+M_{11})$$

$$F = \mu^{([k-1-j]_+,
[k-1-i]_+)}\varphi_{k-M_{11}}(i-k+1+M_{11},j-k+1+M_{11})$$

$$G = \mu^{([k-j]_+,
[k-1-i]_+)}\varphi_{k+1-M_{10}}(i-k+1+M_{10},j-k+M_{10})$$

$$H = \mu^{([k-1-j]_+,
[k-i]_+)}\varphi_{k+1-M_{01}}(i-k+M_{01},j-k+1+M_{01})$$
using $M_{\epsilon_i, \epsilon_j} = [k-i-\epsilon_i]_+ + [k-j-\epsilon_j]_+$ for $\epsilon_i, \epsilon_j \in \{0,1\}$.

To prove Theorem \ref{thm:main} (a), it therefore suffices to prove, using this above shorthand, that
$$D\frac{A}{E} + B\frac{C}{E} = \mu^{([k-j]_+,
[k-i]_+)}\varphi_{k-M_{00}}(i-k+M_{00},j-k+M_{00})$$
and 
$$D\frac{G}{F} + B\frac{H}{F} = \mu^{([k-j]_+,
[k-i]_+)}\varphi_{k+1-M_{00}}(i-k+M_{00},j-k+M_{00}).$$

Letting $\alpha = \mu^{([k-j]_+,
[k-i]_+)}\varphi_{k-M_{00}}(i-k+M_{00},j-k+M_{00})$ and \\ $\beta = \mu^{([k-j]_+,
[k-i]_+)}\varphi_{k+1-M_{00}}(i-k+M_{00},j-k+M_{00})$, 
we note that these two equations, i.e., 
$$\alpha E = BC + DA \mathrm{~~and~~} \beta F = GD + HB,$$
both follow from two applications\footnote{
%The first equation follows immediately while 
The second equation follows from substituting $k$ by $k+1$, $i$ by $i+1$, and $j$ by $j+1$.} of Lemma \ref{lem:genBounce}.

\begin{rem}
The proof is analogous in cases where the element $(i,j)$ covers (or is covered by) only a
single element, with some of the terms in the above expression being replaced with a $1$ or a $0$.  
\end{rem}

\subsection{Proof of Theorem \ref{thm:main} (b)}

Before continuing with the proof in the case when $M> k$, we note the following simplified
formula in the special case when $M=k$. 

\begin{claim} \label{claim:Mk}
Under the hypotheses of Theorem \ref{thm:main}, if $M=k$ (i.e., $i+j=k$)
then $$\rho_B^{k+1}(i,j) = \mu^{(i,j)} \left(\frac{\varphi_{0}(i,j)}{\varphi_{1}(i,j)}\right)
= \mu^{(i,j)} \rho_B^1(i,j) = \frac{1}{x_{r-i,s-j}}.$$ 
\end{claim}

\begin{proof} The first two equalities follow from Theorem \ref{thm:main} (a),
while we prove the last equality as follows.  Since the principal order filter
$\bigvee_{(i,j)}$ is isomorphic to the product of chains $[0,r-i]\times [0,r-j]$, we easily
reduce the claim to the case
%%% Not sure whether it's worth adding a picture here\dots TR
$i=j=k=0$, i.e., it suffices to show the last equality of 
\[
\rho_B^1(0,0) = \frac{\varphi_{0}(0,0)}{\varphi_{1}(0,0)} =
\frac{\prod_{p=0}^r \prod_{q=0}^s A_{pq}}
{\sum_{ \calL  \in S_{1}(0,0)}
\hspace{2em}\prod_{\stackrel{(i,j) \in \lpreg_{(0,0)}^{1}}{(i,j) \not \in L_1}} A_{ij}. 
} = \frac{1}{x_{r,s}}. 
% {\sum_{\mathrm{paths~L~from~}(0,0) \in [0,r] \times
% [0,s]} \prod_{(p,q)\in L} A_{p,q}^{-1} }.
\] 
In this situation, our family of lattices paths reduces to a single lattice path $L_{1}$,
the numerator can be thought of as $\ds \prod_{(p,q)\in P}A_{pq}$, and $\lpreg_{(0,0)}^{1} =
P$ as well.  By clearing denominators and dividing through by the double-product) we
equivalently need to show the following: 
\begin{claim} \label{claim:00}
\[
\sum_{ \calL  \in S_{1}(0,0)}
\kern 1em \prod_{{(i,j) \in L_1}} A_{ij}^{-1} = x_{r,s}. 
% \sum_{\mathrm{paths~L~from~}(0,0) \in [0,r] \times
% [0,s]} \prod_{(p,q)\in L} A_{p,q}^{-1}  = x_{r,s}. 
\]
\end{claim}
\textit{Proof.}
For the base case $s=0$, we get $P$ is a chain of length $r$ and the only lattice path %LP 
consists of
every element of $P$.  In this case $A_{i0} = \frac{x_{i,0}}{x_{i-1,0}}$ for $i\in [r]$, with
$A_{00} = x_{00}$, so the single summand is the telescoping product 
\[
\frac{x_{0,0}}{1}\cdot \frac{x_{1,0}}{x_{0,0}}\cdot \frac{x_{2,0}}{x_{1,0}}\cdot 
\dotsb  \frac{x_{r,0}}{x_{r-1,0}} = x_{r,0}
\]
as required.  Symmetrically, the claim also holds for $r=0$ and any $s$.  Now suppose that
the claim holds for every rectangular poset whose dimensions are strictly smaller than
$[0,r]\times [0,s]$.  Set $\frakL(p,q): = \{\text{lattice paths from } (0,0)\text{ to }
(p,q)\}$.   Any lattice path %LP 
from $(0,0)$ to $(r,s)$ must go through either $(r-1,s)$
or $(r,s-1)$.  Thus,
\begin{align*}
\sum_{ \calL  \in S_{1}(0,0)} \kern 1em \prod_{{(i,j) \in L_1}} A_{ij}^{-1} 
& = A_{r,s}^{-1} \sum_{L\in \frakL (r-1,s)} \kern 1em \prod_{{(i,j) \in L}} A_{ij}^{-1} 
    +A_{r,s}^{-1} \sum_{L\in \frakL (r,s-1)} \kern 1em \prod_{{(i,j) \in L}} A_{ij}^{-1}\\ 
& = A_{r,s}^{-1} (x_{r-1,s} + x_{r,s-1})\\ 
&= x_{r,s}, 
\end{align*}
using the induction hypothesis and the definition of $A_{i,j}$.  This finishes the proofs of
both Claim~\ref{claim:00} and Claim~\ref{claim:Mk}.  
\end{proof}

We next consider the case when $M = k+1$ (i.e., $i+j = k-1$).  We start with the degenerate case
$\rho_B^2(0,0) =   \frac{\rho_B^{2}(1,0) \parallel \rho_B^{2}(0,1)}{\rho_B^1(0,0)}
= \frac{\frac{1}{x_{r-1,s}} \parallel \frac{1}{x_{r,s-1}} }{\frac{1}{x_{rs}}} = \frac{ \frac{1}{x_{r-1,s}+x_{r,s-1}}}{\frac{1}{x_{rs}}}=
 \frac{1}{A_{rs}}.$  Note here that we used Claim \ref{claim:Mk} to simplify the calculations.
Continuing by induction\footnote{As above, if $(i,j)$ only covers one
element, we have a single summand rather than two inside the left parenthesis.},
$$\rho_B^{k+1}(i,j) = \frac{\bigg(\rho_B^k(i,j-1) + \rho_B^k(i-1,j)\bigg)  \bigg( \rho_B^{k+1}(i+1,j) \parallel \rho_B^{k+1}(i,j+1) \bigg)}{\rho_B^k(i,j)}.$$
Using Claim \ref{claim:Mk} and the inductive hypothesis, the right-hand-side simplifies to 
$$\frac{\bigg(\frac{1}{\rho_B^{k-1-(i+j-1)}(r-i,s-j+1)} + \frac{1}{\rho_B^{k-1-(i+j-1)}(r-i+1,s-j)} \bigg) 
 \bigg( 1/x_{r-i-1,s-j} \parallel 1/x_{r-i,s-j-1} \bigg)}{1/x_{r-i,s-j}}
=$$ $$\bigg(\frac{1}{\rho_B^{1}(r-i,s-j+1)} + \frac{1}{\rho_B^{1}(r-i+1,s-j)} \bigg)
 \frac{1}{A_{r-i,s-j}}.$$
Using Equation (\ref{eq:k0}), we can expand this out further as (assuming $i+j=k-1$)
$$\rho_B^{k+1}(i,j) = \bigg(
\sum_{\mathrm{~paths}~L~\text{from}~(r-i,s-j+1)} \frac{1}{\prod_{(p,q)\in L} A_{pq}}
~~~ + \sum_{\mathrm{~paths}~L~\text{from}~(r-i+1,s-j)} \frac{1}{\prod_{(p,q)\in L} A_{pq}}\bigg) \frac{1}{A_{r-i,s-j}}.$$
Any lattice path connecting $(r-i,s-j)$ to $(r,s)$ either goes through $(r-i,s-j+1)$ or
through $(r-i+1,s-j)$.  Combining these into a single sum over lattice paths, we get 
$$\rho_B^{k+1}(i,j)  = \sum_{\mathrm{~paths}~L~\text{from}~(r-i,s-j)} \frac{1}{\prod_{(p,q)\in L} A_{pq}} = \frac{\varphi_1(r-i,s-j)}{\varphi_0(r-i,s-j)} =  \frac{1}{\rho_B^{1}(r-i,s-j)},$$ 
agreeing with Theorem \ref{thm:main} (b) when $k=i+j+1$.

Lastly, when $M > k+1$, we use Theorem \ref{thm:main} (b) inductively to obtain
$$\rho_B^{k+1}(i,j) = \frac{\bigg(\rho_B^k(i,j-1) + \rho_B^k(i-1,j)\bigg)  \bigg( \rho_B^{k+1}(i+1,j) \parallel \rho_B^{k+1}(i,j+1) \bigg)}{\rho_B^k(i,j)}$$
$$ = \frac{\bigg(\frac{1}{\rho_B^{k-i-j}(r-i,s-j+1)} + \frac{1}{\rho_B^{k-i-j}(r-i+1,s-j)}\bigg)  \bigg( \frac{1}{\rho_B^{k-1-i-j}(r-i-1,s-j)} \parallel \frac{1}{\rho_B^{k-1-i-j}(r-i,s-j-1)} \bigg)}
{\frac{1}{\rho_B^{k-1-i-j}(r-i,s-j)}}$$
$$ = \Bigg(\frac{\bigg(\rho_B^{K+1}(I,J+1) \parallel \rho_B^{K+1}(I+1,J)\bigg) \bigg(\rho_B^{K}(I-1,J) + \rho_B^{K}(I,J-1)\bigg)}{\rho_B^{K}(I,J)} \Bigg)^{-1} = \frac{1}{\rho_B^{K+1}(I,J)}$$
where $K = k-1-i-j$, $I = r-i$, $J=s-j$.  This finishes the proof.
%then we obtain a variant of Lemma \ref{lem:genBounce} after inductively using Theorem \ref{thm:main} (b):
%\rho_B^{k+1}(i,j) = \frac{1}{\rho_B^{k-i-j}(r-i,s-j)}

\end{comment}

%\bibliography{biblioPathsFPSAC18}
%\bibliographystyle{halpha}
\printbibliography

\end{document}

