**Probl****em (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.