26 Chapter 1 Fundamentals
Remove n + 1 and split the remainder of X
1
into singleton sets {x
1
}, {x
2
}, . . . , {x
m
}. Now
{{x
1
}, {x
2
}, . . . , {x
m
}, X
2
, X
3
, . . . , X
k
} is a partition of the n −1 element set {1, 3, . . . , n}.
Subtracting one from all the elements except 1 produces a partition of [n −1] with at least
one singleton set. If p ∈ A
n,1
, designate the partition of [n − 1] obtained in this way by
f(p).
Now we define a function g from B
n−1
to A
n,1
. If partition p ∈ B
n−1
contains no sin-
gletons, say p = {X
1
, . . . , X
k
}, add two to every element forming sets X
∗
i
, and let g(p) =
{{1}, {2}, X
∗
1
, . . . , X
∗
k
}. If p contains singletons, say p = {{x
1
}, {x
2
}, . . . , {x
m
}, X
2
, X
3
, . . . , X
k
},
then add 1 to all elements except 1, forming a partition {{x
∗
1
}, {x
∗
2
}, . . . , {x
∗
m
}, X
∗
2
, X
∗
3
, . . . , X
∗
k
}
of the set {1, 3, . . . , n}. Now let g(p) = {{2}, {x
∗
1
, x
∗
2
, . . . , x
∗
m
, n + 1}, X
∗
2
, . . . , X
∗
k
}.
Since f (g(p)) = p and g(f(p)) = p, f and g are inverses and so f is a bijection between
A
n,1
and B
n−1
, as desired.
Exercises 1.4.
1. Show that if {A
1
, A
2
, . . . , A
k
} is a partition of {1, 2, . . . , n}, then there is a unique equivalence
relation ≡ whose equivalence classes are {A
1
, A
2
, . . . , A
k
}.
2. Suppose n is a square-free number, that is, no number m
2
divides n; put another way, square-
free numbers are products of distinct prime factors, that is, n = p
1
p
2
···p
k
, where each p
i
is prime and no two prime factors are equal. Find the number of factorizations of n. For
example, 30 = 2 ·3 ·5, and the factorizations of 30 are 30, 6 ·5, 10 ·3, 2 ·15, and 2 ·3 ·5. Note
we count 30 alone as a factorization, though in some sense a trivial factorization.
3. The rhyme scheme of a stanza of poetry indicates which lines rhyme. This is usually expressed
in the form ABAB, meaning the first and third lines of a four line stanza rhyme, as do the
second and fourth, or ABCB, meaning only lines two and four rhyme, and so on. A limerick
is a five line poem with rhyming scheme AABBA. How many different rhyme schemes are
possible for an n line stanza? To avoid duplicate patterns, we only allow a new letter into
the pattern when all previous letters have been used to the left of the new one. For example,
ACBA is not allowed, since when C is placed in p osition 2, B has not been used to the left.
This is the same rhyme scheme as ABCA, which is allowed.
4. Another way to express the Bell numbers for n > 0 is
B
n
=
n
k=1
S(n, k),
where S(n, k) is the number of partitions of {1, 2, . . . , n} into exactly k parts, 1 ≤ k ≤ n.
The S(n, k) are the Stirling numbers of the second kind. Find a recurrence relation
for S(n, k). Your recurrence should allow a fairly simple triangle construction containing the
values S(n, k), and then the Bell numbers may be computed by summing the rows of this
triangle. Show the first five rows of the triangle, n ∈ {1, 2, . . . , 5}.
5. Let A
n
be the number of partitions of {1, 2, . . . , n + 1} in which no consecutive integers
are in the same part of the partition. For example, when n = 3 these partitions are
{{1}, {2}, {3}, {4}}, {{1}, {2, 4}, {3}}, {{1, 3}, {2}, {4}}, {{1, 3}, {2, 4}}, {{1, 4}, {2}, {3}},
so A
3
= 5. Let A(n, k) be the number of partitions of {1, 2, . . . , n + 1} into exactly k parts,