4. (This question is worth 50 points) Given positive integers $m, n(2 \leq m \leq n)$, let $a_{1}, a_{2}, \cdots, a_{m}$ be a permutation of $m$ distinct numbers chosen from $1,2, \cdots, n$. If there exists $k \in\{1,2, \cdots, m\}$ such that $a_{k}+k$ is odd, or there exist integers $k, l(1 \leq k < l \leq m)$ such that $a_{k} > a_{l}$, then $a_{1}, a_{2}, \cdots, a_{m}$ is called a "good permutation". Determine the number of all good permutations.
Solution: First, note that "there exists $k \in\{1,2, \cdots, m\}$, such that $a_{k}+k$ is odd" means there is a number whose parity is different from the parity of its position index; "there exist integers $k, l(1 \leq k < l \leq m)$ such that $a_{k} > a_{l}$" means the permutation is not monotonically increasing.

We call permutations that are not good permutations "bad permutations". Below, we first find the number of bad permutations, then subtract the number of bad permutations from the total number of permutations. Note that bad permutations simultaneously satisfy: (1) odd positions must be filled with odd numbers, even positions must be filled with even numbers; (2) monotonically increasing. 10 points

Next, we find the number of bad permutations. Let $\mathrm{P}$ be the set of all bad permutations, and $\mathrm{Q}$ be the set of all monotonically increasing sequences formed by choosing $m$ items from $1,2, \cdots,\left[\frac{n+m}{2}\right]$. For any permutation $a_{1}, a_{2}, \cdots, a_{m}$ in $\mathrm{P}$, define
$$
f\left(a_{1}, a_{2}, \cdots, a_{m}\right)=\left(\frac{a_{1}+1}{2}, \frac{a_{2}+2}{2}, \cdots, \frac{a_{m}+m}{2}\right).
$$

Since $a_{k} \leq n, k \leq m$, by condition (1), all $\frac{a_{k}+k}{2}$ belong to the set $\left\{1,2, \cdots,\left[\frac{n+m}{2}\right]\right\}$. By condition (2), $\left\{\frac{a_{k}+k}{2}\right\}(k=1,2, \cdots, m)$ is monotonically increasing. Therefore, the above-defined $f$ gives a mapping from $P \rightarrow Q$. Clearly, $f$ is an injection. 30 points

Next, we prove that $f$ is a surjection. In fact, for any sequence $b_{1}, b_{2}, \cdots, b_{m}$ in $\mathrm{Q}$, let $a_{k}=2 b_{k}+1$ $(k=1,2, \cdots, m)$. Since the integers $b_{k+1} > b_{k}$, we have $b_{k+1} \geq b_{k}+1$, thus
$$
a_{k+1}-a_{k}=2\left(b_{k+1}-b_{k}\right)-1 \geq 1(1 \leq k \leq m-1)
$$

Hence, $a_{1}, a_{2}, \cdots, a_{m}$ is monotonically increasing.
Also, $a_{1} \geq 1$, and $a_{m} \leq 2\left[\frac{n+m}{2}\right]-m \leq n$, and $a_{k}+k=2 b_{k}$ is even, so $a_{1}, a_{2}, \cdots, a_{m}$ is a permutation in $\mathrm{P}$. Clearly, $f\left(a_{1}, a_{2}, \cdots, a_{m}\right)=\left(b_{1}, b_{2}, \cdots, b_{m}\right)$, so $f$ is a surjection.
In summary, $f$ is a bijection from $P \rightarrow Q$, hence $|P|=|Q|$. 40 points
Since all sequences in $\mathrm{Q}$ correspond one-to-one with all $m$-element subsets of the set $\left\{1,2, \cdots,\left[\frac{n+m}{2}\right]\right\}$, we have $|Q|=C_{\left[\frac{n+m}{2}\right]}^{m}$, thus $|P|=C_{\left[\frac{n+m}{2}\right]}^{m}$.

Finally, we subtract the number of bad permutations from the total number of permutations $P_{n}^{m}=\frac{n!}{(n-m)!}$, to get the number of all permutations as $\frac{n!}{(n-m)!}-C_{\left[\frac{n+m}{2}\right]}^{m}$. 50 points