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