\input amstex

\input epsf.tex
\documentstyle{amsppt}
\NoBlackBoxes

%First page headline in AmS-TeX for S\'eminaire Lotharingien de Combinatoire
\catcode`\@=11
\def\output@{\shipout\vbox{%
 \iffirstpage@ \global\firstpage@false
%insert headline:
\headline={\frheadline}
\makeheadline
  \pagebody \makefootline%
 \else \ifrunheads@ \makeheadline \pagebody
       \else \pagebody \makefootline \fi
 \fi}%
 \advancepageno \ifnum\outputpenalty>-\@MM\else\dosupereject\fi}
\catcode`\@=13
\font\rms=cmr8 
\font\its=cmti8 
\font\bfs=cmbx8
\def\frheadline{\its S\'eminaire Lotharingien de
Combinatoire \bfs 46 \rms (2001), Article~B46f\hfill} 

\define\wh{\widehat}
\define\bu{\bullet}
\define\emp{\emptyset}
\define\sq{\square}
\define\st{\star}
\define\bd{\blacktriangledown}
\define\ap{\approx}
\define\aA{\Bbb A}
\define\zz{\Bbb Z}
\define\nn{\Bbb N}
\define\cc{\Bbb C}
\define\rr{\Bbb R}
\define\qqq{\Bbb Q}
\define\tT{\Bbb T}
\define\ee{\Bbb E}
\define\sS{\Bbb S}
\define\oo{\Bbb O}
\define\ooo{\overline \oo}
\define\gG{\Bbb G}
\define\sm{\setminus}
\define\pr{\prime}
\define\Ga{\Gamma}
\define\Om{\Omega}
\define\De{\Delta}
\define\Si{\Sigma}
\define\la{\lambda}
\define\ga{\gamma}
\define\si{\sigma}
\define\de{\delta}
\define\ep{\epsilon}
\define\al{\alpha}
\define\be{\beta}
\define\om{\omega}
\define\k{\kappa}
\define\ka{\kappa}
\define\ve{\varepsilon}
\define\vr{\varrho}
\define\vp{\varphi}
\define\vt{\vartheta}
\define\vk{\varkappa}
\define\CR{\Cal R}
\define\GG{\goth G}
\define\GI{\goth I}
\define\CS{\Cal S}
\define\ca{\Cal A}
\define\CB{\Cal B}
\define\T{\bold T}
\define\CT{\Cal T}
\define\BB{\bold B}
\define\bP{\bold P}
\define\ssu{\subset}
\define\sss{\supset}
\define\wt{\widetilde}
\define\<{\langle}
\define\>{\rangle}
\define\La{\Lambda}
\define\const{\text{{\rm const}}}
\define\sc{ {\text {\rm sc}  } }
\define\rc{ {\text {\rm rc}  } }
\define\y{ {\text {\rm y}  } }
\define\sy{ {\text {\rm sy}  } }
\define\Z{ {\text {\rm Z} } }
\define\rk{ {\text {\rm rk}  } }
\define\prev{\prec}
\define\oa{\overrightarrow}
\define\Ups{\Upsilon}
\define\syt{ {\text {\rm SYT}}}
\define\rpp{ {\text {\rm RPP}}}
\define\vo{ {\text {\rm vol}}}
\define\h{ {\text {\rm h}  } }
\define\pP{ {\text {\rm P}}}
\define\qQ{ {\text {\rm Q}}}
\define\rR{ {\text {\rm R}}}
\define\xx{{\bold r}}
\define\yy{{\bold y}}
\define\ds{\al}
\define\rs{\be}
\define\sa{\rightsquigarrow}

\topmatter

\title
Hook length formula and geometric combinatorics
\endtitle

\leftheadtext{Igor~Pak}
\rightheadtext{Hook Length Formula}
\author {Igor~Pak\medskip
{\rm Department of Mathematics\\
Massachusetts Institute of Technology\\
Cambridge, MA 02139 USA \\
E-mail: pak\@math.mit.edu}}
\endauthor
%\date March 15, 2000 \enddate


\keywords Hook length formula, RSK, convex polytope,
Ehrhart polynomial
\endkeywords

\abstract
We present here a transparent proof of the hook length
formula. The formula is reduced to an equality between the number of
integer point in certain polytopes. The latter is established by
an explicit continuous volume-preserving piecewise linear map.
\endabstract

\endtopmatter


\document

\specialhead Introduction \endspecialhead

\medskip

About one hundred years ago, Alfred Young realized that
the dimension of the irreducible representation of the
symmetric group is given by the number of what
we now call standard Young tableaux. About fifty years ago,
Frame, Robinson and Thrall discovered a remarkable and
somewhat mysterious hook length formula for this dimension. Ever since,
a quest for a simple combinatorial proof has been under way.
Although several beautiful proofs have been found, it is our
personal view that the real meaning of the formula is yet to
be understood. Thus the current paper as another meager attempt.

Roughly, our proof consists of three steps, which can be outlined
as follows. In the first step
we reduce the hook length formula to Stanley's hook content formula
for the number of reverse plane partitions. Since we do not need
the full power of Stanley's theorem, we use a simple geometric
argument to prove the claim. Then we extend the result, by
switching from the cone of reverse plane partitions to certain
finite polytopes. Finally, we prove that the integer volumes of
these polytopes are identical by using an explicit continuous
volume-preserving map between them.
We enclose three ``bonus'' sections which describe
special properties of the map defined above. We conclude with
brief remarks and pointers to the literature, which are completely
absent in the main body of the paper.

The goal of this paper is not to invent a completely new
approach or a new bijection, but rather to create a simple
and transparent proof with virtually no technical
details. In the process, we utilize some well known ideas and
simplify the existing bijections. After certain reservations about
the merit of such an exercise, we decided that it has both
scientific and educational value. We defer the final judgement
to the reader.

A few words about notation. Throughout the paper we use
$[\la]$ to denote the set of squares of a Young diagram $\la$
(see below). We write \,
$[n]=\{1,2,\dots,n\}$, $\zz_+ = \{0,1,2,\dots\}$. Furthermore, we write
\, $f \sim g$ \, for functions $f,g : \rr_+ \to \rr_+$,
when \, $f(z)/g(z)~\to~1$ \, as~$z \to \infty$. Also, for any
array $\bold d = (d_1,\dots,d_k)$, we write $|d|=d_1+\dots+d_k$.
We will abbreviate the hook length formula as HLF, the hook content
formula as HCF, etc. A small warning: the proof of
Lemma~1 should not be skipped even if the result is well known
to the reader. The proof contains definitions and notation we use
thereafter.

\bigskip

\vskip 10pt

\head 1. The hook length formula \endhead

\medskip

Let \, $\la = (\la_1,\la_2,\dots,\la_\ell)$ \, be a {\it partition} \, of
$n$ (denotes $\la \vdash n$), if $\la_1 \ge \la_2 \ge \dots \ge
\la_\ell$, $|\la| = \sum_i \la_i = n$. From now on, let \, $\ell$ \,
denotes the number of parts;
let \, $m = \la_1$ \, denote the length of the largest part.
Define the \, {\it conjugate partition} \,
$\la^\pr = (\la_1^\pr,\dots,\la_m^\pr)$ \, by
$\la_j^\pr = |\{i : \la_i \ge j\}|$.

A {\it Young diagram} \, $[\la]$ \, corresponding to $\la$,
is a collection of squares $(i,j) \in \zz^2$, such that $1 \le j \le \la_i$.
Define the {\it hook length} \,
$\h(\xx) = \la_i +\la_j^\pr - i - j +1$,
where \, $\xx = (i,j) \in [\la]$.

We say that \, $(i_1,j_1) \prec (i_2,j_2)$ \, if \, $i_1 \le i_2$,
$j_1 \le j_2$.
A {\it standard Young tableau} \, $A$ \, of shape $\la$ is a bijective map
$f: [\la] \to [n] = \{1,\dots,n\}$, such that $f(i_1,j_1) < f(i_2,j_2)$
for all $(i_1,j_1) \prec (i_2,j_2)$. We denote the set of
standard Young tableaux of shape~$\la$  by~$\syt(\la)$.

\bigskip


\midinsert
%\vskip 10pt
\line{\hfill\epsfysize=3.3cm\epsfbox{fig1.eps}\hfill}
%\vskip 10pt
\botcaption{Figure 1} \, Young diagram $[\la]$, where $\la = (6,6,5,3,2)$.
A hook at $\xx=(2,3)$, $\h(\xx)=6$. A standard Young tableau of
shape $(3,2,2)$.
\endcaption
\endinsert

\bigskip

{\bf Theorem 1. (Hook Length Formula) :} \
$$\bigl|\syt(\la)\bigr| = \frac{n!}{\prod_{\xx \in [\la]} \h(\xx)}\,.$$


\bigskip
\vskip 10pt

\head 2. Reverse plane partitions \endhead

\medskip

A {\it reverse plane partition} \, $A$ of shape $\la$ is a function
$f: [\la] \to \zz_+ = \{0,1,2,\dots\}$, such that
$f(i_1,j_1) \le f(i_2,j_2)$
for all $(i_1,j_1) \prec (i_2,j_2)$. We denote the set of reverse plane
partitions of shape $\la$ by \, $\rpp(\la)$. Let
\, $|A| = \sum_{\xx \in [\la]} f(\xx)$ \, denote the {\it size} \,
of $A$. One can think of $A$ as of a two-dimensional array
$(x_{i,j})$ of shape $[\la]$.

\bigskip


\midinsert
%\vskip 10pt
\line{\hfill\epsfysize=2.5cm\epsfbox{fig2.eps}\hfill}
%\vskip 10pt
\botcaption{Figure 2} \, A reverse plane partition $A$ of shape $\la =
(4,3,2)$; $|A| = 37$.
\endcaption
\endinsert

\bigskip

{\bf Theorem 2. (Hook Content Formula) :} \
$$\sum_{A \in \rpp(\la)} \, t^{|A|} \,  = \, \prod_{\xx \in [\la]}
\frac{1}{\, 1- t^{\,\h(\xx)}  } \, .$$

\bigskip

{\bf Lemma 1.} \, {\it The Hook Content Formula implies
the Hook Length Formula. }

\bigskip

{\it Proof.} \ Let $V \simeq \rr^n$ be the vector space of
all real functions $f: [\la]\to \rr$, and let $f(i,j) = x_{i,j}$.
Consider the cone $C(\la) \ssu V$ of all real functions
$f : [\la] \to \rr_+$, such that $f(i_1,j_1) \le f(i_1,j_2)$
for all $(i_1,j_1) \prec (i_2,j_2)$. In other words, $C(\la)$
is defined by the inequalities $x_{i,j} \ge 0$,
$x_{i_1,j_1} \le x_{i_2,j_2}$, for all $i_1 \le i_2$,
$j_1 \le j_2$. Let $\vp: C(\la) \to \rr_+$ be a linear
function $\vp = \sum_{(i,j) \in [\la]} \, x_{i,j}$.

Similarly, let $W \simeq \rr^n$ be the set of functions
$g: [\la] \to \rr$, $g(i,j) = y_{i,j}$,
and let $D(\la) = \rr_+^n$ be the cone of nonnegative functions:
$y_{i,j} \ge 0$. Denote by $\psi: D(\la) \to \rr_+$ the linear
function $\psi = \sum_{\xx \in [\la]} \, \h(\xx) \, y_{\xx}$.

Now we can restate the HCF as follows:
$$e\bigl(C(\la) \cap \{\vp = N\}\bigr) =
e\bigl(D(\la) \cap \{\psi = N\}\bigr), \ \ \text{for all} \ N \, \in
\zz_+,$$
where $e(P)$ denotes the number of integer points in the
polytope $P$. Let us rewrite this as follows:
$$e\bigl(C(\la) \cap \{\vp \le N\}\bigr) =
e\bigl(D(\la) \cap \{\psi \le N\}\bigr), \ \ \text{for all} \ \, N \in
\zz_+.$$
This implies that
$$(\star) \qquad
\vo\bigl(C(\la) \cap \{\vp \le z\}\bigr) \sim
\vo\bigl(D(\la) \cap \{\psi \le z\}\bigr), \ \ \text{as} \ \, z \to \infty.$$
Now, for every bijection \, $\si: [\la] \to [n]$ \, we can define the cone
$C(\si) \ssu V$ to be the cone of functions $f: [\la] \to \rr_+$ such that
\, $f(\si^{-1}(i)) \le f(\si^{-1}(j))$ \, for all $i < j$. Clearly,
$$\aligned
& C(\la) = \cup_{\si \in \syt(\la)} \, C(\si), \quad
\cup_{\si} \, C(\si) = \rr_+^n \ssu V, \\
& \vo\bigl(C(\si) \cap \{\vp \le z\}\bigr)  =
 \vo\bigl(C(\si^\pr) \cap \{\vp \le z\}\bigr), \\
& \vo\bigl(C(\si)\cap C(\si^\pr) \cap \{\vp \le z\} \bigr) = 0,
 \ \text{for every} \, \si \ne \si^\pr.
 \endaligned $$
 Therefore
$$\aligned
& \vo\bigl(C(\la) \cap \{\vp \le z\}\bigr) =
\sum_{\si \in \syt(\la)} \, \vo\bigl(C(\si) \cap
\{\vp \le z\}\bigr) \\
& \ \ = \frac{|\syt(\la)|}{n!} \, \vo\bigl(D(\la) \cap \{\vp \le z\}\bigr) =
\frac{|\syt(\la)|}{n!} \ z^n \, \vo\bigl(D(\la) \cap \{\vp \le 1\}\bigr).
\endaligned$$
On the other hand, the change of coordinates \, $y^\pr_{i,j} =
\frac{\h(i,j)}{z} \, y_{i,j}$ \, gives:
$$\vo\bigl(D(\la) \cap \{\psi \le z\}\bigr) = \left(\prod_{\xx \in [\la]} \,
\frac{z}{\h(\xx)}\right) \, \vo\bigl(D(\la) \cap \{\vp \le 1\}\bigr). $$
We conclude
$$\vo\bigl(C(\la) \cap \{\vp \le z\}\bigr) =
\frac{n!}{|\syt(\la)| \, \prod_{\xx \in [\la]} \h(\xx)} \
\vo\bigl(D(\la) \cap \{\psi \le z\}\bigr).$$
Substituting this into \, $(\star)$ \, and
letting \, $z \to \infty$, implies the result. \ $\sq$

\bigskip

\vskip 10pt

\head 3. Two polytopes \endhead

\medskip


Denote by $\xx_c = (i_c,j_c)$ \, the maximal element in $[\la]$
along diagonal \, $i-j = c$ :
$$\xx_c = \max_\prec \ \{(i,j) \in [\la] : \, i-j = c\} . $$
Now, let $\ds_c$, $1-m \le c \le \ell -1$, be the {\it diagonal sums} :
$$\ds_c \, = \sum_{(i,j) \in [\la]: \ i-j =c} \, x_{i,j} .$$
We think of $\ds_c$ as of linear functions on $V$.
Clearly,  $\sum_c \, \ds_c = \, \vp$.

Similarly, consider {\it rectangular sums} : \,
$$\rs_c \, = \sum_{\xx=(i,j) \prec \xx_c} \, y_{i,j}.$$
Again, we think of $\rs_c$ as of linear functions on $W$.
Later we prove that \,
$\sum_{c} \, \rs_c = \psi$.

\medskip


\midinsert
%\vskip 10pt
\line{\hfill\epsfysize=3.cm\epsfbox{fig3.eps}\hfill}
%\vskip 10pt
\botcaption{Figure 3} \, The area of the diagonal
sum $\al_{-2}$ and the rectangular
sum $\be_{-2}$. The~corner square $\xx_{2}=(4,2)$.
\endcaption
\endinsert

\medskip

Now, for every integer array \,
$\bold d =(d_{1-m},\dots,d_{\ell-1})$,
consider the two polytopes:
$$\aligned
\pP_\la(\bold d) \, &= \, C(\la) \cap \{\ds_{1-m} = d_{1-m},\dots,
\ds_0 = d_0, \dots, \ds_{\ell-1} = d_{\ell-1}\} \ssu V, \\
\qQ_\la(\bold d) \, &= \, D(\la) \cap \{\rs_{1-m} = d_{1-m},\dots,
\rs_0 = d_0, \dots, \rs_{\ell-1} = d_{\ell-1}\} \ssu W.
\endaligned$$

\bigskip

{\bf Theorem 3. (Two Polytopes Theorem)} \ {\it

%\noindent
For any integer array
$\bold d =(d_{1-m},\dots,d_{\ell-1})$, we have
 \, $e\bigl(\pP_\la(\bold d)\bigr) \, = \,
e\bigl(\qQ_\la(\bold d)\bigr)$. }

\bigskip

{\bf Lemma 2. } \ {\it  The Two Polytopes Theorem  implies the
Hook Content Formula.}

\medskip

{\it Proof.} \ Consider the linear function \,
$\vr = \sum_{c=1-m}^{\ell-1} \, \rs_c$.
Let us first prove that \,
$\vr = \psi$.
Indeed,
$$
\vr = \sum_{c=1-m}^{\ell-1} \, \rs_c =
\sum_{c=1-m}^{\ell-1} \, \sum_{(i,j) \prec \xx_c} \, y_{i,j} =
 \sum_{(i,j) \in [\la]} \, \sum_{c=i-\la_i}^{j-\la_j} \, y_{i,j}
 = \sum_{(i,j) \in [\la]} \, \h(i,j) \, y_{i,j} = \psi.
$$
Therefore, Theorem~3 implies that
$$\aligned
& e\bigl(C(\la) \cap \{\vp =z\}\bigr)  =
\sum_{\bold d : \ \vp = z} \, e\bigl(\pP_\la(\bold d)\bigr) =
\sum_{\bold d : \ \vr = z} \,
e\bigl(\qQ_\la(\bold d)\bigr) \\
& \qquad \ \ =  \sum_{\bold d :
 \ \psi = z} \, e\bigl(\qQ_\la(\bold d)\bigr) =
e\bigl(D(\la) \cap \{\psi =z\}\bigr).
\endaligned
$$
From the proof of Lemma~1, this implies HCF. \ $\sq$


\bigskip

{\it Proof of the HLF.} \ From above, Theorem~3 and Lemma~2
imply the HCF. Now the HLF follows from
the HCF by Lemma~1. \ $\sq$


\bigskip

{\bf Corollary 1.} \ {\it For all $\la$, $\bold d$, the
polytopes $\pP_\la(\bold d)$ and $\qQ_\la(\bold d)$ have the same
Ehrhart polynomial. }

\bigskip

{\it Proof.} \ For any polytope $P$, let \,
$N \cdot P = \{N\,x : x \in P\}$.
The Ehrhart polynomial is defined as
\, $E(P,t) = e(t \cdot P)$. We use $N \cdot \bold a$ to denote
$(N a_1, N a_2, \dots )$.


By definition of polytopes $\pP_\la$ and $\qQ_\la$, we have:
$$\aligned
& E\bigl(\pP_\la(\bold d),N\bigr) = e\bigl(N \cdot \pP_\la(\bold d)\bigr) =
e\bigl(\pP_\la(N \cdot \bold d)\bigr) \\ &  \ \ \ =
e\bigl(\qQ_\la(N \cdot \bold d)\bigr) = e\bigl(N \cdot \qQ_\la(\bold d)\bigr)
= E\bigl(\qQ_\la(\bold d),N\bigr),
\endaligned$$
for every $N\ge 1$.
This implies the result. \ $\sq$


\bigskip

\vskip 10pt

\head 4. Proof of the Two Polytopes Theorem \endhead

\medskip

In this section we prove TPT by induction on $n = |\la|$.
When $n=1$, we have $\la=(1)$, $\pP_\la=\qQ_\la$, and the result
is trivial. We define an identity map \, $\xi_\la : \pP_\la \to \qQ_\la$ \,
in this case.

Now, let \, $\xx_c$ \, be the maximal element
on diagonal \, $i-j=c$ in $\la$.
We say that $\xx_c=(i_c,j_c)$ is a {\it corner} \, in $[\la]$, if
\, $\xx_{c-1}, \xx_{c+1} \prec \xx_c$. We have \,
$\xx_{c-1} = (i_c-1,j_c)$, $\xx_{c+1} = (i_c,j_c-1)$ \, in this case.
Observe that if \, $\xx_c$ \, is a corner in $[\la]$, then
$[\mu]=[\la]-\xx_c$ is a Young diagram of a partition
\, $\mu = (\la_1, \dots,\la_{i_c-1},\la_{i_c}-1,\la_{i_c+1},\dots)
\vdash n-1$.
The step of induction we present below is a reduction of TPT from \,
$[\la]$ \, to \, $[\mu] = [\la] - \xx_c$.


Let $\bold d =(d_{1-m},\dots,d_{\ell-1})$ be as above.
We shall construct an explicit map \,
$\xi_\la : \pP_{\la}(\bold d) \to \qQ_{\la}(\bold d)$,
which gives a bijection between integer points in
$\pP_\la(\bold d)$ and in $\qQ_\la(\bold d)$. Indeed, let
$A=(x_{i,j}) \in \pP_\la(\bold d)$. Define
$$x_{i,j}^\pr \, = \, \left\{
\aligned
& x_{i,j}, \ \text{if} \  \, i-j \ne c \\
& x_{i,j} - \max \bigl\{x_{i-1,j} \, , \, x_{i,j-1}\bigr\},
\ \text{if} \ (i,j) = (i_c,j_c) \\
& \max \bigl\{x_{i-1,j} \, , \, x_{i,j-1}\bigr\} +
\min \bigl\{x_{i+1,j} \, , \,  x_{i,j+1}\bigr\} - x_{i,j}, \\
& \qquad \qquad \qquad \qquad \quad \ \
 \text{if} \ \, i-j = c, (i,j) \ne (i_c,j_c).
\endaligned \right.
$$
Here we use the convention $x_{i,0} = x_{0,j}=0$. Let $A^\pr =
(x^\pr_{i,j})$, $\zeta = \zeta_{\la,c}: (x_{i,j}) \to (x^\pr_{i,j})$.

Notice that
by construction, $\zeta$ \, is a continuous piecewise linear map,
with the inverse \, $\zeta^{-1}: (x^\pr_{i,j}) \to (x_{i,j})$ \, given by
$$x_{i,j} \, = \, \left\{
\aligned
& x_{i,j}^\pr, \ \text{if} \  \, i-j \ne c \\
& x_{i,j}^\pr + \max \bigl\{x_{i-1,j}^\pr \, , \, x_{i,j-1}^\pr\bigr\},
\ \text{if} \ (i,j) = (i_c,j_c) \\
& \max \bigl\{x_{i-1,j}^\pr \, , \, x^\pr_{i,j-1}\bigr\} +
\min \bigl\{x_{i+1,j}^\pr \, , \,  x_{i,j+1}^\pr\bigr\} - x^\pr_{i,j}, \\
& \qquad \qquad \qquad \qquad \quad \ \
 \text{if} \ \, i-j = c, (i,j) \ne (i_c,j_c).
\endaligned \right.
$$

\noindent

Now let \, $\xi_\la: A \to B$, where \,
$B=(y_{i,j}) \in  \qQ_{\la}(\bold d)$ \, is defined as follows:
$$\bigl(y_{i,j}\bigr)_{\{(i,j) \in [\mu]\}} =
\, \xi_\mu\bigl(x^\pr_{i,j}\bigr)_{\{(i,j) \in [\mu]\}}, \ \ \text{and}
\ \ y_{i_c,j_c} = \, x^\pr_{i_c,j_c}. $$
One can think of \, $\xi_\la$ as of a composition \,
$\xi_\la = \xi_\mu \circ \zeta :
A \rightarrow^\zeta\, A^\pr  \rightarrow^{\xi_\mu} \, B$.


Note that one can define $\xi_\la$ as a map \,
$\xi_\la: V \to W$, with an obvious
inverse \, $\xi_\la^{-1} = \zeta^{-1} \circ \xi_\mu^{-1}$.
Now the inductive assumption implies that $\xi_\la$ is
one-to-one.

We need to show that \,
$\xi_\la: \pP_{\la}(\bold d) \to \qQ_{\la}(\bold d)$ \, is a bijection.
First, observe that \, $\xi_\la(A) \in D(\la) \ssu W$ \, for
all \, $A \in C(\la)$. Similarly, $\xi^{-1}(B) \in C(\la)\ssu V$ \, for
all \, $B \in D(\la)$. We use here the inductive assumption and construction
of $\zeta$. Now it remains to show that
$\al_r(A) = \be_r(B)$ for all $B = \xi_\la(A)$, $1-m \le r \le \ell -1$.
Note that we will prove this for all $A \in V$, $B \in W$, $B =
\xi_\la(A)$.

Clearly, $\al_r(A) = \al_r(A^\pr) = \be_r(B)$ for all $r \ne c$.
Indeed, $x_{i,j} = x^\pr_{i,j}$ by construction, and $x^\pr_{i,j} = y_{i,j}$
by induction, for all $i-j=r \ne c$. Checking that \,
$\al_c(A) = \be_c(B)$ \, is a simple but delicate computation.
First, observe that
$$\aligned
\al_c(A^\pr - \xx_c) - x^\pr_{i_c,j_c} & =  \sum_{i-j=c, i < i_c} \,
 \max \bigl\{x_{i-1,j} \, , \, x_{i,j-1}\bigr\} +
\min \bigl\{x_{i+1,j} \, , \,  x_{i,j+1}\bigr\}  - x_{i,j}
\\
& \qquad   + \, \max \bigl\{x_{i_c-1,j_c} \, , \, x_{i_c,j_c-1}\bigr\}
\, - \, x_{i_c,j_c}  \\
& = \sum_{i-j=c-1} x_{i,j} \ + \sum_{i-j=c+1} x_{i,j} \ - \sum_{i-j=c} x_{i,j} \\
& = \, \al_{c-1}(A) \, + \,  \al_{c+1}(A) \, - \, \al_c(A),
\endaligned$$
where the first equality follows by definition of $\zeta$, the
second equality is obtained by collection of terms, and \,
$(A^\pr-\xx_c)$ \, stands for restriction of~$A$ to~$[\mu]$.
Therefore we obtain:
$$\aligned
\be_c(B) & = \be_{c-1}(B) + \be_{c+1}(B) + \, y_{i_c,j_c} - \, \be_c(B-\xx_c)\\
& = \al_{c-1}(A) + \al_{c+1}(A) - \left( \al_c(A^\pr - \xx_c ) -
 x^\pr_{i_c,j_c}\right) \, = \, \al_c(A).
\endaligned$$
This completes the proof. \ $\sq$

\bigskip

\vskip 10pt

\head 5. A General Bijection \endhead

\medskip

The inductive proof of TPT given in Section~4 can be extended
to a piecewise linear map \,
$\xi_\la : \pP_\la(\bold d) \to \qQ_\la(\bold d)$, which preserves the
volume and maps integer points to integer points. However,
it is unclear from the construction that this bijection is independent
of the choice of corners $\xx_c$ in the proof.

\bigskip


\midinsert
%\vskip 10pt
\line{\hfill\epsfysize=7.cm\epsfbox{fig5.eps}\hfill}
%\vskip 10pt
\botcaption{Figure 4} \, A bijection $\xi_{(3,3,3)} =
\zeta_0 \circ \zeta_1 \circ \zeta_{-1} \circ \dots \circ \zeta_0$.
\endcaption
\endinsert

\bigskip

{\bf Theorem 4.} \ {\it The bijection $\xi_\la$ defined
as above does not depend on the choice of corners $\xx_c$ in the
construction. }


\bigskip

{\it Proof.} \ By induction, we can write $\xi_\la$ as follows:
$$(\ast) \ \ \ \xi_\la = \zeta_{\la,c} \, \circ \, \zeta_{(\la-\xx_c),c^\pr}
\, \circ \, \zeta_{(\la-\xx_c-\xx_{c^\pr}),c^{\pr\pr}} \, \circ \ \dots $$
From now on we drop \, $\la$ \, in \, $\zeta_{\la,c}$ \, if it is clear
what partition is meant.

Clearly, \, $\zeta_{c}$ \, commutes with \, $\zeta_{c^\pr}$,
for all \, $|c-c^\pr | \ge 2$. In other words, if \, $\xx=\xx_c$ \, and \,
$\xx^\pr = \xx_{c^\pr}$ \, are corners of \, $[\la]$;
$[\mu]=[\la]-\xx$, $[\mu^\pr]=[\la]-\xx^\pr$, then
$$\zeta_{\mu,c^\pr} \circ \zeta_{\la,c} =
\zeta_{\mu^\pr,c} \circ \zeta_{\la,c^\pr}.$$
Thus it suffices to prove that every
two products as in $(\ast)$ can be obtain from each other by use
of these commutations.

Note that the sequence of squares \,
$\xx_{c}$, $\xx_{c^{\pr}}$, $\xx_{c^{\pr\pr}}$, \dots, defines a
standard Young tableau $A$ of shape $\la$. Consider a graph
$\Ga(\la)$ with vertices being standard Young tableaux of shape $\la$
(incidentally, there are $n!/\prod_\xx \h(\xx)$ of them by the HLF), and edges
$(A,A^\pr)$, whenever $A^\pr$ is obtained from $A$ by exchange
of values $i$ and $i+1$.

\medskip


{\bf Lemma 3.} {\it The graph \, $\Ga(\la)$ \, is connected.}

\medskip

Note that the edges of $\Ga(\la)$ correspond to the
commutations as above. Indeed, by definition of a Young tableau,
the values $i$ and $i+1$ cannot be in the same or adjacent
diagonals. Thus the Lemma implies that
any two products as in $(\ast)$ can be obtained by a sequence of
commutations and thus give the same result. \ $\sq$

\bigskip


\midinsert
%\vskip 10pt
\line{\hfill\epsfysize=3.5cm\epsfbox{fig4.eps}\hfill}
%\vskip 10pt
\botcaption{Figure 5} \, Oriented graph $\Ga(3,2)$.
\endcaption
\endinsert

\bigskip

{\it Proof of Lemma~3.} \ Let $A_0$ be the standard Young tableau
of shape $\la$ \, given by $f(1,1)=1$,
$f(1,2)=2$, \dots, $f(1,\la_1)=\la_1$, $f(2,1)=\la_1+1$, \dots,
$f(2,\la_2)=\la_1+\la_2$, $f(3,1) = \la_1+\la_2+1$, \dots \,
Let us orient all edges of $\Ga(\la)$, so that $A \to
A^\pr$ if $A$ and $A^\pr$ exchange the values of $i$ and $i+1$, and $i$
occurs in a row of $A^\pr$ smaller than that of $A$. Observe that
$A_0$ is the only vertex with no outgoing edges in $\Ga(\la)$.
Therefore, every $A$ is connected
to $A_0$ in $\Ga(\la)$, which proves the result. \ $\sq$

\bigskip

\vskip 10pt

\head 6. The Two Polytopes Theorem and RSK \endhead

\medskip

In this section we deduce from Theorem~3 the numerical result of the
Robinson-Schensted-Knuth correspondence.

\smallskip

Let \, $\la=(n^n) = (n,n,\dots,n)$, \, $n$ times. In this case
$[\la] = [n]\times [n]$, $\ell(\la) = m = n$. Let $\bold d =
(d_{1-n},\dots,d_0,\dots, d_{n-1})$ be as above. Suppose
$$(\diamond) \ \ \ a_i = d_{i-n}-d_{i-n-1}, \ b_i = d_{n-i}-d_{n-i+1}, \ \
\text{for all} \ 1 \le i \le n.$$
Then the integer points in $\qQ_\la(\bold d)$ correspond to contingency tables
(nonnegative integer $n \times n$ matrices with given row and column sums):
$$\sum_{j=1}^n \, y_{i,j} = a_i, \ \ \sum_{i=1}^n \ y_{i,j} = b_j, \ \
y_{i,j} \ge 0, \ \ \text{for all} \ \, 1 \le i, j \le n. $$

We say that $f: [\la] \to \zz_+$ is a {\it Young tableau of
shape} \, $\la$, if \, $f(i,j) \le f(i,j+1)$ \, and \,
$f(i,j) < f(i+1,j)$, whenever both sides are defined. We say that
$A$ has {\it weight} \, $\bold a = (a_1,\dots,a_n)$, if \, $|\{(i,j)\in
[\la] : f(i,j) = k\}| = a_k$, for all \, $1 \le k \le n$.

\bigskip

{\bf Theorem 5. (RSK)} \ {\it Let \, $\bold a = (a_1,\dots,a_n)$  and
\, $\bold b = (b_1,\dots,b_n)$  be two nonnegative integer arrays such
that \, $|\bold a| = |\bold b|$.
Then the  number of contingency tables
with row sums $a_i$, and column sums
$b_j$, is equal to the number of pairs of
Young tableaux of the same shape $\la \vdash n$, and weight
\, $\bold a$ and \, $\bold b$ respectively.}

\bigskip

{\it Proof. } \ Let $d_{-i} = a_{1} + \dots + a_{n-i}$,
$d_{i} = b_{1} + \dots + b_{n-i}$, for $0 \le i \le n-1$, so that
$d_0 = |\bold a| = |\bold b|$. Then $a_i$, $b_j$ satisfy
$(\diamond)$ and the number of contingency tables is
equal to \, $e\bigl(\qQ_\la(\bold d))$.

Now, let $A$, $B$ be Young tableaux of shape $\mu = (\mu_1,\dots,\mu_n) \vdash n$
with weights $\bold a$ and $\bold b$, given by functions $f_A$ and $f_B$,
respectively. Let $X = (x_{i,j})$ be the reverse plane partition of shape $\la$,
defined by
$$x_{i,j} = \left\{ \aligned
\bigl|\{k : f_A(n-j+1,k) \le i\}\bigr|, \ \ \text{if} \ i \le j \, ; \\
\bigl|\{k : f_B(n-i+1,k) \le j\}\bigr|, \ \ \text{if} \ i \ge j \, .
\endaligned \right.
$$

\medskip

\midinsert
%\vskip 10pt
\line{\hfill\epsfysize=4.5cm\epsfbox{fig6n.eps}\hfill}
%\vskip 10pt
\botcaption{Figure 6} \,
 A reverse plane partition $X$ of shape
$(3,3,3)$ and a corresponding pair of Young tableaux of shape
$(7,4,1)$ with weights $\bold a = (4,5,3)$ and $\bold b =
(2,5,5)$.
\endcaption
\endinsert

\medskip

Note that
$$x_{i,i} = \bigl|\{k: f_A(n-i+1,k) \le i\}\bigr| =
\bigl|\{k: f_B(n-i+1,k) \le i\}\bigr| = \mu_{n-i+1}. $$
Also, $(x_{i,j}) \in C(\la)$, since all the inequalities follow
from the definition of Young tableaux. Finally, by definition of
the weight, we have
$$\al_{-i}(X) = a_{1} + \,\dots \, + a_{n-i} = d_{-i}, \ \, \text{and}
\ \, \be_i(X) = b_{1} + \, \dots \, + b_{n-i}=d_i, \ \, \text{for} \ \, 0 \le i \le
n-1. $$
Therefore, pairs of Young tableaux of the same shape \, $\mu \vdash n$ \, and
weight \, $\bold a$ and \, $\bold b$, are in bijection with reverse plane
partitions $X=(x_{i,j}) \in \pP_\la(\bold d)$ of shape $\la$. This
completes the proof. \ $\sq$

\bigskip

Denote by \, $\theta$ \, the correspondence between reverse plane
partitions $X$ and pairs of Young tableaux as in the proof above.
Let \, $\eta = \theta \cdot \xi$ \, be the bijection between
contingency tables \, $Y=(y_{i,j})$ \, and pairs of Young tableaux
of the same shape (as in Theorem~5.) \, By $Y^T$ denote the
transpose matrix \, $Y^T=(y^T_{i,j})$, where \,
$y^T_{i,j}=y_{j,i}$, $1 \le i, j \le n$.

\bigskip

{\bf Corollary~2.} \ {\it If \, $\eta(Y) = (A,B)$, then \,
$\eta(Y^T) = (B,A)$. }

\medskip

{\it Proof.} \ By construction, if \, $\theta(X) = (A,B)$, then \,
$\theta(Y^T) = (B,A)$. It remains to check that \, $\xi(Y^T) =
\bigl(\xi(Y)\bigr)^T$. But this follows immediately from \,
Theorem~4 since the transposition simply changes the order of
the corners in the  definition of~$\xi_\la$.~\,~ $\sq$

\bigskip

\vskip 10pt

\head 7. Monotone paths \endhead

\medskip

We say that the squares $(i\pm 1,j)$ and $(i,j\pm 1)$ \, are {\it
adjacent} \, to $(i,j)$ in $\zz^2$. A~{\it monotone path} \, $\ga$ \,
in $[\la]$, denoted by $\ga \sa [\la]$, is a sequence of adjacent squares \,
$\xx \prec \xx^\pr \prec \xx^{\pr\pr}
\prec \dots$, where \, $\xx, \xx^\pr, \dots \in [\la]$.
Let $g: [\la] \to \rr_+$ \, be any nonnegative function on $[\la]$,
which defines a tableau $B = (y_{i,j})$, where
$y_{i,j} = g(i,j)$ for all $(i,j) \in [\la]$.
Define the {\it height of a path} \, $\ga$ \, to be the sum \,
$\om_B(\ga) = g(\xx)+g(\xx^\pr)+g(\xx^{\pr\pr})+\dots$.

\bigskip

{\bf Theorem 6.} \ {\it Let $\xi_\la : \pP_\la(\bold d) \to
\qQ_\la(\bold d)$ be the map defined as above. Fix a square
$\xx_c=(i_c,j_c)$, where \, $1-m \le c \le \ell-1$;
$[\nu_c] = \{(i,j) : i \le i_c, j\le j_c\}$.
Then for every
$A=(x_{i,j})$, $B=(y_{i,j})$, $B = \xi_\la(A)$,
we have
$$x_{i_c,j_c} = \max_{\ga \sa [\nu_c]} \, \om_B(\ga).$$}

\bigskip


\midinsert
%\vskip 10pt
\line{\hfill\epsfysize=2.5cm\epsfbox{fig7n.eps}\hfill}
%\vskip 10pt
\botcaption{Figure 7} \, An example of bijection $\xi_{(3,3,3)} : A \to B$
(cf. Figure~4.) The value
of $A$ at $\xx_1 = (3,2)$ is equal to the sum along the
monotone path from $(1,1)$ to $(3,2)$ with maximum height: $4 =1+0+3+0$.
\endcaption
\endinsert

\medskip

{\it Proof.} \ Use induction. When $n=1$ the result is trivial.
Suppose it holds for $[\mu] = [\la] - \xx_c$, where $\xx_c$ is the
corner of $[\la]$. By definition of \, $\zeta_{\la,c}$ , we have:
$$\aligned
\max_{\ga \sa [\nu_c]} \, \om_B(\ga) & = \, \max\bigr\{
\max_{\ga \sa [\nu_{c-1}]} \, \om_B(\ga)\, , \,
\max_{\ga \sa [\nu_{c+1}]} \, \om_B(\ga) \bigr\} \, + \, y_{i_c,j_c} \\
& = \, \max \bigl\{x_{i_c-1,j_c} \, , \, x_{i_c,j_c-1}\bigr\} +
\left( x_{i_c,j_c} - \max \bigl\{x_{i_c-1,j_c} \, , \,
x_{i_c,j_c-1}\bigr\} \right) \\
& = \, x_{i_c,j_c}
\endaligned
$$
Since the off-diagonal values of $\zeta_{\la,c}$ remain unchanged,
this implies the result. \ $\sq$

\bigskip

\vskip 10pt

\head 8. Historical remarks and quick guide through the literature \endhead

\medskip

As we mentioned in the introduction, the hook length formula
first appeared in \cite{FRT},
after it was independently discovered by the authors of that paper
(see \cite{Sa}).
Various combinatorial proofs were later obtained in
\cite{FZ,GNW,Kr,NPS}. We will not review these proofs here, but
rather refer the reader to the textbooks \cite{JK,K2,M,Sa,S3} for
these and other proofs, and further references.

The hook content formula was discovered by Stanley in \cite{S2}.
Note that what we call HCF is really a special case of a more
general result in \cite{S2}, when the size of the entries $f(i,j)$
in a reverse plane partition is bounded.
Lemma~1 is a very special case, for a poset $([\la], \prec)$,
of another general result of Stanley \cite{S1}. Our presentation
is elementary and probably well known, although we could not find
a precise reference.


The idea to prove HLF via HCF goes back to \cite{S1}, and was
utilized by Hillman and Grassl in the pioneering work \cite{HG}.
The similarity between the Hillman-Grassl bijection and
the Robinson-Schensted-Knuth correspondence was observed by
Gansner in \cite{G1,G2}, who proved versions of Theorem~3 and
Lemma~2, although by a different technique.

The proof of TPT that we present here was inspired by \cite{PP}.
The continuous version first appeared there as well.
Let us emphasize here that \, $\bold d$ \, can be any nonnegative
real array. The construction
of a map \, $\wt \zeta_c$, remarkably similar to~$\zeta_c$, but
for diagonals with no corners, was discovered
independently in~\cite{BK}. There, the
authors also pursued ``continuous combinatorics'', and obtained
the Sch\" utzenberger involution as a certain
product \, $\prod_c \wt \zeta_c$.
In a different direction, we believe that our proof of TPT is
equivalent to a special case of the general approach
in~\cite{F}. Unfortunately, the translation is quite cumbersome
and requires some extra work.

Let us note that Corollary~1 in a special case gives an
interpretation of the Ehrhart polynomial of the Birkhoff
polytope \cite{P1}, long studied by combinatorialists (see e.g. \cite{S3}).
Lemma~3 is well known. Exactly this version appeared in~\cite{P2}.
An advanced generalization, in the language of Bruhat orders,
is given in~\cite{BW}.

Theorem~5 is due to Knuth \cite{K1}, who proved it by a bijection,
now known as Robinson-Schensted-Knuth correspondence (see \cite{K2,R,Sa,S3}).
It is known~\cite{PP} that our
bijection \, $\xi_\la$ in this special case coincides
with RSK (after translation as in the proof).
The proof requires the understanding of the classical formulation of
the RSK correspondence and goes beyond this paper.

Corollary~2 is a famous symmetry property of RSK \cite{K1}, long
studied in this context. The result is quite nontrivial when
dealing with the original correspondence, and rather immediate
from our approach\footnote{
We believe that our construction of \, $\xi_\la$ \, has a certain
advantage when compared to the original construction of the
RSK correspondence (we have \, $\la=(n^n)$ \, in this case.)
It seems that
with a small exception of the {\it dual RSK} \, (which does not seem
to have a ``continuous'' generalization), all properties
of the RSK correspondence are easier to prove in our
setting.
}.

The `monotone path' property of \, $\xi_\la$, given by Theorem~6,
is well known for the RSK correspondence (see \cite{Sa}).
The concept of monotone paths
generalizes longest increasing subsequences, which were the
motivation in \cite{Sc}. One can also extend Greene's Theorem \cite{Gr}
in this case.

To conclude, let us speculate about possible extensions of the
HLF. Versions of the map \, $\zeta_\la$ \, exist
for all differential posets and even dual graded
graphs \cite{F,S3}. The proof of Lemma~1 generalizes to all posets
with no difficulty. It is Lemma~2 that is
specific for the Young lattice, and is a key to possible
generalizations.


\bigskip

{\bf Acknowledgements}

\medskip

Over the years the author benefited from helpful conversations with a
number of people. It is my pleasure to thank here Ron Adin,
Arkady Berenstein, Jean B\'etr\'ema, Persi Diaconis, Joseph Donin,
Adriano Garsia, Ira Gessel, Alexandre Kirillov,
Christian Krattenthaler, Ezra Miller, Jean-Christophe Novelli,
Alex Postnikov, Yuval Roichman, Bruce Sagan,
Richard Stanley, Sasha Stoyanovskii, Xavier Viennot and Andrei
Zelevinsky. Communication with Herb Wilf was educational and
entertaining. We also thank the referees for the thorough reading
of the paper.

\smallskip

The paper was written when the author was a Fellow at \, MSRI \, in
\, Berkeley, CA.

\vfill\eject

\Refs\widestnumber\key{50000}

\medskip


\ref \key BK \by A. Berenstein, A. Kirillov
\paper  Groups generated by involutions,
Gelfand-Tsetlin patterns, and combinatorics of Young tableaux
\jour St\. Petersburg Math\. J.
\vol 7
\yr  1996
\pages 77--127
\endref


\ref \key BW \by A. Bj\"orner, M. Wachs
\paper Generalized quotients in Coxeter groups
\jour  Trans\. Amer\. Math\. Soc\.
\vol  308
\yr 1988
\pages 1--37
\endref

\ref \key F \by S.~Fomin
\paper Duality of graded graphs;
Schensted algorithms for dual graded graphs
\jour J.\ Alg.\ Comb\.
\vol 3, 4
\yr 1994--5
\pages 357--404; 5--45
\endref


\ref \key FRT \by J.~S.~Frame, G.~de~B.~Robinson, R.~M.~Thrall
\paper The hook graphs of the symmetric group
\jour Canad\. J. Math\.
\vol 6
\yr 1954
\pages 316--325
\endref

\ref \key FZ \by D.~S.~Franzblau, D.~Zeilberger
\paper A bijective proof of the hook-length formula
\jour J. Algorithms
\vol 3
\yr 1982
\pages 317--343
\endref

\ref \key G1 \by  E.~Gansner
\paper Matrix correspondences of plane partition
\jour Pacific J. Math\.
\vol 92
\yr 1981
\pages 295--315
\endref

\ref \key G2 \by  E.~Gansner
\paper The Hillman-Grassl correspondence and the
enumeration of reverse plane partitions
\jour J. Combin\. Theory, Ser.~A
\vol 30
\yr 1981
\pages 71--89
\endref

\ref \key Gr \by C.~Greene
\paper An extension of Schensted's theorem
\jour Advances in Math\.
\vol 14
\yr 1974
\pages 254--265
\endref

\ref \key GNW \by C.~Greene, A.~Nijenhuis, H.~S.~Wilf
\paper A probabilistic proof of a formula for the number of
Young tableaux of a given shape
\jour Adv\. in Math\.
\vol  31
\yr 1979
\pages 104--109
\endref

\ref \key HG \by A.~P.~Hillman, R.~M.~Grassl
\paper Reverse plane partitions and tableau hook numbers
\jour J. Comb\. Theory, Ser.~A
\vol 21
\yr 1976
\pages 216--221
\endref

\ref \key JK  \by G.~James, A.~Kerber
\book The Representation Theory of the Symmetric Group
\publ Addison-Wesley
\publaddr Reading, MA
\yr 1981
\endref

\ref \key K1 \by  D.~Knuth
\paper Permutations, matrices and generalized
Young tableaux
\jour Pacific J. Math\.
\vol 34
\yr 1970
\pages 709--727
\endref

\ref \key K2 \by D. E. Knuth
\book The Art of Computer Programming \, {\rm (Second Edition),
 Vol.~3, Sorting and Searching}
\publ Addison-Wesley
\publaddr Reading, Massachusetts
\yr 1998
\endref

\ref \key Kr \by C.~Krattenthaler
\paper Bijective proofs of the hook formulas for the number
of the standard Young tableaux, ordinary and shifted
\jour Electr\. J. Comb\.
\vol 2
\yr 1995
\pages \#R13
\endref

\ref \key M \by I.~G.~Macdonald
\book Symmetric Functions and Hall Polynomials
\bookinfo second edition
\publ Oxford University Press
\publaddr London
\yr 1995
\endref

\ref \key NPS \by J-C~Novelli, I.~Pak, A.~V.~Stoyanovskii
\paper A direct
combinatorial proof of the hook-length formula
\jour Discrete Math\. and Theor\. Comp\. Sci\.
\vol 1
\yr 1997
\pages 53--67
\endref

\ref \key P1 \by I.~Pak
\paper Four questions on Birkhoff polytope
\jour Annals of Combinatorics
\vol 4
\yr 2000
\pages 83--90
\endref


\ref \key P2 \by I.~Pak
\paper Ribbon tile invariants
\jour Trans\. Amer\. Math\. Soc\.
\vol 352
\yr 2000
\pages 5525--5561
\endref

\ref \key PP \by  I.~Pak, A.~Postnikov
\paper Oscillating tableaux and generalized RSK correspondence
\publ Proc\. of Eighth FPSAC Conference
\publaddr UMN, Minneapolis, 1996
\endref


\ref \key R  \by G. de B. Robinson
\book Representation Theory of the Symmetric Group
\publ Edinburgh University Press
\yr 1961
\endref


\ref \key Sa \by  B.~Sagan
\book The symmetric group: Representations, Combinatorial Algorithms
and Symmetric Functions {\rm (Second Edition)}
\publ Springer
\publaddr New York
\yr 2001
\endref

\ref \key Sc \by C.~Schensted
\paper Longest increasing and decreasing subsequences
\jour Canad\. J. Math\.
\vol 13
\yr 1961
\pages 179--191
\endref

\ref \key S1 \by R.~P.~Stanley
\paper Ordered structures and partitions
\jour Memoirs of the AMS
\vol 119
\publ AMS
\publaddr Providence, R.I., 1972
\endref

\ref \key S2 \by R.~P.~Stanley
\paper Theory and application of plane partitions, I, II
\jour Studies in Appl\. Math\.
\vol 50
\yr 1971
\pages 167--188, 259--279
\endref

\ref \key S3 \by R.~P.~Stanley
\book Enumerative Combinatorics, {\rm Vol.~1, 2}
\publ Cambridge University Press
\publaddr Cambridge, UK
\yr 1999
\endref

\endRefs

\end{document}
