An interesting Google interview question

Recently I read about an interesting Google interview question at https://www.geeksforgeeks.org/count-strings-can-formed-using-b-c-given-constraints/

The problem statement is:

Given a length n, count the number of strings of length n that can be made using ‘a’, ‘b’ and ‘c’ with at-most one ‘b’ and two ‘c’s allowed.

The page on GeeksForGeeks provide two programmatic solutions using recursion. But most interesting   one is mathematical one which directly calculate value. It took me quite long time to derive that formula. The formula is:

count = 1 + 2n+ n*((n*n)-1)/2 

Here I want to provide derivation for this formula. You may find it useful.

1. count of strings with no b's and no c's = 1
2. count of strings with one b and no c's = n
3. count of strings with no b's and one c = n
4. count of strings with one b and one c = n*(n-1)
5. count of strings with one b and two c's = n*(n-1)*(n-2)/2;
6. count of strings with no b and two c's = n*(n-1)/2

If you add all 6 values then you will get

count = 1 + 2n+ n*((n*n)-1)/2

The above formula works only for n greater than or equal to 3.