1

For any integer n ≥ 1, let r(n) denote the number of different ways that the set [n] := {1, . . . , n} can be partitioned into disjoint non-empty subsets, the union of which is the entire set [n].

I need to first find r(3) and list all the ways it can be partitioned.

This part I did, r(3) = 5. Since the set {1, 2, 3} can be partitioned in 5 distinct ways: {{1}, {2}, {3}} ; {{1}, {2, 3}} ; {{2}, {1, 3}} ; {{3}, {1, 2}} ; & {{1, 2, 3}}.

Now I have to prove that, for all even integers n ≥ 2:

(n/2)^(n/2) ≤ r(n) ≤ n^n

I'm unsure of how to go about proving this?

Krzysztof Jaminski
  • 37

1 Answers1

1

One approach to questions with bounds on combinatoric items is to find a collection of $(\frac n2)^{n/2}$ partitions that you can define (even though it does not include all the partitions), then to find a collection of $n^n$ things that include all the partitions of interest (and also some other things).

For the upper bound, there are at most $n$ sets in the partition, so imagine making $n$ buckets and putting each number in one bucket. Assuming the buckets are different, there are $n^n$ ways to distribute the numbers, each representing a partition. We will have counted each partition many ways as in your problem the buckets are not distinct, but we will have gotten them all, so $r(n) \le n^n$

For the lower bound, imagine $\frac n2$ buckets and put the numbers $1$ through $\frac n2$ into them, one to each. Can you find $(\frac n2)^{n/2}$ distinct ways to finish the partition?

Ross Millikan
  • 374,822