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 B_0,B_1,B_2,\dots are defined by letting (for n>0) B_n be the number of equivalence relations on a set of n elements. As shown in class, an equivalence relation is essentially the same as a partition of a set, so one can also define B_n as the number of ways of partitioning a set of size n into non-empty pieces. (For convenience, we define B_0=1.)

For example, B_2=2: If A=\{a,b\}, the only two equivalence relations on A are E_1=\{(a,a),(b,b)\} and E_2=\{(a,a),(a,b),(b,a),(b,b)\}. They correspond to the two partitions P_1=\{\{a\},\{b\}\} and P_2=\{\{a,b\}\}.

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

2. Verify that B_{n+1}=\sum_{k=0}^n \binom nk B_k.

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

  • In X={\mathbb R}^2-\{(0,0)\}, set P\sim Q iff the points P and Q lie on the same line through the origin. (Why did I remove the origin from the set X?)
  • In X={\mathbb R}^2, set (a,b)\sim(c,d) iff a^2+b^2=c^2+d^2.

4. Given a finite set A, let X={\mathcal P}(A) be the power set of A, that is, the collection of all subsets of A. Define a relation on X by setting B\sim C iff B and C have the same size. Show that \sim is an equivalence relation. If A has size n, 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 a and b is n-full iff every n-tuple appears exactly once, so for example aabba is 2-full.

Prove that in any n-full sequence the first n-1 terms and the last n-1 terms coincide. For example, in the 2-full sequence aabba the first and last terms are a, while in the 3-full sequence ababbbaaab the first two terms are ab, 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 x_1,\dots,x_n to have property * iff there are no i<j\le n/2 such that the sequence x_i,\dots,x_{2i} is a subsequence of the sequence x_j,\dots,x_{2j}, where we say that z_1,\dots,z_k is a subsequence of y_1,\dots,y_m iff there are 1\le i_1<\dots<i_k\le m such that y_{i_1}=z_1,y_{i_2}=z_2,\dots,y_{i_k}=z_k.

We defined n(k) as the largest n such that there is a sequence x_1,\dots,x_n with property * and each x_i is one of 1,2,\dots,k.

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

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

Advertisements

6 Responses to 305 – Homework II

  1. […] 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 […]

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

  3. […] 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.) […]

  4. […] 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 […]

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

  6. […] 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 […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: