This homework set is due **Wednesday, February 15th**, at the beginning of lecture, but feel free to turn it in earlier if possible.

**1.** The** Bell numbers** are defined by letting (for ) be the **number of equivalence relations** on a set of elements. As shown in class, an equivalence relation is essentially the same as a partition of a set, so one can also define as the number of ways of partitioning a set of size into non-empty pieces. (For convenience, we define .)

For example, : If , the only two equivalence relations on are and . They correspond to the two partitions and .

Find . (Please do not just give me three numbers, but also provide a proof of the values you obtain.)

**2.** Verify that .

**3.** Draw a diagram illustrating the equivalence classes of the following equivalence relations (please also verify that they are, in fact, equivalence relations):

- In , set iff the points and lie on the same line through the origin. (Why did I remove the origin from the set ?)
- In , set iff .

**4.** Given a finite set , let be the **power set** of , that is, the collection of all subsets of . Define a relation on by setting iff and have the same size. Show that is an equivalence relation. If has size , find the number of equivalence classes, and the size of each class.

**5.** References for this problem are the books “How the other half thinks,” by Sherman Stein (there is a nice review of this book in the Notices of the AMS), and “Shift register sequences,” by Solomon Golomb (this one is hard to find).

Find a 4-full and a 5-full sequence.

Recall that a sequence consisting only of the letters and is **-full** iff every -tuple appears exactly once, so for example is 2-full.

Prove that in any -full sequence the first terms and the last terms coincide. For example, in the 2-full sequence the first and last terms are , while in the 3-full sequence the first two terms are , and so are the last two terms.

[**Edit (Feb. 7):** A more recent and in-depth reference is the book “Algebraic shift register sequences” by Mark Goresky and Andrew Klapper, Cambridge University Press, March 31, 2012. A pdf of a draft version can be found here.]

**6.** A reference for this problem is the paper *Long finite sequences*, by Harvey Friedman, *J. Combin. Theory Ser. A* **95 (1)** (2001), 102–144, but please try not to consult the paper while working on the problem.

Recall that, following Friedman, we defined a sequence to have **property ** iff there are no such that the sequence is a subsequence of the sequence , where we say that is a **subsequence** of iff there are such that

We defined as the largest such that there is a sequence with property and each is one of

Find (with proof) as large a lower bound as you can for the number . The person who finds the largest lower bound will receive an additional extra credit bonus. For extra credit, find an upper bound for . Recall that is a **lower bound** for iff , and is an **upper bound** for iff .

(You are free to use a computer if it helps. If you do, please also turn in a copy of the code you use.)

[…] is a link to the review of the paper on MathSciNet. As mentioned on Homework II, you may want to wait until after you have turned in your homework before looking at the paper (or […]

[…] want to give a brief idea of the size of Friedman’s , as defined on homework 2. The reference for what follows […]

[…] of producing a really long sequence giving us a better bound for than what you obtained when the homework was due, please turn it in as well.) […]

[…] of producing a really long sequence giving us a better bound for than what you obtained when the homework was due, please turn it in as well.) 43.614000 -116.202000 Like this:LikeBe the first to like […]

[…] want to give a brief idea of the size of Friedman’s , as defined on homework 2. The reference for what follows […]

[…] is a link to the review of the paper on MathSciNet. As mentioned on Homework II, you may want to wait until after you have turned in your homework before looking at the paper (or […]