Seeking combinatorial or group theoretic proof for permutation identity While working on another problem, I found the following combinatorial equality, but I got it analytically, and I'm curious to find a counting argument.
Fix $n$ a positive integer. For $n_1\leq n_2\leq \cdots \leq n_k$ with $\sum n_i=n$, let $s_{n_1,\dots,n_k}$ be the number of permutations in $\Sigma_n$ with sorted cycle lengths $n_1,n_2,\dots,n_k$. 
Then show:
$$\sum_{n_1,\dots,n_k} 4^{k-1}s_{n_1,\dots,n_k}=n\cdot n!$$
where the sum is restricted to the case where all $n_i$ are odd.
I suppose we could just write $t_k$ as the number of permutations in $\Sigma_n$ composted of $k$ odd cycles, and write it as $\sum_{k} 4^{k-1}t_k = n\cdot n!$.
For example, for $n=5$, the possible permutations of signature $s_{5}=4!$, $s_{1,1,3}=2\binom{5}{2}=20$, $s_{1,1,1,1,1}=1$ so the sum is:
$$4^0\cdot24+4^2\cdot 20 + 4^4\cdot 1=600=5\cdot 5!$$
I have a proof of this, which is gross - it involves substituting the power series for $\theta=\arctan x$ into the power series for $\sin 4\theta$ and $\cos 4\theta$ (for odd and even $n$, respectively.) That seems unpleasant, so I am seeking a more direct combinatorial argument.
One thing I considered was the possibility of using the identity:
$$\sum_{n=0}^{m} n\cdot n! =(m+1)!-1$$
 A: Permutations with odd cycles only and cycle count marked have 
the species
$$\mathfrak{P}(\mathcal{U}\mathfrak{C}_{=1}(\mathcal{Z})
+ \mathcal{U}\mathfrak{C}_{=3}(\mathcal{Z})
+ \mathcal{U}\mathfrak{C}_{=5}(\mathcal{Z})
+ \mathcal{U}\mathfrak{C}_{=7}(\mathcal{Z})
+ \cdots).$$
which yields the EGF
$$G(z,u) =
\exp\left(uz+
u\frac{z^3}{3}+
u\frac{z^5}{5}+
u\frac{z^7}{7}+\cdots\right)
\\ = \exp\left(u\sum_{k\ge 0}\frac{z^{2k+1}}{2k+1}\right)
\\ = \exp\left(u\log\frac{1}{1-z}
- u\sum_{k\ge 1} \frac{z^{2k}}{2k}\right)
\\ = \exp\left(u\log\frac{1}{1-z}
- u\frac{1}{2}\log\frac{1}{1-z^2}\right).$$
Now here we have $u=4$ so we continue with
$$\frac{1}{(1-z)^4}
\exp\left(2\log(1-z^2)\right)
= \frac{(1-z^2)^2}{(1-z)^4}
= \frac{(1+z)^2}{(1-z)^2}
\\ = (1+2z+z^2) \frac{1}{(1-z)^2}.$$
We get as our result the quantity
$$\frac{1}{4} n! [z^n] G(z, 4)
= \frac{1}{4} n!
\left({n+1\choose 1} + 2{n\choose 1}
+ {n-1\choose 1}\right)
\\ = \frac{1}{4} n!
(n+1+2n+n-1) = n! \times n.$$
A: I am going to introduce a fancy structure, that is a coloured permutation. 
A coloured permutation $\sigma$ is a permutation acting on $\{1,2,\ldots,n\}$, with the property that every element has an odd order. Moreover, the elements of $\{1,\ldots,n\}$ are coloured with some colour from $\{\text{cyan},\text{magenta},\text{yellow},\text{black}\}$ and the permutation is colour-preserving, i.e. the colour of $\sigma(a)$ is the same as the colour of $a$. We want to count the number of coloured permutations,
given by:
$$ L_n=\!\!\!\!\sum_{\substack{n_1,\ldots,n_k \text{ odd}\\ n_1+\ldots n_k=n}}\!\!\! 4^k\cdot s_{n_1,\ldots,n_k}.$$
Preliminary lemma: the number of permutations of $\{1,\ldots,k\}$ such that every element has an odd order is given by:
$$ C_k =  k!\cdot [x^k]\frac{1}{1-x}\cdot\exp\left(-\frac{x^2}{2}-\frac{x^4}{4}-\ldots\right)= k!\cdot [x^k]\sqrt{\frac{1+x}{1-x}}. $$
Consequence: the number of coloured permutations is given by
$$ \sum_{c+m+y+k=n}\binom{n}{c}\binom{n-c}{m}\binom{n-c-m}{y} C_c C_m C_y C_k = n!\cdot [x^n]\left(\frac{1+x}{1-x}\right)^2=4n\cdot n!.$$ 
Done. Double counting wins again.

Another chance would be given by showing that $L_{n+1}-L_n = (n+1)!-n!$ by some recursive argument. However, I was not able to find it.
