305 – Homework II

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.)

Advertisement