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


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

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

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

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s