\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

\usepackage{fullpage}
\usepackage{amssymb}
\usepackage{amsmath}


\usepackage{graphpap}
\usepackage{graphics}
\usepackage{pst-node,pst-tree,pst-coil,avm}
\usepackage{pstcol, pst-3d}
\input{pst-qtree}
\psset{levelsep=5em}
\usepackage{psfrag}
\usepackage{picins}

\usepackage[numbers]{natbib}
\def\namecite{\citet}

\newtheorem{thm}{Theorem}[section]
\newtheorem{pro}[thm]{Proposition}
\newtheorem{obs}{Observation}[section]
\newtheorem{exc}{Exercise}
\newtheorem{nte}{Note}
\newtheorem{rem}{Remark}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{con}{Conjecture}
\newtheorem{exm}[thm]{Example}
\newenvironment{prf}[1]{\noindent{\bf{Proof #1\\}}}{$\hfill\blacksquare$\nopagebreak[4]\vskip 0.3cm}
\newtheorem{dfn}[thm]{Definition}
\newtheorem{ide}{Idea}
\newtheorem{que}{Question}
\newenvironment{sol}[1]{\noindent{\bf{Solution to Exercise \ref{#1}\\}}}{$\hfill\blacksquare$\nopagebreak\vskip 0.1cm}


\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}

\newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\begin{center}
\vskip 1cm{\LARGE\bf 
Enumeration of Factorizable \\
\vskip .1in
Multi-Dimensional Permutations
}
\vskip 1cm
\large
Hao Zhang and Daniel Gildea\\
Department of Computer Science\\
University of Rochester\\
Rochester, NY  14627 \\
USA\\
\href{mailto:zhanghao@cs.rochester.edu}{\tt zhanghao@cs.rochester.edu} \\
\href{mailto:gildea@cs.rochester.edu}{\tt gildea@cs.rochester.edu} \\
\end{center}

\vskip .2 in

\begin{abstract}
A $d$-dimensional permutation is a sequence of $d+1$ permutations
with the leading element being the identity permutation. 
It can be viewed as an alignment structure across $d+1$ sequences, or 
visualized as the result of permuting $n$ hypercubes of $(d+1)$ dimensions.
% in $(d+1)$-dimensionalspace. 
We study the hierarchical decomposition of $d$-dimensional permutations.
We show that when $d \ge 2$, the ratio between non-decomposable or simple
$d$-permutations and all $d$-permutations approaches $1$. We also prove
that the growth rate of the number of $d$-permutations that can be factorized 
into $k$-ary branching trees approaches $\left(\frac{k}{e}\right)^d$ as
$k$ grows.  
\end{abstract}


\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{conjecture}[theorem]{Conjecture}


\section{Introduction}
The study of multiple permutations has generated recent interest in both computational 
biology and computational linguistics. In 
biology, the original problem was the enumeration of all common intervals
between genetic sequences aligned according to a specified permutation \cite{UnoYag00}, 
which was then generalized to multiple permutations
\cite{HeberStoye01}. 
In linguistics, permutations play an essential role 
in the definition of Syntax Directed Translation Schemata \cite{AhoUll72}, 
or equivalently Synchronous Context Free Grammars (SCFG) \cite{SattaPeserico05},
which model language translation by generating strings in two languages in parallel. 
\namecite{Melamed-naacl03}
generalized SCFG to ``multitexts'' of more than two languages,
which also require multiple permutations. 
In both domains, factoring long permutations into compositions of
smaller permutations has proved important.
This technique is used as a representational tool for compactly 
representing common intervals of gene sequences \cite{Landau05}, and also as a method
to model language translation using synchronous grammars with limited-length
rules, which in turn admit efficient parsing algorithms \cite{Zhang-gildea-tr06}.

\namecite{AlbertAtkinsonKlazar03} pioneered the combinatorial study of permutation
factorization, studying the one-dimensional case.
Albert et al.\ first reported the sequence of the number of simple permutations of $n$
(sequence A111111 of \cite{sloane}) 
and showed the fundamental role of simple permutations for generating all
permutations. In this paper, we take a similar analytical approach
to study the generalized problems of the factorization of $d$-dimensional permutations 
and the enumeration of $d$-dimensional simple permutations. We discover
a new family of integer sequences $H_{d,n}$: the number of simple $d$-dimensional 
permutations of $n$. The first $8$ elements of $H_{2}$ are
\[1, 4, 8, 172, 5204, 222716, 12509188, 889421564, \dots \]

In Section~\ref{sec:defs}, we formally define a $d$-dimensional permutation 
that induces the alignment view for both interval
commonality in genomics and word
translational equivalence in linguistics. We also define $d$-permutation trees
as a structural analysis and description tool for $d$-dimensional permutations. 
In Section~\ref{sec:mathkd}, we develop the generating function for $k$-ary
$d$-permutation trees. In Section~\ref{sec:dsimp}, we study the asymptotics
of $d$-dimensional simple permutations. In Section~\ref{sec:gog}, we study
the growth rates of $k$-ary $d$-permutations. 


%\namecite{Landau05} use PQ tree as the representational tool, and
%hint the specialization of PQ trees by assigning exact permutations
%to the P nodes. 
% Variations of this idea go back to \namecite{AhoUll72}'s Syntax-Directed
% Translation Systems, but also include \namecite{DekaiCL}'s Inversion 
% Transduction Grammar, which restricts grammar rules to be binary, 
% as well as tree-transformation models of 
% translation such as \namecite{YamadaKnight01}, \namecite{galley-naacl04}, and \namecite{Chiang-acl05}.

\section{Multi-dimensional Permutations}\label{sec:defs}
% We begin with the definition of $d$ dimensional permutations. An ordinary or one dimensional {\em permutation}
% is a bijective function from the set of $\{1,...,n\}$ to the set of $\{1,...,n\}$, conventionally
% denoted as $\pi$, where $\pi(i)=j$ means the number $i$ in the domain 
% is mapped to the number $j$ in the range. A {\em $d$ dimensional permutation} is
% a sequence of $d$ one dimensional permutations, represented as $\pi=(\pi_{1},...,\pi_{d})$ 
% where we use the notion of $\pi_{d'}$ ($1 \le d' \le d$) 
% to denote the component function for the $d'$-th dimension. 

% There are two views of the function of $\pi$. In both views, we
% start from the sequence of $(1,...,n)$, and 
% generate a total of $d$ permuted sequences through mapping. 
% In the first view, we put 
% the number $\pi_{d'}(i)$ at the $i$-th position in the $d'$-th sequence. In the second view,
% we put the number $i$ to the $\pi_{d'}(i)$-th position in the $d'$-th sequence. ILLUSTRATED EXAMPLE NEEDED HERE.

% We call the first view the functional view, because 
% the resultant $d'$-th sequence read off from left to right is
% exactly the image sequence of $(\pi_{d'}(1),...,\pi_{d'}(n))$, a
% straightforward compact representation of $\pi_{d'}$. 
% We call the second view the alignment view. In the alignment view, what
% we read off from left to right on the resultant sequence 
% in each dimension is actually the image sequence of the inverse
%of the respective component function: $(\pi_{d'}^{-1}(1),...,\pi_{d'}^{-1}(n))$.  
%So, since $(\pi_{d'}^{-1})^{-1}=\pi_{d'}$, when we are interested in the 
%function $\pi$ but are given the alignment view, we can simply take the inverse of the
%functional view of each dimension. 
%The two views are interchangeable by taking the functional inverse in
%each dimension. 

%A (one dimensional) permutation
%can be graphically represented as a permutation matrix in which each column and
%each row has exactly one elment being $1$ and the rest being $0$. A $2$ dimensional permutation
%can be visualized in $3D$ space as a cube in which each cutting plane of size $n$ by $n$ has
%exactly one element being $1$ with the rest being $0$. ILLUSTRATED EXAMPLE HERE.

\begin{figure*}
\begin{center}
\begin{tabular}{cccc}
\resizebox{2.5in}{!}{
\begin{pspicture}(15, 15)
%\psgrid
\rput(1, 2){\rnode{id1}{\Huge $1$}}
\rput(5, 2){\rnode{id2}{\Huge $2$}}
\rput(9, 2){\rnode{id3}{\Huge $3$}}
\rput(13, 2){\rnode{id0}{\Huge $4$}}

\rput(1, 7){\rnode{pi11}{\Huge $2$}}
\rput(5, 7){\rnode{pi12}{\Huge $1$}}
\rput(9, 7){\rnode{pi13}{\Huge $3$}}
\rput(13, 7){\rnode{pi10}{\Huge $4$}}

\rput(1, 12){\rnode{pi21}{\Huge $2$}}
\rput(5, 12){\rnode{pi22}{\Huge $3$}}
\rput(9, 12){\rnode{pi23}{\Huge $1$}}
\rput(13, 12){\rnode{pi20}{\Huge $4$}}

\ncline{id0}{pi10}
\ncline{id1}{pi12}
\ncline{id2}{pi11}
\ncline{id3}{pi13}

\ncline{pi10}{pi20}
\ncline{pi11}{pi21}
\ncline{pi12}{pi23}
\ncline{pi13}{pi22}
\end{pspicture}
}&&&
\resizebox{2.5in}{!}{
\begin{pspicture}(15, 15)
%\psgrid
\rput(1, 2){\rnode{id1}{\Huge $1$}}
\rput(5, 2){\rnode{id2}{\Huge $2$}}
\rput(9, 2){\rnode{id3}{\Huge $3$}}
\rput(13, 2){\rnode{id0}{\Huge $4$}}

\rput(1, 7){\rnode{pi11}{\Huge $2$}}
\rput(5, 7){\rnode{pi12}{\Huge $1$}}
\rput(9, 7){\rnode{pi13}{\Huge $3$}}
\rput(13, 7){\rnode{pi10}{\Huge $4$}}

\rput(1, 12){\rnode{pi21}{\Huge $3$}}
\rput(5, 12){\rnode{pi20}{\Huge $4$}}
\rput(9, 12){\rnode{pi22}{\Huge $2$}}
\rput(13, 12){\rnode{pi23}{\Huge $1$}}

\ncline{id0}{pi10}
\ncline{id1}{pi12}
\ncline{id2}{pi11}
\ncline{id3}{pi13}

\ncline{pi10}{pi20}
\ncline{pi11}{pi22}
\ncline{pi12}{pi23}
\ncline{pi13}{pi21}
\end{pspicture}
}
\end{tabular}
\end{center}
\caption{
2-dimensional permutations $((2,1,3,4),(2,3,1,4))$ (left)
and $((2,1,3,4), (3,4,2,1))$ (right)
}\label{fig:twodperm}
\end{figure*}


We begin with the definition of multi-dimensional permutations. 
An ordinary or one-dimensional {\em permutation} 
is a bijective function from the set $\{1,\dots,n\}$ to the same set, conventionally 
denoted by $\pi$.
%, where $\pi(i)=j$ means the number $i$ in the domain 
%is mapped to the number $j$ in the range. 
A permutation is usually
written compactly as the functional image sequence $\pi=(\pi(1),\dots,\pi(n))$. A permutation
can also be thought of as an alignment between the two sequences $(1,\dots,n)$ and
$(\pi(1),\dots,\pi(n))$ where identical numbers from both sides are linked together. 
A {\em $d$-dimensional permutation}, abbreviated as {\em $d$-permutation}, is
a sequence of $d$ one-dimensional permutations, represented as $\pi=(\pi_{1},\dots,\pi_{d})$ 
where we use the notation $\pi_{d'}$ ($1 \le d' \le d$) 
to denote the component function for the $d'$-th dimension. 
A multi-dimensional permutation
can be viewed as a multilateral alignment across the identity permutation $id_{n}=(1,\dots,n)$ and
the remaining permutations $\pi_{1},\dots \pi_{d}$. Figure~\ref{fig:twodperm} shows two examples
of $2$-dimensional permutations. To visualize $2$-dimensional permutations better, we can plot the numbers in the 3-dimensional cube of size $n$
that has $n^3$ 
unit cubes of size $1$. A $2$-dimensional permutation is an arrangement of
$n$ numbers into $n$ of the $n^3$ positions with the permutation constraints
from all dimensions. Figure~\ref{fig:3dview} demonstrates the $3$-d view
for the same two examples. 


\begin{figure*}
\begin{center}
\begin{tabular}{c}
\resizebox{3in}{!}{
\begin{pspicture}(-5,-1)(1,4)
\psset{unit=1cm}
\psset{viewpoint=-2.5 4 1}
\psset{griddots=10}
\psset{gridlabels=0}
\psset{subgriddiv=1}
\ThreeDput[normal=0 0 1]{\psline[linewidth=0.8mm]{->}(0, 0)(4.5, 0)}
\ThreeDput[normal=0 0 1]{\psline[linewidth=0.8mm]{->}(0, 0)(0, 4.5)}
\ThreeDput[normal=0 -1 0]{\psline[linewidth=0.4mm]{->}(0, 0)(0, 4.3)}
%
\ThreeDput[normal=0 0 1]{\psgrid(0, 0)(4, 4)}
\ThreeDput[normal=0 -1 0]{\psgrid(0, 0)(4, 4)}
%
\ThreeDput[normal=0 1 0]{\rput(-0.5, 4.3){\psframebox*[border=0pt]{1}}}
\ThreeDput[normal=0 1 0]{\rput(-1.5, 4.3){\psframebox*[border=0pt]{2}}}
\ThreeDput[normal=0 1 0]{\rput(-2.5, 4.3){\psframebox*[border=0pt]{3}}}
\ThreeDput[normal=0 1 0]{\rput(-3.5, 4.3){\psframebox*[border=0pt]{4}}}
%
\ThreeDput[normal=-1 0 0]{\rput(0.3, 0.5){\psframebox*[border=0pt]{2}}}
\ThreeDput[normal=-1 0 0]{\rput(0.3, 1.5){\psframebox*[border=0pt]{3}}}
\ThreeDput[normal=-1 0 0]{\rput(0.3, 2.5){\psframebox*[border=0pt]{1}}}
\ThreeDput[normal=-1 0 0]{\rput(0.3, 3.5){\psframebox*[border=0pt]{4}}}
%
\ThreeDput[normal=-1 0 0]{\rput(-0.5, -0.3){\psframebox*[border=0pt]{2}}}
\ThreeDput[normal=-1 0 0]{\rput(-1.5, -0.3){\psframebox*[border=0pt]{1}}}
\ThreeDput[normal=-1 0 0]{\rput(-2.5, -0.3){\psframebox*[border=0pt]{3}}}
\ThreeDput[normal=-1 0 0]{\rput(-3.5, -0.3){\psframebox*[border=0pt]{4}}}
%
\psset{border=0.5pt}
\psset{bordercolor=black}
\ThreeDput[normal=0 0 1](0, 1, 3){
\psframe*[linecolor=darkgray](1, 1)}
\ThreeDput[normal=0 1 0](1, 2, 2){
\psframe*[linecolor=white](1, 1)}
\ThreeDput[normal=0 1 0](0.5, 2, 2.5){
\psframebox*[border=0pt]{1}}
\ThreeDput[normal=-1 0 0](0, 2, 2){
\psframe*[linecolor=gray](1, 1)}
\ThreeDput[normal=0 0 1](1, 0, 1){
\psframe*[linecolor=darkgray](1, 1)}
\ThreeDput[normal=0 1 0](2, 1, 0){
\psframe*[linecolor=white](1, 1)}
\ThreeDput[normal=0 1 0](1.5, 1, 0.5){
\psframebox*[border=0pt]{2}}
\ThreeDput[normal=-1 0 0](1, 1, 0){
\psframe*[linecolor=gray](1, 1)}
\ThreeDput[normal=0 0 1](2, 2, 2){
\psframe*[linecolor=darkgray](1, 1)}
\ThreeDput[normal=0 1 0](3, 3, 1){
\psframe*[linecolor=white](1, 1)}
\ThreeDput[normal=0 1 0](2.5, 3, 1.5){
\psframebox*[border=0pt]{3}}
\ThreeDput[normal=-1 0 0](2, 3, 1){
\psframe*[linecolor=gray](1, 1)}
\ThreeDput[normal=0 0 1](3, 3, 4){
\psframe*[linecolor=darkgray](1, 1)}
\ThreeDput[normal=0 1 0](4, 4, 3){
\psframe*[linecolor=white](1, 1)}
\ThreeDput[normal=0 1 0](3.5, 4, 3.5){
\psframebox*[border=0pt]{4}}
\ThreeDput[normal=-1 0 0](3, 4, 3){
\psframe*[linecolor=gray](1, 1)}

\ThreeDput[normal=1 0 0]{\psgrid(0, 0)(4, 4)}
\end{pspicture}
}\\
\\
\resizebox{3in}{!}{
\begin{pspicture}(-5,-1)(1,4)
\psset{unit=1cm}
\psset{viewpoint=4.5 1.5 1}
\psset{viewpoint=3.5 2 1}
\psset{griddots=10}
\psset{gridlabels=0}
\psset{subgriddiv=1}
\ThreeDput[normal=0 0 1]{\psline[linewidth=0.8mm]{->}(0, 0)(4.5, 0)}
\ThreeDput[normal=0 0 1]{\psline[linewidth=0.8mm]{->}(0, 0)(0, 4.5)}
\ThreeDput[normal=0 -1 0]{\psline[linewidth=0.4mm]{->}(0, 0)(0, 4.3)}
%
\ThreeDput[normal=0 0 1]{\psgrid(0, 0)(4, 4)}
\ThreeDput[normal=0 -1 0]{\psgrid(0, 0)(4, 4)}
\ThreeDput[normal=1 0 0]{\psgrid(0, 0)(4, 4)}
%
%
\ThreeDput[normal=0 1 0]{\rput(-0.5, 4.3){\psframebox*[border=0pt]{1}}}
\ThreeDput[normal=0 1 0]{\rput(-1.5, 4.3){\psframebox*[border=0pt]{2}}}
\ThreeDput[normal=0 1 0]{\rput(-2.5, 4.3){\psframebox*[border=0pt]{3}}}
\ThreeDput[normal=0 1 0]{\rput(-3.5, 4.3){\psframebox*[border=0pt]{4}}}
%
\ThreeDput[normal=1 0 0](4, 0, 0){\rput(-0.3, 0.5){\psframebox*[border=0pt]{3}}}
\ThreeDput[normal=1 0 0](4, 0, 0){\rput(-0.3, 1.5){\psframebox*[border=0pt]{4}}}
\ThreeDput[normal=1 0 0](4, 0, 0){\rput(-0.3, 2.5){\psframebox*[border=0pt]{2}}}
\ThreeDput[normal=1 0 0](4, 0, 0){\rput(-0.3, 3.5){\psframebox*[border=0pt]{1}}}
%
\ThreeDput[normal=1 0 0](4, 0, 0){\rput(0.5, -0.3){\psframebox*[border=0pt]{2}}}
\ThreeDput[normal=1 0 0](4, 0, 0){\rput(1.5, -0.3){\psframebox*[border=0pt]{1}}}
\ThreeDput[normal=1 0 0](4, 0, 0){\rput(2.5, -0.3){\psframebox*[border=0pt]{3}}}
\ThreeDput[normal=1 0 0](4, 0, 0){\rput(3.5, -0.3){\psframebox*[border=0pt]{4}}}
%
\psset{border=0.5pt}
\psset{bordercolor=black}

\ThreeDput[normal=0 0 1](0, 1, 4){
\psframe*[linecolor=darkgray](1, 1)}
\ThreeDput[normal=0 1 0](1, 2, 3){
\psframe*[linecolor=gray](1, 1)}
\ThreeDput[normal=1 0 0](1, 1, 3){
\psframe*[linecolor=white](1, 1)}
\ThreeDput[normal=1 0 0](1, 1.5, 3.5){
\psframebox*[border=0pt]{1}}
\ThreeDput[normal=0 0 1](1, 0, 3){
\psframe*[linecolor=darkgray](1, 1)}
\ThreeDput[normal=0 1 0](2, 1, 2){
\psframe*[linecolor=gray](1, 1)}
\ThreeDput[normal=1 0 0](2, 0, 2){
\psframe*[linecolor=white](1, 1)}
\ThreeDput[normal=1 0 0](2, 0.5, 2.5){
\psframebox*[border=0pt]{2}}
\ThreeDput[normal=0 0 1](2, 2, 1){
\psframe*[linecolor=darkgray](1, 1)}
\ThreeDput[normal=0 1 0](3, 3, 0){
\psframe*[linecolor=gray](1, 1)}
\ThreeDput[normal=1 0 0](3, 2, 0){
\psframe*[linecolor=white](1, 1)}
\ThreeDput[normal=1 0 0](3, 2.5, 0.5){
\psframebox*[border=0pt]{3}}
\ThreeDput[normal=0 0 1](3, 3, 2){
\psframe*[linecolor=darkgray](1, 1)}
\ThreeDput[normal=0 1 0](4, 4, 1){
\psframe*[linecolor=gray](1, 1)}
\ThreeDput[normal=1 0 0](4, 3, 1){
\psframe*[linecolor=white](1, 1)}
\ThreeDput[normal=1 0 0](4, 3.5, 1.5){
\psframebox*[border=0pt]{4}}
\end{pspicture}
}
\end{tabular}
\end{center}
\hspace{0.8in}
\caption{
Three-dimensional view of the 2-dimensional permutations $((2,1,3,4),(2,3,1,4))$ (top)
and $((2,1,3,4), (3,4,2,1))$ (bottom). If we project the cubes
onto each axis, we can read off the permutation in each dimension. 
}\label{fig:3dview}
\end{figure*}

\subsection{Multi-dimensional Permutation Trees}\label{sec:multree}
In this section, we introduce the hierarchical view
of multi-dimensional permutations. We start with
the hierarchical decomposition of one-dimensional permutations.
We define a {\em permuted sequence} as a permutation of a sequence of consecutive 
natural numbers ranging from $min$ to $max$. A standard
permutation is the special case where $min=1$ and $max=n$. 
We use the range notation
$[min \dots max]$ to denote a permuted sequence when it
is considered as a block that can be permuted as a unit with
other blocks of numbers.
%its 
%internal order is irrelevant . 
A permutation can possibly be partitioned into permuted sequences which themselves can contain
even shorter permuted sequences, thus specifying 
a hierarchical decomposition. 
\namecite{AlbertAtkinsonKlazar03} discuss the subset of permutations
that do not have a decomposition which are called {\em simple permutations}.
\namecite{Zhang-gildea-tr06} analyze the spectrum of decomposable permutations
based on their minimum branching factors. 
%CITATIONS HERE.

In a multi-dimensional permutation, 
a permuted sequence of numbers in one dimension may not form a permuted sequence
in other dimensions.  In order to produce a single factorization, we are interested in
decompositions that guarantee the consistency of permuted sequences
across {\em all} dimensions. Hence we have the notion of {\em $d$-dimensional
permuted sequence}, which is a $d$-dimensional permutation of
the consecutive range of numbers in $[min \dots max]$. Similarly,
a $d$-dimensional permutation becomes the special case when $min=1$ and
$max=n$. We call a $d$-dimensional permuted sequence
{\em $k$-ary ($k \ge 1$) parsable} if and only if one of the following
conditions holds:
\begin{enumerate}
\item The permuted sequence only has one number, i.e., $min=max$.
\item It has more than one number and can be consistently segmented
into $k'$ ($2 \le k' \le k$) permuted sequences in all $d$ dimensions. 
The permuted sequences sharing the same $[min \dots max]$ range are linked
across the dimensions to form a $d$-dimensional permuted sequence. 
Each of the $k'$ $d$-dimensional permuted sequences is also $k$-ary parsable. 
\end{enumerate}

The above definition is a recursive one, and implies a recursive structure
that we call a {\em $d$-dimensional permutation tree}. We use the $d$-dimensional
permutation applied on the children as the label for each parent node. 
The maximum number of children of any node in
the tree is called the branching factor of the tree. A $k$-ary parsable
$d$-dimensional permutation has a branching factor no larger than $k$.
We are interested in minimizing the branching factor for a given multi-dimensional
permutation. 
The two examples in Figure~\ref{fig:twodperm} can be decomposed into a ternary
tree and a binary tree, respectively. The case $((2,1,3,4),(2,3,1,4))$ can not be binarized
because $(2,1)$ is not a permuted sequence in the second dimension. 
However, the case $((2,1,3,4), (3,4,2,1))$ can be binarized as $(((2,1),(3,4)),((3,4),(2,1)))$.
Figure~\ref{fig:twodpermtree} shows the tree structures of the two examples.

\begin{figure*}
\begin{center}
\begin{tabular}{cc}
$\begin{array}{c} \Tree[.{$\left(\begin{array}{cc}1&2\\1&2\end{array}\right)$} [.{$\left(\begin{array}{ccc}2&3&1\\2&1&3\end{array}\right)$} 1 2 3 ] 4 ]\end{array}$&
$\begin{array}{c} \Tree[.{$\left(\begin{array}{cc}2&1\\1&2\end{array}\right)$} [.{$\left(\begin{array}{cc}2&1\\2&1\end{array}\right)$} 1 2 ] [.{$\left(\begin{array}{cc}1&2\\1&2\end{array}\right)$} 3 4 ] ] \end{array}$\\
\end{tabular}
\end{center}
\caption{
$2$-dimensional permutation trees for $((2,1,3,4),(2,3,1,4))$ (left)
and $((2,1,3,4), (3,4,2,1))$ (right). The labels for the intermediate
nodes are $2$-dimensional permutations indicating the reordering of
the children in each dimension. 
}\label{fig:twodpermtree}
\end{figure*}

%More specifically, we provide a top-down generative view
%of a $d$ dimensional permutation. 
%We define a {\em $d$ dimensional permuted sequence}
%as a $d$ dimensional permutation of a consecuitive sequence $[min \dots max]$.
%A $d$ dimensional permuted sequence is said to be {\em parsable} 


\subsection{Factorization Algorithms}
%OUTLINE the existing algorithms. 
The particular recursive definition for permutation is
natural in the context of Synchronous Context Free Grammars \cite{SattaPeserico05}, \cite{ZHGK-naacl06}.
\namecite{Zhang-gildea-tr06} generalize the definition in \cite{ZHGK-naacl06} 
from binary permutation trees to
trees with an arbitrary maximum branching factor. In Section~\ref{sec:multree}, 
we generalized the definition to $d$-permutations. 
We follow the same line of generalization for the factorization algorithm. The main
idea of the algorithms is left-to-right scanning and 
greedy recursive reduction on permuted sequences. 

The other line of development is in the context of finding
all common intervals of permutations. \namecite{UnoYag00}
is the breakthrough work that presents a clever algorithm
optimal in time complexity: $O(n+K)$, where $K$ is the 
number of common intervals between two permutations. 
The algorithm 
is then generalized to $d$ permutations by \namecite{HeberStoye01}, with
an $O(d \cdot n + K)$ complexity. 
The main idea of these algorithms is right-to-left
scanning and elimination of impossible right boundaries
for reductions. 

\namecite{Landau05} and \namecite{BuiXuan05} bridge 
the two lines of research by introducing PQ tree
as a representational tool. 
PQ trees represent families of one-dimensional permutations that 
can be created by composing operations of 
scrambling subsequences according to any permutation (P nodes)
and concatenating subsequences in order (Q nodes).
Our definition of $d$-permutation tree 
can be thought of as a more specific version of a PQ tree, where the nodes
are all labeled with a specific multidimensional permutation
that is not decomposable.  

\namecite{BuiXuan05} 
modify the original Uno\&Yagiura algorithm
by introducing greedy recursive reductions,
producing a tree-like representation from which 
all common intervals can be easily enumerated. 
Their algorithm solves
the $d$-permutation factorization problem 
in $O(d \cdot n)$ time. 


%\namecite{Bergeron05},


\subsection{Uniqueness of Normalized Factorization}
Roughly speaking, the minimum tree decomposition of a $d$-dimensional permutation is
unique upon normalization. 
%Two minimum branching decompositon trees can differ
%only at binary branching nodes. Depending on the preference for
%a left-heavy or right-heavy tree, one can binarize a monotonical 
%$d$ dimensional permuted sequence accordingly. As an example,
%the $2$ dimensional permutation $((1,2,3),(3,2,1))$ which is
%monotonical in both dimensions can be
%binarized into $(((1,2),3), (3,(2,1)))$ or $((1,(2,3)), ((3,2),1))$. 
%So if we define a normalized tree as the one that results in
%the left-heavy projected tree in the identity permutation, we
%will guarantee the uniqueness of decomposition. 
%One
%proof for the uniqueness depends on the correctness proof
%of the left-to-right shift-reduce algorithm we will discuss
%in the following section. 
If a $d$-dimensional permutation of $n$ has a $k$-ary tree, 
we can always produce a normalized tree 
%which agrees with the output of the $k$-arizer
that is minimized and left-heavy. 
%In other words, the permutation must
%be accepted by the $k$-arizer.

%CITE The simple permutation paper and our paper.
\namecite{AlbertAtkinsonKlazar03} present a theorem on the
uniqueness of one-dimensional permutation decomposition. 
%discuss the subset of permutations, 
%that do not have a decomposition which are named as {\em simple permutations}.
\namecite{Zhang-gildea-tr06} prove the uniqueness of permutation
factorization from
an algorithmic perspective. The main idea is that if there
are two overlapping permuted sequences in a permutation, 
the overlapping portion itself must be a permuted sequence
and the ambiguity can be succinctly captured as two possible
binarization patterns: $((1, 2), 3)$ versus $(1, (2, 3))$ or 
equivalently $(3, (2, 1))$ versus $((3, 2), 1)$ for 
three consecutive blocks. The basic structure of ambiguity
is the same for $d$-dimensional permutations: multiple 
bracketings are possible only in the case of groups of binary nodes
labeled with the same internal permutation.
However, there are now $2^d$ possible types of binary ambiguities,
depending on the internal permutation,
instead of only two types for one-dimensional permutations. 
We can perform two types of operations to 
make sure we prefer the left-heavy minimal trees. 


The first type of normalization operation is {\em node expansion}. 
If a $d$-permutation being applied in the tree can be further parsed 
into a subtree with a smaller branching factor, we replace the original node 
with the tree fragment made up by these elementary permutations. We
iteratively do the expansion until no node in the transformed tree
can be expanded. 
This process ensures that we only use long $d$-permutations when absolutely necessary.
%For example, of the 24 permutations possible with a 4-ary rule, 
%only the two permutations that cannot be produced using binary rules
%will ever appear in our normalized parses. 
Another way of stating this property is that no $d$-permutation in the tree
has any strict subset of children that is consecutive in all $d+1$ dimensions.

\begin{figure*}
\begin{center}
\begin{tabular}{ccc}
\resizebox{2in}{!}{
\Tree [.{$\left(\begin{array}{cc}2&1\\1&2\end{array}\right)$} $Subtree_1$ [.{$\left(\begin{array}{cc}2&1\\1&2\end{array}\right)$} $Subtree_2$ [.{$\left(\begin{array}{cc}2&1\\1&2\end{array}\right)$} $Subtree_3$ $\dots$ ] ] ]
%\Tree [.S [.B [.B [.A [.C 1/3 ] [.C 2/4 ] ] [.C 3/2 ] ] [.C 4/1 ] ] ]
}
&
$=>$
&
\resizebox{2in}{!}{
\Tree [.{$\left(\begin{array}{cc}2&1\\1&2\end{array}\right)$} [.{$\left(\begin{array}{cc}2&1\\1&2\end{array}\right)$} [.{$\left(\begin{array}{cc}2&1\\1&2\end{array}\right)$} $Subtree_1$ $Subtree_2$ ] $Subtree_3$ ] $\dots$ ]
%\Tree [.S [.B [.B [.A [.C 1/3 ] [.C 2/4 ] ] [.C 3/2 ] ] [.C 4/1 ] ] ]
}
\end{tabular}
\end{center}
\caption{
  Spine Rotation
}\label{fig:spine-rot}
\end{figure*}

The second type of normalization operation is {\em spine rotation},
and applies only to binary nodes. 
% First of all, it is convenient to turn the $k$-ary parse tree into an equivalent
% binary parse tree. If a node is $k_1$-ary, where $3 \le k_1 \le k$, we create a virtual 
% node for the children from number $2$ to number $k_1$, and let the virtual node
% be the child right to the number $1$ child under the parent node. 
% The virtual node can be further binarized. Finally, by creating $k_1-2$ virtual 
% nodes, the original $k_1$-ary node can be binarized in a right-heavy manner. 
% After binarizing all the fan-out-more-than-two nodes, we have a binary tree 
% in which each node is either a leaf or a binary branching internal node. 
First, we label each internal node with its $d$-permutation. 
A spine is a sequence of nodes 
such that each node is the rightmost-child of the 
previous node. If we discover a section of consecutive identical binary $d$-permutation labels on a spine, 
we rotate the section to the left side as shown in 
Figure~\ref{fig:spine-rot}. 
%It is easy to verify that the new parse
%is still a valid parse for the given permutation. 
%This also holds if we
%discover consecutive $(2,1)$ labels on a spine. 
We apply the rotation
iteratively until no spine in the transformed tree has 
consecutive identical binary nodes. 
%consecutive $(1,2)$
%labels or consecutive $(2,1)$ labels. 
%The spine rotation operation 
%is the same as the normalization done for ITG by \namecite{DekaiCL}.

The resultant parse tree yields the same $d$-permutation
as before normalization, but with a minimized branching factor
and left-most bracketing structure wherever there are multiple
bracketings. The left-most preference for resolving binarization ambiguity
is also used by both \namecite{ShapiroStephens91} and \namecite{DekaiCL} for
the case of $k=2$ and $d=1$. 

%The proof for the uniqueness of normalized $d$-permutation trees 
%is a straightforward generalization of the one-dimensional case. 

\section{The number of $k$-ary parsable $d$-permutations}\label{sec:mathkd}
%In this section, we discuss the behavior of the number of $k$-arizable 
%$d$-permutations of length $n$ as both $n$ and $k$ increase.
In this section, we develop the recurrence and the generating
function for $k$-ary parsable $d$-permutations by counting
the $k$-ary $d$-permutation trees. The counting technique
is a generalization of that of \namecite{ShapiroStephens91}, who studied
the special case where $k=2$ and $d=1$. 

In the previous section, we 
have stated the one-to-one correspondence between $d$-dimensional permutations
and their normalized parses. We can count the normalized $d$-dimensional permutation
trees with $n$ leaves and a maximum of $k$ children for any internal node.
We focus on the cases where $d \ge 2$. 
%we have shown that if we partition the set
%of $k$-ary permutation trees according to the permutations of the leaves that they describe, the
%trees in each partition can be normalized to one {\em standard} permutation
%tree which is the output of the $k$-arizer. So, the number of 
%permutations of $n$ that are $k$-ary parsable is the
%number of the partitions, which is the number of standard permutation
%trees having $n$ leaves. 

We let $S_{d,k}[n]$ ($d \ge 2$, $k \ge 2$, $n \ge 1$)
be the number of $k$-ary parsable $d$-permutations of
length $n$.

The standard trees have two defining properties according to the
two-step normalization:
\begin{enumerate}
\item A $k$-ary $d$-permutation is used 
if and only if 
it is not $k-1$ parsable.  We define $H_{d,k}$ to be the number of such simple or non-decomposable 
$k$-ary $d$-permutations applied in the trees:
\begin{eqnarray}
H_{d, k}=(k!)^{d}-S_{d, k-1}[k] . \label{eq:H}
\end{eqnarray}
%$H_{k}$ is non-trivial only for $k \ge 3$. We know $H_{1}=1$, and $H_{2}=2$. 
%It is also easy to verify that $H_{3}=0$.
\item No two identical binary $d$-permutations can be applied consecutively on
any spine.
\end{enumerate}

From now on, the term {\em permutation tree} will refer to a normalized tree.

We use $A_{d}[k][i]$ to represent the number of 
ways of labeling a rightmost spine having $i$ internal nodes
in a binarized version of any $k$-ary permutation tree.
To help derive the recurrence for $A_{d}$, we can divide spines into
cases where the last child is one of the $2^{d}$ binary $d$-permutations
($A_{d,b}$ for $b=1, \dots, 2^{d}$) 
%straight binary rule (which we denote $A_{[]}$),
%an inverted binary rule ($A_{\langle\rangle}$), 
or one of the non-binary $d$-permutations
($A_{d,*}$)

\begin{eqnarray}
A_{d,b}[k][i] &=& A_{d}[k][i-1] - A_{d,b}[k][i-1]\hspace{3em} (b=1, \dots, 2^{d}) \nonumber \\
A_{d,*}[k][i] &=& \sum_{k'=3}^{k}{H_{d, k'} \cdot A_{d}[k][i-k'+1]} \nonumber \\
A_{d}[k][i] &=& \sum_{b'=1}^{2^{d}}{A_{d, b'}[k][i]} +A_{d, *}[k][i] . \label{eq:a}
\end{eqnarray}

Eq.~\ref{eq:a} can be simplified into a recurrence on $A$ itself
\begin{eqnarray}
A_{d}[k][i] &=& \sum_{b'=1}^{2^{d}}{(A_{d}[k][i-1]-A_{d, b'}[k][i-1])} +A_{d, *}[k][i] \nonumber\\
        &=& 2^{d}A_{d}[k][i-1]-\sum_{b'=1}^{2^{d}}{A_{d, b'}[k][i-1]} + A_{d, *}[k][i] \nonumber\\
        &=& 2^{d}A_{d}[k][i-1]-(A_{d}[k][i-1]-A_{d, *}[k][i-1])+ A_{d, *}[k][i] \nonumber\\
        &=& (2^{d}-1)A_{d}[k][i-1] + \sum_{k'=3}^{k}{H_{d, k'} \cdot (A_{d}[k][i-k']+A_{d}[k][i-k'+1])} . \label{eq:asimp}
\end{eqnarray}

The base cases of the recurrence are $A_{d}[k][0]=1$ and $A_{d}[k][1]=2^{d}$. 

Based on the numbers of spines, we count
the $k$-ary permutation trees with $n$ leaves as follows:
%
\begin{eqnarray}
S_{d, k}[n]=\sum_{i=1}^{n-1}{A_{d}[k][i] \cdot \sum_{\substack{l_1 \dots l_{i}\\ {\sum_{j} l_j=n-1}}} \prod_{j=1}^{i} S_{d, k}[l_j] } \label{eq:ssimp1}
\end{eqnarray}
%
with the base case $S_{d, k}[1]=1$.
The outermost summation is over spines of different lengths $i$. The inner
summation is over all possible distributions of $n-1$ children into the $i$ subtrees attached to the
spine.  
%This inner summation is equivalent to convolving the sequence $S_k$ with itself $i$ times: 
%\begin{eqnarray}
%S_{d, k}[n]=\sum_{i=1}^{n-1}{A_{d}[k][i] \cdot (\overbrace{S_{d, k} \otimes S_{d, k} \otimes \ldots S_{d, k}}^i )[n-1] } \label{eq:ssimp1}
%\end{eqnarray}
%

To simplify the equation, we enter the domain of generating functions. 
A sequence's generating function $R$ is defined as a power series of a new variable, $x$,
where each term $x^n$ has as its coefficient the $n$th term of the series. 
We define the generating function for $S_{d,k}$ as 
\[ R_{d,k}(x) = \sum_{n=1}^{\infty}{S_{d, k}[n] \cdot x^n} . \nonumber \]
which can be interpreted as an infinite sum of all $d$-dimensional $k$-ary permutation trees.
%One convenient property of generating functions for our purposes is that convolving
%two sequences corresponds to multiplying their generating functions.
Starting with eq.~\ref{eq:ssimp1}, 
%we can derive a much simpler 
%counterpart for the generating function $R_{d,k}(x)$:
we can derive the following equation for $R_{d,k}(x)$: 
%
%\begin{eqnarray}
%R_k(x) &=& \sum_{n=1}^{\infty}{S_{k}[n] \cdot x^n} \nonumber \\
%%       &=& x+ x \cdot \sum_{n=1}^{\infty}{S_{k}[n+1] \cdot x^n} \nonumber \\
%       &=& x+ x \cdot \sum_{n=1}^{\infty}{\left(  \sum_{i=1}^{n}{A[k][i] \cdot \sum_{\substack{l_1...l_{i}\\ {\sum_{j} l_j=n}}} \prod_{j=1}^{i} S_{k}[l_j] } \right) \cdot  x^n}  \nonumber%\\
%%       &=& x+ x \cdot \sum_{n=1}^{\infty}{\left(  \sum_{i=1}^{\infty}{A[k][i] \cdot \sum_{\substack{l_1...l_{i}\\ {\sum_{j} l_j=n}}} \prod_{j=1}^{i} S_{k}[l_j] } \right) \cdot  x^n}  \nonumber\\
%\end{eqnarray}
\begin{eqnarray}
% R_k(x)      &=& x+ x \cdot \sum_{i=1}^{\infty}{A[k][i] \cdot \left( \sum_{n=1}^{\infty}  {\left( \sum_{\substack{l_1...l_{i}\\ {\sum_{j} l_j=n}}} \prod_{j=1}^{i} S_{k}[l_j] \right) \cdot  x^n } \right) }  \nonumber\\
%      &=& x+ x \cdot \sum_{i=1}^{\infty}{A[k][i] \cdot R_k^i(x)} \nonumber \\
R_{d,k}(x)      &=& x \cdot \sum_{i=0}^{\infty}{A_{d}[k][i] \cdot R_{d,k}^i(x)} \label{eq:gen}%\nonumber
\end{eqnarray}
%% for a non-leaf tree node. We use $R_k(x)$ to denote the infinite sum of all $k$-ary permutation trees.
%% A term of $x^i$ in the expansion of $R_k(x)$ is the sum of all trees having $i$ non-leaf nodes, i.e.
%% $i+1$ leaves.
%% If we interpret the multiplication in this algebra as the operation of attachment, $\overbrace {x^iR_k^i(x) + x^iR_k^i(x) +... x^iR_k^i(x)}^{A[k][i]}$ 
%% can be interpreted as a representation of trees with $i$ non-leaf nodes on the rightmost spine. So we have
%% the following equation for $R_k(x)$:
%%
%%\begin{eqnarray}
%%R_k(x)=x \cdot \sum_{i=0}^{\infty}{A[k][i] \cdot R_k^i(x)} \label{eq:gen}
%%\end{eqnarray}
%The connection between Equations~\ref{eq:ssimp1} and~\ref{eq:gen} comes from the fact
%that taking the $i$th power of a generating function corresponds to convolving the 
%original series $i$ times.  
where the initial factor of $x$ % in eq.~\ref{eq:gen} 
shifts the series by one position, corresponding to the fact that we convolve terms
summing to $n-1$ rather than $n$ in eq.~\ref{eq:ssimp1}.

At a more intuitive level, each term in eq.~\ref{eq:gen} corresponds to $d$-permutation
trees with a rightmost spine of length $i$, with a single leaf at the end of the spine
(the $x$ factor), and all possible combinations of trees attached at the $i$ other points 
along the spine ($R_{d,k}^i(x)$ in the equation)
\newcommand{\dottededge}{\ncdiag[arm=0,angleA=-90,angleB=90,linestyle=dotted]}
\newcommand{\dashededge}{\ncdiag[arm=0,angleA=-90,angleB=90,linestyle=dashed]}
\[R_{d,k}(x) = \sum_{i} \left. \begin{array}{c} \resizebox{1.0in}{!}{{\Tree[.{} $R_{d,k}(x)$ [.{}  $R_{d,k}(x)$ [.!\TR[edge=\dashededge]{}  $R_{d,k}(x)$ x ] ] ]}} \end{array} \right\rbrace i .
\]
%\vspace{-1in}
This simplified equation will help us eliminate the dependency on $A$ in computing the series $S$.
% If we multiply $R_{d,k}(x)$ on both sides of eq.~\ref{eq:gen}, and assume $A_{d}[k][i]=0$ for all $i<0$:
% %
% \begin{eqnarray}
% R_{d,k}^2(x) &=& x \cdot \sum_{i=0}^{\infty}{A_{d}[k][i-1] \cdot R_{d,k}^{i}(x)} \label {eq:sub1}
% \end{eqnarray}
% %
% If we multiply $R_{d,k}^{k'-1}(x)$ on both sides of eq.~\ref{eq:gen}:
% %
% \begin{eqnarray}
% R_{d,k}^{k'}(x) &=& x \cdot \sum_{i=0}^{\infty}{A_{d}[k][i-k'+1] \cdot R_{d,k}^{i}(x)} \nonumber
% \end{eqnarray}
% %
% Multiplying the equation above by $H_{d,k'}$ and summing over the values of $k'$:
% %
% \begin{eqnarray}
% \sum_{k'=4}^{k}{H_{d,k'} \cdot R_{d,k}^{k'}(x)} 
% %                  &=& \sum_{k'=4}^{k}{H_{k'} \cdot x \cdot \sum_{i=0}^{\infty}{A[k][i-k'+1] \cdot R_k^{i}(x)}} \nonumber\\
%                   &=& x \cdot \sum_{i=0}^{\infty}{\sum_{k'=3}^{k}{H_{d,k'} \cdot A_{d}[k][i-k'+1]} \cdot R_{d,k}^{i}(x)} \label {eq:sub2}
% \end{eqnarray}
% %
% Similarly, beginning with eq.~\ref{eq:gen}, multiplying both sides this time by $R_{d,k}^{k'}(x)$:
% %
% \begin{eqnarray}
% \sum_{k'=4}^{k}{H_{d, k'} \cdot R_{d, k}^{k'+1}(x)} 
%                   &=& x \cdot \sum_{i=0}^{\infty}{\sum_{k'=3}^{k}{H_{d, k'} \cdot A_{d}[k][i-k']}  \cdot R_{d,k}^{i}(x)} \label {eq:sub3}
% \end{eqnarray}
% %
We now subtract 
%the two sides of eq.~\ref{eq:sub1} timed by $2^{d}-1$, eq.~\ref{eq:sub2}, and eq.~\ref{eq:sub3}
from eq.~\ref{eq:gen}
its multiples
%
\begin{eqnarray}
\lefteqn{R_{d,k}(x) -(2^{d}-1) R_{d, k}^2(x) - \sum_{k'=3}^{k}{H_{d, k'}  \left(R_{d,k}^{k'}(x)+R_{d,k}^{k'+1}(x)\right)} } \nonumber \\
&=& x \cdot \sum_{i=0}^{\infty}\left(A_{d}[k][i]-(2^{d}-1)A_{d}[k][i-1]-\phantom{\sum_{k'=3}^{k}}\right. \nonumber\\
&&\hspace{1in} \left. \sum_{k'=3}^{k}{H_{d, k'} \cdot \left(A_{d}[k][i-k']+A_{d}[k][i-k'+1]\right)}\right)  R_{d,k}^i(x) \nonumber  \\
&=& x \cdot \left( 1+ R_{d,k}(x)  + \sum_{i=2}^{\infty}{0 \cdot R_{d,k}^i(x)} \right) \nonumber \\
&=& x + xR_{d,k}(x) \nonumber
\end{eqnarray}
where we have applied eq.~\ref{eq:asimp} to show that all terms where $i\ge 2$ equal zero.  Rearranging the above
equation, we obtain a general form for $R$ that does not require computing $A$
\begin{equation} 
R_{d, k}(x) =  x + xR_{d, k}(x) + (2^{d}-1)R_{d, k}^2(x) + \sum_{k'=3}^{k}{H_{d, k'} \left(R_{d, k}^{k'}(x)+R_{d, k}^{k'+1}(x)\right)} . \label {eq:simpgen}
\end{equation}
Eq.~\ref{eq:simpgen} can be converted 
%from the domain of generating functions 
back into a recurrence on
our original sequence $S_{d, k}$, by replacing powers of $R$ with convolutions of $S$
%
\begin{eqnarray}
S_{d, k}[n]&=& S_{d, k}[n-1] \nonumber \\
&&\;{}+ (2^{d}-1)\sum_{i_1+i_2=n}{S_{d, k}[i_1] \cdot S_{d, k}[i_2]} \nonumber \\
&&\;{}+ \sum_{k'=3}^{k}{H_{d, k'}  \left(\sum_{\substack{l_1 \dots l_{k'}\\ {\sum_{j} l_j=n}}} \prod_{j=1}^{k'} S_{d, k}[l_j] +\sum_{\substack{l_1 \dots l_{k'+1}\\ {\sum_{j} l_j}=n}} \prod_{j=1}^{k'+1} S_{d, k}[l_j] \right)} \label{eq:ssimp2}
\end{eqnarray}
%
with the base case $S_{d, k}[1]=1$. Compared to eq.~\ref{eq:ssimp1}, this equation does not depend on the numbers of spines.
When $d=1$ and $k=2$, our sequence $S_{1, 2}$ is the Large Schr{\"o}der Number (sequence A006318 of \cite{sloane}).
%, twice the number of generalized parentheses, also called the Little Schr{\"o}der Number, from the second problem of \namecite{Schroder1870}. 


\section{Asymptotics of Simple $d$-permutations}\label{sec:dsimp}
\begin{table*}[t]
\centerline{
\begin{tabular}{r|r}
               $k$   &   $H_{2,k}$     \\[-1pt]
\hline
               1  &   1\\
               2  &   4\\
               3  &   8\\
               4  &   172\\
               5  &   5204\\
               6  &   222716\\
               7  &   12509188\\
               8  &   889421564\\
               9  &   78097622276\\
              10  &   8312906703868\\
               11  &  1056520142488580\\
              12  &   158263730949406716\\
              13  &   27626236450406776836\\
              14  &   5563092167972597137404\\
              15  &   1280742543230231763615748\\
              16  &   334405228960123174787678204\\
              17  &   98317121153947856929753989124\\
              18  &   32339023133437156084762282819580\\
              19  &   11831483864832785151824395066146820\\
              20  &   4789379698138059405310741712024371196\\
%               21  &   2134861159557952735332805016987007713284\\
%               22  &   1043316392303599075837179165223000473599996\\
%               23  &   556781657973816198153596312029601137164288004\\
%               24  &   323284175451032941989645496242213240679956479996\\
%               25  &   203539234481053182132678053019049074787608780865540\\
%               26  &   138522693080922473858146126291652207049336006459260924\\
%               27  &  101612500192850887896542308794663197162898796346702036996\\
%               28  &  80123532107942881571438482136134718663673787772833554759676\\
%               29  &  67744347373176302592103032190488581039223856687110207192432644\\
%               30 &  61273328705911999548897840367441286833742129672710921413801803772\\
\end{tabular}}
\caption{\label{t:H} The numbers of two-dimensional simple permutations, i.e., $2$-permutations of $k$ that are {\em not} $k-1$-ary parsable. 
}
\end{table*}

Table~\ref{t:H} shows the values of $H_{2, k}$ ($1 \le k \le 20$). $H_{d, k'}$ ($1 \le k' \le k$) plays
an important role in the generation of the $k$-ary parsable $d$-permutations. 
When $d=1$, the sequence of $H$ is called the number of {\em simple} 
permutations by \namecite{AlbertAtkinsonKlazar03}.
They show that ${H_{1, n} \over {n!}} \rightarrow e^{-2}$ as $n$ goes to infinity, 
demonstrating that $H$ grows very rapidly.
We show that when $d \ge 2$, ${H_{d, n} \over {(n!)^{d}}} \rightarrow 1$. 

Our proof technique is analogous to that used by \namecite{AlbertAtkinsonKlazar03}. 
To count the number of simple $d$-permutations, we subtract from
$(n!)^d$ the numbers of permutations with component blocks of
sizes ranging from $2$ to $n-1$. 
%minimal blocks of
%sizes ranging from $2$ to $n-1$. 
More precisely, we let $p_{d, n, k}$ be the number of $d$-permutations
of $n$ whose non-trivial minimal non-decomposable $d$-dimensional permuted sequence
is of size $k$. So we have the following equation:
\begin{eqnarray}
H_{d,n}=(n!)^d-\sum_{k=2}^{n-1}p_{d,n,k} . \label{eq:simpe}
\end{eqnarray}

When $d=1$, it has been shown that $\sum_{k=3}^{n-1}{{p_{1,n,k}} \over {n!}}=O(n^{-1})$ 
\cite{AlbertAtkinsonKlazar03}. However, the series $p_{1,n,2}$ grows rapidly
as $n$ increases. The counting of $p_{1,n,2}$ is a problem studied in an earlier
context of runs of consecutive elements in permutations \cite{Wolfowitz44}. It 
turns out the numbers of consecutive runs follow a Poisson distribution of
mean value $2$. $p_{1,n,2} \over {n!}$ is the probability mass contributed by
the permutations containing a non-zero number of consecutive runs, which
turns out to be $1-e^{-2}$. Thus, the ratio of simple permutations versus
all permutations is asymptotically $1-(1-e^{-2})-O(n^{-1})=e^{-2}+O(n^{-1})$.

Now we look into the cases when $d \ge 2$. First of all, we generalize
Lemma 7 of \namecite{AlbertAtkinsonKlazar03}:

%{\tt \char'134begin\char'173Lemma\char'175}
\begin{lem}\label{l:residual}
For any fixed positive integer $c$:
\[\sum_{k=c+2}^{n-c}{{p_{d,n,k}} \over {(n!)^d}}=O(n^{-{c \cdot d}}) . \]
\end{lem}
%{\tt \char'134end\char'173Lemma\char'175} 
\begin{prf}: 
Following the same line of reasoning as in the original paper, 
we generalize the upper bound by raising an additional power of $d$. 
We observe that 
\[p_{d,n,k} \le H_{d,k}(n-k+1)((n-k+1)!)^{d}\]
since the right hand side overcounts $d$-permutations with
more than one minimal block of size $k$. Using the fact that $H_{d,k} \le (k!)^d$
and $(n-k+1) \le (n-k+1)^d$, we arrive at the following
inequality:
\[p_{d,n,k} \le (k!(n-k+1)(n-k+1)!)^{d}\]
for which we can invoke the bounding results for 
\[k!(n-k+1)(n-k+1)!\]
and we have the main result. 
\end{prf}

Based on Lemma~\ref{l:residual}, we know $\sum_{k=3}^{n-1}{{p_{d,n,k}} \over {(n!)^d}}=O(n^{-d})$.
We have the following lemma regarding $p_{d,n,2}$:

\begin{lem}\label{l:pdn2}
When $d \ge 2$, 
\[{p_{d,n,2} \over {(n!)^d}}=O(n^{-(d-1)}) . \]
\end{lem}
\begin{prf}: 
The idea is similar to that used for analyzing consecutive runs \cite{Wolfowitz44}.
We imagine a stochastic process for generating a $d$-permutation in which
we randomly pick a $d$-dimensional alignment link for $i$ at the $i$-th
step. Whenever we have a minimal block of size $2$ in the $d$-permutation,
we have two adjacent alignment links forming a binary permuted sequence. The
probability of having one such binary block is bounded by $O((2/n)^d)$. So
the mean of the number of $d$-dimensional consecutive runs is $O(2^d/n^{d-1})$. 
When $d \ge 2$, as $n$ approaches infinity, the mean approaches zero. 
Thus, we can invoke the Markov inequality to bound the probability of observing
a nonzero number of consecutive $d$-dimensional runs as $O(n^{-(d-1)})$. 
\end{prf}

\begin{thm}\label{l:dsimp}
When $d \ge 2$, 
\[{H_{d, n} \over {(n!)^{d}}} =1 +O(n^{-(d-1)}) . \]
\end{thm}
%{\tt \char'134end\char'173Lemma\char'175} 
\begin{prf}: 
Based on Lemma~\ref{l:residual}, Lemma~\ref{l:pdn2}, and eq.~\ref{eq:simpe}, the ratio is asymptotically
$1-O(n^{-(d-1)})-O(n^{-d})=1+O(n^{-(d-1)})$.
\end{prf}

\section{Growth Rates for Factorizable $d$-permutations}\label {sec:gog}
\begin{table*}[t]
\centerline{
\begin{tabular}{r|rcr|r}
                  &   $G_{2, k}$  &\hspace{1in}&     &   $G_{2, k}$      \\[-1pt]
\hline
        2  & 13.93 & \hspace{1in}&          12  & 57.60 \\
        3  & 17.91 &          &  13  &  63.22\\
        4  & 22.08&           & 14  & 69.17 \\
        5  & 26.03 &           & 15  & 75.43 \\
        6  & 29.97 &           & 16  & 82.01 \\
        7  & 34.00 &           & 17  & 88.90 \\
        8  & 38.19 &           & 18  & 96.10 \\
        9  & 42.61 &          & 19  & 103.60 \\
        10  &47.31 &          & 20  & 111.41 \\
          11  & 52.30  \\
\end{tabular}
}
\caption{\label{t:K} The growth rate of $S_{2, k}$, which is the asymptotic ratio of $S_{2, k}[n]/S_{2, k}[n-1]$. 
}
\end{table*}

Since $S_{d,k}$ represents a monotonically increasing combinatorial sequence
with an algebraic generating function (by Eq.~\ref{eq:simpgen}), 
a standard argument \cite{FlSe01} shows that 
the ratio between
successive numbers in $S_{d,k}$ approaches a constant, which we call
the growth rate $G_{d,k}$. A more careful analysis of Eq.~\ref{eq:simpgen} shows 
that it is a single-equation algebraically aperiodic irreducible 
polynomial system specified by a Context-free class with one combinatorial
equation, which indicates that the underlying sequence $S_{d,k}$ 
satisfies $S_{d,k} \sim {\gamma \over {\sqrt{\pi n^3}  } }\omega^{n}$  \cite{FlSe01}. We
are interested in the asymptotic behavior of $\omega=G_{d,k}$ as $k$ goes to infinity 
for a certain $d$.

\namecite{Zhang-gildea-tr06} 
%study the difference between successive growth rates. 
%One might ask, how do the growth rates in Table~\ref{t:K} behave in the limit 
%as $k$ increases?  
show that the difference between successive
growth rates $G_{1, k}$
\[ G_{1, k} = \lim_{n\rightarrow\infty} \frac{S_{1, k}[n]}{S_{1, k}[n-1]} \]
approaches $1/e \simeq .37$
\[ \lim_{k\rightarrow\infty} \left\{ G_{1, k} - G_{1, k-1} \right\} = e^{-1} . \]

%The intuition behind this surprising fact is that the dominant 
%term in $S_{k}[n]$ consists of permutation trees that use
%the maximum branching factor $k$ throughout, with $H_k$ possible
%labels at each node.  The number of such trees can be estimated
%using Stirling's approximation $k! = \sqrt{2\pi}k^{k+\frac{1}{2}}e^{-k}$.
%Both Stirling's approximation and the approximation $H_k=k!/e^2$
%are accurate to within a factor of $1+O(k^{-1})$, which we omit:

In this section, we study the generalized problem of the
asymptotic behavior of $G_{d, k}$
\[ G_{d, k} = \lim_{n\rightarrow\infty} \frac{S_{d, k}[n]}{S_{d, k}[n-1]} . \]

Table~\ref{t:K} shows the change of growth rate $G_{2, k}$ as $k$
increases from $2$ to $20$. It seems the difference between
successive rates is growing roughly linearly. This observation is
confirmed by our main result in this section, the following theorem:
\begin{thm}\label{l:growth}
\[ G_{d, k} = \left( k \over e \right)^d + O(k^{d-1}\cdot \log{k}) . \]
\end{thm}
\begin{prf}:
We approximate $G_{d,k}$ by bounding $S_{d, k}$ using exponential
functions from both directions. 
To get a lower bound of $S_{d, k}$, we under-count the $k$-ary trees
by focusing only on the $k$-ary $d$-permutation 
trees in which the maximum branching factor $k$ is used throughout on
the level immediately above the leaves, and these $k$-ary nodes are
themselves ordered according to the identity permutation in each dimension.
For sufficiently large $k$, 
%The number of such trees can be estimated
%using Stirling's approximation $k! = \sqrt{2\pi}k^{k+\frac{1}{2}}e^{-k}$.
%Both Stirling's approximation and the approximation $H_{d, k}=(k!)^d$
%are accurate to within a factor of $1+O(k^{-1})$.
%, which we omit:
\begin{eqnarray}
S_{d, k}[n] &\ge& H_{d,k}^{n/k} \notag\\
G_{d, k} & \ge & H_{d,k}^{1/k} \notag\\
&=& \left((1-\epsilon) (k!)^d \right) ^{1/k} \notag\\
&=& \left((1-\epsilon') {\sqrt{2\pi}k^{k+\frac{1}{2}}e^{-k} } \right) ^{d /k} \notag\\
&=& \left( \frac{k}{e} \right)^{d} \left( (1-\epsilon')\sqrt{2\pi}k^{\frac{1}{2} } \right) ^{d /k} \notag\\
&\ge& \left( \frac{k}{e} \right)^{d } . \label{eq:lowerbound}
%S_{d, k}[n] &=& \Omega\left(\left(\left(\frac{k}{e}\right)^d\right)^n\right) 
\end{eqnarray}

%Because this approximation counts only some of the trees (those having 
%a fixed branching factor of $k$), it gives a lower bound on the growth rate
%as a function of $k$, $S_{k}[n] = \Omega((\frac{k}{e})^n)$.
%In the Appendix, we provide an upper bound of 
%$S_{k}[n] = O((\frac{k}{e} + c \log k)^n)$.
%Because the base of the exponent is at least $k/e$ and
%at most $k/e + O(\log k)$, the difference between 
%successive terms as $k$ increases converges to $1/e$.

To derive an upper bound on $G_{d, k}$, we return to the domain of generating functions.
Because our generating function for any given $k$
\begin{eqnarray*} 
R_{d, k}(x) &=&  x + xR_{d, k}(x) + (2^d-1)R_{d, k}^2(x) + \sum_{k'=3}^{k}{H_{d, k'} \left(R_{d, k}^{k'}(x)+R_{d, k}^{k'+1}(x)\right)} \\
\end{eqnarray*}
is analytic and all terms of the sequence $S$ are positive, we
can put a bound on the growth rate of $S$ by finding the largest $x$
for which the generating function converges \cite{Odlyzko95}.
% This technique can be understood from the definition of the generating function:
% \begin{eqnarray*} 
% R_k(x) &=&  \sum_n S_k[n]x^n 
% \end{eqnarray*}
% If this sum converges to a real number $c$ for a given $x$,
% \[ \sum_n S_k[n]x^n = c \]
% it can be shown that:
% \begin{align*}
%   S_k[n] &\le c \left(\frac{1}{x}\right)^n  \\
%   S_k[n] &= O\left( \left(\frac{1}{x}\right)^n \right) 
% \end{align*}
% To put a tight upper bound on the growth of $S_k$, we wish to
% find the largest $x$ for which $R(x)$ converges.

%\begin{figure*}
%\resizebox{\textwidth}{!}{
%\rotatebox{-90}{\includegraphics{graph_zx.eps}}}
%\caption{Eq.~\ref{eq:geninv}, the inverse of the generating function, for
%various values of $k$.  For any $x$ on the curve, $1/x$ gives an upper bound on the growth rate of $S_k$. }\label{fig:graph_zx}
%\end{figure*}

We wish to understand the change in growth rate as $k$ increases,
but for each value of $k$, $R_{d, k}$ is a different (and increasingly 
complex) function.
Thus we need a function of $k$, say $f_{d}(k)$, such that $R_{d,k}(f_{d}(k))$
is guaranteed to converge for all $k$ as $k$ increases.
Because of the form of our generating function, it is easier to 
work with its inverse, choosing a value for the function $R_{d, k}(x)$ itself
and then solving for $x$ to obtain $f_{d}(k)$\@.  Let $z=R_{d, k}(x)$ to simplify notation
\begin{eqnarray}
%x &=& \frac{z - (2^d-1)z^2 - \sum_{{k'}} H_{d, k'} ( z^{k'} + z^{{k'}+1} )}{1+z} \nonumber\\
%x &=& \frac{z - (2^d-1)z^2 - (1+z)\sum_{{k'}} H_{d, k'} ( z^{k'} )}{1+z} \nonumber\\
x &=& \frac{z - (2^d-1)z^2}{1+z} - \sum_{{k'}} H_{d, k'} z^{k'}  \label{eq:geninv}
\end{eqnarray}
%Given this equation, plotted in Figure~\ref{fig:graph_zx},
we can choose a value of $z$ as a function of $k$:
\begin{eqnarray*}
 z &=&  \left(\frac{e}{k} \left( \frac{1}{k^4} \right) ^ \frac{1}{k} \right)^d
\end{eqnarray*}
and show that there always exists an $x$ such that $z=R_{d, k}(x)$.
The intuition behind this choice of $z$ is that for $x$ to remain positive,
the first term must be larger than the sum over $H_{d, k'}$ terms.
$H_{d, k'}$ grows very quickly, as $(k'!)^d$,
and $z^{k'}$ must decrease faster than $H_{d, k'}$ grows.
%A detailed proof that 
%While we omit the proof for reasons of space, it can be shown that:
In the Appendix, we show that: 
\[ 
 \sum_{{k'}} H_{d, k'} z^{k'}  = O(k^{1-3d}) . 
\]
%is given in the Appendix.
%We begin by putting a bound on the last term of eq.~\ref{eq:geninv}:
%\begin{eqnarray*}
%\sum_{{k'}} H_{k'} z^{k'}  &=& \frac{1}{e^2} \sum_{{k'}} k'! \left( \left( \frac{1}{k!k^2} \right) ^ \frac{1}{k}\right)^{k'} \\
%&\simeq& \frac{1}{e^2} \sum_{{k'}} \left(\frac{k'}{e}\right)^{k'} \left(  \frac{e}{k} \right) ^{k'} \left(  \frac{1}{k^2} \right) ^{\frac{k'}{k}}  \\
%&=& \frac{1}{e^2} \sum_{{k'}} \left(\frac{k'}{k} \right) ^{k'}  \left(  \frac{1}{k^2} \right) ^{\frac{k'}{k}} \\
%&=& \frac{1}{e^2} \sum_{k'} \left(1-\frac{k-k'}{k} \right) ^{k'}  \left(  \frac{1}{k^2} \right) ^{\frac{k'}{k}} \\
%&=& \frac{1}{e^2} \sum_{i} \left( 1-\frac{i}{k} \right) ^{k}  \left(  \frac{1}{k^2} \right) ^{\frac{k-i}{k}} \\
%&\simeq& \frac{1}{e^2} \sum_{i} e^{-i}  \left(  \frac{1}{k^2} \right) ^{\frac{k-i}{k}} \\
%&\le& \frac{1}{e^2} \left(  \frac{1}{k^2} \right)  \sum_{i} e^{-i} \\
%&\le& \frac{1}{e^2} \left(  \frac{1}{k^2} \right)  \frac{1}{1-e^{-1}} 
%\end{eqnarray*}
For our growth rate, we need to analyze the behavior of $\frac{1}{x}$ as $k$ increases, 
by substituting the result above into eq.~\ref{eq:geninv}
\begin{align*}
x &= \frac{z - (2^d-1)z^2}{1+z} + O(k^{1-3d}) \notag\\
\intertext{using $\frac{1}{1-y} = 1 + O(y)$ as $y \rightarrow 0$:}
  &= z + O(z^2) + O(k^{1-3d}) \notag\\
\intertext{using $z = O(k^{-d})$:}
  &= z + O(k^{-2d}) . \notag\\
\intertext{The upper bound on the growth rate is the inverse of $x$:}
\frac{1}{x} &= \frac{1}{z}\left(\frac{1}{1 + O(k^{-d})}\right) \notag\\
\intertext{again using $\frac{1}{1-y} = 1 + O(y)$:}
  &= \frac{1}{z}\left(1 + O(k^{-d})\right) \notag\\
  &= \frac{1}{z} + O(z^{-1}k^{-d}) \notag\\
  &= \frac{1}{z} + O(1) \notag\\
  &= \left(\frac{k}{e}\left(k^4\right)^\frac{1}{k}\right)^d + O(1)  \notag\\
  &= \left(\frac{k}{e}e^{ \frac{4}{k} \log k}\right)^d + O(1)  \notag\\
\intertext{using $e^y = 1 +O(y)$ as $y \rightarrow 0$:}
  &= \left(\frac{k}{e}\left(1 +  O\left(\frac{4}{k} \log k\right) \right) \right)^d + O(1)  \notag\\
  &= \left(\frac{k}{e}\right)^d +  O(k^{d-1} \cdot  \log k ) .  \notag\\
\end{align*}
This upper bound, together with the lower bound of eq.~\ref{eq:lowerbound},
show that the dominating term of the growth rate is $\left(\frac{k}{e}\right)^d$.
\end{prf}
%as $k$ increases, the difference between successive growth rates
%approaches $e^{-1}$.
%\footnote{The sublinear $o(k)$ term can be refined to derive an approximation $\lim_{k\rightarrow \infty} \frac{1}{x}= \frac{ k }{e} + c\log k $}

\section{Conclusion}
We view a sequence of multiple permutations as a combinatorial
object and study the recursive decomposition of such objects. 
With probability almost one a given $d$-dimensional ($d\ge 2$) permutation
is simple. Although the number of $k$-ary parsable $d$-permutations grows
very fast: the ratio between successive terms approaches  $\left(\frac{k}{e}\right)^d$,
the number of all $d$-permutations grows even faster: as $(n!)^d$. 
Previous work has studied the algorithmic aspect of the problem 
%has been studied 
with the notion 
of PQ tree for representing common intervals of $d$ permutations. Our 
$d$-permutation trees are PQ trees with detailed permutation specification
at each node. 

Given our finding that the probability of
maintaining the consecutive property across all dimensions is extremely low,
an interesting topic for future work would be the exploration of
alternative definitions of $d$-permutation decomposition which
allow for a sequence of consecutive numbers in one dimension 
to become several segments in another dimension. 

\section{Acknowledgments}
%We thank the anonymous referee for constructive suggestions. 
We thank Daniel \v{S}tefankovi\v{c} for helpful discussions.
This work was supported by NSF grants IIS-0546554 and
IIS-0428020.

\section*{Appendix}
\input{deriv_h_Ok-2}

\begin{thebibliography}{16}
\providecommand{\natexlab}[1]{#1}

\bibitem[{Aho and Ullman(1972)}]{AhoUll72}
Albert~V. Aho and Jeffery~D. Ullman.
\newblock \emph{The Theory of Parsing, Translation, and Compiling}, volume~1.
\newblock Prentice-Hall, Englewood Cliffs, NJ, 1972.

\bibitem[{Albert et~al.(2003)Albert, Atkinson, and
  Klazar}]{AlbertAtkinsonKlazar03}
M.~H. Albert, M.~D. Atkinson, and M.~Klazar.
\newblock The enumeration of simple permutations.
\newblock \emph{J. Integer Sequences} \textbf{6} (2003), 03.6.??.

\bibitem[{Bui-Xuan et~al.(2005)Bui-Xuan, Habib, and Paul}]{BuiXuan05}
Binh~Minh Bui-Xuan, Michel Habib, and Christophe Paul.
\newblock Revisiting {T. Uno} and {M. Yagiura}'s algorithm.
\newblock In \emph{The 16th Annual International Symposium on Algorithms and
  Computation (ISAAC'05)}. 2005, pp. 146--155.

\bibitem[{Flajolet and Sedgewick(2001)}]{FlSe01}
Philippe Flajolet and Robert Sedgewick.
\newblock Analytic combinatorics: Functional equations, rational and algebraic
  functions.
\newblock Technical Report 4103, INRIA, 2001.
\newblock 98 pages.

\bibitem[{Heber and Stoye(2001)}]{HeberStoye01}
Steffen Heber and Jens Stoye.
\newblock Finding all common intervals of k permutations.
\newblock In \emph{Combinatorial Pattern Matching, 12th Annual Symposium}.
  Springer-Verlag, 2001, pp. 207--218.

\bibitem[{Landau et~al.(2005)Landau, Parida, and Weimann}]{Landau05}
Gad~M. Landau, Laxmi Parida, and Oren Weimann.
\newblock Gene proximity analysis across whole genomes via {PQ} trees.
\newblock \emph{J. Computational Biology} \textbf{12} (2005),
  1289--1306.

\bibitem[{Melamed(2003)}]{Melamed-naacl03}
I.~Dan Melamed.
\newblock Multitext grammars and synchronous parsers.
\newblock In \emph{Proceedings of the 2003 Meeting of the North American
  chapter of the Association for Computational Linguistics (NAACL-03)}.
  Edmonton, 2003, pp.\ 158--165.

\bibitem[{Odlyzko(1995)}]{Odlyzko95}
Andrew Odlyzko.
\newblock Asymptotic enumeration methods.
\newblock In R.~L. Graham, M.~Groetschel, and L.~Lovasz, editors,
  \emph{Handbook of Combinatorics vol. 2}, Elsevier. 1995, pp. 1063--1229.

\bibitem[{Satta and Peserico(2005)}]{SattaPeserico05}
Giorgio Satta and Enoch Peserico.
\newblock Some computational complexity results for synchronous context-free
  grammars.
\newblock In \emph{Proceedings of Human Language Technology Conference and
  Conference on Empirical Methods in Natural Language Processing (HLT/EMNLP)}.
  Vancouver, Canada, 2005, pp. 803--810.

\bibitem[{Shapiro and Stephens(1991)}]{ShapiroStephens91}
L.~Shapiro and A.~B. Stephens.
\newblock Bootstrap percolation, the {Schr\"{o}der} numbers, and the $n$-kings
  problem.
\newblock \emph{SIAM J.  Discrete Math.} \textbf{4} (1991),
  275--280.

\bibitem[{Sloane(2006)}]{sloane}
N.~J.~A. Sloane.
\newblock The On-Line Encyclopedia of Integer Sequences, 2006.

\bibitem[{Uno and Yagiura(2000)}]{UnoYag00}
Takeaki Uno and Mutsunori Yagiura.
\newblock Fast algorithms to enumerate all common intervals of two
  permutations.
\newblock \emph{Algorithmica} \textbf{26} (2000), 290--309.

\bibitem[{Wolfowitz(1944)}]{Wolfowitz44}
J.~Wolfowitz.
\newblock Note on runs of consecutive elements.
\newblock \emph{Ann. of Math. Stat.} \textbf{15} (1944), 97--98.

\bibitem[{Wu(1997)}]{DekaiCL}
Dekai Wu.
\newblock Stochastic inversion transduction grammars and bilingual parsing of
  parallel corpora.
\newblock \emph{Computational Linguistics} \textbf{23} (1997), 377--403.

\bibitem[{Zhang and Gildea(2006)}]{Zhang-gildea-tr06}
Hao Zhang and Daniel Gildea.
\newblock Efficient factorization of synchronous context-free grammars.
\newblock Technical Report 889, University of Rochester, 2006.

\bibitem[{Zhang et~al.(2006)Zhang, Huang, Gildea, and Knight}]{ZHGK-naacl06}
Hao Zhang, Liang Huang, Daniel Gildea, and Kevin Knight.
\newblock Synchronous binarization for machine translation.
\newblock In \emph{Proceedings of the Human Language Technology
  Conference/North American Chapter of the Association for Computational
  Linguistics (HLT/NAACL)}, 2006, pp.\ 256-263.

\end{thebibliography}


\bigskip
\hrule
\bigskip

\noindent 2000 {\it Mathematics Subject Classification}:
Primary: 05A16; Secondary: 05A05, 05A15.

\noindent \emph{Keywords: } asymptotic enumeration, permutation.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A006318} and \seqnum{A111111}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received December 18 2006;
revised version received  June 5 2007.
Published in {\it Journal of Integer Sequences}, June 5 2007.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}