I defined three functions:
C(i) - the number of ways to make the album if it consists of only i songs.
A(i) - the number of ways ending in 1.
B(i) - the number of ways ending in 2.

C(i) = A(i) + B(i)

A(i) = 1 if i <= 1
     = C(i-1) if  1< i <=a
     = C(i-1) - B(i-a-1) i>a

Notice that if i <= a there's no way to have more than a 1's, so we call C(i-1) and 'append' 1 at position i. The number of ways to do this reminds the same as C(i-1).

If i>a you could have an invalid string of 1's. To counter this, we call B(i-a-1) to know exactly how many sequences would be invalid if we 'append' a 1 at position i. When i=a+1, there's only one invalid string resulting of appending 1 at a+1, the sequence consisting of only 1's.

B is analogous to A (calls A instead of B and uses b instead of a).

Edited by author 12.07.2019 04:31

But how do we eliminate duplicates ?