More of the prolog.

[saga.git] / rank.tex

diff --git a/rank.tex b/rank.tex
index ceea89f8ac50490ed7c0df116feeb0f64d1bc97d..014d56d4af97000a8f3593f26d96aec6e5a1c0c0 100644 (file)
--- a/rank.tex
+++ b/rank.tex
@@ -3,8 +3,9 @@
 \fi
 
 \chapter{Ranking Combinatorial Structures}
 \fi
 
 \chapter{Ranking Combinatorial Structures}

+\id{rankchap}

 
 

-\section{Ranking and unranking}
+\section{Ranking and unranking}\id{ranksect}%

 
 The techniques for building efficient data structures on the RAM described
 in Chapter~\ref{ramchap} can be also used for a~variety of problems related
 
 The techniques for building efficient data structures on the RAM described
 in Chapter~\ref{ramchap} can be also used for a~variety of problems related


@@ -79,9 +80,10 @@ RAM data structures, yields a~linear-time algorithm for lexicographic
 \nota\id{brackets}%
 We will view permutations on a~finite set $A\subseteq {\bb N}$ as ordered $\vert A\vert$-tuples
 (in other words, arrays) containing every element of~$A$ exactly once. We will
 \nota\id{brackets}%
 We will view permutations on a~finite set $A\subseteq {\bb N}$ as ordered $\vert A\vert$-tuples
 (in other words, arrays) containing every element of~$A$ exactly once. We will

-use square brackets to index these tuples: $\pi=(\pi[1],\ldots,\pi[\vert A\vert])$.
-The corresponding lexicographic ranking and unranking functions will be denoted by~$L(\pi,A)$
-and $L^{-1}(i,A)$ respectively.
+use square brackets to index these tuples: $\pi=(\pi[1],\ldots,\pi[\vert A\vert])$,
+and sub-tuples: $\pi[i\ldots j] = (\pi[i],\ldots,\pi[j])$.
+The lexicographic ranking and unranking functions for the permutations on~$A$
+will be denoted by~$L(\pi,A)$ and $L^{-1}(i,A)$ respectively.

 
 \obs\id{permrec}%
 Let us first observe that permutations have a simple recursive structure.
 
 \obs\id{permrec}%
 Let us first observe that permutations have a simple recursive structure.


@@ -89,12 +91,12 @@ If we fix the first element $\pi[1]$ of a~permutation~$\pi$ on the set~$[n]$, th
 elements $\pi[2], \ldots, \pi[n]$ form a~permutation on $[n]-\{\pi[1]\} = \{1,\ldots,\pi[1]-1,\pi[1]+1,\ldots,n\}$.
 The lexicographic order of two permutations $\pi$ and~$\pi'$ on the original set is then determined
 by $\pi[1]$ and $\pi'[1]$ and only if these elements are equal, it is decided
 elements $\pi[2], \ldots, \pi[n]$ form a~permutation on $[n]-\{\pi[1]\} = \{1,\ldots,\pi[1]-1,\pi[1]+1,\ldots,n\}$.
 The lexicographic order of two permutations $\pi$ and~$\pi'$ on the original set is then determined
 by $\pi[1]$ and $\pi'[1]$ and only if these elements are equal, it is decided

-by the lexicographic comparison of permutations $(\pi[2],\ldots,\pi[n])$ and
-$(\pi'[2],\ldots,\pi'[n])$. Moreover, for fixed~$\pi[1]$ all permutations on
-the smaller set occur exactly once, so the rank of $\pi$ is $(\pi[1]-1)\cdot
-(n-1)!$ plus the rank of $(\pi[2],\ldots,\pi[n])$.
+by the lexicographic comparison of permutations $\pi[2\ldots n]$ and $\pi'[2\ldots n]$.
+Moreover, for fixed~$\pi[1]$ all permutations on the smaller set occur exactly
+once, so the rank of $\pi$ is $(\pi[1]-1)\cdot (n-1)!$ plus the rank of
+$\pi[2\ldots n]$.

 
 

-This gives us a~reduction from (un)ranking of permutations on $[n]$ to (un)ranking
+This gives us a~reduction from (un)ranking of permutations on $[n]$ to (un)rank\-ing

 of permutations on a $(n-1)$-element set, which suggests a straightforward
 algorithm, but unfortunately this set is different from $[n-1]$ and it even
 depends on the value of~$\pi[1]$. We could renumber the elements to get $[n-1]$,
 of permutations on a $(n-1)$-element set, which suggests a straightforward
 algorithm, but unfortunately this set is different from $[n-1]$ and it even
 depends on the value of~$\pi[1]$. We could renumber the elements to get $[n-1]$,


@@ -121,7 +123,7 @@ translates to the following recursive algorithms for both ranking and unranking
 \>We can call $\<Rank>(\pi,1,n,[n])$ for ranking on~$[n]$, i.e., to calculate
 $L(\pi,[n])$.
 
 \>We can call $\<Rank>(\pi,1,n,[n])$ for ranking on~$[n]$, i.e., to calculate
 $L(\pi,[n])$.
 

-\alg $\<Unrank>(j,i,n,A)$: Return an~array~$\pi$ such that $\pi[i,\ldots,n]$ is the $j$-th permutation on~$A$.
+\alg $\<Unrank>(j,i,n,A)$: Return an~array~$\pi$ such that $\pi[i\ldots n]$ is the $j$-th permutation on~$A$.

 \id{unrankalg}
 \algo
 \:If $i>n$, return $(0,\ldots,0)$.
 \id{unrankalg}
 \algo
 \:If $i>n$, return $(0,\ldots,0)$.


@@ -131,7 +133,7 @@ $L(\pi,[n])$.
 \:Return~$\pi$.
 \endalgo
 
 \:Return~$\pi$.
 \endalgo
 

-\>We can call $\<Unrank>(j,1,n,[n])$ for the unranking problem on~$[n]$, i.e., to get $L^{-1}(j,[n])$.
+\>We can call $\<Unrank>(j,1,n,[n])$ for the unranking problem on~$[n]$, i.e., to calculate $L^{-1}(j,[n])$.

 
 \para
 The most time-consuming parts of the above algorithms are of course operations
 
 \para
 The most time-consuming parts of the above algorithms are of course operations


@@ -146,7 +148,7 @@ Then lexicographic ranking and unranking of permutations can be performed in tim
 
 \proof
 Let us analyse the above algorithms. The depth of the recursion is~$n$ and in each
 
 \proof
 Let us analyse the above algorithms. The depth of the recursion is~$n$ and in each

-nested invokation of the recursive procedure we perform a~constant number of operations.
+nested invocation of the recursive procedure we perform a~constant number of operations.

 All of them are either trivial, or calculations of factorials (which can be precomputed in~$\O(n)$ time),
 or operations on the data structure.
 \qed
 All of them are either trivial, or calculations of factorials (which can be precomputed in~$\O(n)$ time),
 or operations on the data structure.
 \qed


@@ -166,7 +168,7 @@ of all, we will make sure that the ranks are large numbers, so the word size of
 machine has to be large as well:
 
 \obs
 machine has to be large as well:
 
 \obs

-$\log n! = \Theta(n\log n)$, therefore the word size~$W$ must be~$\Omega(n\log n)$.
+$\log n! = \Theta(n\log n)$, therefore the word size must be~$\Omega(n\log n)$.

 
 \proof
 We have $n^n \ge n! \ge \lfloor n/2\rfloor^{\lfloor n/2\rfloor}$, so $n\log n \ge \log n! \ge \lfloor n/2\rfloor\cdot\log \lfloor n/2\rfloor$.
 
 \proof
 We have $n^n \ge n! \ge \lfloor n/2\rfloor^{\lfloor n/2\rfloor}$, so $n\log n \ge \log n! \ge \lfloor n/2\rfloor\cdot\log \lfloor n/2\rfloor$.


@@ -193,7 +195,7 @@ on the data structure to allow order of elements dependent on the history of the
 structure (i.e., on the sequence of deletes performed so far). We can observe that
 although the algorithm no longer gives the lexicographic ranks, the unranking function
 is still an~inverse of the ranking function, because the sequence of deletes
 structure (i.e., on the sequence of deletes performed so far). We can observe that
 although the algorithm no longer gives the lexicographic ranks, the unranking function
 is still an~inverse of the ranking function, because the sequence of deletes

-from~$A$ is the same when both ranking and unraking.
+from~$A$ is the same when both ranking and unranking.

 
 The implementation of the relaxed structure is straightforward. We store the set~$A$
 in an~array~$\alpha$ and use the order of the elements in~$\alpha$ determine the
 
 The implementation of the relaxed structure is straightforward. We store the set~$A$
 in an~array~$\alpha$ and use the order of the elements in~$\alpha$ determine the


@@ -206,7 +208,7 @@ array~$\alpha$ and update~$\alpha^{-1}$ accordingly.
 
 %--------------------------------------------------------------------------------
 
 
 %--------------------------------------------------------------------------------
 

-\section{Ranking of {\secitfont k\/}-permutations}
+\section{Ranking of \iftoc $k$\else{\secitfont k\/}\fi-permutations}

 \id{kpranksect}
 
 The technique from the previous section can be also generalized to lexicographic ranking of
 \id{kpranksect}
 
 The technique from the previous section can be also generalized to lexicographic ranking of


@@ -245,7 +247,7 @@ and $\log n^{\underline k} \ge (n/2)(\log n - 1) \ge (k/2)(\log n - 1)$.
 It remains to show how to translate the operations on~$A$ to operations on~$H$,
 again stored as a~sorted vector~${\bf h}$. Insertion to~$A$ correspond to
 deletion from~$H$ and vice versa. The rank of any~$x\in[n]$ in~$A$ is $x$ minus
 It remains to show how to translate the operations on~$A$ to operations on~$H$,
 again stored as a~sorted vector~${\bf h}$. Insertion to~$A$ correspond to
 deletion from~$H$ and vice versa. The rank of any~$x\in[n]$ in~$A$ is $x$ minus

-the number of holes which are smaller than~$x$, therefore $R_A(x)=x-R_H(x)$.
+the number of holes that are smaller than~$x$, therefore $R_A(x)=x-R_H(x)$.

 To calculate $R_H(x)$, we can again use the vector operation \<Rank> from Algorithm \ref{vecops},
 this time on the vector~$\bf h$.
 
 To calculate $R_H(x)$, we can again use the vector operation \<Rank> from Algorithm \ref{vecops},
 this time on the vector~$\bf h$.
 


@@ -290,9 +292,9 @@ constant time. The time bound follows. \qed
 
 %--------------------------------------------------------------------------------
 
 
 %--------------------------------------------------------------------------------
 

-\section{Hatcheck lady and other derangements}
+\section{Restricted permutations}

 
 

-Another interesting class of combinatorial objects which can be counted and
+Another interesting class of combinatorial objects that can be counted and

 ranked are restricted permutations. An~archetypal member of this class are
 permutations without a~fixed point, i.e., permutations~$\pi$ such that $\pi(i)\ne i$
 for all~$i$. These are also called \df{derangements} or \df{hatcheck permutations.}\foot{%
 ranked are restricted permutations. An~archetypal member of this class are
 permutations without a~fixed point, i.e., permutations~$\pi$ such that $\pi(i)\ne i$
 for all~$i$. These are also called \df{derangements} or \df{hatcheck permutations.}\foot{%


@@ -337,7 +339,7 @@ $T(\pi)$ avoids the holes.
 Let~$H\subseteq B$ be any set of holes in the board. Then:
 \itemize\ibull
 \:$N_j$ denotes the number of placements of $n$~rooks on the board such that exactly~$j$ of the rooks
 Let~$H\subseteq B$ be any set of holes in the board. Then:
 \itemize\ibull
 \:$N_j$ denotes the number of placements of $n$~rooks on the board such that exactly~$j$ of the rooks

-stand on holes. That is, $N_j := \#\{ \pi\in{\cal P}: \#(H\cap T(\pi)) = j \}$.
+stand on holes. That is, $N_j := \#\{ \pi\in{\cal P} \mid \#(H\cap T(\pi)) = j \}$.

 \:$r_k$ is the number of ways how to place $k$~rooks on the holes. In other words,
 this is the number of $k$-element subsets of~$H$ such that no two elements share
 a~common row or column.
 \:$r_k$ is the number of ways how to place $k$~rooks on the holes. In other words,
 this is the number of $k$-element subsets of~$H$ such that no two elements share
 a~common row or column.


@@ -363,7 +365,7 @@ each of them which stands on a~hole with an~element of~$[x]$. The right-hand
 side counts the same: We can obtain any such configuration by placing $k$~rooks
 on~$H$ first, labeling them with elements of~$\{2,\ldots,x\}$, placing
 additional $n-k$ rooks on the remaining rows and columns (there are $(n-k)!$ ways
 side counts the same: We can obtain any such configuration by placing $k$~rooks
 on~$H$ first, labeling them with elements of~$\{2,\ldots,x\}$, placing
 additional $n-k$ rooks on the remaining rows and columns (there are $(n-k)!$ ways

-how to do this) and labeling those of the the new rooks standing on a~hole with~1.
+how to do this) and labeling those of the new rooks standing on a~hole with~1.

 \qed
 
 \cor
 \qed
 
 \cor


@@ -373,7 +375,7 @@ $$N_0 = N(0) = \sum_{k=0}^n (-1)^k \cdot (n-k)! \cdot r_k.$$
 
 \example\id{hatcheck}%
 Let us apply this theory to the hatcheck lady problem. The set~$H$ of holes is the main diagonal
 
 \example\id{hatcheck}%
 Let us apply this theory to the hatcheck lady problem. The set~$H$ of holes is the main diagonal

-of the board: $H=\{ (i,i) : i\in[n] \}$. When we want to place $k$~rooks on the holes,
+of the board: $H=\{ (i,i) \mid i\in[n] \}$. When we want to place $k$~rooks on the holes,

 we can do that in $r_k={n\choose k}$ ways. By the previous corollary, the number of
 derangements is:
 $$
 we can do that in $r_k={n\choose k}$ ways. By the previous corollary, the number of
 derangements is:
 $$


@@ -420,7 +422,7 @@ See observations \ref{rooksobs} and~\ref{matchobs}.
 The diversity of the characterizations of restricted permutations brings
 both good and bad news. The good news is that we can use the
 plethora of known results on bipartite matchings. Most importantly, we can efficiently
 The diversity of the characterizations of restricted permutations brings
 both good and bad news. The good news is that we can use the
 plethora of known results on bipartite matchings. Most importantly, we can efficiently

-determine whether there exists at least one permutation satistying a~given set of restrictions:
+determine whether there exists at least one permutation satisfying a~given set of restrictions:

 
 \thm
 There is an~algorithm which decides in time $\O(n^{1/2}\cdot m)$ whether there exists
 
 \thm
 There is an~algorithm which decides in time $\O(n^{1/2}\cdot m)$ whether there exists


@@ -446,7 +448,7 @@ If there is a~polynomial-time algorithm for lexicographic ranking of permutation
 a~set of restrictions which is a~part of the input, then $P=\#P$.
 
 \proof
 a~set of restrictions which is a~part of the input, then $P=\#P$.
 
 \proof

-We will show that a~polynomial-time ranking algorithm would imply a~polynomial-time
+We will show that a~polynomial-time ranking algorithm would imply a~po\-ly\-nom\-ial-time

 algorithm for computing the permanent of an~arbitrary zero-one matrix, which
 is a~$\#P$-complete problem.
 
 algorithm for computing the permanent of an~arbitrary zero-one matrix, which
 is a~$\#P$-complete problem.
 


@@ -496,7 +498,7 @@ with its $i$-th row and $j$-th column removed.
 \obs
 Let us consider a~permutation $\pi\in{\cal P}_A$ and $n=\vert A\vert$.
 When we fix the value of the element $\pi[1]$, the remaining elements form
 \obs
 Let us consider a~permutation $\pi\in{\cal P}_A$ and $n=\vert A\vert$.
 When we fix the value of the element $\pi[1]$, the remaining elements form

-a~permutation $\pi'=(\pi[2],\ldots,\pi[n])$ on the set~$A'=A\setminus\{\pi[1]\}$.
+a~permutation $\pi'=\pi[2\ldots n]$ on the set~$A'=A\setminus\{\pi[1]\}$.

 The permutation~$\pi$ satisfies the restriction matrix~$M$ if and only if
 $M[1,a]=1$ for $a=R_A(\pi[1])$ and $\pi'$ satisfies a~restriction matrix~$M'=M^{1,a}$.
 This translates to the following counterparts of algorithms \ref{rankalg}
 The permutation~$\pi$ satisfies the restriction matrix~$M$ if and only if
 $M[1,a]=1$ for $a=R_A(\pi[1])$ and $\pi'$ satisfies a~restriction matrix~$M'=M^{1,a}$.
 This translates to the following counterparts of algorithms \ref{rankalg}


@@ -561,7 +563,28 @@ and $\O(n^2\cdot t(n))$ by the computations of the~$N_0$'s.
 \qed
 
 \rem
 \qed
 
 \rem

-This time bound is obviously very coarse, its main purpose was to demonstrate that
+In cases where the efficient evaluation of the permanent is out of our reach,
+we can consider using the fully-polynomial randomized approximation scheme
+for the permanent described by Jerrum, Sinclair and Vigoda in \cite{jerrum:permanent}.
+We then get an~approximation scheme for the ranks.
+
+\rem
+There are also deterministic algorithms for computing the number of perfect matchings
+in various special graph families (which imply polynomial-time ranking algorithms for
+the corresponding families of permutations). If the graph is planar, we can
+use the Kasteleyn's algorithm \cite{kasteleyn:crystals} based on Pfaffian
+orientations which runs in time $\O(n^3)$.
+It has been recently extended to arbitrary surfaces by Yuster and Zwick
+\cite{yuster:matching} and sped up to $\O(n^{2.19})$. The counting problem
+for arbitrary minor-closed classes (cf.~section \ref{minorclosed}) is still
+open.
+
+%--------------------------------------------------------------------------------
+
+\section{Hatcheck lady and other derangements}
+
+The time bound for ranking of general restricted permutations shown in the previous
+section is obviously very coarse. Its main purpose was to demonstrate that

 many special cases of the ranking problem can be indeed computed in polynomial time.
 For most families of restriction matrices, we can do much better. One of the possible improvements
 is to replace the matrix~$M$ by the corresponding restriction graph and instead of
 many special cases of the ranking problem can be indeed computed in polynomial time.
 For most families of restriction matrices, we can do much better. One of the possible improvements
 is to replace the matrix~$M$ by the corresponding restriction graph and instead of


@@ -571,14 +594,14 @@ matrices using information already computed for the larger matrices.
 
 These speedups are hard to state formally in general (they depend on the
 structure of the matrices), so we will concentrate on a~specific example
 
 These speedups are hard to state formally in general (they depend on the
 structure of the matrices), so we will concentrate on a~specific example

-instead. We will show that for derangements one can achieve linear time complexity.
+instead. We will show that for the derangements one can achieve linear time complexity.

 
 

-\examplen{Ranking of hatcheck permutations a.k.a.~derangements}\id{hatrank}%
+\nota\id{hatrank}%

 As we already know, the hatcheck permutations correspond to restriction
 As we already know, the hatcheck permutations correspond to restriction

-matrices which contain zeroes only on the main diagonal and graphs which are
-complete bipartite with the matching $\{(i,i) : i\in[n]\}$ deleted. For
+matrices that contain zeroes only on the main diagonal and graphs that are
+complete bipartite with the matching $\{(i,i) \mid i\in[n]\}$ deleted. For

 a~given order~$n$, we will call this matrix~$D_n$ and the graph~$G_n$ and
 a~given order~$n$, we will call this matrix~$D_n$ and the graph~$G_n$ and

-we will show that the submatrices of~$D_n$ share a~nice property:
+we will show that the submatrices of~$D_n$ share several nice properties:

 
 \lemma\id{submatrixlemma}%
 Let $D$ be a~submatrix of~$D_n$ obtained by deletion of rows and columns.
 
 \lemma\id{submatrixlemma}%
 Let $D$ be a~submatrix of~$D_n$ obtained by deletion of rows and columns.


@@ -598,33 +621,15 @@ same number of vertices and also the same number of missing edges. As the
 number of matchings is an~isomorphism invariant, the lemma follows.
 \qed
 
 number of matchings is an~isomorphism invariant, the lemma follows.
 \qed
 

+\rem
+There is a~clear combinatorial intuition behind this lemma: if we are
+to count permutations with restrictions placed on~$z$ elements and these
+restrictions are independent, it does not matter how exactly they look like.
+

 \defn
 Let $n_0(z,d)$ be the permanent shared by all submatrices as described
 by the above lemma, which have $d\times d$ entries and exactly~$z$ zeroes.
 
 \defn
 Let $n_0(z,d)$ be the permanent shared by all submatrices as described
 by the above lemma, which have $d\times d$ entries and exactly~$z$ zeroes.
 

-\para
-Instead of maintaining the matrix~$M$ over the course of the algorithm, it is sufficient to remember
-the number~$z$ of zeroes in this matrix and the set~$Z$ which contains the elements
-$x\in A$ whose locations are restricted (there is a~zero anywhere in the $(R_A(x)+1)$-th
-column of~$M$). In other words, every $x\in Z$ can appear at all positions in the
-permutation except one (and these forbidden positions are different for different~$x$'s),
-while the remaining elements of~$A$ can appear anywhere.
-
-As we already observed (\ref{hatcheck}) that the number of derangements on~$[n]$ is $\Theta(n!)$,
-we can again use word-sized vectors to represent the sets~$A$ and~$Z$ with insertion,
-deletion, ranking and unranking on them in constant time.
-
-When the algorithm selects a~submatrix $M'=M^{1,k}$ for an~element $x$ of~rank~$k-1$, it is described by either
-$z'=z-1$ and~$Z'=Z\setminus\{x\}$ (if $x\in Z$) or $z'=z$ and $Z'=Z$ (if $x\not\in Z$).
-All computations of~$N_0$ in the algorithm can therefore be replaced by looking
-up the appropriate $n_0(z',\vert A\vert-1)$ in a~precomputed table. Moreover, we can
-calculate a~single~$C_a$ in constant time, because all summands are either $n_0(z,\vert A\vert-1)$
-or $n_0(z-1,\vert A\vert-1)$ depending on the set~$Z$. So we get:
-$$C_a = r\cdot n_0(z-1,\vert A\vert-1) + (a-r) \cdot n_0(z,\vert A\vert-1),$$
-where $r=R_Z(R^{-1}_A(a))$, that is the number of restricted elements among the $a$~smallest ones in~$A$.
-
-It remains to show how to precompute the table of the $n_0$'s efficiently.
-

 \lemma
 The function~$n_0$ satisfies the following recurrence:
 $$\eqalign{
 \lemma
 The function~$n_0$ satisfies the following recurrence:
 $$\eqalign{


@@ -632,7 +637,7 @@ n_0(0,d) &= d!, \cr
 n_0(d,d) &= d! \cdot \sum\nolimits_{k=0}^d {(-1)^k \over k!}, \cr
 \noalign{\medskip}
 n_0(z,d) &= z\cdot n_0(z-1,d-1) + (d-z)\cdot n_0(z,d-1) \quad\hbox{for $z<d$.} \cr
 n_0(d,d) &= d! \cdot \sum\nolimits_{k=0}^d {(-1)^k \over k!}, \cr
 \noalign{\medskip}
 n_0(z,d) &= z\cdot n_0(z-1,d-1) + (d-z)\cdot n_0(z,d-1) \quad\hbox{for $z<d$.} \cr

-}$$
+}\eqno{(*)}$$

 
 \proof
 The base cases of the recurrence are straightforward: $n_0(0,d)$ counts the
 
 \proof
 The base cases of the recurrence are straightforward: $n_0(0,d)$ counts the


@@ -651,5 +656,89 @@ permutations. On the other hand, if we use an~unrestricted element, all restrict
 stay in effect, so there are~$n_0(z,d-1)$ ways how to do so.
 \qed
 
 stay in effect, so there are~$n_0(z,d-1)$ ways how to do so.
 \qed
 

+\lemma
+The function~$n_0$ also satisfies the following recurrence:
+$$
+n_0(z-1,d) = n_0(z,d) + n_0(z-1,d-1) \quad\hbox{for $z>0$, $d>0$.} \eqno{(\maltese)}
+$$
+
+\proof
+We will again take advantage of having proven Lemma~\ref{submatrixlemma}, which
+allows us to choose arbitrary matrices with the given parameters. Let us pick a~matrix~$M_z$
+containing $z$~zeroes such that $M_z[1,1]=0$. Then define~$M_{z-1}$ which is equal to~$M_z$
+everywhere except $M_{z-1}[1,1]=1$.
+
+We will count the permutations $\pi\in {\cal P}_d$ satisfying~$M_{z-1}$ in two ways.
+First, there are $n_0(z-1,d)$ such permutations. On the other hand, we can divide
+the them to two types depending on whether $\pi[1]=1$. Those having $\pi[1]\ne 1$
+are exactly the $n_0(z,d)$ permutations satisfying~$M_z$. The others correspond to
+permutations $(\pi[2],\ldots,\pi[d])$ on $\{2,\ldots,d\}$ that satisfy~$M_z^{1,1}$,
+so there are $n_0(z-1,d-1)$ of them.
+\qed
+
+\cor\id{nzeroprecalc}%
+For a~given~$n$, a~table of the values $n_0(z,d)$ for all $0\le z\le d\le n$
+can be precomputed in time~$\O(n^2)$.
+
+\proof
+Use either recurrence and induction on~$z+d$.
+\qed
+
+\cor\id{smalldiff}%
+For every $0\le z<d$ we have $n_0(z,d) - n_0(z+1,d) \le n_0(z,d)/d$.
+
+\proof
+According to the recurrence $(\maltese)$, the difference $n_0(z,d) - n_0(z+1,d)$ is
+equal to $n_0(z,d-1)$. We can bound this by plugging the trivial inequality $n_0(z,d-1) \le n_0(z-1,d-1)$
+to~$(*)$, from which we obtain $n_0(z,d) \ge d\cdot n_0(z,d-1)$.
+\qed
+
+\para\id{rrankmod}%
+Let us show how to modify the ranking algorithm (\ref{rrankalg}) using the insight
+we have gained into the structure of derangements.
+
+The algorithm uses the matrix~$M$ only for computing~$N_0$ of its submatrices
+and we have shown that this value depends only on the order of the matrix and
+the number of zeroes in it. We will therefore replace maintenance of the matrix
+by remember the number~$z$ of its zeroes and the set~$Z$ that contains the elements
+$x\in A$ whose locations are restricted (there is a~zero anywhere in the $(R_A(x)+1)$-th
+column of~$M$). In other words, every $x\in Z$ can appear at all positions in the
+permutation except one (and these forbidden positions are different for different~$x$'s),
+while the remaining elements of~$A$ can appear anywhere.
+
+As we already observed (\ref{hatcheck}) that the number of derangements on~$[n]$ is $\Theta(n!)$,
+we can again use word-sized vectors to represent the sets~$A$ and~$Z$ with insertion,
+deletion, ranking and unranking on them in constant time.
+
+When the algorithm selects a~submatrix $M'=M^{1,k}$ for an~element $x$ of~rank~$k-1$, this
+matrix it is described by either by the choice of $z'=z-1$ and~$Z'=Z\setminus\{x\}$ (if $x\in Z$)
+or $z'=z$ and $Z'=Z$ (if $x\not\in Z$).
+All computations of~$N_0$ in the algorithm can therefore be replaced by looking
+up the appropriate $n_0(z',\vert A\vert-1)$ in the precomputed table. Moreover, we can
+calculate a~single~$C_a$ in constant time, because all summands are either $n_0(z,\vert A\vert-1)$
+or $n_0(z-1,\vert A\vert-1)$ depending on the set~$Z$. We get:
+$$C_a = r\cdot n_0(z-1,\vert A\vert-1) + (a-r) \cdot n_0(z,\vert A\vert-1),$$
+where $r=R_Z(R^{-1}_A(a))$, that is the number of restricted elements among the $a$~smallest ones in~$A$.
+
+All operations at a~single level of the \<Rank> function now run in constant time,
+but \<Unrank> needs to search among the~$C_a$'s to find the first of them which
+exceeds the given rank. We could use binary search, but that would take $\Theta(\log n)$
+time. There is however a~clever trick: the value of~$C_a$ does not vary too much with
+the set~$Z$. Specifically, by Corollary~\ref{smalldiff} the difference between the values
+for $Z=\emptyset$ and $Z=A$ is at most $n_0(z-1,\vert A\vert -1)$. It is therefore
+sufficient to just divide the rank by $n_0(z-1,\vert A\vert-1)$ and we get either
+the correct value of~$a$ or one more. Both possibilities can be checked in constant time.
+
+We can therefore conclude this section by the following theorem:
+
+\thmn{Ranking of derangements}%
+For every~$n$, the derangements on the set~$[n]$ can be ranked and unranked according to the
+lexicographic order in time~$\O(n)$ after spending $\O(n^2)$ on initialization of auxiliary tables.
+
+\proof
+We modify the general algorithms for (un)ranking of restricted permutations (\ref{rrankalg} and \ref{runrankalg})
+as described above (\ref{rrankmod}). Each of the $n$~levels of recursion will then run in constant time. The values~$n_0$ will
+be looked up in a~table precalculated in quadratic time as shown in Corollary~\ref{nzeroprecalc}.
+\qed

 
 \endpart
 
 \endpart