Partitioning in groups - Combinatorial Proof Define $G(n;k)$ as the number of possibilities to portion out $n$ distinguishable elements into $k$ groups. For each group we count the number of unique orders. Two orders are different if they produce different cycles. (for example ABC and ACB are different, ABC and BCA are equal). 
Prove the following combinatorial: $G(n;k)=(n-1) \cdot G(n-1;k)+G(n-1;k-1)$ and $\sum\limits_{k=0}^n G(n;k) = n!$.
I am struggling with the combinatorial part of the proof. Can somebody help me with starting this proof in words? Thanx in advance!
 A: It seems to me that $G(n;k)$ is the number of permutations $w \in S_n$ that have exactly $k$ cycles.  Rather than using letters, I'll use numbers.  Then an element of $G(5;3)$ could look like $(1)(5)(243)$ which would be the same as $(1)(5)(432)$.  We can thus always put the smallest number at the beginning of each cycle.
In Combinatorics, these numbers $G(n;k)$ are referred to as Stirling Numbers of the First Kind.  When viewing these as cycles, it's easier to see that $$ \sum\limits_{k = 0}^n G(n;k) = \#\{\text{Permutations of } n \text{ elements with any number of cycles}\} = \# S_n = n!$$
For the recurrence relation, we can do the following: 
Choose a permutation $w \in G(n-1;k)$.  We can insert the symbol $n$ after any of the numbers $1,2,\ldots,n-1$ in the disjoint cycle decomposition of $w$ in $n-1$ ways, yielding a new permutation $w' \in G(n;k)$ where $n$ appears in a cycle of length at least $2$.  On the other hand, given a cycle $\sigma \in G(n-1;k-1)$, we can add the number $n$ as a cycle by itself, yielding a new element $\sigma' \in G(n;k)$.  We then see that every element of $G(n;k)$ can either be constructed by the above process from either a $w \in G(n-1,k)$ or a $\sigma \in G(n;k)$.  Every $w \in G(n-1;k)$ gives us $n-1$ unique elements of $G(n;k)$, and every $\sigma \in G(n-1;k-1)$ gives us $1$ element of $G(n;k)$.  Thus, we have the desire relation: $$ G(n;k) = (n-1)G(n-1;k) + G(n-1;k-1). $$ 
If you'd like, we can also prove that $\sum_k G(n;k) = n!$ using this relation.  We note that $G(n;0) = 0$ by definition and $G(n;k) = 0$ for $k > n$.  Then clearly $\sum G(1,k) = G(1,1) = 1$.  We proceed inductively.  Suppose that $\sum\limits_{k=0}^{n-1} G(n-1;k) = (n-1)!$.  Then \begin{align*}
\sum\limits_{k = 1}^n G(n;k) &= \sum\limits_{k = 1}^n(n-1) G(n-1;k) + G(n-1;k-1) \\
&= (n-1)\sum\limits_{k=1}^{n-1} G(n-1;k) + \sum\limits_{k=2}^n G(n-1; k-1) \\
&= (n-1)*(n-1)! + (n-1)! \\
&= n!
\end{align*}
