%lbt.tex
\magnification\magstep1
\baselineskip14pt
\def\adj{\mathrel-\joinrel\mathrel-}   %long minus


\centerline{\bf Labeled bipartite trees and nonattaching kings}

\bigskip
There are $(m+1)^n(n+1)^m$ ways to place $mn$ kings on a $2m\times 2n$
chessboard subject to the condition that they do not attack except perhaps in
the configurations
$$\vcenter{\halign{$#$\hfil\qquad&$#$\hfil\qquad\qquad
&#\hfil\qquad\qquad&$#$\hfil\qquad&$#$\hfil\cr
SE&&or&&SW\cr
&NW&&NE\cr}}$$
in diagonally adjacent $2\times 2$ subcells. Boris Pittel noticed that
$(m+1)^n(n+1)^m$ is also the number of labeled trees on $\{U_0,\ldots,U_m\}$
and $\{V_0,\ldots,V_n\}$ such that all edges go from~$U_i$ to~$V_j$. There's a
very nice and reasonably simple one-to-one correspondence between king
placements and trees (see, for example, exercise 2.3.4.4--28 in Volume~1), so
I~will reiterate it here.

The trees in question are equivalent to directed graphs on 
the vertices $\{U_0,\ldots,
U_m\}$ and $\{V_0,\ldots, V_n\}$ in which there are arcs from~$U_j$
to~$V_{f(y)}$ for $1\leq j\leq m$ and from~$V_k$ to~$U_{g(k)}$ for $0\leq k\leq
n$, where the functions~$f$ and~$g$ are chosen so that no oriented cycles
occur. The number of ways to choose $f$ and~$g$ without the cycle condition is
obviously 
$(n+1)^m(m+1)^{n+1}$; it turns out that exactly $1/(m+1)$ of these choices will
avoid cycles.

Given $f$, there's a one-one correspondence between suitable~$g$'s and
auxiliary 
sequences $(h_0,\ldots,h_n)$ where $0\leq h_j\leq m$ and $h_n=0$, as follows.
Let $f(0)=\infty$ for convenience. The $i\/$th arc, for $0\leq i\leq n$, goes
from~$V_{j_i}$ to~$U_{h_i}$, where $j_i$ is the smallest nonnegative 
integer not in $\{j_0,\ldots,j_{i-1},\,f(h_i),\ldots,f(h_n)\}$. For example,
suppose $m=3$, $n=5$, $f(1)=f(2)=2$, $f(3)=0$, and
$(h_0,\ldots,h_5)=(3,1,3,0,2,0)$; then the sequence $(j_0,\ldots,j_5)$ turns out
to be $(1,3,4,0,5,2)$, so the tree is
$$\vcenter{\halign{$#$\hfil\quad
&$#$\hfil\quad
&$#$\hfil\quad
&$#$\hfil\quad
&$#$\hfil\quad
&$#$\hfil\quad
&$#$\hfil\quad
&$#$\hfil\quad
&$#$\hfil\quad
&$#$\hfil\quad
&$#$\hfil\quad
&$#$\hfil\quad
&$#$\hfil\quad
&#\cr
V_1&&&&&&&&&&U_1&\leftarrow&V_3\cr
&\searrow&&&&&&&&\swarrow\cr
&&U_3&\rightarrow&V_0&\rightarrow&U_0&\rightarrow&V_2\cr
&\nearrow&&&&&&&&\nwarrow\cr
V_4&&&&&&&&&&U_2&\leftarrow&V_5&.\cr}}$$

Now let's try to relate this correspondence to the king placements. The values
of~$f$ tell us the East-West configuration; thus $f(1)=f(2)=2$ and $f(3)=0$ and
$m=3$, $n=5$ corresponds to
$$\vcenter{\halign{$#$\hfil\quad
&$#$\hfil\quad
&$#$\hfil\quad
&$#$\hfil\quad
&$#$\hfil\quad
&#\hfil\cr
W&W&E&E&E\cr
W&W&E&E&E&.\cr
E&E&E&E&E\cr}}$$
The values of $h$ tell us North-South configuration; in this example we need to
avoid
$$\vcenter{\halign{$#$\hfil\quad
&$#$\hfil\quad
&$#$\hfil\quad
&$#$\hfil\quad
&$#$\hfil\cr
N&\ast&\ast&\ast&\ast\cr
N&S&\ast&\ast&\ast\cr
N&S&\ast&\ast&\ast\cr}}$$
which means $h_0=3$ and $h_1\leq 1$ if $h$ counts the $N$s (or $h_0=0$ and
$h_1\geq 2$ if $h$ counts the~$S$'s).

I looked closer at the case $m=2$ and started to see a pattern relating ``bad''
trees to ``bad'' kings. But it wasn't beautiful, at least not at first glance.
Other one-to-one correspondences
 exist (see exercise 2.3.4.4--18 and the reference
cited in its answer), and may well lead to a natural defining property of
 ``bad'' trees.

\bye
