## 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 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 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 that $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.)

### 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 […]