The symbol
$$n\choose k$$
is a shorthand for "The number of ways to choose $k$ objects from a collection of $n$ objects."
That is: you have $n$ objects in a line. You select $k$ of them, and paint them red, and you paint the other $n-k$ blue. How many ways are there to do that so that the final result looks different?
A moment of reflection will convince you that you could have chosen $n-k$ of the objects to paint blue first, and painted the rest of the objects red. The answer shouldn't depend on something arbitrary like whether you pick up the blue or the red paint first. If you can grok this fact, then you will have proved to yourself that
$${n\choose k} = {n\choose n-k}$$
How does this relate to binomial expansions? Well, say that we want to expand
$$(r + b)^n$$
Then we'll get a bunch of terms, each of which is a product of some $r$s with some $b$s. There are $n$ brackets, so there will be $n$ multipliers in each of the terms, and each of them will be either $r$ or $b$, so every term looks like
$$a_kr^kb^{n-k}$$
where $a_k$ is a coefficient, and $k=0, 1, 2, \dots n$.
What is $a_k$? Notice that in every bracket, we have to choose either an $r$ or a $b$. We can imagine going through the brackets one by one and making these choices, or you can imagine looking at all the brackets at once, and choosing which of them to pick $r$ form and which to pick $b$ from. The coefficient $a_k$ is the number of different ways of picking $k$ $r$s and $(n-k)$ $bs$ from the $n$ brackets. That is:
$$a_k = {n\choose k}$$
which, using the fact from earlier, we can instantly use to prove that the coefficients in a binomial expansion are symmetric:
$$a_k = {n\choose k} = {n\choose n-k} = a_{n-k}$$
Maybe you can see how binomial expansions relate to Pascal's triangle now?
Hint: It is linked to another cool and exciting relationship between the binomial coefficients!
The following relations all hold modulo 2 (you can think of them as a special case of Lucas' theorem, or just prove them directly):
$$
{2a \choose 2b} \equiv {a \choose b}, \mbox{ and } {2a \choose 2b+1} \equiv 0\\
{2a+1 \choose 2b} \equiv {2a+1 \choose 2b+1} \equiv {a \choose b} \, .
$$
Using these, you can recursively check whether any given bit sequence $B=(b_1,b_2,\dots,b_k)$ could possibly occur:
- For $B$ to occur in an even row of the triangle, every other bit in $B$ must be $0$: that is, $B=(0,b_2,0,b_4,\dots)$ or $B=(b_1,0,b_3,0,\dots)$. Such a $B$ will actually occur in some even row if the shortened sequence $(b_2,b_4,\dots)$ or $(b_1,b_3,\dots)$ occurs in some row of the triangle.
- For $B$ to occur in an odd row of the triangle, the bits in $B$ must be equal in adjacent pairs: that is, $B=(b_1, b_1, b_3, b_3, \dots)$, or $B=(b_1, b_2, b_2, b_4, b_4, \dots)$. Such a $B$ will actually occur in some odd row if the shortened sequence $(b_1,b_3,b_5,\dots)$ or $(b_1,b_2, b_4, b_6,\dots)$ occurs in some row of the triangle.
Each application of one of these rules will approximately halve the length of $B$; if neither rule can be made to apply at any step, we eliminate $B$ from consideration. So eventually, if you don't eliminate $B$ from consideration, you'll end up at the trivial string $1$ (which gets sent to itself by both rules, and clearly appears in the triangle).
Applying this algorithm, we can see that your $1101$ fails immediately; it doesn't consist either of repetitions or of something padded with zeroes. The other specific examples you're asking about will fail for similar reasons. Any sequence with two adjacent $1$s cannot have rule 1. applied to it: that already means it's impossible for every other bit to be a $0$. Moreover, any sequence with an odd-length run of either $1$s or $0$s cannot have rule 2. applied to it, unless the run starts or ends the sequence; it makes it impossible to pair the bits off with each other. Since your sequences end with two $1$s, and have a run of $2^n-1$ $0$s in the middle, neither rule can be applied to them, so they can't possibly be in the triangle.
On the other hand, something like $101000001$ passes, via the sequence of transformations
$$
101000001 \to^1 11001 \to^2 101 \to^1 11 \to^2 1 \, .
$$
If you want to enumerate all sequences that appear somewhere, you can apply these two rules in reverse. For a given sequence $B=(b_1,b_2,\dots,b_k)$, how could it have been produced from rules 1. and 2.?
$B$ could have been produced from rule 1. by any of four bit strings: $(0, b_1, 0, b_2, \dots, 0, b_k, 0)$, $(0, b_1, 0, b_2, \dots, 0, b_k)$, $(b_1, 0, b_2, \dots, 0, b_k, 0)$, or $(b_1, 0, b_2, \dots, 0, b_k)$.
$B$ could also have been produced from rule 2. by any of four bit strings: $(b_1, b_1, b_2, b_2, \dots, b_k, b_k)$, $(b_1, b_2, b_2, \dots, b_k, b_k)$, $(b_1, b_1, b_2, b_2, \dots,b_{k-1}, b_{k-1}, b_k)$, or $(b_1, b_2, b_2, \dots, b_{k-1}, b_{k-1}, b_k)$.
In both cases, there is a longest string that can be produced (the first one listed), and three other strings that can be obtained from the longest string by removing its first or last element, or both.
For example, if we start with the string $1011$, we can run rule 1. backward to get the strings $010001010$, $10001010$, $01000101$, and $1000101$. We can run rule 2. backward to get the strings $11001111$, $1001111$, $1100111$, and $100111$.
We know that, for any string which appears in the triangle, we can repeatedly apply rules 1. and 2. until the string $1$ is obtained. So we must be able to obtain all possible strings by repeatedly applying the backwards versions of rules 1. and 2. to the string $1$. Moreover, each backwards rule goes from a string of length $k$ to a string of length at least $2k-2$. So if we want to find all strings of length $k$, we'll only have to apply the algorithm until the shortest strings being produced at any given stage are of length at least $k$, and this will take about $\log_2 k$ steps.
To be precise, if we start with a string of length $3$, we can get to a string of length up to $2^n+2$ in $n$ steps. Our algorithm starts being a little funkier for shorter strings than that, but you can enumerate all the possibilities and see that every string of length $3$ is obtainable from the string $1$ in at most $2$ steps. So any string of length up to $2^n+2$ can
be obtained in at most $n+2$ steps, meaning that any string of length $k$ can be obtained in at most $\left\lceil\log_2(k-2)+2\right\rceil$ steps.
This already gives us a pretty good algorithm for enumerating all possible strings. But we can do better. The implication of everything above is that any sequence comes from a $1$ floating somewhere in the triangle. But no matter which $1$ we start with, we'll end up with the same set of bit strings (as long as we adopt the standard convention that ${a \choose b}=0$ whenever $b<0$ or $b>a$; otherwise, some of the sequences we produce might go out of bounds).
So we might as well imagine that we're starting with the $1$ at the very top of the triangle, in row $0$. By the original Lucas' theorem argument, each step will, at worst, take us from row $n$ of the triangle to row $2n+1$. So, after $t$ steps, we'll be, at worst on row $2^t-1$. Since $\left\lceil\log_2(k-2)+2\right\rceil$ steps are sufficient to produce all strings of length $k$, we see that every string of length $k$ that occurs at all will occur before row
$$
2^\left\lceil\log_2(k-2)+2\right\rceil-1<8k \, ,
$$
to give a crude upper bound which can probably be improved upon.
In summary, every bit string of length $k$ that appears in the mod 2 version of Pascal's triangle will occur somewhere in the first $8k$ rows. So you can enumerate them all just by computing the first $8k$ rows of Pascal's triangle and looking at all the $k$-element substrings of the result (remembering to pad the triangle on the left and right by sufficiently many zeroes). I think this a much nicer way of doing things than my other algorithm (which basically boiled down to computing bits of Pascal's triangle anyways...)
Best Answer
When $p = 2$, Lucas' Theorem states that ${n \choose m} \equiv 0 \pmod{2}$ if and only if in the binary expansion of $n = (\overline{ \cdots n_1n_0})_2$ and $m = (\overline{ \cdots m_1m_0})_2$, some binary digit (say the $d$th binary digit) satisfies $n_d = 0, m_d = 1$. In particular, this shows that ${2^k + n \choose m} \equiv {2^k + n \choose 2^k + m} \equiv {n \choose m} \pmod{2}$ when $2^k > n > m$, which describes the recursive nature of the Sierpinski triangle that can be found in Pascal's triangle by highlighting the odd elements (which it seems is the geometric interpretation you referred to). However, this is a fairly restricted application of Lucas' Theorem and can be seen by easier means.