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!

  • $\begingroup$ Can you restate the question more clearly? Your defintion of $G(n;k)$ has nothing to do with "regulations". $\endgroup$ – MarkG Feb 14 '15 at 14:02
  • $\begingroup$ Is this more clear? $\endgroup$ – iJup Feb 14 '15 at 14:29
  • $\begingroup$ No. What does the number of unique orders have to do with $G(n;k)$? A small example might help. $\endgroup$ – MarkG Feb 14 '15 at 14:33

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*}

  • $\begingroup$ Super! One thing remains, can you give a combinatorial interpretation of the $sum = n!$ proof? $\endgroup$ – iJup Feb 14 '15 at 15:14
  • $\begingroup$ We can do it via the recurrence relation (as above), or quite simply see that there are $n!$ permutations, and every permutation must appear in the sum exactly once, implying equality between the two numbers. $\endgroup$ – Marcus M Feb 14 '15 at 15:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.