4. Given positive integers $m, n(2 \leqslant m \leqslant 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 \leqslant k < l \leqslant 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.
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 its position index; "there exist integers $k, l(1 \leqslant ka_{l}$" means the permutation is not monotonically increasing.

A permutation that is not a good permutation is called a "bad permutation". Then a bad permutation simultaneously satisfies: (1) odd positions must be filled with odd numbers, even positions must be filled with even numbers; (2) monotonically increasing.
Next, we will find the number of bad permutations. Let $P$ be the set of all bad permutations, and $Q$ be the set of all monotonically increasing sequences formed by choosing $m$ items from $1,2, \cdots,\left[\frac{m+n}{2}\right]$.

For any sequence $a_{1}, a_{2}, \cdots, a_{m}$ in $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} \leqslant n, k \leqslant m$, by condition (1), all $\frac{a_{k}+k}{2}$ belong to the set
$\left\{1,2, \cdots,\left[\frac{m+n}{2}\right]\right\}$; and by condition (2), the sequence $\left\{\frac{a_{k}+k}{2}\right\}(k=1,2, \cdots, m)$ is monotonically increasing. Clearly, $f$ is an injection from $P \rightarrow Q$.
Next, we prove that $f$ is a surjection. In fact, for any sequence $b_{1}, b_{2}, \cdots, b_{m}$ in $Q$, let $a_{k}=2 b_{k}-k(k=1,2, \cdots, m)$, since $b_{k+1}>b_{k} \Rightarrow b_{k+1} \geqslant b_{k}+1$, then $a_{k+1}-a_{k}=\left(2 b_{k+1}-k-1\right)-\left(2 b_{k}-k\right)=2\left(b_{k+1}-b_{k}\right)-1 \geqslant 1(1 \leqslant k \leqslant m)$, thus $a_{1}, a_{2}, \cdots, a_{m}$ is monotonically increasing;
Also, $a_{1} \geqslant 1, a_{m} \leqslant 2\left[\frac{m+n}{2}\right]-m \leqslant n$, and $a_{k}+k=2 b_{k}$ is even, so $a_{1}, a_{2}, \cdots, a_{m}$ is a permutation in $P$, and satisfies $f\left(a_{1}, a_{2}, \cdots, a_{m}\right)=\left(b_{1}, b_{2}, \cdots, b_{m}\right)$, hence $f$ is a surjection. In summary, $f$ is a bijection from $P \rightarrow Q$, thus $|P|=|Q|$.
The sequences in $Q$ correspond one-to-one with all $m$-element subsets of the set $\left\{1,2, \cdots,\left[\frac{m+n}{2}\right]\right\}$, so $|P|=|Q|=C_{\left[\frac{m+n}{2}\right]}^{m}$.

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