3
$\begingroup$

A binary sequence is a sequence of 1s and 0s, and there are $2^n$ such sequences of length $n$.

Define the "pattern" as the number of consecutive $1$s in the sequence. For example, when $n=5$, the sequence $11010$ has pattern $[2,1]$ and the sequence $10011$ has pattern $[1,2]$. These two are of different patterns.

When $n=3$, there are $5$ patterns for total $2^3$ sequences:

[0]: 000
[1]: 001, 010,100
[2]: 011,110
[1,1]: 101
[3]: 111

So, the question is: for binary sequence with length $n$, how many patterns are there? Denoted by $a_n$.

It seems to be related to the Fibonacci numbers. If true, please help to prove it.

Thank you.

$\endgroup$
3
$\begingroup$

First of all, note the following formula for the sum of the first n fibonacci numbers:

$F_1 + F_2 + ... + F_n = F_{n+2} - 1$

This can be seen easily by induction on n.

Now, consider your case.

Assume inductively that number of patterns, $a_n$ = $F_{n+2}$ for n <= some $n_0$.

Any pattern must begin with one of $0, 1, 2, 3, ... n$

Each pattern that begins with say 3 can be uniquely identified with a sequence that starts with $1110$. Number of such sequences = $a_{n-4}$.

Using a similar logic, number of patterns that begin with i = $a_{n-1-i}$. This goes on for 0< i < $n-1$. For i = n, we have a single possible sequence with n 1's. For i = n-1, $a_0$ can be taken as 1 for simplicity. (number of patterns with 0 elements = 1, which is just $|\{0\}|$). This also satisfies $a_i = F_{i+2}$ as $F_2 = 1$. For i=0, We count the all zeroes case, adding another 1.

Now, each of the cases we have found so far are disjoint from each other. We can add them up.

$a_n = a_{n-2} + a_{n-3} + ... + a_1 + a_0 + 1 + 1$

By induction hypothesis, this becomes:

$a_n = F_{n} + F_{n-1} + ... + F_3 + F_2 + F_1 + 1$

So $a_n = (F_{n+2} - 1) + 1$

(by the formula for sum of first n fibonacci numbers).

This gives us $a_n = F_{n+2}$, like we wanted.

$\endgroup$
  • $\begingroup$ I doubt "Each pattern that begins with say 3 can be uniquely identified with a sequence that starts with 1110", sequence that starts with 01110 will also do. $\endgroup$ – bigheadghost Jun 19 '14 at 7:31
  • $\begingroup$ What I mean is that while there will be sequences starting with 01110, for each such sequence there will also be a sequence starting with 1110. We just pick the sequence starting with 1110 (not 01110) as the identifier for the pattern. For example, consider the example you had given. [1] corressponds to 001, 010 and 100. My strategy is to pick 100 as the 'identifier' for [1], instead of 001 or 010. The point is that you can always pick such an identifier starting with 111...1110. $\endgroup$ – Wonder Jun 19 '14 at 7:35
  • $\begingroup$ It may be clearer to see how things work out in the n=3 case: Note that $a_1$ = 2 (pattern can be [0] or [1]). For n=3 we basically end up counting 000, 111, then {101,100} and 110. 000 and 111 are counted as 1 + 1 in the formula I gave, then size of {101, 100} (i.e. sequences starting with 10) give another $a_1 = 2$, then {110} adds another $a_0 = 1$ $\endgroup$ – Wonder Jun 19 '14 at 7:41
  • 1
    $\begingroup$ I am not attempting to count the number of sequences with a given pattern, I am associating a unique sequence with each pattern - in such a way that I can easily count these 'identifying sequences'. In case of pattern [1], this sequence is 100. $\endgroup$ – Wonder Jun 19 '14 at 7:49
  • 1
    $\begingroup$ Let me put it this way: for each valid pattern $[i_1, i_2, ... i_k]$ for some n, one of the sequences satisfying this pattern is $i_1 ones$ 0 $i_2 ones$ 0 ... $i_k ones$ <pad with 0s at the end to get n>. Call a sequence in such a form a 'good' sequence. There is a bijection between valid patterns and good sequences. In this answer I count good sequences since the number of good sequences for a given n = number of valid patterns for n. $\endgroup$ – Wonder Jun 19 '14 at 7:57
1
$\begingroup$

For those who may concern, here are some additional notes on the problem.

Let's have a close look at the $ 2^n $ sequences of length n. If we shrink the extra zeros out of each sequence, resulting in sequences containing no two consecutive zeros nor zeros at both the left and right ends, just like what Christian's answer suggested, then we have a shrinked version (denoted by $SS_n$) of the original $S_n$. Each item in $SS_n$ represents a unique pattern. The length of $SS_n$ is the total count of unique patterns, the final answer.

For the sequence of all 0's in $S_n$, it can be shrinked to $\varnothing$ in $SS_n$, representing pattern [0].

For other item in $SS_n$, their count is the number of "sequences of length n containing no two consecutive zeros nor zeros at both ends". Christian has given a proof. Here is another one using the same denotion $s_n$. Since the number of "sequences of length n containing no two consecutive zeros" has been proved to be $F_{n+2}$, and $s_n$ is the $n-2$ case on it because the beginning and ending digits have to be 1. Thus $s_n = F_{(n-2)+2} =F_n$, Q.E.D.

Here is another perspective on the initial question using Pascal Triangle. $s_n$ is the sums of its "shallow" diagonals.

$P_i$, the sum of row $i$ of Pascal Triangle, is the number of unique patterns of sequences with $i$ 1's totally, given enough sequence length. It is also the number of compositions of integer $i$. And $P_i=2^{i-1}$

$P_{i, j}$, the $j$th item in the $i$th row of Pascal Triangle, is the count of patterns with $j$ items among total $P_i$ .

e.g., i=3, the 3rd row is 1, 2, 1. There are $P_3=1+2+1=4$ unique patterns of sequences with 3 1's totally, given enough sequence length: [3], [1,2],[2,1],[1,1,1]. These are also patterns whose items' sum are 3, i.e. compositions of 3. $P_{3, 1}$ is the number of patterns with 1 item among them, i.e. [3]. $P_{3, 2}$ is the number of patterns with 2 item among them: [1,2] and [2,1].

Now, back to the "shallow" diagonals, every time when the sequence length $n$ increase into $n+1$, new oppotunities open for $P_{i,j}$s which were not counted in $a_n$ because there were not enough length to expand (i.e. adding 0's). These $P_{i,j}$ items compose the $i$th "shallow" diagonal.

$\endgroup$
0
$\begingroup$

Denote by $S_n$ $(n\geq1)$ the set, and by $s_n$ the number of binary sequences of length $n$ containing no two consecutive zeros nor zeros at the ends. Then $s_1=s_2=1$, $s_3=2$, and one has the recursion formula $$s_n=s_{n-1}+s_{n-2}\qquad(n\geq3)\ .$$ Proof. A word $w\in S_n$ ends with $11$ or with $01$. In the first case the word $w'$ obtained by dropping the last $1$ is in $S_{n-1}$, and in the second case the word $w''$ obtained by dropping the final $01$ is in $S_{n-2}$. Conversely, appending $1$ to a word in $S_{n-1}$ or $01$ to a word in $S_{n-2}$ produces each $w\in S_n$ exactly once.

It follows that $s_n=f_n$ (the $n$'th Fibonacci number) for all $n\geq1$.

Now $s_n$ counts the number of your "patterns" (apart from the empty pattern) requiring at least $n$ letters to write down. But each pattern can as well be packed into longer words by padding it with extra zeros. It follows that the number $p_n$ of patterns that can be packed into an $n$-letter word is given by $$p_n=1+\sum_{k=1}^n s_k=1+\sum_{k=1}^n f_k=1+(f_{n+2}-1)=f_{n+2}\ .$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.