# Basic Enumeration continued

Problem (a): Find recurrence relations for the Stirling partition numbers $\left \{ \begin{array}{c} n \\ k \end{array} \right \}$ and the Stirling cycle numbers $\left [ \begin{array}{c} n \\ k \end{array} \right ]$ and tabulate them for $n \leq 6$.

Problem (b): Prove that $\left \{ \begin{array}{c} n \\ n-k \end{array} \right \}$ and $\left [ \begin{array}{c} n \\ n-k \end{array} \right ]$ are polynomials in n for each fixed k.

Problem (c): Show that there is a unique way to extend the definition of $\left \{ \begin{array}{c} n \\ k \end{array} \right \}$ and $\left [ \begin{array}{c} n \\ k \end{array} \right ]$ over all integers n and k so that the recurrence relations in (a) are preserved and the “boundary conditions” $\left \{ \begin{array}{c} 0 \\ 0 \end{array} \right \}$ which equals $\left [ \begin{array}{c} 0 \\ 0 \end{array} \right ]=1$

and $\left \{ \begin{array}{c} 0 \\ m \end{array} \right \}$ which equals $\left [ \begin{array}{c} m \\ 0 \end{array} \right ]=0$ ( $m \neq 0$) are fulfilled.

Problem (d):

Prove the duality relation: $\left \{ \begin{array}{c} n \\ k \end{array} \right \}$ is equal to $\left [ \begin{array}{c} -k \\ -n \end{array} \right ]$.

Hints:

Hint (a):

Possible recurrence relations are $\left \{ \begin{array}{c} n + 1 \\ k \end{array} \right \}$ which is equal to the sum of $\left \{ \begin{array}{c} n \\ k -1 \end{array} \right \}$ and $k \left \{ \begin{array}{c} n \\ k \end{array} \right \}$.

Hint (b):

Observe that in a partition of n elements into $n-k$ classes, at least $n-2k$ classes must be singletons.

Hint (c):

For the Stirling partition numbers, write the recurrence relations in (a) as $\left \{ \begin{array}{c} n\\ k-1\end{array} \right \}$ is equal to the sum of $\left \{ \begin{array}{c} n+1\\ k \end{array} \right \}$ and $-k \left \{ \begin{array}{c} n \\ k \end{array} \right \}$ to get a recurrence for negative values of k.

Hint (d): $\left \{ \begin{array}{c} n\\ k\end{array} \right \}$ and $\left [ \begin{array}{c} -k\\ -n\end{array} \right ]$ satisfy the same recurrence and boundary conditions.

More later,

Nalin Pithwa.