Number of combinations with LEGO plastic bricks C++

If this is a counting problem (not outputting combination, rather just counting them) it's an easy one. Assume we solved it for n ≥ 3 now to solve it for n+1, we solve it by induction:

Assume f is a function that shows the number of possible ways such that the last item is a brick. Analogously g is a function that shows the number of possible ways such that the last item is not brick. Let define h = f+g, to be the number of all possible ways.

So we have:

f(n+1) = f(n) + g(n-2)
g(n+1) = g(n) + f(n)

With initial condition:

for n=0,1,2: g=1, f= 0.
for n = 3: g=1,f=1

Samples:

n=4: g=2,f=2 ==> h=4
n=5: g=4, f= 3 ==> h=7
n=6: g=7, f= 4 ==> h=11
n=7: g=11,f=6 ==> h=17

We can solve it with one for loop in O(n).

---

Why:

f(n+1) = f(n) + g(n-2)
g(n+1) = g(n) + f(n)

First, let prove first part:

Remember that we assumed f(n) is a working solution which has a plastic brick in the last item, and g(n) is a working solution which doesn't have a brick in the last item.

f(n+1) can be obtained from f(n) by adding one brick at the last place. Also f(n+1) can be obtained by adding three brick after g(n-2), it means cells of n-1,n,n+1.

Note that we can't add brick after g(n-1) or g(n) to create a valid solution for f(n+1) because they are not valid solutions (number of consecutive bricks is less than 3). Also, note that we don't need to count the number of ways which arises by adding bricks after g(n-3) because they are previously enumerated by f(n). So we have f(n+1) = f(n) + g(n-2).

In the same way we can prove g(n+1) = f(n)+g(n) this case is easier, because g(n+1) simply can be made from any valid solution up to n, as there is no 3 consecutive brick barrier here, they can come after any valid solution.

As a person with math training, rather than CS, I feel obliged to mention that, while Saeed Amiri's algorithm is very nice and would probably work fast enough for N up to a few millions (with constant memory, of course), there is a better algorithm from the time perspective.

I will pick up where he has left:

f(n+1) = f(n) + g(n-2)
g(n+1) = f(n) + g(n)

Since f and g are discrete functions, you can treat them as sequences. This becomes a linear system of recurrence relations, then. Luckily, a system like this can be completely solved, so that the explicit form of f and g can be presented.
Unfortunately, SO does not seem to support MathJax like math.SE, so I apologize for the low quality of the equations from here on.
Let

     | f(n) |
     |f(n-1)|
u(n)=|f(n-2)|
     | g(n) |
     |g(n-1)|
     |g(n-2)|

That is, u(n) is a vector row. Then, the following is true:

|f(n+1)|   |1 0 0 0 0 1|   | f(n) |
| f(n) |   |1 0 0 0 0 0|   |f(n-1)|
|f(n-1)| = |0 1 0 0 0 0| . |f(n-2)|
|g(n+1)|   |1 0 0 1 0 0|   | g(n) |
| g(n) |   |0 0 0 1 0 0|   |g(n-1)|
|g(n-1)|   |0 0 0 0 1 0|   |g(n-2)|

What follows from this is, that u(n) = A * u(n-1), where A is the matrix above.
Then, u(n) = (A^(n-2)) * u(2), where u(2) is the vector, containing the initial values to the problem. This, in turn, gives an algorithm with O(log(n)) complexity, since you can use fast exponentiation to calculate (A^(n-2)) and then multiply it to u(2).

Of course, any such technique would probably require a BigInt of some sort, since otherwise the overflow is pretty much guaranteed.

Also note that this technique can be applied one step further:
You can find the eigenvectors and eigenvalues of A and then decompose u(2) into the eigenvectors. Then, you will have a closed form for both f(n) and g(n).

I strongly advise you against an algorithm based on the closed form
It almost certainly will involve high-precision floating-point calculations (unless all eigenvalues are integers, which is highly unlikely), which are of at least this complexity from programming perspective, and are not generally constant-time operations. Of course, neither are BigInt operations. So a constant-time algorithm is generally not feasible, plus you probably do not even need the O(log(n)), since for most uses the linear is good enough.

Note
The technique described here can be used in a variety of problems and is of extreme use in dynamic optimization problems. Plus, usually people are pretty impressed when they see this for the first time ;)