Split the large section on restricted permutations.

[saga.git] / rank.tex

diff --git a/rank.tex b/rank.tex
index 60a3be2bf43a79b98ff43863234e0a9de1ea5bd9..fe43933d28740f4a95bb7bb47c5b70ac2cb0316e 100644 (file)
--- a/rank.tex
+++ b/rank.tex
@@ -290,7 +290,7 @@ 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
 ranked are restricted permutations. An~archetypal member of this class are
@@ -560,8 +560,12 @@ spend time $\O(n^2)$ on operations with the set~$A$, $\O(n^4)$ on matrix manipul
 and $\O(n^2\cdot t(n))$ by the computations of the~$N_0$'s.
 \qed
 
-\rem
-This time bound is obviously very coarse, its main purpose was to demonstrate that
+%--------------------------------------------------------------------------------
+
+\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
@@ -571,9 +575,9 @@ 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
-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
 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