The Art and Craft of Problem Solving

220 CHAPTER 6 COMBINATORICS

Thus we can conclude that

en =

_ 1 (2n).

n+ 1 n

For a fascinating, purely combinatorial derivation of this formula, see [16], pp. 345-

346.

Problems and Exercises

In the problems below, you should notice, among other things, the ubiquity of Fibonacci-and

Catalan-style recurrences.

6.4.4 Consider a language whose alphabet has just

one letter, but in which words of any length are al­

lowed. Messages begin and end with words, and when

you type a message, you hit the space bar once be­

tween words. How many different messages in this

language can be typed using exactly n keystrokes?

6.4.5 For a set S of integers, define S + 1 to be {x + 1 :

XES}. How many subsets S of {I, 2, ... , n} satisfy

S U (S + 1) = {I ,2, ... ,n}? Can you generalize this?

6.4.6 Find the number of subsets of {I, 2, ... , n} that

contain no two consecutive elements of {I, 2, ... , n}.

6.4.7 Find the maximum number of regions in the

plane that are determined by n "vee"s. A vee is the

union of two distinct rays that share the same starting

point.

6.4.8 Fix positive a, b, c. Define a sequence of real

numbers by Xo = a, XI = b, and xn+ I = CXnXn-l. Find

a nice formula for Xn.

6.4.9 For each n 2 1, we call a sequence of n (s and n

)s "legal" if the parentheses match up, somehow. For

example, if n = 4, the sequence «)OO) is legal, but

O(»(O is not. Let en denote the number of legal ar­

rangements for the 2n parentheses. Find a recurrence

relation for en.

6.4. 10 How many ways can you tile a 3 x n rectangle

with 2 x 1 dominos?

6.4.11 (Putnam 1996) Define a selfish set to be a set

that has its own cardinality (number of elements) as an

element. Find, with proof, the number of subsets of

{I, 2, ... , n} that are minimal selfish sets, that is, self­

ish sets none of whose proper subsets is selfish.

6.4. 12 In Pascal's Triangle below, examine the sum

along each dotted line.

••

• .

: : .. : · (^1) ·

. 1 ··.:.

.

.

.

.

.

.

. · 2 ":"::::: 1.·.

I. .. (^3) ··· g ...
. (^1) · :. ·.· 4.
.
·
·
·
.. ·
6 ·
.
4
.}". ··· 5 · 10 10 5
Make a conjecture and prove it.
6.4. 13 Let u(n) denote the number of ways in which
a set of n elements can be partitioned. For example,
u(3) = 5, corresponding to
{a,b, c};
{a,c},{b};
{a,b},{c}; {a},{b,c};
{a},{b},{c}.
Find a recurrence relation for u(n). You might hope
that u(4) = 14 , suggesting a Catalan-style recurrence,
but unfortunately, u(4) = 15.
6.4. 14 A movie theater charges $5 for a ticket. The
cashier starts out with no change, and each customer
either pays with a $5 bill or offers a $10 bill (and gets
change). Clearly, the cashier will be in trouble if there
are too many customers with only $10 bills. It turns
out that there were 2n customers, and the cashier never
had to turn anyone away, but after dealing with the last
customer, there were no $5 bills left in the cash regis­
ter. Let Wn denote the number of different ways this
could have happened. Find a recurrence for Wn.
6.4. 15 The number of derangements Dn was defined
in Problem 6.3.13. Show that
and use this to prove by induction the formula given in
6.3.13.