The Art and Craft of Problem Solving

Stirling Numbers
Problems 6.4.16-- 6.4.22 develop a curious "dual" to
the Binomial Theorem.

6.4. 16 For n, k positive integers with n � k, define

{ �} (called the Stirling numbers of the second

kind)^7 to be the number of different partitions of a set
with n elements into k non-empty subsets. For exam-

ple, { � } = 6, because there are six three-part parti­

tions of the set {a,b, c,d}, namely

{a}, {b}, {c,d};

{b}, {e}, {a,d};

{a},{c},{b,d};

{b}, {d}, {a, c};

Show that for all n > 0,

(a) {�} = 1.

(b) {�} = 2�-^1 - 1.

(c)

{n:l}

=

G)'

{a}, {d}, {b,c};

{c}, {d}, {a,b}.

6.4. 17 Find a combinatorial argument to explain the
recurrence

6.4. 18 Imagine that you are going to give n kids ice­
cream cones, one cone per kid, and there are k dif­
ferent flavors available. Assuming that no flavors get
mixed, show that the number of ways we can give out
the cones using all k flavors is

6.4. 19 The previous problem should have reminded
you of Problem 6.3.16, which stated that number of

6.4 RECURRENCE 221

ways to give n kids ice-cream cones, one cone per kid,

using all of k different flavors available, is

It' -G) (k - 1 t + G) (k - 2 t -G) (k - 3)" +

... + (_I)k G)on.

Please do this now (using PIE), if you haven't already.

6.4.20 Combine the two previous problems, and you

get a nice formula for the Stirling numbers of the sec­

ond kind. It is not closed-form, but who's complain­

ing?

{

n

} = � {. (-I)' (

k

k ) (k -r)".

k. r�O r

6.4.21 Returning to the ice-cream cone problem, now

consider the case where we don't care whether we use

all k flavors.

(a) Show that now there are k" different ways to

feed the kids (this is an easy encoding problem

that you should have done before).

(b) Partition these kn possibilities by the exact num­

ber of flavors used. For example, let A I denote

the set of "feedings" in which just one flavor is

used; clearly IA II = k. Show that in general,

IArl = { ; } P(k, r).

6.4.22 The Stirling Number "Dual" of the Binomial

Theorem. For positive integers r, define

X-- :=x(x -I) · ··(x - r+ I).

(Thus X--is the product of r terms). Use the previous

problems to show that

(^7) See [16], Chapter 6, for information about Stirling numbers of the first kind.