0

I'm trying to figure out a way to calculate this permutation (as an example):

  • size n = 5
  • members = {0, 1}

On this case we have 2^5 possibility to form a group of 5 numbers using 0 and 1 (e.g. 00000, 00001, ...) The question is, how can I subtract the number of groups that have 2 or more 1's in row (e.g. 01100, 10110, 01110... etc. not 010101 as the 1's are not besides each others on this case).

input: n, output: number of permutations that doesn't have 2 or more consecutive 1's

what would be the equation then?

Thanks in advance!

Heidar
  • 103

2 Answers2

2

Let $f(n)$ be the number of $n$-term binary sequences such that no two consecutive terms are equal to $1$.

Clearly, $f(0)=1$, and $f(1)=2$.

For $n \ge 2$, there are two scenarios . . .

If the first term is $0$, then the next $n-1$ terms can be any legal $(n-1)$-term sequence, hence there are $f(n-1)$ possible sequences for this case.

If the first term is $1$, then the next term must be $0$, and the next $n-2$ terms can be any legal $(n-2)$-term sequence, hence there are $f(n-2)$ possible sequences for this case.

It follows that for $n \ge 2$, we have $f(n) = f(n-1) + f(n-2)$, which is the Fibonacci recursion.

Let $F_k$ denote the $k$-th Fibonacci number.

Then since $f(0)=F_2$, and $f(1)=F_3$, it follows that $f(n)=F_{n+2}$, for all $n$.

quasi
  • 58,772
0

Here are all the numbers that do not have $2$ or more ones in a row (we do this in four steps):

Step 1: $00000;00001;00010;00100;01000;10000$ (for the case zero or one $1$ only)

Step 2: $00101;01001;10001;01010;10010;10100$ (for the case there are two ones)

Step 3: For the case of three ones: Only $10101$ satisfy.

Step 4: For the case of four or five ones: There are no numbers satisfy this (you can prove it if necessary).

So there are $13$ groups that do not have $2$ or more ones in a row, implies that the rest $19$ numbers have $2$ or more ones in a row.

user061703
  • 3,877