# 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.