Solution:

Let the positions of the books in the stack be $1,2,3, \ldots, 2000$ from the top (and consider them modulo $2000$). Notice that both operations fix the parity of the number of the book at any given position. Operation (i) subtracts an even integer from the number of the book at each position. If $A$ is an operation of type (i), and $B$ is an operation of type (ii), then the operation $A^{-1} B A$ changes the order of the books in the positions $n+1$ to $n+m$ where $n$ is even and $m$ is odd. This is called turning the interval.

Now we prove that all the volumes in odd positions can be placed in the odd positions in every way we like: If the volume we want in position $1$ is in position $m_{1}$, we turn the interval $1$ to $m_{1}$. Now if the volume we want in position $3$ is in position $m_{3}$, we turn the interval $3$ to $m_{3}$, and so on. In this way we can permute the volumes in odd positions exactly as we want to.

Now we prove that we can permute the volumes in even positions exactly as we want without changing the positions of the volumes in the odd positions: We can make a transposition of the two volumes in position $2n$ and $2n+2m$ by turning the interval $2n+1$ to $2n+2m-1$, then turning the interval $2n+2m+1$ to $2n-1$, then turning the interval $2n+1$ to $2n-1$, and finally adding $2m$ to the number of the volume in each position.

Since there are $1000!$ permutations of the volumes in the odd positions, and $1000!$ permutations of the volumes in the even positions, altogether we have $(1000!)^{2}$ different permutations.

Solution:

We show that the volumes can be permuted so that the volumes with odd numbers are in an arbitrary order in the odd-numbered places and the volumes with even numbers are in an arbitrary order in the even-numbered places. The main idea is to construct two combinations of the allowed operations. The first one turns the volumes in a specified interval, starting and ending in an odd-numbered place, in the opposite order while keeping everything outside this interval fixed, or keeps everything fixed in an interval while turning the order of the volumes outside this interval in the opposite direction, when the counting starts below that interval and is continued from the top after reaching the bottom volume. The second combined operation just exchanges two volumes in even-numbered places while keeping everything else fixed.

Let $E=\{1,2, \ldots, 2000\}$. We formulate the operations described in conditions (i) and (ii), depending on an even integer $n$ and odd integer $m$ as functions $f_{n}: E \rightarrow E$ and $g_{m}: E \rightarrow E$, defined by

$$f_{n}(p)=\begin{cases} 2000+p-n & \text{ for } p \geq n, \\ p-n & \text{ for } n<p \end{cases} \quad \text{and} \quad g_{m}(p)= \begin{cases}m-p+1 & \text{ for } p \leq m \\ p & \text{ for } m<p\end{cases}$$

We immediately see that $f_{n}$ and $g_{m}$ map even numbers into even numbers and odd numbers into odd numbers. So the volumes can never be permuted so that an odd-numbered volume would be in an even place or an even-numbered would be in an odd place. The observation $f([1, n])=[2000-(n+1), 2000]$ easily leads to $f_{n}^{-1}=f_{2000-n}$.

Now let $n$ be even and $m$ odd and $n+m<2000$. Consider the combined mapping $f_{n}^{-1} \circ g_{m} \circ f_{n}$. If $n<n+p \leq n+m$, then $f_{n}(n+p)=p \leq m$, $g_{m}(p)=m-p+1<2000-n$ and $f_{n}^{-1}(m-p+1)=f_{2000-n}(m-p+1)=2000+m-p+1-2000+n=n+m+1-p$. Because $f_{n}([n+1, n+m])=[1, m]$, $f_{n}$ maps numbers $p$ outside the interval $[n+1, n+m]$ into numbers outside the interval $[1, m]$; $g_{m}$ keeps these numbers fixed and $f_{n}^{-1}$ returns $f_{n}(p)$ into $p$. So we have shown that for any interval $[s, t] \subset E$ with $s$ and $t$ odd, there is a function $h_{s, t}$, combined of functions of the $f$ type and $g$ type such that $h_{s, t}$ reverses the order of numbers in the interval $[s, t]$ and is the identity function outside this interval.

The functions $h_{s, t}$ allow us to order the odd numbers in an arbitrary manner. If $p_{1}$ ought to be in position $1$, then apply (if needed) $h_{1, p_{1}}$; if the number $p_{2}$ which ought to be in position $3$ now is in position $x$, the $x \geq 3$ and we may apply (if needed) $h_{3, x}$. Continuing this way, we eventually arrive at the desired order of the odd numbers.

To construct the second one of the desired operations, we have to obtain a counterpart for $h_{s, t}$ for $t<s$. To this end, consider $f_{n}^{-1} \circ g_{m} \circ f_{n}$ for $m+n>2000$. By the definition of $f_{n}$, $f_{n}(n+m-2000)=2000+(n+m-2000)-n=m$, and so $f_{n}[n+m-2000+1, n]=[m+1, 2000]$. Consequently, $f_{n}^{-1} \circ g_{m} \circ f_{n}$ keeps numbers in the interval $[n+m-2000+1, n]$ (with even endpoints) fixed. Since $g_{m}$ turns the order around in $[1, m]$ and $f_{n}^{-1}=f_{2000-n}$ maps $[1, m]$ onto the complement of $[n+m-2000+1, n]$ in such a way that $f_{2000-1}(1)=n+1$, the order of numbers in the complement is reversed in the desired manner. We have shown that for odd $s$ and $t$ such that $t<s$ there exists a function $h_{s, t}$, combined of functions of the $f$ type and $g$ type such that $h_{s, t}$ is the identity on the interval $[t+1, s-1]$, but reverses the order of the numbers outside this interval, when counting is started from $s$ and continued through over $2000$ and $1$ over to $t$, in other words modulo $2000$.

To finish the proof, we show that two numbers in the even positions can be exchanged while everything else is fixed. This clearly allows us to put the even numbers in an arbitrary order without violating the order of the odd numbers. To achieve this, we take two even numbers $p$ and $q$, $p<q$, and consider the function $\phi_{p, q}=f_{2000+p-q} \circ h_{p+1, p-1} \circ h_{q+1, p-1} \circ h_{p+1, q-1}$. The innermost function $h_{p+1, q-1}$ reverses the order on $[p+1, q-1]$ and fixes everything else, the next function $h_{q+1, p-1}$ fixes numbers in $[p, q]$, $h_{p+1, p-1}$ fixes $p$ and reverses the order $(\bmod 2000)$ in $E \setminus \{p\}$, and $f_{2000+p-q}(p)=q$. The two innermost components of $\phi_{p, q}$ fix $q$, $h_{p+1, p-1}$ takes $q$ to a position $x$ $q-p$ steps ahead of $p$ $(\bmod 2000)$ and $f_{2000+p-q}=f_{q-p}^{-1}$ moves $x$ $q-p$ positions back, i.e. to $p$. If $p+k$ is between $p$ and $q$, then the innermost function maps it to $q-k$, the next one fixes $q-k$, the third function maps $q-k$ to $p-(q-k-p)=2p-q+k$ $(\bmod 2000)$, and $f_{q-p}^{-1}$ maps $2p-q+k$ back to $p+k$. A similar reasoning shows that $\phi_{p, q}$ also fixes numbers in $E \setminus [p, q]$.

Since both even and odd numbers have $1000!$ different permutations, the volumes can be permuted into $(1000!)^{2}$ different orders by using the given operations repeatedly.

Solution:

We show by induction, that if in an ordered sequence one may exchange two consecutive elements without changing the places of any other element, then any two elements can be exchanged so that all other elements remain in place. We assume that this is true for elements which are at most $k$ steps away from each other in the sequence. Assuming that $a$ precedes $b$ by $k+1$ steps and that $c$ is immediately behind $a$, the following sequence of exchanges is allowed: $\ldots, a, c, \ldots, b, \ldots \rightarrow \ldots, a, b, \ldots, c, \ldots \rightarrow \ldots, b, a, \ldots, c, \ldots \rightarrow \ldots, b, c, \ldots, a, \ldots$. By assumption, all elements in the places indicated by three dots remain on their places, as does $c$.

If any two elements can be exchanged without violating the other elements, then the elements in the sequence can be arranged to any order. One just gets the desired first element to its place by (at most) one exchange, and if the first $k$ elements already are in their desired places, then the one wanted to be in place $k+1$ is not among the first $k$ elements, and it can be moved to its place by at most one exchange, not violating the order of the first $k$ elements.

We now show, that any two volumes in consecutive odd places can be exchanged. The volumes on top and in place $3$ can be exchanged by operation (ii) applied to the three topmost volumes. The volumes in places $2n+1$ and $2n+3$ can be exchanged by first applying operation (i) to the $2n$ topmost volumes, which moves them to the bottom but preserves their order, then applying (ii) to the three topmost volumes and finally operation (i) to the $2000-2n$ topmost volumes. The last operation returns the $2n$ volumes to top preserving the order and returns the remaining $2000-2n$ volumes to the bottom, preserving the order, save the volumes in places $2n+1$ and $2n+3$, which have changed places. By the general remarks above, it is now clear that operations (i) and (ii) can be used to arrange the volumes in odd positions into any order while the volumes in even positions remain in their places.

We still need to show, that a similar procedure is possible for volumes in even positions. First of all, the volumes in positions $1$ to $5$ can be moved to order $5,4,3,2,1$ by performing operation (ii) to the five topmost volumes. Then it is possible to exchange the volumes in positions $1$ and $5$ without changing anything else. So the volumes in even positions closest to the top can be exchanged. For volumes on positions $2n$ and $2n+2$ one can first perform operation (i) to the $2n-2$ topmost volumes. The volumes in places $2n$ and $2n+2$ will be taken to places $2$ and $4$, and they can be exchanged. Performing operation (i) to the $2000-(2n-1)$ topmost volumes then returns everything to their previous places, except that the volumes in positions $2n$ and $2n+2$ have changed places. So all volumes in even positions can be put into any order by using the operations (i) and (ii), and the total number of possible orderings is $(1000!)^{2}$.