6
$\begingroup$

Moderator Note: This question is from a contest which ended 1 Dec 2012.

Consider Pascal's Triangle taken $\pmod 2$:

First few rows of Pascal's Triangle modulo 2

For simplicity, we will call a finite string of 0's and 1's proper if it occurs in one of the rows of this modified Pascal's triangle. (for example, 0 (row 3) and 10001 (row 5) are proper).

I've been exploring proper strings of length $n$. My professor told me it is possible to

i) characterize explicitly all proper strings of length $n$

and ii) Find an explicit formula for the number of proper strings of length $n$.

But I cannot figure out how to even begin either parts. This is a very interesting problem, and I was wondering if someone could help me. Thank you!

  • 0
    I would start by trying to answer the question for small values of n.2012-11-05
  • 0
    This may be a silly question, but can you see any strings which are _not_ proper?2012-11-05
  • 0
    @JavaMan The smallest examples would be $1011$ and $1101$.2012-11-05
  • 0
    The numbers seem to satisfy [A014206](http://oeis.org/A014206), but the strings themselves are not bitonic.2012-11-05
  • 0
    @EuYu: Thanks for the example!2012-11-05
  • 1
    @Andy I suggest that you tell us in which context your professor told you all this. For this problem, I suggest that you gives us all the strings of length $\le 10$ that you could not find.2012-11-05

2 Answers 2