From e4b43f1ab23c4c86c9e8b79e11c927280d48ad62 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Wed, 27 Feb 2008 20:45:16 +0100 Subject: [PATCH] Split the large section on restricted permutations. --- macros.tex | 1 + rank.tex | 14 +++++++++----- 2 files changed, 10 insertions(+), 5 deletions(-) diff --git a/macros.tex b/macros.tex index ec1cb6d..3e0ba4e 100644 --- a/macros.tex +++ b/macros.tex @@ -354,6 +354,7 @@ \def\algn{\alg\label} \def\notan{\nota\labelx} \def\examplen{\example\labelx} +\def\problemn{\problem\labelx} \def\proof{\noindent {\sl Proof.}\enspace} \def\proofsketch{\noindent {\sl Proof sketch.}\enspace} diff --git a/rank.tex b/rank.tex index 60a3be2..fe43933 100644 --- 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 -- 2.39.2