7
$\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!

$\endgroup$
6
  • $\begingroup$ I would start by trying to answer the question for small values of n. $\endgroup$
    – Jonah Sinick
    Nov 5, 2012 at 0:54
  • $\begingroup$ This may be a silly question, but can you see any strings which are not proper? $\endgroup$
    – JavaMan
    Nov 5, 2012 at 3:34
  • $\begingroup$ @JavaMan The smallest examples would be $1011$ and $1101$. $\endgroup$
    – EuYu
    Nov 5, 2012 at 3:46
  • $\begingroup$ The numbers seem to satisfy A014206, but the strings themselves are not bitonic. $\endgroup$
    – EuYu
    Nov 5, 2012 at 3:47
  • 1
    $\begingroup$ @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. $\endgroup$
    – Phira
    Nov 5, 2012 at 10:00

2 Answers 2

Reset to default
2
$\begingroup$

(The following was shown to me a few years ago by David Kelly, who used this discovery to generate an approximation of the Sierpinski Triangle by looking at Pascal's Triangle in base 2 -- though the details of this part escape me.)

Let $n \in \mathbb{N}$, and let:

$$F(n) = \textrm{max}\{k \in \mathbb{N} \, \colon \, 2^k \textrm{ divides }n\}.$$

$$B(n) = \textrm{ count of 1s in the base-2 representation of } n.$$

$$P(n) = \textrm{ count of odd numbers in the } n\textrm{th row of Pascal's Triangle.}$$

Proposition: For every $n \in \mathbb{N}$, the following hold:

  1. $F(n) + B(n) = n,$
  2. $P(n) = 2^{B(n)}.$
$\endgroup$
2
  • $\begingroup$ This seems interesting, but I am wondering how this relates to proper strings? $\endgroup$
    – Andy
    Nov 5, 2012 at 0:52
  • $\begingroup$ Well, the values for B(n) and P(n) are obtained by string operations. $\endgroup$
    – Charles Boyd
    Nov 5, 2012 at 0:59
1
$\begingroup$

You start by drawing a very large example of the triangle. Or finding it somewhere on the internet. Then start looking for regularities. Patterns that occur.

(edit). My initial ideas. You can see long runs of $1$'s or long runs of $0$'s. I can see $0110$, by I think I cannot find $01110$. Why? What can be above that sequence...

$\endgroup$
1
  • $\begingroup$ That much I figured :) But patterns only yield so much insight.... and for me, none at all :P $\endgroup$
    – Andy
    Nov 5, 2012 at 0:27

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .