Number of ways of coloring n objects in a row with k colors such that adjacent objects are of different colors except when a particular color I am trying to build upon this question:
Number of ways of coloring n objects which are laid in a row with k colors such that the adjacent objects are of different colors
The caveat is that if two adjacent objects are of one particular color, say yellow, then it is acceptable.
Example: 3 objects, with 3 colors (Y, R, B), where two adjacent Ys are acceptable.
Then we have 17 possible combinations: YYY, RYY, YYR, BYY, YYB, BYB, YBY, RYR, YRY, BYR, RYB, BRY, RBY, BRB, RBR, YBR, YRB.
Is there a possible formula for a question like this?
 A: Nice question! :)
Denote with $a_n$ the number of sequencies of length $n$ with the last ball having your "particular color" (yellow). Denote the total number of sequencies with $c_n$. The number of sequencies of length $n$ with the last ball not having yellow color is obviously: $c_n-a_n$
What is the number of sequencies of length $n+1$ ending in yellow collor? You can create such sequence by adding a yellow ball to any valid sequence of $n$ balls. So obviously:
$$a_{n+1}=c_n\tag{1}$$
What is the total number of sequencies of length $n+1$? You can create such sequence:


*

*by adding a ball of any color to a sequence ending in yellow collow

*by adding a ball of different color to a sequence not ending in yellow color


In other words:
$$c_{n+1}=ka_n+(k-1)(c_n-a_n)\tag{2}$$
Note that from (1) we have that $a_n=c_{n-1}$. Replace that into (2) and you have the following recurrence formula:
$$\boxed{c_{n+1}=(k-1)c_n+c_{n-1}}\tag{3}$$
...with the following starting values:
$$c_1=k,\ \ \ c_2=k+(k-1)^2\tag{4}$$
Explanation: $c_1$ is obvious. For $c_2$, you can create a sequence of length 2 by adding $k$ different balls to the starting yellow ball or, if the starting ball is not yellow ($k-1$ choices), by adding a ball of different color ($k-1$ choices again).
The point is: the recurrence relation (3) can be easily solved and it is possible to write $c_n$ as a simple function of $n$. I won't demonstrate this in a general case, but let us do that for $k=3$ different colors.
In that case from (3) and (4) we have:
$$c_{n+1}-2c_n-c_{n-1}=0\tag{5}$$
...with the following initial conditions:
$$c_1=3, \ \ \ c_2=7\tag{6}$$ 
Characteristic equation:
$$r^2-2r-1=0$$ 
...has the following solutions:
$$r_{1,2}=1\pm\sqrt2$$
So we can write $c_n$ as:
$$c_n=A(1+\sqrt{2})^n+B(1-\sqrt{2})^n$$
You can easily calculate unknown constants $A$ and $B$ from starting values $c_1$ and $c_2$. The final solution looks like this:
$$\boxed{c_n=\frac{(1+\sqrt2)^{n+1}+(1-\sqrt2)^{n+1}}2}\tag{7}$$
Binomial expansion gives the following alternative form:
$$c_n=\sum_{i=0}^{\lfloor{\frac{n+1}2}\rfloor}\binom{n+1}{2i}2^i$$
The first 20 values of this sequence are: 3, 7, 17, 41, 99, 239, 577, 1393, 3363, 8119, 19601, 47321, 114243, 275807, 665857, 1607521, 3880899, 9369319, 22619537, 54608393.
It's interesting to note that for large values of $n$, the seond term in the numerator of (7) becomes close to zero. So for big $n$:
$$c_n\approx\frac12(1+\sqrt2)^{n+1}$$
$$\ln c_n\approx(n+1)\ln(1+\sqrt2)-\ln2=0.188226 + 0.881374 n$$
So for big values of $n$, $\ln c_n$ is a linear function of $n$. This is clearly seen in the the following graph, even if you plot only the first 100 values:

And if you google this sequence, OEIS A078057 pops up immeidately. It turns out that this sequence has a lot of interesting properties.
