From 4c60b74b53bb951ebe9b64267fa7c9ea241d887e Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Wed, 27 Feb 2008 19:32:00 +0100 Subject: [PATCH] Uff. The bound seems to work. --- rank.tex | 79 ++++++++++++++++++++++++++++++++++++++------------------ 1 file changed, 54 insertions(+), 25 deletions(-) diff --git a/rank.tex b/rank.tex index ceea89f..8df70ca 100644 --- a/rank.tex +++ b/rank.tex @@ -578,7 +578,7 @@ 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 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. @@ -602,29 +602,6 @@ number of matchings is an~isomorphism invariant, the lemma follows. 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{ @@ -632,7 +609,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 $z0$, $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\}$ which satisfy~$M_z^{1,1}$, +so there are $n_0(z-1,d-1)$ of them. +\qed + +\cor For every $0\le z