So here's an idea on how you can prove (1) combinatorially. Let $N$ be the set $\{1 \ldots n\}$, and define $Z = \{(R,B)\}$ where $R$ is a permutation of some subset of $N$ with exactly $m$ cycles (the "red" permutation), and $B$ is any permutation of the remaining elements of $N$ (the "blue" permutation).

On the one hand, for any $k \ge m$, you can start with any permutation of $N$ with $k$ cycles (of which there are $\begin{bmatrix} n \\ k \end{bmatrix}$), pick any $m$ of the $k$ cycles (which can be done in $\left (\begin{matrix} k \\ m \end{matrix}\right)$ ways) to color red, and then the remaining cycles define the blue permutation using cycle notation. This gives the left side of (1).

On the other hand, let $X$ be any permutation of $N \cup \{*\}$, where $*$ is not in $N$, with exactly $m+1$ cycles, of which there are $\begin{bmatrix} n+1 \\ m+1 \end{bmatrix}$. Color the $m$ cycles which do not contain $*$ red.

For the blue permutation, let the remaining cycle $Y$ containing $*$ be written as $(*,y_1, \ldots, y_{\ell})$; since a cycle is identical up to rotation, we may assume without loss of generality that $*$ comes first. Let $\{n_1 \ldots n_\ell\}$ be the elements of $N$ that appear in $Y$, where $n_i < n_{i+1}$; note that as sets $\{y_1 \ldots y_\ell\} = \{n_1 \ldots n_\ell\}$. Define the blue permutation via the function $\pi:n_i \rightarrow y_i$. So every $X$ corresponds to a unique $(R,B)$, showing the right side of (1).

So here's an idea on how you can prove (1) combinatorially. Let $N$ be the set $\{1 \ldots n\}$, and define $Z = \{(R,B)\}$ where $R$ is a permutation of some subset of $N$ with exactly $m$ cycles (the "red" permutation), and $B$ is any permutation of the remaining elements of $N$ (the "blue" permutation).

On the one hand, for any $k \ge m$, you can start with any permutation of $N$ with $k$ cycles (of which there are ${n\brack k}$), pick any $m$ of the $k$ cycles (which can be done in $\binom{k}{m}$ ways) to color red, and then the remaining cycles define the blue permutation using cycle notation. This gives the left side of (1).

On the other hand, let $X$ be any permutation of $N \cup \{*\}$, where $*$ is not in $N$, with exactly $m+1$ cycles, of which there are ${n+1\brack m+1}$. Color the $m$ cycles which do not contain $*$ red.

For the blue permutation, let the remaining cycle $Y$ containing $*$ be written as $(*,y_1, \ldots, y_{\ell})$; since a cycle is identical up to rotation, we may assume without loss of generality that $*$ comes first. Let $\{n_1 \ldots n_\ell\}$ be the elements of $N$ that appear in $Y$, where $n_i < n_{i+1}$; note that as sets $\{y_1 \ldots y_\ell\} = \{n_1 \ldots n_\ell\}$. Define the blue permutation via the function $\pi:n_i \rightarrow y_i$. So every $X$ corresponds to a unique $(R,B)$, showing the right side of (1).