Basic Enumeration continued

Posted by Nalin Pithwa

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.

Leave a Reply Cancel reply

Enter your comment here...

Fill in your details below or click an icon to log in:

Email (required) (Address never made public)

Name (required)

Website

You are commenting using your WordPress.com account. ( Log Out / Change )

You are commenting using your Google+ account. ( Log Out / Change )

You are commenting using your Twitter account. ( Log Out / Change )

You are commenting using your Facebook account. ( Log Out / Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: