I noticed something curious when I was working on my summer project last year. Basically, you consider the set of binary strings (strings of length
where each symbol is either a
or a
and
‘s are non-adjacent). So we construct a table like
Length | 1 | 2 | 3 | 4 | 5 | 6 |
Strings | 0;1 | 00;01;10 | 000;001;010;100;101 | 0000;0001;0010;0100;0101;1000;1001;1010 | … | … |
And then count the number of elements of length with
ones.
Number of ones [m] (below) | Number of strings (below) | |||||
Length of string [n] (right) | 1 | 2 | 3 | 4 | 5 | 6 |
0 | 1 | 1 | 1 | 1 | 1 | 1 |
1 | 1 | 2 | 3 | 4 | 5 | 6 |
2 | 0 | 0 | 1 | 3 | 6 | 10 |
3 | 0 | 0 | 1 | 4 | ||
4 | 0 | 0 |
Do you see Pascal’s Triangle hiding inside? Starting from the top left and diagonally down to the left. First one is 1,2,1, then is 1,3,3,1 etcThe explanation is simple enough. We are using the fact that the subset of
composed of strings with
ones (lets call this
) can be made by taking an element in
and appending a zero to it or an element in
and appending a zero-one to it. We end up with the recurrence
. If we consider
as the
element in the
diagonal, then we realize that
follows the same recurrence. This reccurence is well documented in the literature for calculating
, here we are just using this idea for subsets of
with exactly
ones to connect it with Pascal’s Triangle.
The adventure continues in Part 2!