0

Say I have two elements (0, 1) and I want to find the number of permutations of sequences of, say, length 10. However, I want to limit it so that "1" can never appear more than twice in a row, with no limits on "0." So, 0110110110 is ok, but 0111000000 is not. How can I figure that out? I am interested in the general case, but I thought the example might help.

EDIT: I'm looking for the number of permutations of (in this case) of two elements for sequences (in this case) of length 10, clearly with repetition. 2^10 if not for the limitation I am placing above, that is, I want to remove all sequences that have 3 or more 1's in a row.

Jake Malloy
  • 5
  • General case of the limit or the length of the sequence? – barak manos Aug 18 '15 at 18:35
  • 1
    You may need to clarify your question because you say "permutations," to you, is a permutation any string of length $n$ (say $n = 10$) made up of 0 and 1? Or do you have a fixed string (i.e. fixed number of 0 and 1) and you want to know the number of valid permutations of that string (i.e., putting the 0 and 1 occurrences anywhere you want, but leaving the number of 0 fixed and number of 1 fixed)? – user2566092 Aug 18 '15 at 18:43

2 Answers2

0

Assuming you want to count all 0/1 strings of length $n$ so that there are no runs of 3 or more 1's in a row, you can write down a recurrence and then simplify and solve it, either analytically or very efficiently with a computer. Let $F_0(n)$ be the number of valid sequences of length $n$ that end in $0$, and $F_1(n)$ be the number of valid sequences of length $n$ that end in a single $1$ (i.e. if there is a digit before the last digit then it is $0$), and $F_2(n)$ be the number of valid sequences of length $n$ that end in a sequence of 2 1's. Then, by conditioning on whether the last digits in a valid sequence is 0 or 01 or 11, you have

$$F_0(n+1) = F_0(n) + F_1(n) + F_2(n)$$ $$F_1(n+1) = F_0(n)$$ $$F_2(n+1) = F_1(n)$$

There are ways to solve some such linear recurrence systems analytically, or you can just code up the recurrence with dynamic programming on a computer to get the answer very quickly for any $n$.

user2566092
  • 26,142
0

Call such a sequence valid, and call the number of length-$n$ valid sequences $f_n$. You want $f_{10}$.

A valid sequence ends in either a $0$, a $01$, or a $11$ (why?). How many length-$n$ valid sequences end in a $0$? in a $01$? in a $11$?

Since a sequence ending in $0$ can only be formed by any $n-1$-length sequence with a $0$ added at the end, there are $f_{n-1}$ of them. A sequence ending in $01$ can only be formed by any $n-2$-length sequence with a $01$ added at the end, so there are $f_{n-2}$ of them. And if it ends in $11$, then it can only be formed by any $n-3$-length sequence with a $011$ added at the end (why?), so there are $f_{n-3}$ of them. Thus:\begin{align}f_n=f_{n-1}+f_{n-2}+f_{n-3}\end{align}Combining this with the fact that $f_1=2$, $f_2=4$, and $f_3=7$, we get the tribonacci numbers!\begin{align}f_n=T_{n+1}\end{align}

Thus, $f_{10}=274$.

Akiva Weinberger
  • 23,062