Problem (a): Find recurrence relations for the Stirling partition numbers
and the Stirling cycle numbers
and tabulate them for .
Problem (b): Prove that
are polynomials in n for each fixed k.
Problem (c): Show that there is a unique way to extend the definition of
over all integers n and k so that the recurrence relations in (a) are preserved and the “boundary conditions”
and which equals
() are fulfilled.
Prove the duality relation:
is equal to
Possible recurrence relations are
which is equal to the sum of
Observe that in a partition of n elements into classes, at least classes must be singletons.
For the Stirling partition numbers, write the recurrence relations in (a) as
is equal to the sum of
to get a recurrence for negative values of k.
satisfy the same recurrence and boundary conditions.