% This is a 8 page plain tex file
% INVERSES OF WORDS, Dominique Foata and Guo-Niu Han
% =======================================================

\magnification=1200
\hsize=11.25cm\hoffset=1cm
\parindent=0pt
\def\intinv{\mathop{\rm intinv}\nolimits}
\def\extinv{\mathop{\rm extinv}\nolimits}
\def\inv{\mathop{\rm inv}\nolimits}
\def\qed{\quad\raise -2pt
\hbox{\vrule\vbox to 10pt{\hrule width 4pt
\vfill\hrule}\vrule}}

\overfullrule=0pt

\def\myitem#1#2
    {{\leftskip=12mm\noindent
    \hangindent=0mm\hangafter=1
     \llap{#1 \hskip.35em}{#2}\smallskip}}

\line{\hfill Jan. 30, 1998}
\vskip 2cm

\centerline{\bf INVERSES OF WORDS}
\bigskip
\centerline{\sl Dominique Foata and Guo-Niu Han}
\bigskip\bigskip

% ----------------------------------------------------------
{\it Abstract}. 
The inverse of a permutation is one of the
basic operations in the symmetric group. In this paper we
propose an extension of this operation to words (with
repetitions) by constructing an explicit one-to-one
transformation on words. We also show that there exists
another transformation having one more property that would be
the definitive bijection for deriving the inverse of a word. The
open problem is to imagine its construction.



% ----------------------------------------------------------
\bigskip\bigskip
\centerline{\bf 1. Introduction}
\medskip
Back in the Fall of 1997 we received a letter from Don Knuth
[Kn97] saying the following: ``While proofreading the new
edition of my book {\sl Sorting and Searching}, I ran across a
remark in the last paragraph of the answer to exercise
5.1.2-14 that I had forgotten (page 583 of the first edition).
Basically it asks for a bijective way to define the inverse of a
multiset permutation (word). Has anybody come up with a
satisfactory solution of that problem?"

\medskip
Well, the immediate reaction was to go back to the
theory of partially commutative monoids, where the notion of
{\it cycle} (see [CF69]) had been introduced and try to use the
result on unique decomposition of words. As we shall see, we
can come up with a satisfactory answer that is developed in
the next two sections. However an easy calculation on
$q$-multinomial coefficients shows that there exists another
transformation on words having one more property that would
make it the definitive bijection to define the inverse of a
word. In the last section we give the list of the properties of
that ideal transformation and invite the reader to imagine its
construction.

\medskip
Let us first recall the basic properties of the inverse of a
permutation. If $\sigma=\sigma(1)\sigma(2)\ldots\sigma(n)$ is
a permutation of order~$n$, its {\it inverse} $\sigma^{-1}$ is
defined by $\sigma^{-1}(\sigma(i))=i$ for all~$i$ and its {\it
number of inversions} ``inv" by
$$
\inv \sigma=\#\{(i,j):1\le i<j\le n,\,\sigma(i)>\sigma(j)\}.
$$
For the material on Young tableaux and
the Robinson-Schensted correspondence the reader is referred
to the book by Knuth [Kn73, pp.~52]. That famous
correspondence maps each permutation~$\sigma$ onto an
ordered pair of standard Young tableaux $(P,Q)$ of the same shape. 
We shall denote it by
$\sigma\mapsto (P,Q)$.

\medskip
Let us enumerate some basic properties of the inverse.

\myitem{(P1)}{The map $\sigma\mapsto \sigma^{-1}$ is involutive.}

\myitem{(P2)}{Each pair $(i,\sigma(i))$ is mapped onto the pair
$(\sigma(i),i)$.}

\myitem{(P3)}{The number of inversions
``$\inv$" is preserved under the transformation
$\sigma\mapsto \sigma^{-1}$, i.e.,
$\inv\sigma^{-1}=\inv\sigma$.}

\myitem{(P4)}{If $\sigma\mapsto (P,Q)$, then
$\sigma^{-1}\mapsto (Q,P)$.}

\medskip
Our two results are the following.
\smallskip

{1)} {In section 2 we construct an explicit transformation
$w\mapsto w^*$ that extends the inverse mapping
$\sigma\mapsto \sigma^{-1}$ to words. Furthermore,
the properties (P1), (P2), (P3), once suitably reinterpreted for
dealing with words, also hold (section~3).}
\smallskip

{2)} {In section 4 we prove the {\it existence} of a
transformation that has all the properties (P1), (P2), (P3), (P4)
adapted to words.
However the explict construction of such a transformation is
still an open problem.}

% ----------------------------------------------------------
\bigskip\bigskip
\centerline{\bf 2. The transformation}
\medskip

For convenience, let $X$  be the alphabet $\{1,2,\ldots,r\}$.
If ${\bf c}=(c_1,c_2,\ldots, c_r)$ is a sequence of $r$
nonnegative integers, then $1^{c_1}2^{c_2}\ldots
r^{c_r}=y_1y_2\ldots y_m$ is a nondecreasing word of
length~$m$ with
$m=c_1+c_2+\cdots+c_r$ and $y_1=\cdots =y_{c_1}=1$,
$y_{c_1+1}=\cdots=y_{c_1+c_2}=2$, \dots~,
$y_{c_1+\cdots+c_{r-1}+1}=\cdots=y_m=r$. Denote by
$R({\bf c})$ be the set of all rearrangements of the word
$y_1y_2\ldots y_m$. 

A {\it circuit} is
defined to be an ordered pair
$\displaystyle{u\choose v}$, where the
words $u=y_1y_2\ldots y_m$ and
$v=x_1x_2\ldots x_m$ are rearrangements of each other.

We use the following
commutation rule for two adjacent biletters
$${a\choose b}
{c\choose d}=
{c\choose d}
{a\choose b}\quad{\rm  if\ and\ only\ if\ }a\not=c
\leqno(\spadesuit)
$$
to change a circuit to another. 
Two circuits $\displaystyle{u\choose v}$ and
$\displaystyle{u_1\choose v_1}$ are said to be {\it equivalent}, if
we can go from one to the other by a finite sequence of adjacent
transpositions of bi-letters as defined in $(\spadesuit)$.

\medskip
{\it Construction of the transformation $w\mapsto w^*$}.
Let $w$ be a word in $R({\bf c})$. We first form the circuit
$\Gamma(w)=\displaystyle{\overline w\choose w}$, where
$\overline w$ is the nondecreasing rearrangement of~$w$.
Using the same example as in [Lo83 p.~199] namely
$w=31514226672615$, we get
$$
\Gamma(w)={\overline w\choose w}
=\pmatrix{1&1&1&2&2&2&3&4&5&5&6&6&6&7\cr
3&1&5&1&4&2&2&6&6&7&2&6&1&5\cr}.
$$

Next we form
the {\it dominated circuit factorization} of the circuit
$\Gamma(w)$ as described in [Lo83 p.~199]
$$
\Gamma(w)=\pmatrix{1&1&2&3\cr
3&1&1&2\cr}
\pmatrix{4&2&2&6\cr
6&4&2&2\cr}
\pmatrix{6\cr 6\cr}
\pmatrix{5&1&6\cr
6&5&1\cr}
\pmatrix{5&7\cr
7&5\cr}.
$$
Now such a circuit can be decomposed into a product of
{\it cycles}. The theory is not made in [Lo83], but is made in
[CF69] (see page~42, Proposition~4.1). It is also discussed in [Kn73, theorem C, p.
28]. With the
previous example
$$
\Gamma(w)=
\pmatrix{1&2&3\cr
3&1&2\cr}
\pmatrix{1\cr 1\cr}
\pmatrix{4&2&6\cr
6&4&2\cr}
\pmatrix{2\cr 2\cr}
\pmatrix{6\cr 6\cr}
\pmatrix{5&1&6\cr
6&5&1\cr}
\pmatrix{5&7\cr
7&5\cr}.
$$
As shown in [CF69, p. 42] or [Kn73, p. 28] the above factorization (``decomposition")
is {\it unique} in the sense that if two such factorizations are
equal to the same $\Gamma(w)$ we can go from the first one to
the second by a finite sequence of elementary transformations
consisting of permuting two consecutive cycles having no
letter in common.

Having such a product we can take the inverse of
each cycle consisting of permuting the top and the bottom
rows within each cycle. Call it $\tau\,\Gamma(w)$:
$$
\tau\,\Gamma(w)=
\pmatrix{3&1&2\cr 1&2&3\cr}\!
\pmatrix{1\cr 1\cr}\!
\pmatrix{6&4&2\cr 4&2&6\cr}\!
\pmatrix{2\cr 2\cr}\!
\pmatrix{6\cr 6\cr}\!
\pmatrix{6&5&1\cr 5&1&6\cr}\!
\pmatrix{7&5\cr 5&7\cr
}.
$$
Next using the commutation rule $(\spadesuit)$ we rearrange the above
product
$\tau\,\Gamma(w)$ in such a way that the top row is
nondecreasing. We get a circuit that corresponds to a
rearrangement $w^*$ of~$w$:
$$
\Gamma(w^*)
=\pmatrix{1&1&1&2&2&2&3&4&5&5&6&6&6&7\cr
2&1&6&3&6&2&1&2&1&7&4&6&5&5\cr}.
$$
The word $w^*$ is defined as the bottom
row of the previous two-matrix, that is
$$
w^* = 21636212174655.
$$


The above construction can be described as the sequence:
$$
w\mapsto \Gamma(w)={\overline w\choose w}
\mapsto {u\choose v}
\buildrel \textstyle\tau\over \mapsto{v\choose u}\mapsto
\Gamma(w^*)={\overline w\choose w^*}\mapsto w^*.
\leqno(\clubsuit)
$$
Note that the unique decompositions $\displaystyle{u\choose v}$ and
$\displaystyle{v\choose u}$ are equivalent to the
two circuits $\Gamma(w)$ and $\Gamma(w^*)$, respectively.
\medskip

{\it Remark}. 
In a subsequent letter [Kn98] Knuth told us that he had thought of the same
construction for $w\mapsto w^*$.

% ----------------------------------------------------
\bigskip\bigskip
\centerline{\bf 3. Properties}
\medskip

Let $w=x_1x_2\ldots x_m$ belong to $R({\bf c})$. 
When dealing with words (with repetitions) two kinds of
inversions can be introduced, the {\it internal}
and the {\it external} inversions. An {\it internal inversion} of
a word $w=x_1x_2\ldots x_m$ in $R({\bf c})$ is an
inversion that occurs {\it inside} any one of the $r$~factors
$x_1\ldots x_{c_1}$, $x_{c_1+1}\ldots x_{c_1+c_2}$,
\dots~, $x_{c_1+\cdots+c_{r-1}+1}\ldots x_m$ of the
word~$w$. An {\it external inversion} is an inversion
of two letters belonging to two different factors. 
Let $\intinv w$ (resp. $\extinv w$) denote the number of
internal (resp. external) inversions of the word~$w$.
Of course, $\intinv+\extinv=\inv$, the usual number of
inversions. If $w$ has no repetitions
(if it is a permutation), then $\intinv  w=0$ while
$\extinv w=\inv w$.


Let $\displaystyle{u\choose v}$ be a circuit. Remember that
$u=y_1y_2\ldots y_m$ and $v=x_1x_2\ldots x_m$ are rearrangements
of each other and $v$ is {\it not} necessarily nondecreasing.
The {\it number of external inversions}
$\extinv\displaystyle{u\choose v}$ of the circuit
$\displaystyle{u\choose v}$ is defined to be the number of
pairs $(i,j)$ such that $1\le i<j\le m$ and either
$y_i<y_j$ and $x_i>x_j$, or
$y_i>y_j$ and $x_i<x_j$.

\proclaim Proposition 1. Let $\overline w$ be the
nondecreasing rearrangement of a word~$w$ and let $u,v,u_1,v_1$ be four
rearrangements of~$w$. Then

\myitem{(E1)}{$\extinv\displaystyle{\overline w\choose w}
=\extinv w$;}

\myitem{(E2)}{$\extinv\displaystyle{u\choose v}
=\extinv {v\choose u}$;}

\myitem{(E3)}{If two circuits
$\displaystyle{u\choose v}$ and  $\displaystyle{u_1\choose v_1}$
are equivalent, then}
$$
\extinv {u\choose v}=\extinv{u_1\choose v_1}.
$$


{\it Proof}: When the top word in a biword is the nondecreasing
rearrangement of the bottom word~$w$, the definitions of
``extinv" for the circuit $\overline w\choose w$ and for the
word~$w$ coincide. Property~(E2) is the extension to words
of the invariance of the inversion number when a permutation
is mapped onto its inverse. Property~(E3) is true
for two circuits differing by a transposition of two adjacent
letters satisfying~$(\spadesuit)$ and then holds for two
equivalent circuits.\qed


\proclaim Theorem 2. The transformation $w\mapsto w^*$ is a bijection 
of $R({\bf c})$ onto itself having the following
properties

\myitem{(W0)}{If $w=\sigma$ is a permutation, then $w^*=\sigma^{-1}$;}

\myitem{(W1)}{$w\mapsto w^*$ is an involution;}

\myitem{(W2)}{For each biletter $\displaystyle{y\choose x}$, the number of occurrences of
the biletter $\displaystyle{y\choose x}$ in $\displaystyle{\overline w\choose w}$
is equal to the number of occurrences of
the biletter $\displaystyle{x\choose y}$ in~$\displaystyle{\overline w\choose w^*}$.}

\myitem{(W3)}{$\extinv w=\extinv w^*$;}


{\it Proof:}
Properties (W0), (W1), (W2) follows immediately from the construction of $w\mapsto
w^*$ described in $(\clubsuit)$. Property (W3) is a consequence of both $(\clubsuit)$ and
Proposition~1.\qed

{\it Example}. With $w$ and $w^*$ derived in section 2 we have
$\extinv w^*=\extinv w=27$.
Here
$\intinv w^*=\intinv w=4$ and
$\inv w^*=\inv w=31$, but this is a simple coincidence (see the example at the
end of section 4.)


% -----------------------------------------------------
\bigskip\bigskip
\centerline{\bf 4. Another analogue?}
\medskip

For each word~$w$ and
each element $i=1,2,\ldots,r$ in the alphabet let
$|w|_i$ denote the number of letters of~$w$ equal to~$i$.
Let $A=(a(i,j))$ be an $r\times r$ matrix with nonnegative
coefficients such that the sum of the entries in the first row
and also in the first column is~$c_1$, \dots~, the sum of the
entries in the $r$-th row and also in the $r$-th column
is~$c_r$. Let $w=x_1x_2\ldots x_m$ belong to $R({\bf c})$. It
is said to be {\it of $A$-type}, if the following conditions hold:
$$
\displaylines{
|x_1\ldots x_{c_1}|_1=a(1,1),\ \ldots\ ,
|x_1\ldots x_{c_1}|_r=a(1,r);\cr
|x_{c_1+1}\ldots x_{c_1+c_2}|_1=a(2,1),\ \ldots\ ,
|x_{c_1+1}\ldots x_{c_1+c_2}|_r=a(2,r);\cr
\dotfill\cr
|x_{c_1+\cdots+c_{r-1}+1}\ldots x_m|_1=a(r,1),\ \ldots\ ,
|x_{c_1+\cdots+c_{r-1}+1}\ldots x_m|_r=a(r,r).\cr}
$$
When $c_1=c_2=\cdots=c_r=1$, each word~$w$ in $R({\bf c})$
may be identified with a permutation of $1,2,\ldots ,r$. If it is
of type $A$, then $A$ is the permutation matrix
corresponding to~$w$. The inverse of~$w$ is of type
$A^T$ (the transpose of~$A$).


\proclaim Proposition 3. Let $R({\bf c},A)$ be the set of the
words in $R({\bf c})$ which are of $A$-type. Then the
generating polynomials for $R({\bf c},A)$ and
for $R({\bf c},A^T)$ by the number of internal inversions are
identical. Moreover,
$$\eqalignno{
\sum _{w\in R({\bf c},A)} q^{\intinv w}
&={c_1\brack a(1,1)\ldots a(1,r)}_q\cdots
{c_r\brack a(r,1)\ldots a(r,r)}_q\cr
&={c_1\brack a(1,1)\ldots a(r,1)}_q\cdots
{c_r\brack a(1,r)\ldots a(r,r)}_q\cr
&=\sum _{w\in R({\bf c},A^T)} q^{\intinv w}\cr}
$$

{\it Proof}. As is well-known (see, e.g., [An76, p. 41]) 
the generating polynomial for
the rearrangements of the word $1^{a(1,1)}\ldots r^{a(1,r)}$
by the number of inversions is equal to multinomial coefficient 
${c_1\brack a(1,1)\ldots a(1,r)}_q$.\qed

\medskip
{\it Remarks}.
\smallskip
1) Proposition~3 implies that there exists a bijection of $R({\bf c},A)$ onto
 $R({\bf c},A^T)$ that preserves the number of internal inversions. As will be
 explained, {\it constructing such a bijection} is the crucial problem still
 unsolved.

\smallskip
2) Our transformation $w\mapsto w^*$ gives a bijective proof of Proposition~3 in
the case $q=1$.


\medskip
Say that a word $w=x_1x_2\ldots x_m$ in $R({\bf c},A)$ is {\it
minimal}, it it has {\it no} internal inversions. This means
that all the factors $x_1\ldots x_{c_1}$,
$x_{c_1+1}\ldots x_{c_1+c_2}$, \dots~,
$x_{c_1+\ldots c_{r-1}+1}\ldots x_m$ are nondecreasing.
In each $A$-type class there is one and only one minimal word.
Write it as the bottom word in the
following two-row matrix:
$$
\pmatrix{1&\ldots &1&2&\ldots&2&\ldots&r&\ldots&r\cr
x_1&\ldots&x_{c_1}&x_{c_1+1}&\ldots&x_{c_1+c_2}&\ldots&
x_{c_1+\cdots+c_{r-1}+1}&\ldots&x_m\cr}.
$$
Interchange the two rows; then rearrange
the vertical bi-letters $a'\choose a$ of the resulting two-row
matrix in such a way that the top row becomes
$1^{c_1}2^{c_2}\ldots r^{c_r}$, using the
commutation rule $(\spadesuit)$.
Let $w'$ be the bottom word in the final two-row matrix.
This implies the following proposition.

\proclaim Proposition 4. The mapping $w\mapsto w'$ is an
involution of the set of the minimal words in $R({\bf c})$
that sends each minimal word of $A$-type onto a minimal word of
$A^T$-type. Moreover
$$
\extinv w'=\extinv w.
$$

{\it Example}. The word $w=3,1,2,2$ is minimal and  of type
\smash{$A=\pmatrix{0&0&1\cr
1&1&0\cr
0&1&0\cr}$.} It is mapped onto
$$\displaylines{
\pmatrix{1&2&2&3\cr 3&1&2&2\cr}
\mapsto
\pmatrix{3&1&2&2\cr 1&2&2&3\cr }
=\pmatrix{1&2&2&3\cr
2&2&3&1\cr}\mapsto 2,2,3,1=w',\cr
\noalign{\vskip5pt}}
$$
which is minimal and of type
\smash{$A^T=\pmatrix{0&1&0\cr
0&1&1\cr
1&0&0\cr}$.} Moreover $\extinv w'=\extinv w=3$.

\medskip
In [Kn70] Knuth derived an extension of the Robinson-Schensted correspondence. When
that extension is applied to a {\it minimal} word $w$, it can be viewed as a
one-to-one
mapping of each circuit $\displaystyle{\overline w\choose w}$ onto an ordered pair
of semi-standard Young tableaux $(P,Q)$ of the same shape and the same evaluation.
Again denote that one-to-one mapping by $w\mapsto (P,Q)$. Knuth also proved the
following property:

\medskip

\centerline{\it If $w\mapsto (P,Q)$, then $w'\mapsto (Q,P)$.}

\medskip

As all words belonging to the same class $R({\bf c},A)$ have
the same number of external inversions, the previous two
propositions imply the following theorem.

\proclaim Theorem 5. There exists a bijection
$w\mapsto w'$ of $R({\bf c})$ having the following
properties

\myitem{(N0)}{If $w=\sigma$ is a permutation, then $w'=\sigma^{-1}$;}

\myitem{(N1)}{$w\mapsto w'$ is an involution;}

\myitem{(N2)}{For each biletter $\displaystyle{y\choose x}$, the number of occurrences of
the biletter $\displaystyle{y\choose x}$ in $\displaystyle{\overline w\choose w}$
is equal to the number of occurrences of
the biletter $\displaystyle{x\choose y}$ in~$\displaystyle{\overline w\choose w'}$.}

\myitem{(N2')}{if $w$ is of $A$-type, then $w'$ is of
$A^T$-type;}

\myitem{(N3)}{$\extinv w=\extinv w'$;}

\myitem{(N4)}{If $w$ is a minimal word and $w$ is mapped onto $(P,Q)$ by the
Robinson-Schensted correspondence, then $w'\mapsto (Q,P)$;}

\myitem{(N4')}{$\intinv w=\intinv w'$;}

\myitem{(N4'')}{$\inv w=\inv w'$;}

\medskip


Take the minimal word $w=3122$. We have $w^*=2321$, which is not a minimal word.
We know that our transformation $w\mapsto w^*$ in
section~2 does not verify all the properties of theorem~5. Finding such a
transformation is the open problem that we propose to the reader.

\vfill\eject




% -------------------------------------------------------
\bigskip\bigskip

\vglue 1cm
\vskip1cm plus .2cm minus .2cm


{
%reference pour un article :
\def\article#1|#2|#3|#4|#5|#6|#7|
    {{\leftskip=7mm\noindent
     \hangindent=2mm\hangafter=1
     \llap{#1 \hskip.35em}{#2},
     #3, {\sl #4} {\bf #5} (#6), #7.\par}}
%reference pour un livre :
\def\livre#1|#2|#3|#4|
    {{\leftskip=7mm\noindent
    \hangindent=2mm\hangafter=1
    \llap{#1 \hskip.35em}{#2},
    {``#3,"} #4.\par}}
%reference complementaire :
\def\divers#1|#2|#3|
    {{\leftskip=7mm\noindent
    \hangindent=2mm\hangafter=1
     \llap{#1 \hskip.35em}{#2},
     #3.\par}}
%

%%\eightpoint
\centerline{\bf REFERENCES}

\bigskip\bigskip

\livre [An76]|George E. Andrews|The Theory of
Partitions|London, Addison-Wesley, {\oldstyle 1976}
({\sl Encyclopedia of Math. and Its Appl.}, {\bf 2})|
\smallskip

\livre [CF69]|P. Cartier and D. Foata|Probl\`emes
combinatoires de permutations et r\'earrangements|Berlin,
Springer-Verlag, {1969} ({\sl Lecture Notes in Math.,
{\bf 85}})|
\smallskip

\article [Kn70]|D.E. Knuth|Permutations, matrices, and generalized Young
tableaux|Pacific J. Math.|34|1970|709-727|
\smallskip

\livre [Kn73]|D.E. Knuth|The Art of Computer
Programming,  {\rm vol.~3}, Sorting and
Searching|Addison-Wesley, Reading,  {1973}|
\smallskip

\divers [Kn97]|D.E. Knuth|Private communication, Oct. 1997|
\smallskip

\divers [Kn98]|D.E. Knuth|Private communication, Jan. 1998|
\smallskip

\livre [Lo83]|M. Lothaire|Combinatorics on
words|Reading, Addison-Wesley, $1983$ 
({\sl Encyclopedia of Math. and its Appl.}, {\bf 17})|
\smallskip


\vskip 1cm
\line{\quad\vtop{\halign{#\hfil\cr
Dominique Foata\cr
D\'epartement de math\'ematique\cr
Universit\'e Louis Pasteur\cr
7, rue Ren\'e-Descartes\cr
F-67084 Strasbourg\cr
{\tt foata@math.u-strasbg.fr}\cr}}\hfil
\vtop{\halign{#\hfil\cr
Guo-Niu Han\cr
{\sevenrm I.R.M.A.} et {\sevenrm C.N.R.S.}\cr
Universit\'e Louis Pasteur\cr
7, rue Ren\'e-Descartes\cr
F-67084 Strasbourg\cr
{\tt guoniu@math.u-strasbg.fr}\cr}}\quad}
}





\bye




% ==============================================
% Priviate note



{\it Example}.

The words of type $A=\pmatrix{2&0&1\cr
1&1&1\cr
0&2&0\cr}$ and of type
$A^T=\pmatrix{2&1&0\cr
0&1&2\cr
1&1&0\cr}$

\bigskip
\centerline{%
\vbox{ \halign{\vrule\strut\ \hfil$#$\hfil\ \vrule
&\ \hfil$#$\hfil\ \vrule
&\ \hfil$#$\hfil\ \vrule
&\ \hfil$#$\hfil\ \vrule \cr
\noalign{\hrule}
\intinv&w\in A&w\in A^T&\intinv\cr
\noalign{\hrule}
&1,1,1,2,2,2,3,3&1,1,1,2,2,2,3,3&\cr
\noalign{\hrule}
0&1,1,3,1,2,3,2,2&1,1,2,2,3,3,1,2&0\cr
1&1,3,1,1,2,3,2,2&1,2,1,2,3,3,1,2&1\cr
2&3,1,1,1,2,3,2,2&2,1,1,2,3,3,1,2&2\cr
\noalign{\hrule}
1&1,1,3,1,3,2,2,2&1,1,2,3,2,3,1,2&1\cr
2&1,3,1,1,3,2,2,2&1,2,1,3,2,3,1,2&2\cr
3&3,1,1,1,3,2,2,2&2,1,1,3,2,3,1,2&3\cr
\noalign{\hrule}
1&1,1,3,2,1,3,2,2&1,1,2,3,3,2,1,2&2\cr
2&1,3,1,2,1,3,2,2&1,2,1,3,3,2,1,2&3\cr
3&3,1,1,2,1,3,2,2&2,1,1,3,3,2,1,2&4\cr
\noalign{\hrule}
2&1,1,3,2,3,1,2,2&1,1,2,2,3,3,2,1&1\cr
3&1,3,1,2,3,1,2,2&1,2,1,2,3,3,2,1&2\cr
4&3,1,1,2,3,1,2,2&2,1,1,2,3,3,2,1&3\cr
\noalign{\hrule}
2&1,1,3,3,1,2,2,2&1,1,2,3,2,3,2,1&2\cr
3&1,3,1,3,1,2,2,2&1,2,1,3,2,3,2,1&3\cr
4&3,1,1,3,1,2,2,2&2,1,1,3,2,3,2,1&4\cr
\noalign{\hrule}
3&1,1,3,3,2,1,2,2&1,1,2,3,3,2,2,1&3\cr
4&1,3,1,3,2,1,2,2&1,2,1,3,3,2,2,1&4\cr
5&3,1,1,3,2,1,2,2&2,1,1,3,3,2,2,1&5\cr
\noalign{\hrule}
}}}