\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} .