
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Input-Datei zum Erzeugen von Gitterpunktwegen.%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%entering a path: 
%  \Pfad(x-coordinate of starting point,y-coordinate of starting point),path
%  as 1-2-word\endPfad
%(1=step in x-direction, 2=step in y-direction)
%
%coordinate-axes:
%  \Koordinatenachsen(length of positive x-axes, length of positive y-axes)(length of negative x-axes, length of negative y-axes)
%The length of negative axes are entered as negative numbers.
%
%lattice:
%  \Gitter(number of points in positive x-direction, number of points in positive y-direction)(number of points in negative x-direction, number of points in negative y-direction)
%
%diagonal lines:
%  \Diagonale(x-coordinate of SW-most point,y-coordinate of SW-most point)length of the projection on the x-axes
%
%antidiagonal lines:
%  \AntiDiagonale(x-coordinate of NW-most point,y-coordinate of NW-most point)length of the projection on the x-axes
%
%labelling of points:
%  \Label[wo?]{[label]}(x-coordinate,y-coordinate)
%where:
%  [location?]=\l,\lo,\lu,\r,\ro,\ru,\o,\u
%and l=left, r=right, u=bottom, o=top.
%In addition, if by \Einheit?cm the basic unit is changed, there exist
%\llo,\loo,\llu,\luu,\rro,\roo,\rru,\ruu.
%
%The basic unit can be changed by entering
%  \Einheit=?cm
%The default is \Einheit=0.5cm.
%
%The thickness of the paths can be changed by entering
%     \PfadDicke{?cm}
%The default is \PfadDicke=1pt.
%
%The following point sizes are available:
%\DuennPunkt, \NormalPunkt, \DickPunkt. Syntax:
%  \DickPunkt(x-coordinate,y-coordinate), etc.
%
%Besides, a circle is available by \Kreis. Syntax:
%  \Kreis(x-coordinate,y-coordinate)
%
\catcode`\@=11
\font\tenln    = line10
\font\tenlnw   = linew10

\newskip\Einheit \Einheit=0.5cm
\newcount\xcoord \newcount\ycoord
\newdimen\xdim \newdimen\ydim \newdimen\PfadD@cke \newdimen\Pfadd@cke

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%LaTeX counters, dimensions, variables for lines%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcount\@tempcnta

\newdimen\@tempdima
\newdimen\@tempdimb


\newdimen\@wholewidth
\newdimen\@halfwidth

\newcount\@xarg
\newcount\@yarg
\newcount\@yyarg
\newbox\@linechar
\newdimen\@linelen
\newdimen\@clnwd
\newdimen\@clnht

\newif\if@negarg

\def\@whilenoop#1{}
\def\@whiledim#1\do #2{\ifdim #1\relax#2\@iwhiledim{#1\relax#2}\fi}
\def\@iwhiledim#1{\ifdim #1\let\@nextwhile=\@iwhiledim
        \else\let\@nextwhile=\@whilenoop\fi\@nextwhile{#1}}

\def\@whileswnoop#1\fi{}
\def\@whilesw#1\fi#2{#1#2\@iwhilesw{#1#2}\fi\fi}
\def\@iwhilesw#1\fi{#1\let\@nextwhile=\@iwhilesw
         \else\let\@nextwhile=\@whileswnoop\fi\@nextwhile{#1}\fi}


\def\thinlines{\let\@linefnt\tenln \let\@circlefnt\tencirc
  \@wholewidth\fontdimen8\tenln \@halfwidth .5\@wholewidth}
\def\thicklines{\let\@linefnt\tenlnw \let\@circlefnt\tencircw
  \@wholewidth\fontdimen8\tenlnw \@halfwidth .5\@wholewidth}
\thinlines
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\PfadD@cke1pt \Pfadd@cke0.5pt
\def\PfadDicke#1{\PfadD@cke#1 \divide\PfadD@cke by2 \Pfadd@cke\PfadD@cke \multiply\PfadD@cke by2}
\long\def\LOOP#1\REPEAT{\def\BODY{#1}\ITERATE}
\def\ITERATE{\BODY \let\next\ITERATE \else\let\next\relax\fi \next}
\let\REPEAT=\fi
\def\Punkt{\hbox{\raise-2pt\hbox to0pt{\hss$\ssize\bullet$\hss}}}
\def\DuennPunkt(#1,#2){\unskip
  \raise#2 \Einheit\hbox to0pt{\hskip#1 \Einheit
          \raise-2.5pt\hbox to0pt{\hss$\bullet$\hss}\hss}}
\def\NormalPunkt(#1,#2){\unskip
  \raise#2 \Einheit\hbox to0pt{\hskip#1 \Einheit
          \raise-3pt\hbox to0pt{\hss\twelvepoint$\bullet$\hss}\hss}}
\def\DickPunkt(#1,#2){\unskip
  \raise#2 \Einheit\hbox to0pt{\hskip#1 \Einheit
          \raise-4pt\hbox to0pt{\hss\fourteenpoint$\bullet$\hss}\hss}}
\def\Kreis(#1,#2){\unskip
  \raise#2 \Einheit\hbox to0pt{\hskip#1 \Einheit
          \raise-4pt\hbox to0pt{\hss\fourteenpoint$\circ$\hss}\hss}}

%%%%%%%%%%%%%%%%%%%%%
%LaTeX line macros%
%%%%%%%%%%%%%%%%%%%%%
\def\Line@(#1,#2)#3{\@xarg #1\relax \@yarg #2\relax
\@linelen=#3\Einheit
\ifnum\@xarg =0 \@vline
  \else \ifnum\@yarg =0 \@hline \else \@sline\fi
\fi}

\def\@sline{\ifnum\@xarg< 0 \@negargtrue \@xarg -\@xarg \@yyarg -\@yarg
  \else \@negargfalse \@yyarg \@yarg \fi
\ifnum \@yyarg >0 \@tempcnta\@yyarg \else \@tempcnta -\@yyarg \fi
\ifnum\@tempcnta>6 \@badlinearg\@tempcnta0 \fi
\ifnum\@xarg>6 \@badlinearg\@xarg 1 \fi
\setbox\@linechar\hbox{\@linefnt\@getlinechar(\@xarg,\@yyarg)}%
\ifnum \@yarg >0 \let\@upordown\raise \@clnht\z@
   \else\let\@upordown\lower \@clnht \ht\@linechar\fi
\@clnwd=\wd\@linechar
\if@negarg \hskip -\wd\@linechar \def\@tempa{\hskip -2\wd\@linechar}\else
     \let\@tempa\relax \fi
\@whiledim \@clnwd <\@linelen \do
  {\@upordown\@clnht\copy\@linechar
   \@tempa
   \advance\@clnht \ht\@linechar
   \advance\@clnwd \wd\@linechar}%
\advance\@clnht -\ht\@linechar
\advance\@clnwd -\wd\@linechar
\@tempdima\@linelen\advance\@tempdima -\@clnwd
\@tempdimb\@tempdima\advance\@tempdimb -\wd\@linechar
\if@negarg \hskip -\@tempdimb \else \hskip \@tempdimb \fi
\multiply\@tempdima \@m
\@tempcnta \@tempdima \@tempdima \wd\@linechar \divide\@tempcnta \@tempdima
\@tempdima \ht\@linechar \multiply\@tempdima \@tempcnta
\divide\@tempdima \@m
\advance\@clnht \@tempdima
\ifdim \@linelen <\wd\@linechar
   \hskip \wd\@linechar
  \else\@upordown\@clnht\copy\@linechar\fi}

%\def\@hline{\ifnum \@xarg <0 \hskip -\@linelen \fi
%\vrule \@height \@halfwidth \@depth \@halfwidth \@width \@linelen
%\ifnum \@xarg <0 \hskip -\@linelen \fi}

\def\@getlinechar(#1,#2){\@tempcnta#1\relax\multiply\@tempcnta 8
\advance\@tempcnta -9 \ifnum #2>0 \advance\@tempcnta #2\relax\else
\advance\@tempcnta -#2\relax\advance\@tempcnta 64 \fi
\char\@tempcnta}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\def\Diagonale(#1,#2)#3{\unskip\leavevmode
  \xcoord#1\relax \ycoord#2\relax
      \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit
         \Line@(1,1){#3}\hss}}
\def\AntiDiagonale(#1,#2)#3{\unskip\leavevmode
  \xcoord#1\relax \ycoord#2\relax \advance\xcoord by -0.05\relax
      \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit
         \Line@(1,-1){#3}\hss}}
\def\Pfad(#1,#2),#3\endPfad{\unskip\leavevmode
  \xcoord#1 \ycoord#2 \ZeichnePfad#3\endPfad}
\def\ZeichnePfad#1{\ifx#1\endPfad\let\next\relax
  \else\let\next\ZeichnePfad
    \ifnum#1=1
      \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit
         \vrule height\Pfadd@cke width1 \Einheit depth\Pfadd@cke\hss}%
      \advance\xcoord by 1
    \else
      \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit
        \hbox{\hskip-1pt\vrule height1 \Einheit width\PfadD@cke depth0pt}\hss}%
      \advance\ycoord by 1
    \fi
  \fi\next}
\def\Koordinatenachsen(#1,#2){\unskip
 \hbox to0pt{\hskip-.5pt\vrule height#2 \Einheit width.5pt depth1 \Einheit}%
 \hbox to0pt{\hskip-1 \Einheit \xcoord#1 \advance\xcoord by1
    \vrule height0.25pt width\xcoord \Einheit depth0.25pt\hss}}
\def\Koordinatenachsen(#1,#2)(#3,#4){\unskip
 \hbox to0pt{\hskip-.5pt \ycoord-#4 \advance\ycoord by1
    \vrule height#2 \Einheit width.5pt depth\ycoord \Einheit}%
 \hbox to0pt{\hskip-1 \Einheit \hskip#3\Einheit 
    \xcoord#1 \advance\xcoord by1 \advance\xcoord by-#3 
    \vrule height0.25pt width\xcoord \Einheit depth0.25pt\hss}}
\def\Gitter(#1,#2){\unskip \xcoord0 \ycoord0 \leavevmode
  \LOOP\ifnum\ycoord<#2
    \loop\ifnum\xcoord<#1
      \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit\Punkt\hss}%
      \advance\xcoord by1
    \repeat
    \xcoord0
    \advance\ycoord by1
  \REPEAT}
\def\Gitter(#1,#2)(#3,#4){\unskip \xcoord#3 \ycoord#4 \leavevmode
  \LOOP\ifnum\ycoord<#2
    \loop\ifnum\xcoord<#1
      \raise\ycoord \Einheit\hbox to0pt{\hskip\xcoord \Einheit\Punkt\hss}%
      \advance\xcoord by1
    \repeat
    \xcoord#3
    \advance\ycoord by1
  \REPEAT}
\def\Label#1#2(#3,#4){\unskip \xdim#3 \Einheit \ydim#4 \Einheit
  \def\lo{\advance\xdim by-.5 \Einheit \advance\ydim by.5 \Einheit}%
  \def\llo{\advance\xdim by-.25cm \advance\ydim by.5 \Einheit}%
  \def\loo{\advance\xdim by-.5 \Einheit \advance\ydim by.25cm}%
  \def\o{\advance\ydim by.25cm}%
  \def\ro{\advance\xdim by.5 \Einheit \advance\ydim by.5 \Einheit}%
  \def\rro{\advance\xdim by.25cm \advance\ydim by.5 \Einheit}%
  \def\roo{\advance\xdim by.5 \Einheit \advance\ydim by.25cm}%
  \def\l{\advance\xdim by-.30cm}%
  \def\r{\advance\xdim by.30cm}%
  \def\lu{\advance\xdim by-.5 \Einheit \advance\ydim by-.6 \Einheit}%
  \def\llu{\advance\xdim by-.25cm \advance\ydim by-.6 \Einheit}%
  \def\luu{\advance\xdim by-.5 \Einheit \advance\ydim by-.30cm}%
  \def\u{\advance\ydim by-.30cm}%
  \def\ru{\advance\xdim by.5 \Einheit \advance\ydim by-.6 \Einheit}%
  \def\rru{\advance\xdim by.25cm \advance\ydim by-.6 \Einheit}%
  \def\ruu{\advance\xdim by.5 \Einheit \advance\ydim by-.30cm}%
  #1\raise\ydim\hbox to0pt{\hskip\xdim
     \vbox to0pt{\vss\hbox to0pt{\hss$#2$\hss}\vss}\hss}%
}
\catcode`\@=13



\TagsOnRight
\catcode`\@=11
\def\iddots{\mathinner{\mkern1mu\raise\p@\hbox{.}\mkern2mu
    \raise4\p@\hbox{.}\mkern2mu\raise7\p@\vbox{\kern7\p@\hbox{.}}\mkern1mu}}
\catcode`\@=13
\def\th{\vartheta}
\def\bvert{\big\vert}
\def\Bvert{\Big\vert}
\def\Expr{\operatorname{Expr}}
\def\less{\operatorname{less}}
\def\xmaj{\operatorname{xmaj}}
\def\ymaj{\operatorname{ymaj}}
\def\stat{\operatorname{stat}}
\def\A{{\Cal A}}
\def\B{{\Cal B}}
\def\E{{\Cal E}}
\def\F{{\Cal F}}
\def\S{{\Cal S}}
\def\RR{{\frak R}}
\def\v#1{{\vert#1\vert}}
\def\V#1{{\Vert#1\Vert}}

\head V. Detailed Proofs and Auxiliary Results\endhead
\subheading{5.1. The major index and strange
major index generating functions for lattice paths without
restrictions}
In this section the strange major generating functions for unrestricted lattice paths
with fixed starting and final point are computed. 
Although it is well-known, 
the result for the major generating function 
is derived as a special case of the strange major result.

Recall that in subsection~2.1 we gave a one-to-one correspondence beetween
lattice paths from $\A=(A_1,A_2)$ to $\E=(E_1,E_2)$ and two-rowed
arrays which are strictly increasing in the rows and of the following
type
$$\matrix \hphantom{{}+1}A_1\le&a_1&\dots&a_k&\le E_1-1\\
A_2+1\le&b_1&\dots&b_k&\le E_2\hphantom{{}-1}\endmatrix\ ,\tag5.1.1$$
where $k$ is some nonnegative integer (cf\. (2.1.1) and (2.1.2)).
Since all the arrays which will appear in the sequel will be row-strict,
we will assume that if we speak of arrays we always mean them to be
strictly increasing in the rows. By definition the empty array is the
only array for $k=0$.

Let $P_K[N_1,N_2]$ denote the set of $K$-element subsets of
$\{N_1,N_1+1,\dots,N_2\}$. For a set $S$ of integers we write $\V{S}$ for the
sum of all the elements of $S$. Then it is well-known (this is seen
e.g\. equating coefficients in \cite{1, (3.3.6)}) that 
$$\sum _{S\in P_K[0,N-1]} ^{}q^{\V{S}}=q^{\binom K2}\bmatrix
N\\K\endbmatrix\ .\tag5.1.2$$
This identity enables us to find expressions for the $\xmaj$- and
$\ymaj$-generating functions for lattice paths from $\A$ to $\E$ by
using the above correspondence.

Let $\A$ and $\E$ be as above, $\A\le\E$, and $A_2\le \ga\le E_2$. 
Then using (4.0.6) and (5.1.2) we obtain for $\ymaj_{\be;\ga}$
$$\align \sum _{P:\A\to\E} ^{}&q^{\ymaj_{\be;\ga}(P)}\\
&=\sum _{k\ge0} ^{}\underset b\in P_k[A_2+1,E_2]\to{\sum _{a\in
P_k[A_1,E_1-1]} ^{}}q^{\V{a}+\V{b}+\be\cdot\vert\{
t:b_t>\ga\}\vert-k(A_1+A_2)}\tag5.1.3\\
&=\sum _{k\ge0} ^{}\Big(\sum _{a\in P_k[A_1,E_1-1]} ^{}q^{\V{a}-kA_1}\Big)
\sum _{i+j=k} ^{}\Big(\sum _{b'\in P_i[A_2+1,\ga]}
^{}q^{\V{b'}-iA_2}\Big)\\
&\quad \quad \quad \times\Big(\sum _{b''\in P_j[\ga+1,E_2]} ^{}q^{\V{b''}+j\be-jA_2}\Big)\\
&=\sum _{k\ge0} ^{}q^{\binom k2}\bmatrix E_1-A_1\\k\endbmatrix
\sum _{i+j=k} ^{}q^{\binom {i+1}2}\bmatrix \ga-A_2\\i\endbmatrix
q^{j(\be+\ga-A_2)+\binom {j+1}2}\bmatrix E_2-\ga\\j\endbmatrix
\endalign$$
by dividing the set $b$ into two arrays $b'$ and $b''$ where $b'$
collects all elements of $b$ being smaller or equal $\ga$ and where $b''$
collects those being greater than $\ga$. Next we replace $i$ by $k-j$
and interchange the order of summations. This transforms the last sum
into
$$\sum _{j\ge0} ^{}q^{j(j+\be+\ga-A_2)}\bmatrix E_2-\ga\\j\endbmatrix
\sum _{k\ge0} ^{}q^{k(k-j)}\bmatrix E_1-A_1\\k\endbmatrix
\bmatrix \ga-A_2\\k-j\endbmatrix\ .
$$
The inner sum can be evaluated by the $q$-Vandermonde summation (see
e.g\. \cite{1, (3.3.10)}), which we restate in the form
$$\sum _{K\ge0} ^{}q^{K(K-H+M)}\bmatrix N\\K\endbmatrix \bmatrix
M\\H-K\endbmatrix=\bmatrix N+M\\H\endbmatrix\ .\tag5.1.4$$
Utilizing $\[\smallmatrix \ga-A_2\\k-j\endsmallmatrix\]=
\[\smallmatrix \ga-A_2\\\ga-A_2+j-k\endsmallmatrix\]$ and (5.1.4) with
$N=E_1-A_1$, $M=\ga-A_2$, $H=\ga-A_2+j$, we get
$$\align \sum _{P:\A\to\E} ^{}&q^{\ymaj_{\be;\ga}(P)}\\
&=\sum _{j\ge0} ^{}q^{j(j+\be+\ga-A_2)}\bmatrix E_2-\ga\\j\endbmatrix
\bmatrix E_1+\ga-A_1-A_2\\j+\ga-A_2\endbmatrix\\
&=\sum _{j\ge0} ^{}q^{j(j+\be+\ga-A_2)}\bmatrix E_2-\ga\\j\endbmatrix
\bmatrix E_1+\ga-A_1-A_2\\E_1-A_1-j\endbmatrix\ ,\tag5.1.5\endalign$$
provided $A_2\le\ga\le E_2$.

There is an alternative expression for the $\ymaj$-generating
function which is obtained using Heine's basic hypergeometric 
transformation formula (cf\. \cite{14, Appendix (III.2)})
$${}_2\phi _1\!\left [ \matrix \let\over/ a,b\\ \let\over/  c\endmatrix ;q,z\right ] = 
\frac {(c/b;q)_\infty (bz;q)_\infty} {(c;q)_\infty(z;q)_\infty}
   {}_2\phi _1\!\left [ \matrix \let\over/ {{a b z}\over c},b\\ \let\over/  b z\endmatrix ;q,{c\over
    b}\right ]\ .\tag5.1.6
$$
First we have to write the sum in the last line of 
(5.1.5) in hypergeometric notation
(cf\. subsection~2.1),
$$\sum _{P:\A\to\E} ^{}q^{\ymaj_{\be;\ga}(P)}=\frac
{(q^{E_1-A_1+1})_{\ga-A_2}} {(q)_{\ga-A_2}}{}_2\phi _1\!\left [ \matrix
q^{\ga-E_2},q^{A_1-E_1}\\q^{\ga-A_2+1}\endmatrix;
q,q^{1+\be+E_1+E_2-A_1-A_2}\right]\ .$$
Now (5.1.6) can be applied to get
$$\multline \sum _{P:\A\to\E} ^{}q^{\ymaj_{\be;\ga}(P)}=\frac
{(q^{E_1-A_1+1})_{\ga-A_2}\,(q^{\ga+E_1-A_1-A_2+1})_\infty\,
(q^{1+\be+E_2-A_2})_\infty} {(q)_{\ga-A_2}\, (q^{\ga-A_2+1})_\infty
\,(q^{1+\be+E_1+E_2-A_1-A_2})_\infty}\\
{}_2\phi _1\!\left [ \matrix
q^\be,q^{A_1-E_1}\\q^{1+\be+E_2-A_2}\endmatrix
;q,q^{1+\ga+E_1-A_1-A_2}\right]\ ,
\endmultline$$
and finally, after simplifying and rewriting this in $q$-binomial
notation,
$$\sum _{P:\A\to\E} ^{}q^{\ymaj_{\be;\ga}(P)}=\sum _{j\ge0}
^{}q^{j(j+\be+\ga-A_2)}\bmatrix -\be\\\hphantom{-}j\endbmatrix \bmatrix
\be+E_1+E_2-A_1-A_2\\E_1-A_1-j\endbmatrix\ ,\tag5.1.7$$
provided $A_2\le\ga\le E_2$.

Now we turn to the $\xmaj$-generating function. Let $A_1\le\ga\le
E_1$. By (4.0.7) we have
$$\align \sum _{P:\A\to\E} ^{}&q^{\xmaj_{\be;\ga}(P)}\\
&=\sum _{k\ge0} ^{}\underset b\in P_k[A_2+1,E_2]\to{\sum _{a\in
P_k[A_1,E_1-1]} ^{}}q^{\V{a}+\V{b}+\be\cdot\vert\{
t:a_t\ge\ga\}\vert-k(A_1+A_2)}\\
&=\sum _{k\ge0} ^{}\underset b'\in P_k[A_2,E_2-1]\to{\sum _{a'\in
P_k[A_1+1,E_1]} ^{}}q^{\V{a'}+\V{b'}+\be\cdot\vert\{
t:a'_t>\ga\}\vert-k(A_1+A_2)}\ ,
\endalign$$
where $a_i':=a_i+1$ and $b_i'=b_i-1$, $i=1,\dots,k$. Comparing the
last line with (5.1.3), one observes that to obtain expressions for
the $\xmaj$-generating function in the previous computations for the
$\ymaj$ only the roles of $A_1$ and $A_2$, and those of $E_1$ and
$E_2$ have to be exchanged. Therefore, from (5.1.5) we get
$$\sum _{P:\A\to\E} ^{}q^{\xmaj_{\be;\ga}(P)}
=\sum _{j\ge0} ^{}q^{j(j+\be+\ga-A_1)}\bmatrix E_1-\ga\\j\endbmatrix
\bmatrix E_2+\ga-A_1-A_2\\E_2-A_2-j\endbmatrix\ ,\tag5.1.8$$
and from (5.1.7) we obtain
$$\sum _{P:\A\to\E} ^{}q^{\xmaj_{\be;\ga}(P)}
=\sum _{j\ge0}
^{}q^{j(j+\be+\ga-A_1)}\bmatrix -\be\\\hphantom{-}j\endbmatrix \bmatrix
\be+E_1+E_2-A_1-A_2\\E_2-A_2-j\endbmatrix\ ,\tag5.1.9$$
both identities holding provided $A_1\le\ga\le E_1$.

There is an important connection between the $\ymaj$- and the
$\xmaj$-generating function. This is revealed by combining (5.1.5)
and (5.1.8). Let $A_1+A_2-E_1\le \ga<A_2$ and in (5.1.8) replace $\ga$ by
$A_1+A_2-\ga$. Then shift the summation index by replacing $j$ by
$j+\ga-A_2$:
$$\align \sum _{P:\A\to\E} ^{}&q^{\xmaj_{\be;A_1+A_2-\ga}(P)}
=\sum _{j\ge A_2-\ga} ^{}q^{(j+\ga-A_2)(j+\be)}\bmatrix
E_1+\ga-A_1-A_2\\j+\ga-A_2\endbmatrix
\bmatrix E_2-\ga\\E_2-\ga-j\endbmatrix\\
&=q^{\be(\ga-A_2)}\sum _{j\ge0} ^{}q^{j(j+\be+\ga-A_2)}\bmatrix E_2-\ga\\j\endbmatrix
\bmatrix E_1+\ga-A_1-A_2\\E_1-A_1-j\endbmatrix\ .\tag5.1.10
\endalign$$
Comparing this last line with (5.1.5) leads to the surprising
discovery that the sum in (5.1.5), and hence also the sum in (5.1.7),
for $\ga\ge A_2$ is equal to the $\ymaj_{\be;\ga}$-generating
function for paths from $\A$ to $\E$, while for $\ga<A_2$ both sums
are, save for the factor $q^{\be(\ga-A_2)}$, equal to the
$\xmaj_{\be;A_1+A_2-\ga}$-generating function for the same family of
paths. Similarly, 
replacing $\ga$ by $A_1+A_2-\ga$ in the computation (5.1.10) and in
(5.1.5)
 shows that the sum in (5.1.8), and hence
also the sum in (5.1.9), for $\ga\ge A_1$ is equal to the
$\xmaj_{\be;\ga}$-generating function for paths from $\A$ to $\E$,
while for $\ga< A_1$ both sums are, save to the factor
$q^{\be(\ga-A_1)}$, equal to
the $\ymaj_{\be;A_1+A_2-\ga}$-generating function for the same family
of paths. It is these observations that justify the seemingly
artificial extension (4.0.3) of $\ymaj_{\be;\ga}$ to $\ga<A_2$ and
the likewise seemingly artificial extension (4.0.4) of
$\xmaj_{\be;\ga}$ to $\ga<A_1$.

\medpagebreak
The next Lemma summarizes results about $\ymaj$- and
$\xmaj$-generating functions for unrestricted paths. Most of them
have already been proved.
\proclaim{Lemma~23}Let $\A=(A_1,A_2)$ and $\E=(E_1,E_2)$ be two
lattice points in the integer lattice $\Z^2$. 

For $A_1+A_2-E_1\le \ga\le E_2$ the $\ymaj_{\be;\ga}$-generating
function for the paths from $\A$ to $\E$ is given by
$$\sum _{P:\A\to\E} ^{}q^{\ymaj_{\be;\ga}(P)}=\sum _{j\ge0}
^{}q^{j(j+\be+\ga-A_2)}\bmatrix -\be\\\hphantom{-}j\endbmatrix \bmatrix
\be+E_1+E_2-A_1-A_2\\E_1-A_1-j\endbmatrix\ .\tag5.1.11$$
For $A_1+A_2-E_2\le \ga\le E_1$ the $\xmaj_{\be;\ga}$-generating
function for the paths from $\A$ to $\E$ is given by
$$\sum _{P:\A\to\E} ^{}q^{\xmaj_{\be;\ga}(P)}
=\sum _{j\ge0}
^{}q^{j(j+\be+\ga-A_1)}\bmatrix -\be\\\hphantom{-}j\endbmatrix \bmatrix
\be+E_1+E_2-A_1-A_2\\E_2-A_2-j\endbmatrix\ .\tag5.1.12$$
In particular, the $\maj$-generating function is given by
$$\sum _{P:\A\to\E} ^{}q^{\maj P}=\bmatrix E_1+E_2-A_1-A_2\\ 
E_1-A_1\ .\endbmatrix\tag5.1.13$$
\endproclaim
\remark{Remark} Of course (5.1.13) is a well-known result of MacMahon
(\cite{32, p.~206}, cf\. \cite{1, Theorem~3.1}).
\endremark
\demo{Proof of the Lemma} First let $\A\le \E$. That (5.1.11) holds
for $A_2\le \ga\le E_2$ has been shown above when establishing (5.1.7)
via (5.1.5). In case that $A_1+A_2-E_1\le\ga <A_2$, by (4.0.3)
$\ymaj_{\be;\ga}$ is equal to $\xmaj_{\be;A_1+A_2-\ga}+\be(A_2-\ga)$.
Because of $A_1<A_1+A_2-\ga\le E_1$, use of (5.1.10) and the
transformation that leads from (5.1.5) to (5.1.7)
shows that (5.1.11) also holds in this case. The arguments for
(5.1.12) are similar. (5.1.13) can be easily derived from (5.1.11) or
(5.1.12) by setting $\be=0$ and applying the $q$-Vandermonde
summation (5.1.4).

What remains is to show that (5.1.11)--(5.1.13) also hold for
$\A\nleq\E$. Since in this case there are no paths between $\A$ and
$\E$, we have to show that the right-hand sides in (5.1.11)--(5.1.13)
equal zero. This is trivial for (5.1.13). Next we turn to (5.1.11).
 If $E_1<A_1$ all the
summands in (5.1.11) are zero because of the second $q$-binomial
coefficient. Now suppose that $E_1\ge A_1$ and $E_2<A_2$. By a
careful examination of the derivation of (5.1.7) from (5.1.5) by
means of Heine's transformation formula, it is
seen that the right-hand side of (5.1.11) agrees with the right-hand
side of (5.1.5) for all choices of the parameters provided
that $\ga\ge A_2$ and provided that $E_1-A_1$ is a nonnegative
integer. Since because of the second requirement the summations are
finite, both, (5.1.5) and (5.1.11), can be written as polynomials in
$q^\ga$. There are infinitely many values of $\ga$ (and therefore of
$q^\ga$) where (5.1.5) and (5.1.11) agree, hence they agree as
polynomials in $q^\ga$. This implies that they agree for all $\ga$.
But the summands in (5.1.5) for $\ga\le E_2$ are non-zero only if
$j\le E_2-\ga$ and $j\ge A_2-\ga$. Supposing that such a $j$ exists
we would get $A_2-\ga\le E_2-\ga$ in contradiction to the assumption
$E_2<A_2$. Therefore the sum in (5.1.5) equals zero for $E_1\ge A_1$
and $E_2<A_2$, hence also the sum in (5.1.11) vanishes in this case,
as desired. All possibilities of $\A\nleq\E$ are now covered. In all
cases (5.1.11) holds.

The arguments for showing that the sum in (5.1.12) vanishes if
$\A\nleq\E$ are similar.\quad \quad \qed
\enddemo



\subheading{5.2. A correspondence for lattice
paths that cross the line $x=y$}
We wish to handle the strange major counting of paths from
$\A=(A_1,A_2)$ to $\E=(E_1,E_2)$ which do not cross the line $x=y$.
Recall that ordinary counting of these paths is done by the
reflection principle (see the second part of subsection~2.2). 
Suppose that $A_1\ge A_2$
and $E_1\ge E_2$, i.e\. that $\A$ and $\E$ lie below or maybe on the
line $x=y$. Remember that when saying that a path ``lies below $x=y$"
we allow the path to touch $x=y$.
 The reflection principle shows that the paths from $\A$
to $\E$ which {\it cross} $x=y$ are in one-to-one correspondence with
the paths from $(A_2-1,A_1+1)$ to $(E_1,E_2)$.


To undertake
the strange major counting, the reflection has to be replaced by a
bijection having similar properties, because we cannot use the
reflection itself since,
when reflecting a part of a path,
 nothing can be said about the major index or the
strange major index of its image. We construct two fundamental
bijections for crossing paths, one for the case $A_1\ge A_2$, $E_1\ge
E_2$, and one for the case $A_1\le A_2$, $E_1\le E_2$. The first
bijection is the analogue for the reflection
procedure described in subsection~2.2. 
It maps paths $P$ from $(A_1,A_2)$ to $(E_1,E_2)$ which
cross $x=y$ onto paths $P'$ from $(A_2-1,A_1+1)$ to $(E_1,E_2)$ in a
way that only the initial portion till the last point lying above
$x=y$ is changed. These properties are shared with the reflection
procedure. In addition, for this mapping there holds a relation between
$\ymaj_{\be;\ga}(P)$ and $\xmaj_{\be;\ga+1}(P')$.
\proclaim{Proposition~24}{\smc First fundamental bijection for crossing
paths.}
Let $\A=(A_1,A_2)$ and $\E=(E_1,E_2)$ be two
lattice points in the integer lattice $\Z^2$ with $A_1\ge A_2$ and
$E_1\ge E_2$. For every integer $\ga$ satisfying 
$$A_2\le \ga\le A_1\tag5.2.1$$
there is a bijection $\Ph_\ga ^{(1)}$ between paths $P$ from $\A$ to
$\E$ which cross the line $x=y$ and the paths from $(A_2-1,A_1+1)$ to
$(E_1,E_2)$, such that the last meeting point of $P$
with $x=y-1$ is identical with the last meeting point of $\Ph_\ga^{(1)}(P)$
with $x=y-1$, such that the path's portions after this meeting point are
identical, and
$$\ymaj_{\be;\ga}(P)=\xmaj_{\be;\ga+1}(\Ph_\ga^{(1)}(P))+A_1-A_2+1+
\be.\tag5.2.2$$
\endproclaim
\remark{Remark} The relevance of the assumption $\ga\le A_1$ lies in
the fact that it allows a path from $\A$ to $\E$ to cross $x=y$ only
before having crossed the horizontal line $y=\ga$. After
having crossed $x=y$ for the first time, the path must have at least one
North-East corner before returning to $x=y$. This
North-East corner, because of lying above $y=\ga$, contributes a $\be$
to the statistics $\ymaj_{\be;\ga}$. This explains the $\be$ in (5.2.2).
\endremark
\demo{Proof of the Proposition} First we consider the case $\ga\ge E_2$. It
is clear that for each point $(p_1,p_2)$ of a path $P$ from $\A$ to
$\E$ we then have $p_1\ge A_1\ge\ga\ge E_2\ge p_2$. This simply means
that $P$ cannot cross the line $x=y$ but stays below everywhere only being
allowed to touch it. Therefore the set of crossing paths is empty as
well as the set of paths from $(A_2-1,A_1+1)$ to
$(E_1,E_2)$ because of $A_1\ge E_2$. This implies that the Proposition in
this case trivially holds.

Now let $\ga<E_2$. The construction of $\Ph_\ga^{(1)}$ is done in
four steps. For the reader who is not interested in all the details,
we outline a short-cut through the following construction.
 The mapping is essentially explained by the lines (5.2.3a,b),
(5.2.4), (5.2.10)--(5.2.15), and the first passage of the fourth
step. An example is added at the end of the proof.

Suppose that $P$ is a path from $\A$ to $\E$ which
crosses $x=y$.

{\it First step.} We map $P$ onto its array representation (cf\.
(2.1.2)). This gives a bijection between crossing paths $P$ and arrays
$(a\mid b)=(a_1,\dots,a_k\mid b_1,\dots,b_k)$,
$$\gather\text {paths } P:(A_1,A_2)\to(E_1,E_2)\text { which cross
}x=y\tag5.2.3a\\
\updownarrow\\
\matrix \hphantom{{}+1}A_1\le &a_1&\hdots&a_k&\le E_1-1\\
A_2+1\le&b_1&\hdots&b_k&\le E_2\hphantom{{}-1}\endmatrix
\text {, there exists an $i$, $1\le i\le k$ with $a_i<b_i$}\tag5.2.3b
\endgather$$
which (because of (4.0.6)) satisfies
$$\ymaj_{\be;\ga}(P)=\V{a}+\V{b}+\be\cdot\vert
\{t:b_t>\ga\}\vert-k(A_1+A_2).\tag5.2.3c$$
The condition required for the arrays in (5.2.3b) is clear from the
construction of the array (which was described in subsection~2.1) and the
fact that a path's North-East corner $(a_i,b_i)$ which lies above
$x=y$  satisfies $a_i<b_i$.

{\it Second step.} Here we use a modification of a correspondence
first introduced in \cite{26, section~4}. Given an array $(a\mid b)$
of the type (5.2.3b) let $I$ be maximal with $a_I<b_I$. We map
$(a\mid b)$ onto another two-rowed array by
$$\multline
\smatrix \format \c\quad &\c\quad &\c\s\c\s\c\quad &\c&\quad \c\\
a_1&\innerhdotsfor2\after{\hskip0pt}
&\omit&a_I&&a_{I+1}&\hdots\hskip3pt&a_k\\
\omit&\omit&\omit&\hlinefor3&\omit&\omit&\omit\\
b_1&\hdots&b_{I-1}&&b_I&\omit&\innerhdotsfor2\after{\hskip0pt}
&b_k\endsmatrix\\
\longrightarrow\quad 
\smatrix \format \c\ &\c\ &\c\quad &\c\quad &\c\s\c\s\c\quad &\c&\quad \c\\
& &b_1&\innerhdotsfor2\after{\hskip0pt}
&\omit&b_{I-1}&&a_{I+1}&\hdots\hskip3pt&a_k\\
\omit&\omit&\omit&\omit&\omit&\hlinefor3&\omit&\omit&\omit\\
a_1&a_2&a_3&\hdots&a_{I}&&b_I&\omit&\innerhdotsfor2\after{\hskip0pt}
&b_k\endsmatrix\ .
\endmultline\tag5.2.4$$
(The vertical and horizontal lines in (5.2.4) are drawn only to
support the orientation of the reader. They visually separate the
parts of the arrays that are changed from the parts that remain
unchanged.)
More precisely, the new array $(\bar a \mid \bar b )=(\bar a _2,\dots,\bar a _k\mid
\bar b _0,\dots,\bar b _k)$ is given by
$$\bar a _i=\cases b_{i-1}&2\le i\le I\\ a_i&I<i\le
k\endcases\hphantom{\ .}$$
and
$$\bar b _i=\cases a_{i+1}&0\le i<I\\ b_i&I\le i\le k\endcases\ .$$
Obviously the new array $(\bar a \mid \bar b )$ is strictly increasing in
both rows. Moreover, $I$ is maximal with $\bar a _I< \bar b _I$. Therefore
the inverse of the mapping (5.2.4) simply is
$$\multline
\smatrix \format \c\ &\c\ &\c\quad &\c\quad &\c\s\c\s\c\quad &\c&\quad \c\\
& &\bar a _2&\innerhdotsfor2\after{\hskip0pt}
&\omit&\bar a _I&&\bar a _{I+1}&\hdots\hskip3pt&\bar a _k\\
\omit&\omit&\omit&\omit&\omit&\hlinefor3&\omit&\omit&\omit\\
\bar b _0&\bar b _1&\bar b _2&\hdots&\bar b _{I-1}&&\bar b _I&\omit&\innerhdotsfor2\after{\hskip0pt}
&\bar b _k\endsmatrix\\
 \longrightarrow\quad 
\smatrix \format \c\quad &\c\quad &\c\s\c\s\c\quad &\c&\quad \c\\
\bar b _0&\innerhdotsfor2\after{\hskip0pt}
&\omit&\bar b _{I-1}&&\bar a _{I+1}&\hdots\hskip3pt&\bar a _k\\
\omit&\omit&\omit&\hlinefor3&\omit&\omit&\omit\\
\bar a _2&\hdots&\bar a _{I}&&\bar b _I&\omit&\innerhdotsfor2\after{\hskip0pt}
&\bar b _k\endsmatrix\ ,
\endmultline$$
where $I$ is maximal with $\bar a _I<\bar b _I$. If there is no such
$I$ then $I=1$. From this it follows that the mapping (5.2.4) is a
bijection between the following two families of arrays
$$\align \matrix \hphantom{{}+1}A_1\le &a_1&\hdots&a_k&\le E_1-1\\
A_2+1\le&b_1&\hdots&b_k&\le E_2\hphantom{{}-1}\endmatrix &\text {,
there is an $i$ with $a _i<b _i$}\tag5.2.5a\\
&\hskip-2cm \longleftrightarrow\quad 
\matrix A_2+1\le & & &\bar a _2&\hdots&\bar a _k&\le E_1-1\\
\hphantom{{}+1}A_1\le&\bar b _0&\bar b _1&\bar b _2&
\hdots&\bar b _k&\le E_2\hphantom{{}-1}\endmatrix\tag5.2.5b
\endalign$$
which satisfies
$$\V{a}+\V{b}+\be\cdot\vert\{t:b_t>\ga\}\vert= \V{\bar a }+\V{\bar b }
+\be\cdot\vert\{t:\bar a _t>\ga\}\vert+\be.\tag5.2.5c$$
The last identity is due to the assumption $\ga\le A_1$. Namely, for
an array $(a\mid b)$ of the type (5.2.3b) and $I$ being maximal with
$a_I<b_I$, we have $\ga\le A_1\le a_I<b_I$. Therefore whenever
$b_i\le \ga$, there holds $i<I$. Let $L$ be maximal with $b_L\le\ga$
and let $(\bar a \mid \bar b )$ the array which by (5.2.4)
corresponds to $(a\mid b)$. Then by means of (5.2.4) there holds
$$\vert\{t:b_t>\ga\}\vert=k-L$$
and
$$\align \vert\{t:\bar a _t>\ga\}\vert&= \vert\{t:\bar a _t>\ga\text
{ and }2\le t\le I\}\vert\\
&\quad \quad \quad +\vert\{t:\bar a _t>\ga\text { and }I<t\le
k\}\vert\\
&= \vert\{t:b_{t-1}>\ga\text
{ and }2\le t\le I\}\vert\\
&\quad \quad \quad +\vert\{t:a_t>\ga\text { and }I<t\le
k\}\vert\\
&=(I-L-1)+(k-I)\\
&=k-L-1,
\endalign$$
which settles (5.2.5c).

{\it An auxiliary correspondence.} Before being able to perform the
next step we need an auxiliary correspondence. We claim that there is
a bijection between the following two families of arrays,
$$\align \matrix 1\le & & &c_2&\hdots&c_{I-1}&c_I&\le M-1\\
0\le&d_0&d_1&d_2&
\hdots&d_{I-1}& &\le N-1\endmatrix&\tag5.2.6a\\
&\hskip-2cm \longleftrightarrow\quad 
\matrix 0\le &\bar c _1&\hdots&\bar c _{J-1}&\bar c _J&\le
M\hphantom{{}-2}\\
1\le&\bar d _1&\hdots&\bar d _{J-1}& &\le N-2\endmatrix \\\tag5.2.6b
\endalign$$
such that 
$$\V{c}+\V{d}+\be\cdot\vert\{t:c_t>\overline\ga\}\vert= \V{\bar c }+\V{\bar d }
+\be\cdot\vert\{t:\bar c _t>\overline\ga+1\}\vert\tag5.2.6c$$
for all integers $\overline\ga$ satisfying $0\le\overline\ga\le M-1$.
The easiest way to see this, is to show that the corresponding
generating functions are equal. For arrays of the type (5.2.6a) we
obtain
$$\align \sum _{I\ge1} ^{}\ &\underset d\in P_I[0,N-1]\to 
{\sum _{c\in P_{I-1}[1,M-1]}
^{}}q^{\V{c}+\V{d}+\be\cdot\vert\{t:c_t>\overline\ga\}\vert}\tag5.2.7a\\
&=\sum _{I\ge1} ^{}\Big(\sum _{d\in P_I[0,N-1]} ^{}q^{\V{d}}\Big)\\
&\quad \quad \quad \times
\sum _{i+j=I-1} ^{}\Big(\sum _{c'\in P_i[1,\overline\ga]} ^{}q^{\V{c'}}\Big)
\Big(\sum _{c''\in P_j[\overline\ga+1,M-1]}
^{}q^{\V{c''}+\be\cdot\vert\{t:c''_t>\overline\ga\}\vert}\Big)\\
&=\sum _{I\ge1} ^{}q^{\binom I2}\bmatrix N\\I\endbmatrix\sum
_{i+j=I-1} ^{}q^{\binom{i+1}2}\bmatrix \overline\ga\\i\endbmatrix
q^{j(\be+\overline\ga)+\binom{j+1}2}\bmatrix
M-\overline\ga-1\\j\endbmatrix\\
&=\sum _{j\ge0} ^{}q^{j(j+\be+\overline\ga+1)}\bmatrix
M-\overline\ga-1\\j\endbmatrix
\sum _{I\ge1} ^{}q^{I(I-1-j)}\bmatrix N\\I\endbmatrix \bmatrix
\overline\ga\\I-1-j\endbmatrix\tag5.2.7b\\
&=\sum _{j\ge0} ^{}q^{j(j+\be+\overline\ga+1)}\bmatrix
M-\overline\ga-1\\j\endbmatrix\bmatrix
N+\overline\ga\\N-1-j\endbmatrix\ ,\tag5.2.7c
\endalign$$
where in the last step we used the $q$-Vandermonde summation (5.1.4).
On the other hand for arrays of the type (5.2.6b) we get 
$$\align \sum _{J\ge1} ^{}&\underset \bar d \in P_{J-1}[1,N-2]\to 
{\sum _{\bar c \in P_{J}[0,M]}
^{}}q^{\V{\bar c }+\V{\bar d }+
\be\cdot\vert\{t:\bar c _t>\overline\ga+1\}\vert}\tag5.2.8a\\
&=\sum _{J\ge1} ^{}\Big(\sum _{d\in P_{J-1}[1,N-2]}
^{}q^{\V{d}}\Big)\\
&\quad \quad \quad \times
\sum _{i+j=J} ^{}\Big(\sum _{c'\in P_i[0,\overline\ga+1]} ^{}q^{\V{c'}}\Big)
\Big(\sum _{c''\in P_j[\overline\ga+2,M]}
^{}q^{\V{c''}+\be\cdot\vert\{t:c''_t>\overline\ga+1\}\vert}\Big)\\
&=\sum _{J\ge1} ^{}q^{\binom J2}\bmatrix N-2\\J-1\endbmatrix\sum
_{i+j=J} ^{}q^{\binom{i}2}\bmatrix \overline\ga+2\\i\endbmatrix
q^{j(\be+\overline\ga+2)+\binom{j}2}\bmatrix
M-\overline\ga-1\\j\endbmatrix\\
&=\sum _{j\ge0} ^{}q^{j(j+\be+\overline\ga+1)}\bmatrix
M-\overline\ga-1\\j\endbmatrix
\sum _{J\ge1} ^{}q^{(J-1)(J-j)}\bmatrix N-2\\J-1\endbmatrix \bmatrix
\overline\ga+2\\J-j\endbmatrix\tag5.2.8b\\
&=\sum _{j\ge0} ^{}q^{j(j+\be+\overline\ga+1)}\bmatrix
M-\overline\ga-1\\j\endbmatrix\bmatrix
N+\overline\ga\\N-1-j\endbmatrix\ ,\tag5.2.8c
\endalign$$
by renewed application of the $q$-Vandermonde summation. Since
(5.2.7c) and (5.2.8c) obviously are identical, the generating
functions (5.2.7a) and (5.2.8a) agree. Hence, there must be a
bijection satisfying (5.2.6). 

This is only an existence proof which
does not please any true combinatorialist. But the computations (5.2.7)
and (5.2.8) tell us how to explicitely construct such a bijection.
For sake of completeness we give a description of it below. We leave
it to the reader to verify that it is well-defined and satisfies the
desired properties (5.2.6).

Let $(c \mid d)$ be an array of the type (5.2.6a). To illustrate the
following we choose a running example, say $M=11$, $N=10$,
$\overline\ga=7$, and the array $(c_{\text{ex}}\mid d_{\text{ex}})$ given by
$$\matrix 1\le&\hphantom{1\ 3\ }1\ 4\ 5\ 7\ 8&\le 10\\
0\le&1\ 3\ 6\ 7\ 8\ 9\ \hphantom{8}&\le \hphantom{1}9\endmatrix\ ,$$
or more precisely $c_{\text{ex}}=\{1,4,5,7,8\}$ and $d_{\text{ex}}=\{1,3,6,7,8,9\}$.

First $c$ is split up into the initial part $c'$ and the final part
$c''$, where $c'$ contains all elements of $c$ which are smaller or
equal $\overline\ga$, and $c''$ contains the rest. In $c'$ add $N$ to
each element to obtain $c'''$. In  our example we have
$c_{\text{ex}}'=\{1,4,5,7\}$, $c_{\text{ex}}''=\{8\}$, and 
$c_{\text{ex}}'''=\{11,14,15,17\}$. Let
$d'$ denote the complement of $d$ with respect to
$\{0,1,\dots,N-1\}$. In $d'$ replace each element $e$ by $N-e$, thus
obtaining $d''$. In our example we have $d_{\text{ex}}'=\{0,2,4,5\}$ and
$d_{\text{ex}}''=\{5,6,8,10\}$. 
Now form the union of $d''$ and $c'''$ and denote
it by $u$. In our example 
this is $\{5,6,8,10,11,14,15,17\}$. 

Next $u$ is split up into $\bar d''$ and $\bar c'''$ where $\bar d''$
contains all elements of $u$ being smaller or equal $\overline\ga+1$
and $\bar c'''$ the rest. In our example  we have $\bar d_{\text{ex}}''=\{5,6,8\}$
and $\bar c_{\text{ex}}'''=\{10,11,14,15,17\}$. Now in $\bar d''$ we replace each
element $e$ by $N-1-e$, thus obtaining $\bar d'$. The complement of
$\bar d'$ with respect to $\{1,2,\dots,N-2\}$ is denoted by $\bar d$.
On the other hand we subtract $N-1$ from each element of $\bar
c'''$ and thus get $\bar c'$. The set $\bar c''$ is formed by adding 1
to each element of $c''$. In our example we get $\bar d_{\text{ex}}'=\{1,3,4\}$,
$\bar d_{\text{ex}}=\{2,5,6,7,8\}$, $\bar c_{\text{ex}}'=\{1,2,5,6,8\}$, and $\bar
c_{\text{ex}}''=\{9\}$. Finally we arrive at the array $(\bar c\mid\bar d)$ by
defining $\bar c$ to be the union of $\bar c'$ and $\bar c''$. 

In our
example this gives the correspondence
$$\matrix 1\le&\hphantom{1\ 3\ }1\ 4\ 5\ 7\ 8&\le 10\\
0\le&1\ 3\ 6\ 7\ 8\ 9\ \hphantom{8}&\le \hphantom{1}9\endmatrix
\quad \longleftrightarrow\quad 
\matrix 0\le&1\ 2\ 5\ 6\ 8\ 9&\le 11\\
1\le&2\ 5\ 6\ 7\ 8\ \hphantom{9}&\le\hphantom{1}8\endmatrix\ .
\tag5.2.9$$

\bigpagebreak
It is a routine verification that this above defined mapping is a
bijection between the sets of arrays in (5.2.6a,b) which satisfies
(5.2.6c). As mentioned above, the motivation of this construction lies
in the computations (5.2.7) and (5.2.8). What we did was to interpret
each step in these computations combinatorially. Starting at (5.2.7a)
first $c$ is split up into $c'$ and $c''$. Then for the moment we
forget about $c''$ and consider only $d$ and $c'$ which corresponds
to the reordering of summations in (5.2.7b). In order to have a
combinatorial version of the next step, the $q$-Vandermonde
summation, we first had to transform $d$ into $d''$. Roughly spoken
this corresponds to transforming $\[\smallmatrix
N\\I\endsmallmatrix\]$ to $\[\smallmatrix
N\\N-I\endsmallmatrix\]$ in (5.2.7b). Now we merged $d''$ and $c'''$
(which has been a shifted version of $c'$)
together, what could be called the combinatorial $q$-Vandermonde
summation. Now we arrived at (5.2.7c) and therefore are able to
continue at (5.2.8c). It should be clear that splitting up $u$,
etc\., has been nothing but working backward from (5.2.8c) to
(5.2.8a).

{\it Third step.} Recall that by the first and second step we mapped
a path $P$ from $\A$ to $\E$ which crosses $x=y$ to an array of the
type (5.2.5b). Besides, we denoted by $I$ the maximal index for
which $\bar a_I<\bar b_I$. Given an array of the type (5.2.5b) and
its correlated index $I$,
$$\smatrix \format \r\quad &\c\ &\c\ &\c\quad &\c\quad &\c\s\c\s\c\quad &\c&\quad
\c&\quad \l\\
A_2+1\le&& &\bar a _2&\innerhdotsfor2\after{\hskip0pt}
&\omit&\bar a _I&&\bar a _{I+1}&\hdots\hskip3pt&\bar a _k&\le E_1-1\\
\omit&\omit&\omit&\omit&\omit&\omit&\hlinefor3&\omit&\omit&\omit&
\omit\\
A_1\le&\bar b _0&\bar b _1&\bar b _2&\hdots&\bar b _{I-1}&&\bar b _I&\omit&\innerhdotsfor2\after{\hskip0pt}
&\bar b _k&\le E_2\endsmatrix
\tag5.2.10
$$
for the moment we only consider the subarray
$$\matrix \hphantom{b_0\ b_1}\ \bar a_2\ \dots\ \bar a_{I-1}\ \bar
a_I\\\bar b_0\ \bar b_1\ \bar b_2\ \dots\ \bar b_{I-1}\ \hphantom{a_I}\endmatrix
\ ,\tag5.2.11$$
or with bounds included (note the upper bounds!)
$$\matrix A_2+1\le\quad \hphantom{b_0\ b_1}\ \bar a_2\ \dots\ \bar a_{I-1}\ \bar
a_I\quad \le \bar b_I-1\\
\hphantom{{}+1}A_1\le\quad \bar b_0\ \bar b_1\ \bar b_2\ 
\dots\ \bar b_{I-1}\ \hphantom{a_I}\quad \le\bar b_I-1\endmatrix
\ .$$
(Similar to (5.2.4), the vertical and horizontal lines in (5.2.10)
are drawn only to help the reader in separating the subarray from the
rest.) We subtract $A_2$ from each entry of the first row and $A_1$ from
each entry of the second row of this subarray. It is clear that the
resulting array is of the type (5.2.6a) with the choices $M=\bar
b_I-A_2$, $N=\bar b_I-A_1$, $\bar \ga=\ga-A_2$,
$$\matrix 1\le&\hphantom{b_0-A_1\quad b_1-A_1}\quad \bar a_2-A_2\quad 
\dots\quad \bar a_{I-1}-A_2\quad \bar
a_I-A_2&\le\bar b_I-A_2-1\\
0\le&\bar b_0-A_1\quad \bar b_1-A_1\quad \bar b_2-A_1\quad \dots\quad 
\bar b_{I-1}-A_1\quad \hphantom{a_I-A_2}&\le\bar b_I-A_1-1\endmatrix\ .
\tag5.2.12$$
Because of the assumption $\ga\ge A_2$ and because of $\ga<b_I$ and
$b_I=\bar b_I$ (this results from the second step) the difference
$\ga-A_2$ indeed satisfies $0\le \ga-A_2\le\bar b_I-A_2-1$. Therefore
by (5.2.6a,b) the array (5.2.12) uniquely corresponds to an array of the
type
$$\matrix 0\le &\tilde a  _1&\hdots&\tilde a  _{J-1}&\tilde a  _J&\le
\bar b_I-A_2\hphantom{{}-2}\\
1\le&\tilde b  _1&\hdots&\tilde b  _{J-1}& &\le \bar b_I-A_1-2\endmatrix\ .
\tag5.2.13$$
Next we add $A_2-1$ to each entry in the first row and $A_1+1$ to
each entry in the second row to obtain the array
$$\matrix A_2-1\le &\tilde a  _1+A_2-1&\hdots&\tilde a  _{J-1}+A_2-1&\tilde a 
_J+A_2-1&\le
\bar b_I-1\\
A_1+2\le&\tilde b  _1+A_1+1&\hdots&\tilde b  _{J-1}+A_1+1& &\le 
\bar b_I-1\endmatrix\ .
\tag5.2.14$$
Finally this array can be put together with the rest of (5.2.10),
$$\smatrix \format \r\quad &\c&\c\quad &\c\s\c\s\c\quad &\c&
\c&\quad \l\\
A_2-1\le&\tilde a  _1+A_2-1&\innerhdotsfor2\after{\hskip0pt}
&\omit&\tilde a  _J+A_2-1&&\bar a _{I+1}&\hdots\hskip3pt&\bar a _k&\le E_1-1\\
\omit&\omit&\omit&\omit&\hlinefor3&\omit&\omit&\omit&
\omit\\
A_1+2\le&\tilde b  _1+A_1+1&\hdots&\tilde b  _{J-1}+A_1+1&&\bar b _I&\omit&\innerhdotsfor2\after{\hskip0pt}
&\bar b _k&\le E_2\endsmatrix\ ,
\tag5.2.15
$$
thus obtaining an array of the type
$$\matrix A_2-1\le &\hat a_1&\hdots&\hat a_{m}&\le E_1-1\\
A_1+2\le &\hat b_1&\hdots&\hat b_{m}&\le E_2\hphantom{{}-1}\endmatrix\ .
\tag5.2.16$$


How are the weights of (5.2.10) and (5.2.16) related? Assuming that $(\hat
a\mid\hat b)$ is defined by (5.2.15), by means of (5.2.6c) and
(5.2.10)--(5.2.15) we have
$$\align \V{\bar a}+&\V{\bar b}+\be\cdot\vert\{t:\bar
a_t>\ga\}\vert\\
&=\V{\hat a }+\V{\hat b}+\be\cdot\vert\{t:\hat a_t\ge\ga +1\}\vert\\
&\hskip2cm+(I-1)A_2+IA_1-J(A_2-1)-(J-1)(A_1+1)\\
&=\V{\hat a}+\V{\hat b}+\be\cdot\vert\{t:\hat a_t\ge\ga +1\}\vert+
(I-J)(A_1+A_2)+A_1-A_2+1.
\endalign$$
Subtraction of $k(A_1+A_2)$ then gives
$$\multline \V{\bar a}+\V{\bar b}+\be\cdot\vert\{t:\bar
a_t>\ga\}\vert-k(A_1+A_2)\\
=\V{\hat a}+\V{\hat b}+\be\cdot\vert\{t:\hat a_t\ge\ga +1\}\vert
-(k-I+J)(A_1+A_2)+A_1-A_2+1.
\endmultline\tag5.2.17$$

{\it Fourth step.} Obviously, arrays of the type (5.2.16) are in
one-to-one correspondence with paths $\hat P$ from $(A_2-1,A_1+1)$ to
$(E_1,E_2)$, and besides there holds
$$\xmaj_{\be;\ga+1}(\hat P)=\V{\hat a}+\V{\hat b}+\be\cdot\vert\{t:\hat a_t\ge\ga
+1\}\vert-m(A_2-1+A_1+1).\tag5.2.18$$

Now we are able to define $\Ph_\ga^{(1)}$. For any path $P$ from $\A$
to $\E$ which crosses $x=y$ perform the steps 1--4. 
The image of $P$ under application of
$\Ph_\ga^{(1)}$ by definition is the resulting path $\hat P$,
$$\Ph_\ga^{(1)}(P):=\hat P.$$

Combining (5.2.3c), (5.2.5c), (5.2.17), and (5.2.18), we obtain the
desired property (5.2.2). Here it is important to notice that the
row lengths of the array in (5.2.15) equal $k-I+J$.

\medpagebreak
Since all steps which led to the construction of $\Ph_\ga^{(1)}$ of a
crossing path $P$ are invertible, $\Ph_\ga^{(1)}$ is a bijection.

The only thing which is still open is the property about the last
meeting point with the line $x=y-1$. Recall that in the second step $I$ was
maximal with $a_I<b_I$. Having in mind the connection between a path $P$ and
its corresponding array representation $(a\mid b)$, we see
that the last meeting point of $P$ with $x=y-1$ is $(b_I-1,b_I)$.
Obviously, the construction of $\Ph_\ga^{(1)}(P)$ has the property
that the last $k-I$ elements in the first row of the array in (5.2.3b)
(i.e\. the elements $a_{I+1},\dots,a_k$) are identical with the last
$k-I$ elements in the first row of the array in (5.2.15), the same
being valid for the last $k-I+1$ elements in the second rows (i.e\.
the elements $b_{I},\dots,b_k$). Besides by construction there holds 
$\tilde a_ J+A_2-1<\bar b_I=b_I$ in (5.2.15). Hence, the last meeting
point of $\Ph_\ga^{(1)}(P)$ with $x=y-1$ is $(b_I-1,b_I)$, too, and
the path portions of $P$ and $\Ph_\ga^{(1)}(P)$ after this last meeting
point are identical. 

This completes the proof of the Proposition.

\medskip
To illustrate the action of $\Ph_\ga^{(1)}$, consider the path
$P_{\text{ex}}=((-1,-2),\mathbreak 1211222111212212122211211112212)$ 
with starting point
$\A_{\text {ex}}=(-1,-2)$ and final point $\E_{\text {ex}}=(15,13)$. 
It is the lower path
in Figure~4. Choose $\ga=5$. In the first step $P_{\text{ex}}$ is mapped to
its array representation
$(a^{(\text {ex})}\mid b^{(\text {ex})})$ given by
$$\matrix -1\le&\hphantom{-}0\ 2\ 5\ 6\ 7\ 8\ 10\ 14&\le14\\
-1\le&-1\ 2\ 3\ 5\ 6\ 9\ 10\ 12&\le13\endmatrix\ .$$
The index $I$ which is maximal with respect to $a^{(\text {ex})}_I<b^{(\text
{ex})}_I$
is $I=6$. Hence, in the second step by (5.2.4) the array $(a^{(\text
{ex})}\mid b^{(\text {ex})})$ is
mapped to the array
$$\matrix -1\le&\hphantom{0\ 2\ }{-1}\ 2\ 3\ 5\ 6\ 10\ 14&\le14\\
-1\le&0\ 2\ \hphantom{-}5\ 6\ 7\ 8\ 9\ 10\ 12&\le13\endmatrix\ .
\tag5.2.19$$
To perform the third step, we first have to restrict our attention
to the subarray
$$\matrix -1\le&\hphantom{0\ 2\ }{-1}\ 2\ 3\ 5\ 6&\le8\\
-1\le&0\ 2\ \hphantom{-}5\ 6\ 7\ 8\ \hphantom{6}&\le8\endmatrix\ .$$
By virtue of (5.2.12) we obtain the array
$$\matrix 1\le&\hphantom{1\ 3\ }1\ 4\ 5\ 7\ 8&\le 10\\
0\le&1\ 3\ 6\ 7\ 8\ 9\ \hphantom{8}&\le \hphantom{1}9\endmatrix\ .$$
Now we have to apply the auxiliary correspondence to this array.
Luckily it just agrees with the left-hand array of (5.2.9) and
therefore corresponds to
$$\matrix 0\le&1\ 2\ 5\ 6\ 8\ 9&\le 11\\
1\le&2\ 5\ 6\ 7\ 8\ \hphantom{9}&\le\hphantom{1}8\endmatrix\ ,$$
the right-hand array in (5.2.9). By (5.2.14), from this array we
obtain
$$\matrix -3\le&-2\ {-1}\ 2\ 3\ 5\ 6&\le8\\
\hphantom{-}1\le&\hphantom{-}2\ \hphantom{-}5\ 6\ 7\ 8\
\hphantom{1}&\le8\endmatrix\ .$$
By (5.2.15), this is glued together with the rest of (5.2.19) to
obtain
$$\matrix -3\le&-2\ {-1}\ 2\ 3\ 5\ 6\ 10\ 14&\le14\\
\hphantom{-}1\le&\hphantom{-}2\ \hphantom{-}5\ 6\ 7\ 8\ 9\ 10\
12&\le13\endmatrix\ ,$$
which is the array representation of the second path in
Figure~4. The last meeting point of $P_{\text {ex}}$ with $x=y-1$ is
$\S_{\text {ex}}=(8,9)$, it is the same as that of $\Ph_5^{(1)}(P_{\text
{ex}})$. Besides these two paths obviously are identical after $\S_{\text
{ex}}$, as was claimed.

\vskip10pt 
\vbox{\noindent
$$\Einheit0.3cm
\Koordinatenachsen(16,14)(-3,-2)
\Gitter(16,14)(-3,-2)
\Diagonale(-3,-3){17}
\Pfad (-1,-2),1211222111212212122211211112212\endPfad
\Pfad (-3,0),1221222111212112121111211112212\endPfad
\Kreis(0,0)
\DickPunkt(-1,-2)
\DickPunkt(-3,0)
\DickPunkt(15,13)
\DickPunkt(8,9)
{\PfadDicke{0.25pt} \Pfad (-4,5),11111111111111111111\endPfad
\Pfad (6,-3),22222222222222222\endPfad}
\Label\r{P_{\text{ex}}}(3,1)
\Label\ro{\Ph_5^{(1)}(P_{\text{ex}})\hskip5pt}(0,7)
\Label\u{\A_{\text{ex}}\hskip8pt}(-1,-2)
\Label\lu{\RR\A_{\text{ex}}\hskip0.85cm}(-3,0)
\Label\r{\hskip12pt\E_{\text{ex}}}(15,13)
\Label\lo{\raise7pt\hbox{$\S_{\text {ex}}$}}(8,9)
{\eightpoint\Label\ro{x=6}(7,13)
\Label\ro{y=5}(16,5)}
\hskip3cm
$$%}
\nobreak
\centerline{\eightpoint Figure 4}
}
\vskip10pt
By definition (4.0.1), we have 

{\eightpoint
$$\ymaj_{\be;5}(P_{\text{ex}})=2+7+11+14+16+20+23+29+4\be=122+4\be,$$}
and by (4.0.2) we have

{\eightpoint
$$\xmaj_{\be;6}(\Ph_5^{(1)}(P_{\text{ex}}))=3+7+11+13+16+18+23+29+3\be=
120+3\be,$$}
in accordance with (5.2.2).
\quad \quad \qed
\enddemo

Setting $\be=0$ in Proposition~24, we obtain as a corollary a bijection
for the ordinary major index. 
\proclaim{Corollary~25}Let $\A=(A_1,A_2)$ and $\E=(E_1,E_2)$ be two
lattice points in the integer lattice $\Z^2$ with $A_1\ge A_2$ and
$E_1\ge E_2$.
There is a bijection $\Ph ^{(1)}$ between paths $P$ from $\A$ to
$\E$ which cross the line $x=y$ and the paths from $(A_2-1,A_1+1)$ to
$(E_1,E_2)$ such that the last meeting point of $P$
with $x=y-1$ is identical with the last meeting point of $\Ph^{(1)}(P)$
with $x=y-1$, such that the path's portions after this meeting point are
identical, and
$$\maj P=\maj \Ph^{(1)}(P)+A_1-A_2+1.\tag5.2.20$$
\endproclaim
\demo{Proof}Set $\be=0$ and define $\Ph^{(1)}:=\Ph_{A_2}^{(1)}$.\quad
\qed
\enddemo

A simpler way to define a bijection satisfying the properties of the
above Corollary has been previously given in \cite{27, Proof of
(5.36)} by extending an idea of F\"urlinger and Hofbauer
\cite{13, Lemma on p.~255}. But this
bijection is only applicable for the major index and is not
extendable in order to be applicable with the strange major index.

\bigpagebreak
The next Proposition provides an analogue of Proposition~24 in the case that the
starting point and the final point of the paths both lie above 
the line $x=y$.
\proclaim{Proposition~26}{\smc Second fundamental bijection for crossing
paths.}
Let $\A=(A_1,A_2)$ and $\E=(E_1,E_2)$ be two
lattice points in the integer lattice $\Z^2$ with $A_1\le A_2$ and
$E_1\le E_2$. 
There is a bijection $\Ph ^{(2)}$ between paths $P$ from $\A$ to
$\E$ which cross the line $x=y$ and the paths from $(A_2+1,A_1-1)$ to
$(E_1,E_2)$, such that the last meeting point of $P$
with $x=y+1$ is identical with the last meeting point of $\Ph^{(2)}(P)$
with $x=y+1$, such that the path's portions after this meeting point are
identical, and which satisfies
$$\xmaj_{\be;\ga}(P)=\ymaj_{\be;\ga-1}(\Ph^{(2)}(P))\tag5.2.21$$
for every integer $\ga$ with $A_1\le \ga\le A_2$, and also
$$\maj P=\maj \Ph^{(2)}(P).\tag5.2.22$$
\endproclaim
\remark{Remark} Quite similarly to the Remark after Proposition~24, it
should be observed that the 
relevance of the assumption $\ga\le A_2$ lies in
the fact that this allows a path from $\A$ to $\E$ to cross $x=y$ only
after before having crossed the vertical line $x=\ga$. 
Again this will be important in the proof.
\endremark
\demo{Proof of the Proposition} The procedure is quite similar to that in
the proof of Proposition~24. It is even simpler  since this auxiliary
correspondence and therefore also the third step can be avoided. So
it will not be necessary to go into all details, a description
without comments should suffice. For a better understanding of the
following the reader might look up the example at the end of the
proof.

First we consider the case $\ga\ge E_1$. It
is clear that for each point $(p_1,p_2)$ of a path $P$ from $\A$ to
$\E$ we then have $p_2\ge A_2\ge\ga\ge E_1\ge p_1$. This simply means
that $P$ cannot cross the line $x=y$ but stays below everywhere only being
allowed to touch it. Therefore the set of crossing paths is empty as
well as the set of paths from $(A_2+1,A_1-1)$ to
$(E_1,E_2)$ because of $A_2\ge E_1$. This implies that the Proposition in
this case trivially holds.

Now let $\ga<E_1$. The construction of $\Ph^{(2)}$ this time is done in
three steps. Suppose that $P$ is a path from $\A$ to $\E$ which
crosses $x=y$.

{\it First step.} Use the array representation (2.1.2) of paths to see that
this provides a bijection between the following sets,
$$\gather\text {paths } P:(A_1,A_2)\to(E_1,E_2)\text { which cross
}x=y\tag5.2.23a\\
\updownarrow\\
\matrix \hphantom{{}+1}A_1\le &a_1&\hdots&a_k&\le E_1-1\\
A_2+1\le&b_1&\hdots&b_k&\le E_2\hphantom{{}-1}\endmatrix
\text {, there exists an $i$, $1\le i\le k-1$ with
$a_{i+1}>b_i$}\tag5.2.23b
\endgather$$
which (because of (4.0.7)) satisfies
$$\xmaj_{\be;\ga}(P)=\V{a}+\V{b}+\be\cdot\vert
\{t:a_t\ge \ga\}\vert-k(A_1+A_2).\tag5.2.23c$$

{\it Second step.} For an array $(a\mid b)$ of the type (5.2.23b) let
$I$ be maximal with $a_{I+1}>b_I$. We map $(a\mid b)$ to another
two-rowed array $(\bar a\mid\bar b)$ by
$$\align \smatrix \format\r\quad &\c\quad &\c\quad &\c\s\c\quad &\c\quad 
&\c\quad &\l\\
A_1\le&a_1&\hdots&a_I&&a_{I+1}&\hdots&a_k&\le E_1-1\\
A_2+1\le&b_1&\hdots&b_I&&b_{I+1}&\hdots&b_k&\le E_2
\endsmatrix&\tag5.2.24a\\
&\hskip-6cm\longleftrightarrow\quad 
\smatrix \format\r\quad &\c\quad &\c\quad &\c\s\c\quad &\c\quad &\c\quad &\l\\
A_2+1\le&b_1&\hdots&b_I&&a_{I+1}&\hdots&a_k&\le E_1-1\\
A_1\le&a_1&\hdots&a_I&&b_{I+1}&\hdots&b_k&\le E_2
\endsmatrix\\\tag5.2.24b
\endalign$$
(Again the vertival lines in (5.2.24) are drawn only to show which
parts of the arrays are changed and which not.)
More precisely, the new array $(\bar a \mid \bar b )=(\bar a _1,\dots,\bar a _k\mid
\bar b _1,\dots,\bar b _k)$ is given by
$$\bar a _i=\cases b_{i}&1\le i\le I\\ a_i&I<i\le k\endcases$$
and
$$\bar b _i=\cases a_{i}&1\le i\le I\\ b_i&I< i\le k\endcases\ .$$
This correspondence has the property
$$\V{a}+\V{b}+\be\cdot\vert\{t:a_t\ge \ga\}\vert= \V{\bar a }+\V{\bar b }
+\be\cdot\vert\{t:\bar b _t\ge\ga\}\vert.\tag5.2.24c$$

{\it Third step.} Each array $(\bar a\mid \bar b)$ of the type
(5.2.24b)
uniquely corresponds to a path $\bar P$ from
$(A_2+1,A_1-1)$ to $(E_1,E_2)$. Besides there holds
$$\ymaj_{\be;\ga-1}(\bar P)=\V{\bar a }+\V{\bar b }
+\be\cdot\vert\{t:\bar b _t>\ga-1\}\vert-k(A_1+A_2).\tag5.2.25$$

Now we are able to define $\Ph^{(2)}$. For any path $P$ from $\A$
to $\E$ which crosses $x=y$ perform the steps 1--3. 
The image of $P$ under application of 
$\Ph^{(2)}$ by definition is the resulting path $\bar P$,
$$\Ph^{(2)}(P)=\bar P.$$
Combining (5.2.23c), (5.2.24c), and (5.2.25), one obtains the desired
property (5.2.21). Evidently, (5.2.22) results from (5.2.21) by
setting $\be=0$.

The fact that the last $k-I$ elements in the rows of the arrays in
(5.2.24a) are identical with the corresponding last $k-I$ elements in
the array in (5.2.24b), implies that the last meeting point of $P$
with $x=y+1$ as well as the last meeting point of
$\Ph^{(2)}(P)$ with $x=y+1$ is $(b_I+1,b_I)$, and that the
portions of $P$ and $\Ph^{(2)}(P)$ after this last meeting point
are identical.

\medpagebreak
Finally we give an example to illustrate the action of $\Ph^{(2)}$.
Consider the path $P_{\text{ex}}=((-3,-1),1121122111212212212211)$ in
Figure~5,
having
the starting point $\A_{\text{ex}}=(-3,-1)$ and the final point $\E_{\text{ex}}=(9,9)$.
(We have marked the North-East corners of the two paths in Figure~5
by thicker dots. So the paths should be easily distinguished.)
In the first step $P_{\text{ex}}$ is mapped to
its array representation
$(a^{(\text {ex})}\mid b^{(\text {ex})})$ given by
$$\matrix -3\le&-1\ 1\ 4\ 5\ 6\ 7&\le8\\
\hphantom{-}0\le&\hphantom{-}0\ 2\ 3\ 5\ 7\ 9&\le9\endmatrix\ .$$
The index $I$ which is maximal with respect to $a^{(\text {ex})}_{I+1}>b^{(\text
{ex})}_I$
is $I=4$. So in the second step, by (5.2.24) the array $(a^{(\text {ex})}\mid b^{(\text
{ex})})$ is
mapped to the array
$$\matrix \hphantom{-}0\le&\hphantom{-}0\ 2\ 3\ 5\ 6\ 7&\le8\\
-3\le&-1\ 1\ 4\ 5\ 7\ 9&\le9\endmatrix\ ,$$
which is the array representation of the second path in Figure~5. $S_{\text
{ex}}$ is the last meeting point of $P_{\text {ex}}$ and
$\Ph^{(2)}(P_{\text {ex}})$ with the line $x=y+1$.

\vskip10pt 
\vbox{\noindent
$$\Einheit0.3cm
\Koordinatenachsen(10,10)(-3,-4)
\Gitter(10,10)(-3,-4)
\Diagonale(-4,-4){14}
\Pfad(-3,-1),1121122111212212212211\endPfad
\Pfad(0,-4),2221122122211212212211\endPfad
\Kreis(0,0)
\DickPunkt(-3,-1)
\DickPunkt(0,-4)
\DickPunkt(9,9)
\DickPunkt(6,5)
\DuennPunkt(-1,0)
\DuennPunkt(1,2)
\DuennPunkt(4,3)
\DuennPunkt(5,5)
\DuennPunkt(6,7)
\DuennPunkt(7,9)
\DuennPunkt(0,-1)
\DuennPunkt(2,1)
\DuennPunkt(3,4)
\Label\ru{\hskip0.7cm\RR\A_{\text{ex}}}(0,-4)
\Label\lu{\A_{\text{ex}}\hskip6pt}(-3,-1)
\Label\ru{\hskip7pt\E_{\text{ex}}}(9,9)
\Label\r{\Ph^{(2)}(P_{\text{ex}})}(4,-1)
\Label\ro{P_{\text{ex}}}(1,2)
\Label\ru{\hskip12pt S_{\text {ex}}}(6,5)
\hskip3cm
$$%}
\nobreak
\centerline{\eightpoint Figure 5}
}
\vskip10pt
It is left to the reader to check that (5.2.21) always holds.
\quad \quad \qed
\enddemo

Also for this case, a
 simpler  bijection which satisfies (5.2.22) only
has been previously given in \cite{27, Proof of
(5.37)}.
It is also not extendable in order to be applicable 
with the strange major index.


\subheading{5.3. A correspondence for pairs of intersecting lattice paths}
Let $\A=(A_1,A_2)$, $\B=(B_1,B_2)$, $\E=(E_1,E_2)$, and $\F=(F_1,F_2)$
be lattice points in $\Z^2$ such that $A_1\le B_1$, $A_2\ge B_2$,
$E_1\le F_1$, $E_2\ge F_2$. Recall \cite{16, 17, 41} (see subsection~2.2) that 
the key for obtaining determinantal
expressions for generating functions for families of nonintersecting
lattice paths where the weight depends on the position of the edges
of the paths in the lattice $\Z^2$ lies in the observation that the
generating function for pairs $(P_1,P_2)$ of {\it intersecting} paths,
$P_1:\A\to\E$, $P_2:\B\to\F$, is equal to the generating function of
{\it arbitrary} pairs $(Q_1,Q_2)$ of paths, $Q_1:\B\to\E$, $Q_2:\A\to\F$.
(Recall that paths are
called {\it intersecting} if they have points in common, and
{\it nonintersecting} if not.)
This has already been explained in subsection~2.2.
 But we are
not interested in edge weights but in weighing families of paths
 by the major index or the strange
major indices, respectively. So what we need is a correspondence with
similar properties, which in addition should take care of
the major index or the strange major indices. The familiar interchanging
procedure described in subsection~2.2 obviously does not.

The first observation is that there cannot be any useful result
unless $(A_1,A_2)$ and $(B_1,B_2)$ lie on a line parallel to the
anti-diagonal $x+y=0$. After we have proved the following Proposition we shall
try to give something like an ``explanation" of this phenomenon. Here
we want to content ourselves with an example. Take $\A_0=(0,0)$,
$\E_0=(2,3)$, and $\B_0=(1,-2)$, $\F_0=(3,1)$. The maj-generating
function for intersecting pairs of paths $(P_1,P_2)$, $P_1:\A_0\to\E_0$,
$P_2:\B_0\to\F_0$, is given by
$$\underset P_1,P_2\text { intersect}\to
{\underset P_2:\B_0\rightarrow\F_0\to{\sum _{P_1:\A_0\to\E_0}
^{}}}q^{\maj P_1+\maj P_2}=
{q^2}+2{q^3}+4{q^4}+4{q^5}+5{q^6}+4{q^7}+2{q^8}+{q^9}+
  {q^{10}}.\tag5.3.1
$$
Suppose that there would be some bijection taking care of the major
index, such
that the above intersecting pairs $(P_1,P_2)$ of paths would uniquely
correspond to pairs $(Q_1,Q_2)$ of paths, $Q_1:\B_0\to\E_0$,
$Q_2:\A_0\to\F_0$. Then the generating function (5.3.1) had to 
equal 
$$\underset Q_2:\A_0\rightarrow\F_0\to{\sum _{Q_1:\B_0\to\E_0}
^{}}q^{\stat_1 Q_1+\stat_2 Q_2}=\Big(\sum _{Q_1:\B_0\to\E_0}
^{}q^{\stat_1
Q_1}\Big)\Big(\sum _{Q_2:\A_0\rightarrow\F_0} ^{}q^{\stat_2 Q_2}\Big),
$$
where $\stat_1$ and $\stat_2$ denote some major-like statistics.
This means that the polynomial on the right-hand side should factor
into two polynomials, one being the sum of 6 monomials of the form
$q^i$, the second
being the sum of 4 monomials of the form $q^i$, $i\in
\{0,1,\dots,10\}$. (There are 6 paths from $\B_0=(1,-2)$ to
$\E_0=(2,3)$, and 4 paths from $\A_0=(0,0)$ to $\F_0=(3,1)$.) But the
polynomial in (5.3.1) does not factor at all! 

Therefore we will restrict ourselves to $\A$ and $\B$
lying on a line parallel to $x+y=0$. This means that in the sequel we
will always assume that there are some integers $A,B,D$ such that 
$\A=(A+D,-A)$ and $\B=(B+D,-B)$. For this choice of the initial points
of the paths it is indeed possible to find a strange major analogue
(and hence also a major analogue) for the 
interchanging procedure of subsection~2.2. 
This analogue also maps pairs $(P_1,P_2)$ of
{\it intersecting} paths, $P_1:\A\to\E$, $P_2:\B\to\F$, onto {\it arbitrary} 
pairs $(Q_1,Q_2)$ of paths, $Q_1:\B\to\E$, $Q_2:\A\to\F$, and it also
preserves the path's portions after the last meeting point.
\proclaim{Proposition~27}{\smc Fundamental bijection for pairs of
intersecting paths.} Let $\A=(A+D,-A)$, $\B=(B+D,-B)$, $\E=(E_1,E_2)$, 
and $\F=(F_1,F_2)$
be lattice points in $\Z^2$ with $A< B$, 
$E_1< F_1$, $E_2\ge F_2$. There is a bijection $\Ps$ between pairs
$(P_1,P_2)$, $P_1:\A\to\E$, $P_2:\B\to\F$, of intersecting paths
and pairs $(Q_1,Q_2)$, $Q_1:\B\to\E$, $Q_2:\A\to\F$, of paths such
that the portions of $P_1$ and $Q_1$ after the last meeting point of
$P_1$ and $P_2$ are identical, including this last meeting point,
and such that 
the portions of $P_2$ and $Q_2$ after this last meeting point,
including the last meeting point, are identical. Moreover, if
$(Q_1,Q_2)=\Ps\big((P_1,P_2)\big)$ then the equations
$$\ymaj_{\be;\ga+1}(P_1)+\ymaj_{\be;\ga}(P_2)=\ymaj_{\be;\ga+1}(Q_1)
+\ymaj_{\be;\ga}(Q_2)+B-A\tag5.3.2$$
and
$$\xmaj_{\be;\ga}(P_1)+\xmaj_{\be;\ga+1}(P_2)=\xmaj_{\be;\ga}(Q_1)
+\xmaj_{\be;\ga+1}(Q_2)+B-A,\tag5.3.3$$
hold for all integers $\ga$. In particular, there holds
$$\maj P_1+\maj P_2=\maj Q_1+\maj Q_2+B-A.\tag5.3.4$$
Besides, if $A+D<\ga_1\le B+D$ and $-B-1\le \ga_2<-A$, the equation
$$\xmaj_{\be;\ga_1}(P_1)+\ymaj_{\be;\ga_2}(P_2)=\ymaj_{\be;\ga_2+1}(Q_1)
+\xmaj_{\be;\ga_1+1}(Q_2)+B-A+\be\tag5.3.5$$
holds. Identity (5.3.5) also holds if the inequality
$\ga_1\le B+D$ is replaced by the requirement that the last meeting
point of $P_1$ and $P_2$ is located to the right or on the vertical
line $x=\ga_1$.

\endproclaim
\demo{Proof}Once the equation (5.3.2) is settled, the equations
(5.3.3) and (5.3.4) immediately follow. For (5.3.3) this is seen using
the relation (4.0.5) between ymaj and xmaj, while for deriving (5.3.4)
we only have to set $\be=0$ in (5.3.2).

The construction of $\Ps$ consists of four steps. As in the proof of
Proposition~24, for the reader who is not interested in all the
details we outline a short-cut through the following construction.
The map $\Ps$ is essentially explained by the lines (5.3.6a--e),
(5.3.10), (5.3.11), (5.3.20), (5.3.21), and the first passage of the
fourth step of the proof. For illustration, an example is carried out
at the end of the proof.

{\it First step.} Again we utilize the array representation of paths.
Let $(P_1,P_2)$ be a pair of intersecting paths, $P_1:\A\to\E$,
$P_2:\B\to\F$. $P_1$ and $P_2$ are in one-to-one correspondence with
two-rowed arrays $(a\mid b)$ and $(c\mid d)$ of the types
$$\matrix \format\r\quad &\c\quad &\c\quad &\c\quad &\l\\
A+D\le&a_1&\hdots&a_k&\le E_1-1\\
-A+1\le&b_1&\hdots&b_k&\le E_2\endmatrix\hphantom{\ ,}\tag5.3.6a$$
and
$$\matrix \format\r\quad &\c\quad &\c\quad &\c\quad &\l\\
B+D\le&c_1&\hdots&c_l&\le F_1-1\\
-B+1\le&d_1&\hdots&d_l&\le F_2\endmatrix\ ,\tag5.3.6b$$
respectively. 


Let $\S$ be the last meeting point of $P_1$ and $P_2$.
By definition set $a_{k+1}:=E_1$, $b_0:=-A$, $b_{k+1}:=E_2+1$, and
$c_{l+1}:=F_1$. (Note that the thereby augmented sequences $a,b,c $
remain strictly increasing.)

\vskip10pt 
\vbox{\noindent
$$
\Pfad(0,0),221111121111\endPfad
\Pfad(-2,-1),11112222221111\endPfad
\DickPunkt(0,2)
\DickPunkt(2,2)
\DickPunkt(2,-1)
\Label\ru{\S}(2,2)
\Label\lo{\hskip-10pt(c_j,d_j)}(0,2)
\Label\ru{(a_i,b_{i-1})}(2,-1)
\Label\r{P_1}(6,5)
\Label\r{P_2}(9,3)
\hskip4cm
$$
\nobreak
\centerline{\eightpoint Figure 6}
}
\vskip10pt
Considering the East-North corner $(a_i,b_{i-1})$ in $P_1$
immediately preceding $\S$ (and being allowed to be equal to $\S$)
and the North-East corner $(c_j,d_j)$ in $P_2$ immediately preceding
$\S$ (and being allowed to be equal to $\S$), we get the inequalities
(cf\. Figure~6)
$$\gather c_j\le a_i<c_{j+1},\tag5.3.6c\\
 b_{i-1}\le
d_j<b_i,\tag5.3.6d
\endgather$$
where
$$1\le i\le k+1,\quad 1\le j\le l.\tag5.3.6e$$

Of course, $k,l,a_i,b_i,c_j,d_j$, etc., refer to the array representations
(5.3.6a,b) of $P_1$ and $P_2$. It now becomes apparent that 
the above assignments for $a_{k+1},b_0,b_{k+1}, c_{l+1}$ are needed
for the inequalities (5.3.6c,d) to make sense for $i=1$, $i=k+1$, or
$j=l$. Vice versa, if (5.3.6c,d,e) is satisfied then $(a_i,d_j)$ is
a meeting point between $P_1$ and $P_2$. 
Besides, a meeting point $\S$ is the {\it last} meeting point
between $P_1$ and $P_2$ if and only if $i$ {\it and} $j$ are maximal
with respect to the property (5.3.6c,d,e).

Summarizing, the existence of $i,j$
satisfying (5.3.6c,d,e) characterize the array representations of
{\it intersecting} pairs of paths. Thus we have
 a bijection between intersecting pairs $(P_1,P_2)$
of paths, $P_1:\A\to\E$, $P_2:\B\to\F$, and pairs ($(a\mid b)$,
$(c\mid d)$) of arrays of the types (5.3.6a) and (5.3.6b),
respectively, for which there exist integers $i,j$ which satisfy
(5.3.6c,d,e). In the sequel we call such a pair of arrays a {\it pair
of arrays of the type\/} (5.3.6).

We finally want to show (5.3.2). So it is necessary to relate 
$\ymaj_{\be;\ga+1}(P_1)+\ymaj_{\be;\ga}(P_2)$ to weights of the
corresponding array representations (5.3.6a,b). Because of
(4.0.6), according to the choice of $\ga$, we have to distinguish
between three cases:

Case A. $\ga\ge -A-1$. Here we have
$$\multline
\ymaj_{\be;\ga+1}(P_1)+\ymaj_{\be;\ga}(P_2)
=\V{a}+\V{b}+\be\cdot\vert\{t:b_t>\ga+1\}\vert\\
+\V{c}+\V{d}+\be\cdot\vert\{t:d_t>\ga\}\vert-(k+l)D.
\endmultline\tag5.3.7a$$

Case B. $-A-1>\ga\ge -B$. Here we have
$$\multline
\ymaj_{\be;\ga+1}(P_1)+\ymaj_{\be;\ga}(P_2)
=\V{a}+\V{b}+\be\cdot\vert\{t:a_t\ge D-\ga-1\}\vert\\
+\V{c}+\V{d}+\be\cdot\vert\{t:d_t>\ga\}\vert-(k+l)D+(-A-\ga-1)\be.
\endmultline\tag5.3.7b$$

Case C. $-B>\ga$. Here we have
$$\multline
\ymaj_{\be;\ga+1}(P_1)+\ymaj_{\be;\ga}(P_2)
=\V{a}+\V{b}+\be\cdot\vert\{t:a_t\ge D-\ga-1\}\vert\\
+\V{c}+\V{d}+\be\cdot\vert\{t:c_t\ge D-\ga\}\vert-(k+l)D+(-A-\ga-1)\be+
(-B-\ga)\be.
\endmultline\tag5.3.7c$$

To show (5.3.5) it will be necessary to use the following identity
$$\multline
\xmaj_{\be;\ga_1}(P_1)+\ymaj_{\be;\ga_2}(P_2)
=\V{a}+\V{b}+\be\cdot\vert\{t:a_t\ge \ga_1\}\vert\\
+\V{c}+\V{d}+\be\cdot\vert\{t:d_t>\ga_2\}\vert-(k+l)D,
\endmultline\tag5.3.8a$$
which in view of (4.0.6) and (4.0.7) certainly holds if $A+D<\ga_1$
and $-B\le \ga_2$. For $\ga_2=-B-1$ we have
$$\multline
\xmaj_{\be;\ga_1}(P_1)+\ymaj_{\be;-B-1}(P_2)
=\V{a}+\V{b}+\be\cdot\vert\{t:a_t\ge \ga_1\}\vert\\
+\V{c}+\V{d}+\be\cdot\vert\{t:c_t\ge B+D+1\}\vert-(k+l)D+\be.
\endmultline\tag5.3.8b$$
{\it Second step.} This is the crucial step in the construction of
$\Ps$.

Let $I$ and $J$ be maximal with 
$$\gather c_J\le a_I<c_{J+1},\tag5.3.9a\\
b_{I-1}\le d_J<b_I,\tag5.3.9b
\endgather$$
and
$$1\le I\le k+1,\quad 1\le J\le l.\tag5.3.9c$$
We map a pair ($(a\mid b)$, $(c\mid d)$) of arrays of the type (5.3.6)
to the pair  ($(\bar a\mid\bar
b)$, $(\bar c\mid\bar d)$) of arrays, where $(\bar a\mid\bar b)=
(\bar a_1,\dots,\bar a_{k-I+J+1}\mid \bar b_2,\dots,\bar b_{k-I+J+1})$ is
given by
$$\matrix c_1-1&c_2-1&\hdots&c_J-1&a_I&\hdots&a_k\\
&d_1+1&\hdots&d_{J-1}+1&b_I&\hdots&b_k\endmatrix
\tag5.3.10a$$
and $(\bar c\mid\bar d)=(\bar c_2,\dots,\bar c_{l-J+I}
\mid \bar d_1,\dots,\bar d_{l-J+I})$ is given by
$$\matrix &a_1+1&\innerhdotsfor2\after\quad &a_{I-1}+1&c_{J+1}&\hdots&c_l\\
b_1-1&b_2-1&\hdots&b_{I-1}-1&d_J&d_{J+1}&\hdots&d_l\endmatrix\ .
\tag5.3.10b$$

We claim that this mapping is invertible. More precisely, we are
going to establish that the mapping (5.3.10) is a bijection between
pairs ($(a\mid b)$, $(c\mid d)$) of arrays of the type (5.3.6) and
pairs ($(\bar a\mid\bar
b)$, $(\bar c\mid\bar d)$) of arrays of the types 
$$\matrix B+D-1\le&\bar a_1&\innerhdotsfor2\after\quad &\bar a_{\bar k}&\le E_1-1\\
\hphantom{D}{}-B+2\le&&\bar b_2&\hdots&\bar b_{\bar k}&\le
E_2\hphantom{{}-1}\endmatrix
\tag5.3.11a$$
and
$$\matrix A+D+1\le&&\bar c_2&\hdots&\bar c_{\bar l}&\le F_1-1\\
\hphantom{1+D}{}-A\le&\bar d_1&\innerhdotsfor2\after\quad &\bar d_{\bar l}&\le
F_2\hphantom{{}-1}\endmatrix\ ,
\tag5.3.11b$$
respectively. That the bounds in (5.3.11) are the right ones, is
trivial. 

To establish that (5.3.10) is invertible we construct the inverse
mapping. Suppose that ($(\bar a\mid\bar b)$, $(\bar c\mid \bar d)$) is a
pair of arrays of the type (5.3.11). By definition set $\bar a_{\bar
k+1}:=E_1$, $\bar b_1:=-B+1$, $\bar b_{\bar k+1}:=E_2+1$, $\bar
c_1:=A+D$, and $\bar c_{\bar l+1}:=F_1$. (Again note that these
assignments guarantee the thereby augmented sequences $\bar a,\bar
b,\bar c$ to remain strictly increasing.)

Let $\bar I$ {\it and} $\bar J$ be maximal with
$$\gather \bar c_{\bar J}\le \bar a_{\bar I}<\bar c_{{\bar
J}+1},\tag5.3.12a\\
 \bar b_{{\bar I}-1}\le
\bar d_{\bar J}<\bar b_{\bar I},\tag5.3.12b
\endgather$$
and
$$2\le \bar I\le \bar k+1,\quad 1\le \bar J\le \bar l.\tag5.3.12c$$
The assignments for $\bar a_{\bar k+1},\bar b_1$, etc., have been
necessary in order that the inequalities (5.3.12a,b) make sense for 
$\bar I=2$, $\bar I=\bar k+1$, $\bar J=1$, or $\bar J=\bar l$. 
We map a pair ($(\bar a\mid\bar b)$, $(\bar c\mid\bar d)$) of arrays of
the type (5.3.11) to the arrays
$$\matrix \bar c_2-1&\hdots&\bar c_{\bar J}-1&\bar a_{\bar
I}&\hdots&\bar a_{\bar k}\\
\bar d_1+1&\hdots&\bar d_{\bar J-1}&\bar b_{\bar I}&\hdots&\bar
b_{\bar k}\endmatrix\tag5.3.13a$$
and
$$\matrix \bar a_1+1&\innerhdotsfor2\after\quad &\bar a_{\bar I-1}+1&\bar c_{\bar
J+1}&\hdots&\bar c_{\bar l}\\
\bar b_2-1&\hdots&\bar b_{\bar I-1}-1&\bar d_{\bar
J}&\bar d_{\bar J+1}&\dots &\bar
d_{\bar l}\endmatrix\ .\tag5.3.13b$$
The mapping (5.3.13) will be shown to be the inverse of (5.3.10).

The first thing to have to be established, is that the map (5.3.13) is always
well-defined. This is the case if and only if there exist $\bar I$
and $\bar J$ which are maximal with respect to (5.3.12). So we have to
show that there is at least one pair of integers $i,j$, with
$$\gather \bar c_{j}\le \bar a_{i}<\bar c_{j+1},\tag5.3.14a\\
 \bar b_{{i}-1}\le
\bar d_{j}<\bar b_{i},\tag5.3.14b
\endgather$$
and
$$2\le i\le \bar k+1,\quad 1\le j\le \bar l.\tag5.3.14c$$

Let $U=\{2,\dots,\bar k+1\}$ be the range of the index $i$ and 
$V=\{1,\dots,\bar l\}$ be the range of the index $j$. 
Next, two mappings $f$ and
$g$, $f:U\to V$, $g:V\to U$, are defined. For $i\in U$ denote by $f(i)$
the uniquely determined integer that satisfies
$$\bar c_{f(i)}\le\bar a_i<\bar c_{f(i)+1}.\tag5.3.15$$
Likewise, for $j\in V$ denote by $g(j)$ the uniquely determined
integer that satisfies
$$\bar b_{g(j)-1}\le\bar d_j<\bar b_{g(j)}.\tag5.3.16$$
We have to confirm that $f$ and $g$ are well-defined for all $i\in
U$, and that $g$ is well-defined for all $j\in V$. What has to be
established is the existence of integers $f(i)$ satisfying (5.3.15) and 
the existence of integers $g(j)$ satisfying (5.3.16). 
Once this has been done the
uniqueness is clear from the fact that the sequences $\bar a,\bar
b,\bar c,\bar d$ are in strictly increasing order.

So let $i\in U$. We have $B+D-1\le\bar a_1<\bar a_i\le\bar a_{\bar
k+1}=E_1$. Because of the assumptions $A<B$ and $E_1<F_1$, we conclude
that $A+D\le \bar a_i<F_1$, or in terms of $\bar c_1$ and $\bar
c_{\bar l+1}$, $\bar c_1\le \bar a_i<\bar c_{\bar l+1}$. Clearly this
settles the existence of an integer $f(i)$ satisfying (5.3.15).

Similarly, let $j\in V$. We have $-A\le \bar d_j\le F_2$. Because of
the assumptions $A<B$ and $E_2\ge F_2$, we get $-B+1\le \bar
d_j<E_2+1$. This inequality, written in terms of $\bar b_1$ and $
\bar b_{\bar k+1}$, reads $\bar b_1\le\bar d_j<\bar b_{\bar k+1}$,
which confirms the existence of an integer $g(j)$ satisfying (5.3.16).

It is a simple matter of fact that $f$ and $g$ are monotone
functions. To be precise, if $i_1\le i_2$ then $f(i_1)\le f(i_2)$,
and if $j_1\le j_2$ then $g(j_1)\le g(j_2)$. This is due to the
strictly increasing order of $\bar a,\bar b,\bar c$, and $\bar d$.
Now start with  $2\in U$ and alternatively apply $f$ and $g$. To be
precise, we form the sequence $s_1,s_2,s_3,\dots$, where $s_1=2$,
$s_{2t}=f(s_{2t-1})$, and $s_{2t+1}=g(s_{2t})$, $t=1,2,\dots$. Then we
consider the subsequences $s_1,s_3,s_5,\dots$ and $s_2,s_4,s_6,
\dots$. Obviously, because of the monotonicity of both $f$ and $g$
these subsequences are weakly increasing. In addition they are
infinite and bounded sequences, hence both must eventually become
stationary. Denote by $\bar i$ the limit element of the first
sequence, and by $\bar j$ the limit element of the second sequence.
By definition of the sequences we have $f(\bar i)=\bar j$ and $g(\bar
j)=\bar i$ which by means of (5.3.15) and (5.3.16) says that $\bar c_{\bar
j}\le\bar a_{\bar i}<\bar c_{\bar j+1}$ and $\bar b_{\bar i-1}\le\bar
d_{\bar j}<\bar b_{\bar i}$. Hence we have found a pair of indices
which satisfies (5.3.14).
\medpagebreak

Now that we have convinced ourselves that the mapping (5.3.13) is
well-defined, it remains to show that it is indeed the inverse of
(5.3.10). As before, let ($(a\mid b)$, $(c\mid d)$) be a pair of arrays
of the type (5.3.6) and $I,J$ be maximal with respect to (5.3.9).
Denote the array in (5.3.10a) by $(\bar a\mid \bar b)$
and the array in (5.3.10b) by $(\bar c\mid\bar d)$. 
(Note that $\bar k=k-I+J+1$
and $\bar l=l-J+I$.) Let $\bar I,\bar J$ be
maximal with respect to (5.3.12). All we have to show is that $\bar
I=J+1$ and $\bar J=I$ since then from (5.3.10) it is obvious that by applying
(5.3.13)
to the pair ($(\bar a\mid\bar b)$, $(\bar c\mid\bar d)$) we obtain the
pair ($(a\mid b)$, $(c\mid d)$) again.

Also from (5.3.9) and (5.3.10) it is clear that (5.3.12) holds if $\bar I$ is
replaced by $J+1$ and $\bar J$ by $I$. Hence the actual values of
$\bar I,\bar J$ because of their maximality must be greater or equal.
To be precisely, the inequalities $\bar I\ge J+1$ and $\bar J\ge I$
must hold. We distinguish between three cases.

{Case 1.} $\bar I>J+1$ and $\bar J>I$. Under these assumptions by
(5.3.10) we have $\bar a_{\bar I}=a_{\bar I-J+I-1}$, $\bar b_{\bar
I}=b_{\bar I-J+I-1}$, $\bar b_{\bar
I-1}=b_{\bar I-J+I-2}$, $\bar c_{\bar J}=c_{\bar J-I+J}$, 
$\bar c_{\bar J+1}=c_{\bar J-I+J+1}$, and $\bar d_{\bar J}=d_{\bar
J-I+J}$. Setting $I_0:=\bar I-J+I-1$ and $J_0:=\bar J-I+J$, the
inequalities (5.3.12a,b) read $c_{J_0}\le a_{I_0}<c_{J_0+1}$ and
$b_{I_0-1}\le d_{J_0}<b_{I_0}$, respectively. Besides, because of
$J+1<\bar I\le\bar k+1=k-I+J+2$ we get $I<I_0\le k+1$, and because of
$I<\bar J\le\bar l=l-J+I$ we get $J< J_0\le l$. This contradicts the
maximality of $I$ and $J$ with respect to (5.3.9).

{Case 2.} $\bar I>J+1$ and $\bar J=I$. Here by (5.3.10) we have
$\bar c_{\bar J+1}=c_{J+1}$, $\bar d_{\bar J}=d_{J}$, and $\bar
a_{\bar I},\bar b_{\bar I},\bar b_{\bar I-1}$ as in Case~1. Setting
$I_0:=\bar I-J+I-1$ and $J_0:=J$ from the second inequality in
(5.3.12a) we get $a_{I_0}<c_{J_0+1}$, while (5.3.12b) reads
$b_{I_0-1}\le d_{J_0}<b_{I_0}$. Again, because of $J+1<\bar I\le \bar
k+1=k-I+J+2$ we have $I<I_0\le k+1$. In particular, from this and
(5.3.9a) we conclude that $c_J\le a_I<a_{I_0}$. This implies
$c_{J_0}<a_{{I_0}}<c_{J_0+1}$. This is a contradiction to the
maximality of $I$ and $J$ with respect to (5.3.9).

{Case 3.} $\bar I=J+1$ and $\bar J>I$. Here by (5.3.10) we have
$\bar a_{\bar I}=a_I$, $\bar b_{\bar I}=b_I$, and $\bar c_{\bar J},
\bar c_{\bar J+1},\bar d_{\bar J}$ as in Case~1. Setting $I_0:=I$ and
$J_0:=\bar J-I+J$, the inequality (5.3.12a) reads $c_{J_0}\le
a_{I_0}<c_{J_0+1}$, while from the second inequality in (5.3.12b) we
derive $d_{J_0}<b_{I_0}$. Because of $I<\bar J\le\bar l=l-J+I$ we
have $J<J_0\le l$. In particular, from this and (5.3.9b) we deduce
$b_{I-1}\le d_J<d_{J_0}$. This implies $b_{I_0-1}<d_{J_0}<b_{I_0}$.
Again we obtain a contradiction to the maximality of $I$ and $J$ with
respect to (5.3.9).

This completes the proof that (5.3.10) is a bijection between pairs of
arrays of the type (5.3.6) and pairs of arrays of the type (5.3.11).
\medpagebreak

Finally we need to say something about weight properties. Again, let
($(a\mid b)$, $(c\mid d)$) be a pair of arrays of the type (5.3.6) and
denote by ($(\bar a\mid \bar b)$, $(\bar c\mid\bar d)$) its image under
application of (5.3.10). The right-hand sides of (5.3.7a,b,c) serve as
a guide which expressions have to be considered. To begin with, a
short computation shows that 
$$\V a+\V b+\V c+\V d-(k+l)D=\V{\bar a}+\V{\bar b}+\V{\bar c}+\V{\bar
d}-(\bar k+\bar l)D+D+1.\tag5.3.17$$
To count contributed $\be$'s, even five cases have to be
distinguished. Since the sense of the following manipulations  will
only become clear later, maybe for the moment the reader should skip the
following case study and come back to it before reading the passage
after (5.3.21), when the study of weight properties is continued.

{Case A1.} $\ga\ge-A$. 
Having in mind (5.3.7a) we obtain
$$\align \be\cdot\vert\{&t:b_t>\ga+1\}\vert
+\be\cdot\vert\{t:d_t>\ga\}\vert\\
&=\be\cdot\vert\{t:b_t>\ga+1\text { and }t\ge I\}\vert
+\be\cdot\vert\{t:b_t-1>\ga\text { and }t<I\}\vert\\
&\quad +\be\cdot\vert\{t:d_t>\ga\text { and }t\ge J\}\vert
+\be\cdot\vert\{t:d_t+1>\ga+1\text { and }t<J\}\vert\\
&=\be\cdot\vert\{t:\bar b_t>\ga+1\}\vert
+\be\cdot\vert\{t:\bar d_t>\ga\}\vert.\tag5.3.18a
\endalign$$

{Case A2.} $\ga=-A-1$. Again having in mind (5.3.7a) we get
$$\align \be\cdot\vert\{&t:b_t>-A\}\vert
+\be\cdot\vert\{t:d_t>-A-1\}\vert\\
&=\be\cdot\vert\{t:b_t>-A\text { and }t\ge I\}\vert
+\be\cdot\vert\{t:b_t>-A\text { and }t<I\}\vert\\
&\quad +\be\cdot\vert\{t:d_t>-A-1\text { and }t\ge J\}\vert
+\be\cdot\vert\{t:d_t>-A-1\text { and }t<J\}\vert.
\endalign$$
Since because of (5.3.6a) the relations $b_t>-A$ and $a_t\ge A+D$
hold for all $t=1,\dots,k$, in the above equation the condition
$b_t>-A$ may freely be substituted by $a_t+1\ge A+D+1$. Another
observation is that by (5.3.9b) we have $-A=b_0\le b_{I-1}\le d_J$.
On the other hand (5.3.9a) gives $A+D\le a_I<c_{J+1}$. These facts
imply
$$\align
\vert\{t:d_t>-A-1\text { and }t\ge J\}\vert&=l-J+1\\
&=\vert\{t:c_t\ge A+D+1\text { and }t\ge J+1\}\vert+1.
\endalign$$
Putting everything together, we obtain
$$\align \be\cdot\vert\{&t:b_t>-A\}\vert
+\be\cdot\vert\{t:d_t>-A-1\}\vert\\
&=\be\cdot\vert\{t:b_t>-A\text { and }t\ge I\}\vert
+\be\cdot\vert\{t:a_t+1\ge A+D+1\text { and }t<I\}\vert\\
&\quad +\be\cdot\vert\{t:c_t\ge A+D+1\text { and }t\ge
J+1\}\vert+\be\\
&\hskip4cm+\be\cdot\vert\{t:d_t+1>-A\text { and }t<J\}\vert\\
&=\be\cdot\vert\{t:\bar b_t>-A\}\vert
+\be\cdot\vert\{t:\bar c_t\ge A+D+1\}\vert+\be.\tag5.3.18b
\endalign$$

{Case B.} $-A-1>\ga\ge -B$. This time having in mind (5.3.7b), we
have
$$\align \be\cdot\vert\{&t:a_t\ge D-\ga-1\}\vert
+\be\cdot\vert\{t:d_t>\ga\}\vert\\
&=\be\cdot\vert\{t:a_t\ge D-\ga-1\text { and }t\ge I\}\vert
+\be\cdot\vert\{t:a_t\ge D-\ga-1\text { and }t<I\}\vert\\
&\quad +\be\cdot\vert\{t:d_t>\ga\text { and }t\ge J\}\vert
+\be\cdot\vert\{t:d_t>\ga\text { and }t<J\}\vert.
\endalign$$
Use of $\ga\ge-B$ and of (5.3.9a) gives $D-\ga\le B+D\le c_J\le a_I$.
On the other hand obviously we have $\ga+1<-A\le b_I$. These facts
imply
$$\align
\vert\{t:a_t\ge D-\ga-1\text { and }t\ge I\}\vert&=k-I+1\\
&=\vert\{t:b_t>\ga+1\text { and }t\ge I\}\vert.
\endalign$$
Moreover, by $-A-1>\ga$ and (5.3.9b) we get $\ga<-A=b_0\le b_{I-1}\le
d_J$, and by $\ga\ge-B$ we get $D-\ga\le B+D\le c_J$. These facts
imply
$$\align
\vert\{t:d_t>\ga\text { and }t\ge J\}\vert&=l-J+1\\
&=\vert\{t:c_t\ge D-\ga\text { and }t\ge J+1\}\vert+1.
\endalign$$
Putting everything together, we obtain
$$\align 
\be\cdot\vert\{&t:a_t\ge D-\ga-1\}\vert
+\be\cdot\vert\{t:d_t>\ga\}\vert\\
&=\be\cdot\vert\{t:b_t>\ga+1\text { and }t\ge I\}\vert
+\be\cdot\vert\{t:a_t+1\ge D-\ga\text { and }t<I\}\vert\\
&\quad +\be\cdot\vert\{t:c_t\ge D-\ga\text { and }t\ge J+1\}\vert+\be\\
&\hskip4cm+\be\cdot\vert\{t:d_t+1>\ga+1\text { and }t<J\}\vert\\
&=\be\cdot\vert\{t:\bar b_t>\ga+1\}\vert
+\be\cdot\vert\{t:\bar c_t\ge D-\ga\}\vert+\be.\tag5.3.18c
\endalign$$

{Case C1.} $\ga=-B-1$. Having in mind (5.3.7c), we get
$$\align \be\cdot\vert\{&t:a_t\ge B+D\}\vert
+\be\cdot\vert\{t:c_t\ge B+D+1\}\vert\\
&=\be\cdot\vert\{t:a_t\ge B+D\text { and }t\ge I\}\vert
+\be\cdot\vert\{t:a_t\ge B+D\text { and }t<I\}\vert\\
&\quad +\be\cdot\vert\{t:c_t\ge B+D+1\text { and }t\ge J+1\}\vert\\
&\hskip4cm+\be\cdot\vert\{t:c_t\ge B+D+1\text { and }t<J+1\}\vert.
\endalign$$
By (5.3.9a) we have $B+D\le c_J\le a_I$, while by (5.3.9b) we have
$-B<d_J<b_I$. This yields
$$\align
\vert\{t:a_t\ge B+D\text { and }t\ge I\}\vert&=k-I+1\\
&=\vert\{t:b_t>-B\text { and }t\ge I\}\vert.
\endalign$$
Moreover, by definition for all $t$ there hold $c_t\ge B+D$ and
$d_t>-B$. Hence
$$\multline
\vert\{t:c_t\ge B+D+1\text { and }t< J+1\}\vert=J-\ch(c_1=B+D)\\
=\vert\{t:d_t+1>-B\text { and }t<J\}\vert+1-\ch(c_1=B+D),
\endmultline$$
where, as in section~2, $\ch$ is the usual truth function. Putting
everything together, we obtain
$$\align \be\cdot\vert\{&t:a_t\ge B+D\}\vert
+\be\cdot\vert\{t:c_t\ge B+D+1\}\vert\\
&=\be\cdot\vert\{t:b_t> -B\text { and }t\ge I\}\vert
+\be\cdot\vert\{t:a_t+1\ge B+D+1\text { and }t<I\}\vert\\
&\quad +\be\cdot\vert\{t:c_t\ge B+D+1\text { and }t\ge J+1\}\vert\\
&\hskip1cm+\be\cdot\vert\{t:d_t+1> -B\text { and
}t<J\}\vert+(1-\ch(c_1=B+D))\cdot\be\\
&=\be\cdot\vert\{t:\bar b_t>-B\}\vert
+\be\cdot\vert\{t:\bar c_t\ge B+D+1\}\vert+\ch(c_1>B+D)\cdot\be.\tag5.3.18d
\endalign$$

{Case C2.} $\ga<-B-1$. Once more, having in mind (5.3.7c), we get
$$\align \be\cdot\vert\{&t:a_t\ge D-\ga-1\}\vert
+\be\cdot\vert\{t:c_t\ge D-\ga\}\vert\\
&=\be\cdot\vert\{t:a_t\ge D-\ga-1\text { and }t\ge I\}\vert
+\be\cdot\vert\{t:a_t+1\ge D-\ga\text { and }t<I\}\vert\\
&\quad +\be\cdot\vert\{t:c_t\ge D-\ga\text { and }t\ge J+1\}\vert\\
&\hskip4cm+\be\cdot\vert\{t:c_t-1\ge D-\ga-1\text { and }t<J+1\}\vert\\
&=\be\cdot\vert\{t:\bar a_t\ge D-\ga-1\}\vert
+\be\cdot\vert\{t:\bar c_t\ge D-\ga\}\vert.\tag5.3.18e
\endalign$$

In order to establish (5.3.5), we need the following considerations. For
$\ga_2\ge -B$, having in mind (5.3.8a), we have
$$\align \be\cdot\vert\{&t:a_t\ge \ga_1\}\vert
+\be\cdot\vert\{t:d_t> \ga_2\}\vert\\
&=\be\cdot\vert\{t:a_t\ge \ga_1\text { and }t\ge I\}\vert
+\be\cdot\vert\{t:a_t\ge \ga_1\text { and }t<I\}\vert\\
&\quad +\be\cdot\vert\{t:d_t>\ga_2\text { and }t\ge J\}\vert
+\be\cdot\vert\{t:d_t>\ga_2\text { and }t<J\}\vert.
\endalign$$
If $\ga_1\le B+D$ then using (5.3.9a) we have $\ga_1\le B+D\le c_J\le
a_I$. On the other
hand, if the last meeting point between $P_1$ and $P_2$ is located to
the right or on the line $x=\ga_1$, we directly infer $\ga_1\le a_I$.
(Recall that this last meeting point actually is $(a_I,d_J)$.)
Using this, (5.3.9a,b), and the assumption $\ga_2<-A$, we get the
inequalities $\ga_1\le a_I<c_{J+1}$, $\ga_2+1\le -A<b_I$, and
$\ga_2<-A\le b_{I-1}\le d_J$. These facts imply
$$\align \vert\{t: a_t\ge \ga_1\text { and }t\ge I\}\vert&=k-I+1\\
&=\vert\{t:b_t>\ga_2+1\text { and }t\ge I\}\vert
\endalign$$
and 
$$\align \vert\{t: d_t> \ga_2\text { and }t\ge J\}\vert&=l-J+1\\
&=\vert\{t:c_t\ge\ga_1+1\text { and }t\ge J+1\}\vert+1.
\endalign$$
Putting everything together, we obtain
$$\align \be\cdot\vert\{&t:a_t\ge\ga_1\}\vert
+\be\cdot\vert\{t:d_t>\ga_2\}\vert\\
&=\be\cdot\vert\{t:b_t>\ga_2+1\text { and }t\ge I\}\vert
+\be\cdot\vert\{t:a_t+1\ge\ga_1+1\text { and }t<I\}\vert\\
&\quad +\be\cdot\vert\{t:c_t\ge\ga_1+1\text { and }t\ge
J+1\}\vert+\be\\
&\hskip2cm+\be\cdot\vert\{t:d_t+1>\ga_2+1\text { and }t<J\}\vert\\
&=\be\cdot\vert\{t:\bar b_t>\ga_2+1\}\vert
+\be\cdot\vert\{t:\bar c_t\ge \ga_1+1\}\vert+\be.\tag5.3.19a
\endalign$$
On the other hand, for $\ga_2=-B-1$, we have to consider the
right-hand side of (5.3.8b). We have 
$$\align \be\cdot\vert\{&t:a_t\ge \ga_1\}\vert
+\be\cdot\vert\{t:c_t\ge B+D+1\}\vert\\
&=\be\cdot\vert\{t:a_t\ge \ga_1\text { and }t\ge I\}\vert
+\be\cdot\vert\{t:a_t\ge \ga_1\text { and }t<I\}\vert\\
&\quad +\be\cdot\vert\{t:c_t\ge B+D+1\text { and }t\ge J+1\}\vert\\
&\hskip2cm+\be\cdot\vert\{t:c_t\ge B+D+1\text { and }t<J+1\}\vert.
\endalign$$
Examining the above considerations for the case $\ga_2\ge-B$, we
discover that the inequality $\ga_1\ge-B$ in fact has never been used.
So also here there hold $\ga_1\le a_I< c_{J+1}$ and $-B<b_I$. Besides
we have
$$\multline \vert\{t: c_t\ge B+D+1\text { and }t<
J+1\}\vert=J-\ch(c_1=B+D)\\
=\vert\{t:d_t+1>-B\text { and }t< J\}\vert+1-\ch(c_1=B+D).
\endmultline$$
Putting everything together, we obtain
$$\align \be\cdot\vert\{&t:a_t\ge\ga_1\}\vert
+\be\cdot\vert\{t:c_t\ge B+D+1\}\vert\\
&=\be\cdot\vert\{t:b_t>-B\text { and }t\ge I\}\vert
+\be\cdot\vert\{t:a_t+1\ge\ga_1+1\text { and }t<I\}\vert\\
&\quad +\be\cdot\vert\{t:c_t\ge\ga_1+1\text { and }t\ge
J+1\}\vert\\
&\hskip1cm+\be\cdot\vert\{t:d_t+1>-B\text { and
}t<J\}\vert+(1-\ch(c_1=B+D))\cdot\be\\
&=\be\cdot\vert\{t:\bar b_t>-B\}\vert
+\be\cdot\vert\{t:\bar c_t\ge
\ga_1+1\}\vert+\ch(c_1>B+D)\cdot\be.\tag5.3.19b
\endalign$$
\bigpagebreak

{\it Third step.} So far we have bijectively mapped intersecting
pairs $(P_1,P_2)$ of paths onto pairs ($(\bar a\mid\bar b)$, $(\bar
c\mid\bar d)$) of arrays of the type (5.3.11). To interpret these arrays 
as paths again, we have to modify them such that both become arrays
consisting of rows with equal length. For $(\bar a\mid\bar b)$ of the
type (5.3.11a) we distinguish between the cases $\bar a_1=B+D-1$ and
$\bar a_1>B+D-1$. In the first case $\bar a_1$ is deleted from the
array $(\bar a\mid\bar b)$, in the second case the element $-B+1$ is
inserted as first element in the second row. This yields a new array
$(\hat a\mid\hat b)$ which comes out of $(\bar a\mid\bar b)$ by
$$(\hat a\mid\hat b)=\cases \hfil\matrix \bar a_2&\hdots&\bar a_{\bar k}\\
\bar b_2&\hdots&\bar b_{\bar k}\endmatrix&\bar a_1=B+D-1\\
\matrix \bar a_1&\bar a_2&\hdots&\bar a_{\bar k}\\
-B+1&\bar b_2&\hdots&\bar b_{\bar k}\endmatrix&\bar a_1>B+D-1\ .\endcases
\tag5.3.20a$$
Similarly, we define a new array $(\hat c\mid\hat d)$ which comes out
of $(\bar c\mid\bar d)$ by
$$(\hat c\mid\hat d)=\cases\hfil \matrix \bar c_2&\hdots&\bar c_{\bar l}\\
\bar d_2&\hdots&\bar d_{\bar l}\endmatrix&\bar d_1=-A\\
\matrix A+D&\bar c_2&\hdots&\bar c_{\bar l}\\
\bar d_1&\bar d_2&\hdots&\bar d_{\bar l}\endmatrix&\bar d_1>-A\ .\endcases
\tag5.3.20b$$
It is clear that (5.3.20) defines a bijection between pairs ($(\bar
a\mid\bar b)$, $(\bar c\mid\bar d)$) of the type (5.3.11) and pairs 
($(\hat a\mid\hat b)$, $(\hat c\mid\hat d)$) of the types
$$\matrix\format\r\quad &\c\quad &\c\quad &\c\quad &\l\\ 
B+D\le&\hat a_1&\dots&\hat a_{\hat k}&\le E_1-1\\
-B+1\le&\hat b_1&\hdots&\hat b_{\hat k}&\le E_2\endmatrix
\hphantom{\ ,}\tag5.3.21a$$
and
$$\matrix\format\r\quad &\c\quad &\c\quad &\c\quad &\l\\ 
 A+D\le&\hat c_1&\hdots&\hat c_{\hat l}&\le F_1-1\\
-A+1\le&\hat d_1&\dots&\hat d_{\hat l}&\le F_2\endmatrix\ ,\tag5.3.21b$$
respectively.
\smallpagebreak

Turning to the weights of the arrays, first observe that in all four
cases of (5.3.20) the following identity holds,
$$\multline \V{\bar a}+\V{\bar b}+\V{\bar c}+\V{\bar d}-(\bar k+\bar
l)D\\
=\V{\hat a}+\V{\hat b}+\V{\hat c}+\V{\hat d}-(\hat k+\hat l)D+B-A-D-1.
\endmultline\tag5.3.22$$
Besides, it is readily seen that (5.3.18a,b,c,e) also hold if $\bar
a,\bar b,\bar c,\bar d$ are replaced by $\hat a,\hat b,\hat c,\hat
d$, respectively. In the exceptional case~C1 (i.e\. $\ga=-B-1$) we
have
$$\align \vert\{t:\hat b_t>-B\}\vert&=\bar k-1+\ch(\bar a_1>B+D-1)\\
&=\vert\{t:\bar b_t>-B\}\vert+\ch( c_1>B+D)\tag5.3.23
\endalign$$
by remembering (5.3.10a). Combining this with (5.3.18d) gives
$$\multline \be\cdot\vert\{t:a_t\ge B+D\}\vert
+\be\cdot\vert\{t:c_t\ge B+D+1\}\vert\\
=\be\cdot\vert\{t:\hat b_t>-B\}\vert
+\be\cdot\vert\{t:\hat c_t\ge B+D+1\}\vert.
\endmultline\tag5.3.24$$
In order to finally prove (5.3.5), we observe that for $\ga_2\ge-B$
the identity (5.3.19a) also holds if $\bar b,\bar c$ are replaced by
$\hat b,\hat c$, respectively. For $\ga_2=-B-1$ however, we may use
(5.3.23) to get from (5.3.19b)
$$\multline \be\cdot\vert\{t:a_t\ge\ga_1\}\vert
+\be\cdot\vert\{t:c_t\ge B+D+1\}\vert\\
\be\cdot\vert\{t:\hat b_t>-B\}\vert
+\be\cdot\vert\{t:\hat c_t\ge \ga_1+1\}\vert.
\endmultline\tag5.3.25$$

{\it Fourth step.} Obviously, pairs ($(\hat a\mid\hat b)$, $(\hat
c\mid\hat d)$) of arrays of the type (5.3.21) uniquely correspond to
pairs $(Q_1,Q_2)$ of paths, $Q_1:\B\to\E$, $Q_2:\A\to\F$ such that
the following weight properties hold:

Case A'. $\ga\ge-A$. Here we have
$$\multline
\ymaj_{\be;\ga+1}(Q_1)+\ymaj_{\be;\ga}(Q_2)
=\V{\hat a}+\V{\hat b}+\be\cdot\vert\{t:\hat b_t>\ga+1\}\vert\\
+\V{\hat c}+\V{\hat d}+\be\cdot\vert\{t:\hat d_t>\ga\}\vert-(\hat k+\hat l)D.
\endmultline\tag5.3.26a$$

Case B'. $-A>\ga\ge -B-1$. Here we have
$$\multline
\ymaj_{\be;\ga+1}(Q_1)+\ymaj_{\be;\ga}(Q_2)
=\V{\hat a}+\V{\hat b}+\be\cdot\vert\{t:\hat b_t>\ga+1\}\vert\\
+\V{\hat c}+\V{\hat d}+\be\cdot\vert\{t:\hat c_t\ge D-\ga\}\vert-(\hat k+\hat l)D
+(-A-\ga)\be.
\endmultline\tag5.3.26b$$

Case C'. $-B-1>\ga$. Here we have
$$\multline
\ymaj_{\be;\ga+1}(Q_1)+\ymaj_{\be;\ga}(Q_2)
=\V{\hat a}+\V{\hat b}+\be\cdot\vert\{t:\hat a_t\ge D-\ga-1\}\vert\\
+\V{\hat c}+\V{\hat d}+\be\cdot\vert\{t:\hat c_t\ge D-\ga\}\vert-(\hat k+\hat l)D
+(-A-\ga)\be+
(-B-\ga-1)\be.
\endmultline\tag5.3.26c$$

What concerns the right-hand side of (5.3.5), we have
$$\multline
\ymaj_{\be;\ga_2+1}(Q_1)+\xmaj_{\be;\ga_1+1}(Q_2)
=\V{\hat a}+\V{\hat b}+\be\cdot\vert\{t:\hat b_t>\ga_2+1\}\vert\\
+\V{\hat c}+\V{\hat d}+\be\cdot\vert\{t:\hat c_t\ge\ga_1+1\}\vert-(\hat k+\hat
l)D,
\endmultline\tag5.3.27$$
provided that $A+D<\ga_1$ and $-B-1\le\ga_2$.

\medpagebreak
Now we are in the position to define $\Ps$. For any intersecting pair
$(P_1,P_2)$ of paths, $P_1:\A\to\E$, $P_2:\B\to\F$, perform the steps
1--4. The image of
$(P_1,P_2)$ under application of $\Ps$ by definition is the resulting
pair $(Q_1,Q_2)$,
$$\Ps\big((P_1,P_2)\big):=(Q_1,Q_2).$$

It has already been shown that $\Ps$ is a bijection. Considering all
cases for $\ga$, a combination of (5.3.7a,b,c), (5.3.17),
(5.3.18a,b,c,e), respectively (5.3.24), (5.3.22), 
(5.3.26a,b,c), together with the
remark that (5.3.18a,b,c,e) also hold if $\bar a,\bar b,\bar c,\bar d$
are replaced by $\hat a,\hat b,\hat c,\hat d$, respectively, by a
little bit of manipulation finally shows, that (5.3.2), and hence
also (5.3.3) and (5.3.4), indeed hold. To establish (5.3.5) we have
to combine (5.3.8a,b), (5.3.17), (5.3.19a), respectively (5.3.25), (5.3.22),
(5.3.27).

Finally we turn to the statement in the Proposition concerning the
last meeting point.
Remember that in the second step $I$ and $J$ have been maximal with
respect to (5.3.9) which had the meaning that $(a_I,d_J)$ is
 the last meeting point between $P_1$ and $P_2$, where $a_I$ and $d_J$
refer to the array representations (5.3.6a,b) of $P_1$ and $P_2$. 
On the other hand, $(\hat a\mid\hat b)$ and $(\hat c\mid\hat d)$,
defined via (5.3.10) and (5.3.20), were the array representations of
$Q_1$ and $Q_2$, respectively. A short look at (5.3.10) and (5.3.20) 
confirms that $Q_1$
and $Q_2$ were constructed just in such a manner that $(a_I, d_J)$ is
the last meeting point of $Q_1$ and $Q_2$, too. Besides, the last
$k-I+1$ elements in the corresponding rows of (5.3.6a) and (5.3.10a)
are identical, as well as the last $l-J$ elements in the
corresponding rows of (5.3.6b) and (5.3.10b). Therefore the tails of
$P_1$ and $Q_1$ and the tails of $P_2$ and $Q_2$ beginning from this
last meeting point are identical.

The proof of the Proposition now is complete.

\medpagebreak
Again, we provide an example. Consider the paths $P_1^{\text{ex}}:\A_{\text{ex}}\to\E_{\text{ex}}$ and
$P_2^{\text{ex}}:\B_{\text{ex}}\to\F_{\text{ex}}$ in
Figure~7, $P_1^{\text{ex}}=((-1,0),1121112122112212)$,
$P_2^{\text{ex}}=((1,-2),122212211\mathbreak 121121121)$, $\A_{\text{ex}}=(-1,0)$, $\E_{\text{ex}}=(8,7)$,
$\B_{\text{ex}}=(1,-2)$, $\F_{\text{ex}}=(11,6)$. The array representations of $(P_1^{\text{ex}},
P_2^{\text{ex}})$ which are formed in the first step are
$$\(\matrix -1\le&1\ 4\ 5\ 7&\le7\\
\hphantom{-}1\le&1\ 2\ 4\ 6&\le7\endmatrix\ ,\ 
\matrix \hphantom{-}1\le&2\ 3\ 6\ 8\ 10&\le10\\
-1\le&1\ 3\ 4\ 5\ \hphantom{1}6&\le\hphantom{1}6\endmatrix\).$$
The integers $I,J$ which are maximal with respect to (5.3.9) are
given by $I=4$ and $J=3$. They correspond to the last meeting point
$\S_{\text {ex}}=(a^{\text {ex}}_4,d^{\text {ex}}_3)=(7,4)$ of
$P_1^{\text{ex}}$ and $P_2^{\text{ex}}$. Hence, by (5.3.10) this pair of arrays is
mapped in the second step to the pair
$$\(\matrix 0\le&1\ 2\ 5\ 7&\le7\\
0\le&\hphantom{1}\ 2\ 4\ 6&\le7\endmatrix\ ,\ 
\matrix 0\le&\hphantom{0}\ 2\ 5\ 6\ 8\ 10&\le10\\
0\le&0\ 1\ 3\ 4\ 5\ \hphantom{1}6&\le\hphantom{1}6\endmatrix\).$$
Next (5.3.20) is applied to obtain from this pair the pair of arrays
$$\(\matrix \hphantom{-}1\le&\hphantom{-}1\ 2\ 5\ 7&\le7\\
-1\le&-1\ 2\ 4\ 6&\le7\endmatrix\ ,\ 
\matrix -1\le&2\ 5\ 6\ 8\ 10&\le10\\
\hphantom{-}1\le&1\ 3\ 4\ 5\ \hphantom{1}6&\le\hphantom{1}6\endmatrix\).$$
These two arrays are the array representations for the paths $Q_1^{\text{ex}}$
and $Q_2^{\text{ex}}$ in Figure~7. $Q_1^{\text{ex}}$ and $Q_2^{\text{ex}}$ also meet in $\S_{\text
{ex}}=(7,4)$ for the last time, and the path portions
after this last meeting point are identical with the corresponding
portions of $P_1^{\text{ex}}$ and $P_2^{\text{ex}}$.

\vskip10pt 
\vbox{\noindent
$$\Einheit0.3cm
\Koordinatenachsen(12,8)(-2,-3)
\Gitter(12,8)(-2,-3)
\raise-1pt\hbox{\Pfad(1,-2),122212211121121121\endPfad
\DickPunkt(1,-2)
\DickPunkt(11,6)}
\raise1pt\hbox{\Pfad(-1,0),1121112122112212\endPfad
\DickPunkt(-1,0)
\DickPunkt(8,7)}
\DickPunkt(7,4)
\Label\lu{\A_{\text{ex}}\hskip14pt}(-1,0)
\Label\u{\raise-16pt\hbox{$\B_{\text{ex}}$}}(1,-2)
\Label\ro{\hskip12pt\E_{\text{ex}}}(8,7)
\Label\r{\hskip12pt\F_{\text{ex}}}(11,6)
\Label\l{P_1^{\text{ex}}}(6,5)
\Label\lo{P_1^{\text{ex}}\hskip7pt}(1,1)
\Label\ru{\hskip7pt P_2^{\text{ex}}}(10,5)
\Label\ro{\hskip10pt P_2^{\text{ex}}}(2,-2)
\Label\ru{\raise-16pt\hbox{$\S_{\text {ex}}$}}(7,4)
\hskip4cm
\longleftrightarrow\hbox to1.5cm{\hss}
\Koordinatenachsen(12,8)(-2,-3)
\Gitter(12,8)(-2,-3)
\hbox to-1pt{\hss}\raise1pt\hbox{\Pfad(1,-2),2122211122112212\endPfad
\DickPunkt(1,-2)
\DickPunkt(8,7)}
\hbox to2pt{\hss}\raise-1pt\hbox{\Pfad(-1,0),111211122121121121\endPfad
\DickPunkt(-1,0)
\DickPunkt(11,6)}\hbox to-1pt{\hss}
\DickPunkt(7,4)
\Label\lu{\A_{\text{ex}}\hskip14pt}(-1,0)
\Label\u{\raise-16pt\hbox{$\B_{\text{ex}}$}}(1,-2)
\Label\ro{\hskip12pt\E_{\text{ex}}}(8,7)
\Label\r{\hskip12pt\F_{\text{ex}}}(11,6)
\Label\ru{\hskip7pt Q_1^{\text{ex}}}(2,-1)
\Label\lo{Q_1^{\text{ex}}\hskip7pt}(7,6)
\Label\ro{\raise5pt\hbox{$Q_2^{\text{ex}}$}}(0,0)
\Label\ru{\hskip12pt Q_2^{\text{ex}}}(10,5)
\Label\ru{\raise-16pt\hbox{$\S_{\text {ex}}$}}(7,4)
\hskip4cm
$$
\nobreak
\centerline{\eightpoint Figure 7}
}
\vskip10pt
 To illustrate (5.3.2), first choose $\ga=0$.
By (4.0.1) we have
$\ymaj_{\be;1}(P_1^{\text{ex}})+\mathbreak
\ymaj_{\be;0}(P_2^{\text{ex}})=34+3\be+53+5\be=87+8\be$ and
$\ymaj_{\be;1}(Q_1^{\text{ex}})+\ymaj_{\be;0}(Q_2^{\text{ex}})=30+3\be+55+5\be=85+8\be$ in accordance
with (5.3.2). For $\ga=-2$ by (4.0.1)--(4.0.3) we have 
$\ymaj_{\be;-1}(P_1^{\text{ex}})+\ymaj_{\be;-2}(P_2^{\text{ex}})=
34+4\be+\be+53+5\be=87+10\be$ and
$\ymaj_{\be;-1}(Q_1^{\text{ex}})+\ymaj_{\be;-2}(Q_2^{\text{ex}})=
30+3\be+55+5\be+2\be=85+10\be$ 
again in accordance with (5.3.2). It is left to the reader to try other cases.
\quad \quad \qed
\enddemo

\remark{Remark} We promised to try to give an explanation why
nothing reasonable can be expected unless the starting points $\A$
and $\B$ of the paths $P_1$ and $P_2$
 lie on a line parallel to $x+y=0$. Remember that the aim has
been to find some correspondence between intersecting pairs $(P_1,P_2)$ of paths
$P_1:\A\to\E$, $P_2:\B\to\F$, and arbitrary pairs $(Q_1,Q_2)$ of paths
$Q_1:\B\to\E$, $Q_2:\A\to\F$, such that the tails of $P_1$ and $Q_1$,
and the tails of $P_2$ and $Q_2$ after the last
meeting point between $P_1$ and $P_2$, which in addition is the same
for $Q_1$ and $Q_2$, are identical. We are basically counting by the major
index. Consider any North-East corner in $P_1$, say, which comes
after this last meeting point. This corner contributes the number of
steps from $\A$ to this corner to the major index or strange major
index. If the desired correspondence would obey the above
described property, then this North-East corner would be also a North-East
corner for $Q_1$. But if $\B$, the starting point of $Q_1$, did not
lie on the same line parallel to $x+y=0$ as $\A$ does, then the
number of steps from the starting point of $Q_1$ to this corner would
be completely different. Of course the same is true with North-East
corners of $P_2$ and $Q_2$. Since the number of North-East corners
which occur after this last meeting point is not predictable, the
difference which would be caused if $\A$ and $\B$ would not lie on a
line parallel to $x+y=0$ could not be handled properly.


