15
$\begingroup$

Moderator Note: At the time that this question was posted, it was from an ongoing contest. The relevant deadline has now passed.

enter image description here

I recently learned that when the Pascal's triangle is reduced to parity(ie even terms are represented as 0, odd terms are represented by 1), the result is a figure resembling Sierpinski's triangle in pattern. This I found to be a very fascinating result. Then I began to notice some sequences, such as particular sequences of zeroes and ones appearing in various rows.

An observation I made is that as Pascal's triangle is symmetric by way of $\binom{n}{m}= \binom{n}{n-m}$, the reverse of any sequence of 0s and 1s that appears in this version of Pascal's triangle will also appear. Looking at various sequences, the shortest sequences to not seem to appear were $1101$ and its reverse, $1011$. I attempted to then prove two things. First, I wanted to prove that these sequences would never appear in the 'parity Pascal triangle'. I can see intuitively why they would never appear- if we divide the Sierpinski triangle into stages of itself, we see that the $101$ sequence only appears in the middle row of the second stage of the fractal, and as the $nth$ stage of the fractal only appears as part of the $n+1$th stage of the fractal, this sequence will always be followed by the center of $0$s of another stage of the fractal. Similarly, any sequence $100...11$ can appear, but $1011,100011, 1000000011$, and so on with the number of 0s being of form $2^n-1$ cannot appear. As I said, intuitively this is because $2^n-1$ 0s bookended by two 1s appears at places where either one of the two 1s is on the edge of the fractal and the other at the edge of the central triangle of 0s in some stage of the fractal. For examples of this happening, see the bottom row of the diagram, the third row of the diagram, the fifth row of the diagram, the ninth row of the diagram. Can anyone formalize this argument into a full, general proof of my statement?

Similarly, for any size of sequence, how can we more explicitly describe all sequences that appear in this 'Parity Pascal' triangle or, more easily, that don't appear in it? And how for any size of sequence, how can we enumerate appearing sequences?


If anyone could give further direct/explicit proof and explanation for the modulo 2 relations Micah mentions(whether or not you do this through making it explicit in terms of Lucas' theorem is not a matter) and why the rules can determine whether a string is in Pascal's mod 2 triangle the way they do, that would be fantastic! I am not sure I understand where they are coming from, as neat as they are.

  • 0
    Andy studies to exactly the [same problem](http://math.stackexchange.com/questions/229304/exploring-properties-of-pascals-triangle-pmod-2/229310#229310) and got no real answer. Your question shows more initial observations.2012-11-09
  • 1
    @Hendrick I hope this means mine will not be marked as a duplicate?2012-11-09
  • 0
    @HendrickJan the first part of my question regarding the formalization of my argument was, I should point out, not part of Andy's question.2012-11-09
  • 1
    Sorry, no. My intention was positive, that is why I explicitly added you showed more own research.2012-11-09
  • 1
    @Hendrick Indeed! And I thank you for that very much. The friend who introduced me to this site warned of duplicate closing, so I was merely being cautious.2012-11-09
  • 0
    +1 for the pretty picture (though more contrast between even and odd colors would have been even better).2012-11-09
  • 0
    And +1 for prompting an interesting answer.2012-11-09
  • 0
    Interestingly, the mod 3, mod 5, mod 7, and in general any mod prime version of Pascal's Triangle will generate similar structures.2014-05-03

1 Answers 1