A sequence with dominoes My friend ran into this problem years ago. He asked for my help, but I couldn't solve it either. The setting is as follows.
Dominoes are placed in a triangular formation. Something like this...
 ㅁ
ㅁㅁ  (n=2)

Rules: 1. If a domino is hit, it may fall or it may not. 2. If a domino is not hit, it does not fall.
Problem: $D_n$ is the number of scenarioes possible for a given $n$. Find the explicit formula of $D_n$.
Example: For n=2, The domino on the top may or may not fall. If it does not fall, the two dominoes under it do not fall. If it does, the two dominoes may or may not fall. Therefore $D_2=5$.
Clarification: The rule is: the top domino can fall; for any non-top domino, it can fall only if at least one domino above it falls.
Please help. Thank you very much.
 A: Update: I found a recurrence in my alternative approach answer, here.

TL;DR
I've reduced the problem to calculating "domino coefficients".
But it appears these coefficients cannot be easily calculated, and that's where my answer stops.  


Reducing the problem to "domino coefficients"
If $d_n$ is the number of scenarios with at least one fallen domino in the $n$th row, then 
$$D_n=D_{n-1}+d_n$$
We define $D_0=1,d_1=1$. This gives $D_1=1+1=2$ as expected.
We say a domino is "activated" (can fall) if and only if a domino above it has fallen.

$\alpha_n(k)$ is the number of ways to have exactly $k$ "activated" dominoes in the $n$th row.

Now to calculate $d_n,n\ge2$ we have the expression:
$$d_n=\sum_{k=1}^n \alpha_n(k) \cdot (2^k-1)$$
Because every "activated" domino is either fallen or not, giving $2^k$ states, and we subtract $1$ for the case when they are all not fallen because that's the definition of $d_n$. 
If a domino falls, it activates the two dominoes below it. This implies that $\alpha_n(1)=0$ because we never have exactly one activated domino. Hence we define $\alpha$ for $2\le k\le n$.

The problem is now calculating the "domino coefficients" $\alpha_n(k)$.

By brute force I've found the triangle that gives $\alpha_n(k)$'s  for $2\le k\le 7$ is:
$$\begin{array}{}
&&&&&& 1 \\
&&&&& 2 && 1 \\
&&&& 7 && 4 && 2 \\
&&& 34 && 21 && 18 && 6 \\
&& 233 && 152 && 184 && 104 && 32 \\
& 2370 && 1609 && 2552 && 1888 && 1056 && 288 \\
 .&& .&& .&& .&& .&& .&& .\\
\end{array}$$
Reading rows $n=2,3,4,5,6,7$ and plugging the coefficients into the recursion: 
$$D_n=D_{n-1}+\sum_{k=2}^n \alpha_n(k) \cdot (2^k-1)$$
Gives $D_n=5,18,97,802,10565,228850$ as expected. (Where $D_1=2$.)


Solving the domino coefficients?
For $k=2$, to activate exactly two dominoes in $(n)$th row, exactly one domino must fall in $(n-1)$th row. This gives the recursion for the first coefficient:
$$\alpha_n(2)=\sum_{r=2}^{n-1}\alpha_{n-1}(r)\cdot r $$
But for $k\ge 3$, I do not see an obvious recursion.
The number of ways activated dominoes in the $(n-1)$th row can fall now depends on the "islands" (consecutive runs of activated dominoes) and "gaps" (consecutive runs of non-activated dominoes). To write this as an expression,
Let $S(n-1,r)$ be the set of all $(n-1)$th row sequences of dominoes where exactly $r$ dominoes are activated. Then we have to sum over all $s\in S(n-1,r)$:
$$
\alpha_n(k)=\sum_{r=2}^{n-1}\sum_{s\in S(n-1,r)}f_k(s)
$$
Where $f_k(s)$ returns a value depending on the size of each "island" $I\in s$ and depending on the value of the target number of activations $k$ in the $n$th row.
Collecting all $s$ sequences and evaluating $f_k(s)$ function on them is a problem now.
Notice that the number of elements of $S(n-1,r)$ is precisely $\alpha_{n-1}(r)$. 
If $k=2$, we simply have $f_2(s)=r$ for all $s$, which gives the recursion $\alpha_{n}(2)$ from above.
If $k=3$, we have $f_3(s)=(r-1)$ if the $s$ contains exactly one island $I$ of length $r$. Otherwise, we need to observe individual islands, to get:
$$f_3(s)=\sum_{I\in s}(\mathcal L(I)-1)$$
where $\mathcal L(I)$ is the length of the island $I\in s$. This is true because to have $k=3$ activated dominoes in the $(n)$th row, we need to have exactly two connected dominoes in the $(n-1)$th row. 
For $k\ge 4$, the $f_k(s)$ is not anymore "as simple" as summing lengths of islands. 
For $k=3$ we counted ways:


*

*to activate "single $2$-long partitions" of the islands


For $k=4$ we need to count ways:


*

*to activate "single $3$-long partitions" of the islands 

*to activate "two $1$-long partitions" separated with gap of at least one


And so on, for larger $k$ we have more ways to "partition the activations" of islands.

I do not see how to simplify this into a "closed form (recursion) expression ".

Hence my answer stops here.
A: Here's another approach, using the principle of inclusion and exclusion.  We want to find the number of 2-colorings of the triangular grid $i\in\{1,\dots,n\},\ j\in\{1,\dots,i\}$ that have none of the following properties:


*

*cell $(i,1)$ is black and cell $(i+1,1)$ is white

*cell $(i,i)$ is black and cell $(i+1,i+1)$ is white

*cells $(i,j)$ and $(i,j+1)$ are black and cell $(i+1,j+1)$ is white


The inclusion-exclusion expressions for small $n$ are as follows.
\begin{align}
n=1:&\quad 2^1 = \color{red}{2}\\
n=2:&\quad 2^3 - 2\cdot 2^1 + 2^0 = 8 - 4 + 1 = \color{red}{5}\\
n=3:&\quad 2^6 - (4\cdot 2^4 + 2^3) + (2^3 + 5\cdot 2^2) - 2^1 = 64 - 72 + 28 - 2 = \color{red}{18}\\
n=4:&\quad 2^{10} - (6\cdot2^8 + 3\cdot2^7) + (2^7 + 14\cdot2^6 + 11\cdot2^5) \\
&- (3\cdot2^5 + 18\cdot2^4 + 9\cdot2^3) + (4\cdot2^3 + 13\cdot2^2) - 6\cdot2^1+ 2^0 \\
&= 1024 - 1920 + 1376 - 456 + 84 - 12 + 1 = \color{red}{97}
\end{align}
For general $n$, the first three terms (up through two properties) are easy, but it gets messy after that.
