Find string probabilities

[duma]

- I have two symbols, one is "long" 1 bit and one is "long" 2 bits. That is X and YY
- The first has probability 2/3 and the second 1/3
- I have a string of these symbols, for example "X YY X X YY YY X X..."

My question: Given a length L, how do I find how many different strings exist of such length? In other words how many different strings I can build such the the length of all its symbols is exactly L

Thanks for the help.

[Shelwien]

Seems to be this:
Table[(Fibonacci[L] + LucasL[L])/2, {L, 1, 100}]
or this:

Table[Total[ Function[x, Binomial[x[[1]] + x[[2]], x[[1]]] ] /@ FrobeniusSolve[{1, 2}, L]], {L, 1, 100}]

(Fibonacci[L-1]+Fibonacci[L]+Fibonacci[L+1])/2

((1+Sqrt[5])^L*(1+Sqrt[5]+((Sqrt[5]-3)/2)^L*(Sqrt[5]-1)))/Sqrt[5]/2^(L+1)

Example: L=4

1) ----
2) ##--
3) -##-
4) --##
5) ####

[duma]

How did you arrive to Table[(Fibonacci[L] + LucasL[L])/2, {L, 1, 100}] ???

[Shelwien]

I only made the "FrobeniusSolve" line, by looking up relevant functions in mathematica help.
Btw, it can be easily modified to compute string probabilities.
Once I had actual values, there's FindSequenceFunction.

Normally its done by building a recurrent function, converting it to generating function, etc.
But I'm too rusty at this stuff.
There's a good book btw - https://en.wikipedia.org/wiki/Concrete_Mathematics