Proof on a property of Stirling Numbers of the first kind

Question

How should i proceed to prove that the sum of every odd stirling number on a row is n!/2?

$$\sum\limits_{k=1|k=odd}^n s(n,k)=\frac{n!}{2}$$

Answer 1

HINT:

$s(n, k)$ is the number of permutations of $1, 2, ..., n$ that can be expressed as a product of $k$ cycles with disjoint orbits. Therefore, $n! = s(n, 0) + ... + s(n, n)$.

Show that $\sum\limits_{k=1|k \equiv 0 \mod 2}^n s(n,k)=\sum\limits_{k=1|k \equiv 1 \mod 2}^n s(n,k)$

And you're done. For that, define a bijection between two sets whose cardinalities are $\sum\limits_{k=1|k \equiv 0 \mod 2}^n s(n,k)$ and $\sum\limits_{k=1|k \equiv 1 \mod 2}^n s(n,k)$.

Answer 2

Recall that permutations by cycles are the following species: $$\mathfrak{P}(\mathfrak{C}(\mathcal{Z})).$$

Therefore the bivariate generating function of permutations by the number of cycles is $$\exp\left(u\log\frac{1}{1-z}\right).$$ It follows that the generating function of permutations with an odd number of cycles is $$\frac{1}{2}\exp\left(+1\times\log\frac{1}{1-z}\right) -\frac{1}{2}\exp\left(-1\times\log\frac{1}{1-z}\right).$$ This simplifies to $$\frac{1}{2}\frac{1}{1-z}-\frac{1}{2}(1-z).$$ Extracting coefficients we get that for $n\ge 2$ $$n! [z^n]\left(\frac{1}{2}\frac{1}{1-z}-\frac{1}{2}(1-z)\right) =\frac{1}{2}n!$$ We get for $n=1$ the result $1/2+1/2=1$ and for $n=0$, zero.