Find a recurrence relation for the next example:
We start with $n$ identical pennies and let $a_n$ count the number of ways we can arrange these pennies-contiguous in each row where each penny above the bottom row touches two pennies in the row below it. (In the arrangements we are not concerned with whether any given penny is heads up or heads down.)
In Fig. we have the possible arrangements for $1\leq n\leq 6$. From this it follows that
\begin{align*}
a_1=1 && a_2=1 && a_3 && a_4=3 && a_5=5 && a_6=8
\end{align*}
Consequently, these results might suggest that, in general, $a_n=F_n$, the $n$th Fibonacci number. Unfortunately, we have been led astray, as one finds, for example, that
\begin{align*}
a_7=12\neq 13=F_7 && a_8=18\neq 21=F_8 && a_9=26\neq 34=F_9
\end{align*}
When $n>6$ fails $a_n=F_n$. I think that
\begin{align*}
a_7=F_7-F_2 && a_8=F_8-F_4 && a_9=F_9-F_6
\end{align*}
Best Answer
It seems possible to get a recurrence relation by using the techniques in this link, but no clean closed form expression. (You will also notice that it is not exactly a direct recurrence relation in $a_n$, but more of an iterative approach for computing $a_n$.)
This problem is different because one is looking at an arrangement with each row/layer consisting of contiguous coins (and hence no gaps allowed).
Here is an approach which incorporates this modification (It is possible I might have made some errors, but I thought I would share my idea in case it helps someone):
Let $f(n,k)$ denote the number of arrangements with exactly $k$ coins in the base layer. Note that $f(n,n) = 1$ for all $n$, $f(1,1)=1$ and $f(n,0) = f(n,1) =0$ for all $n > 1$. In general $f(n,k)$ will be zero if $k$ is too small and $n$ is very large.
Note that \begin{equation} \tag{1} a_n = \mathop{\sum}_{k=0}^n f(n,k) \end{equation}
We will now derive a recurrence relation following the method in the wikipedia link.
Let us define a good arrangement of $n$ coins as an arrangement where the base layer (or bottom-most row) consists of exactly $k$ coins and the second layer from the bottom consists of exactly $k-1$ contiguous coins (Please see the figure below).
Let us denote the number of good arrangements by $g(n,k)$. Then we have
\begin{equation} \tag{2} g(n,k) = f(n-k,k-1) \end{equation} Proof: First lay out the bottom layer of $k$ coins. The second bottom layer now becomes the new base layer with exactly $k-1$ coins and we have remaining $n-k$ coins to arrange. The number of such arrangements is $f(n-k,k-1)$. $\blacksquare$
Now to get the original arrangement of $n$ coins with exactly $k$ coins in the base layer we need to place a good arrangement of size $n-(k-r)$ with exactly $r$ coins in the base among the remaining $k-r$ coins as shown in the figure below.
Note that the block of good arrangement could be placed to the extreme left end ($r'=0$) or the extreme right end ($r' = k-r$). So there are $k-r+1$ slots where the good arrangement can be placed and this can be done in $k-r+1$ ways (choose 1 out of the $k-r+1$ slots). This implies
\begin{equation} f(n,k) = \left\{ \begin{matrix} \sum_{r=0}^k g(n-k+r,r) (k - r + 1), \qquad \text{for } k < n\\ 1, \qquad \text{when } k= n \end{matrix} \right. \end{equation}
Using equation (2) and the fact that $g(n,0) = 0$, the above relation simplifies to
\begin{equation} \tag{3} \boxed{ f(n,k) = \left\{ \begin{matrix} \sum_{r=1}^k f(n-k,r-1) (k - r + 1) , \qquad \text{for } k < n\\ 1, \qquad \text{when } k= n \end{matrix} \right.} \end{equation}
This pretty much gives the desired recurrence relation. One could use the above recursion to write an expression for $a_n$ by using equation (1).
Generating function
It appears that it is possible to write an expression for the generating function for $a_n$!
First, note that equation (3) can also be written as follows (by writing $r$ as $k - r' +1$): \begin{equation} \tag{4} \boxed{ f(n,k) = \left\{ \begin{matrix} \sum_{r'=1}^k f(n-k,k-r') r' , \qquad \text{for } k < n\\ 1, \qquad \text{when } k= n \end{matrix} \right.} \end{equation} Or in a more explicit form as follows \begin{equation} f(n,k) = f(n-k,k-1) + 2 f(n-k, k-2) + \dots (k-1) f(n-k,1) + \delta_{k,n} \end{equation} where $\delta_{i,j}$ denotes Kronecker delta and the term $k. f(n-k,0)$ is not present because $f(a,0)$ is 0 for any $a$.
Let us now denote the generating function for $f(n,k)$ by $F_k(x)$. Then we have,
\begin{equation} \tag{4} F_k(x) = x^k (F_{k-1}(x) + 2 F_{k-2}(x) + \dots + (k-1) F_1(x) +1) \end{equation}
Note that $F_1(x) = x$, $F_2(x) = x^2 (F_1(x) + 1)$, $F_3(x) = x^3( F_2(x) + 2 F_1(x) + 1)$ and so on. From equation (1) it should be clear that the generating function for $a_n$ is \begin{equation} F(x) = \sum_{k=1}^{\infty} F_k(x) \end{equation} Using equation (4) we can see that, $$F(x) = {x\over (1-x)} + {x^3 \over (1-x)^2 (1- x^2)} + {x^6 \over (1-x)^2(1-x^2)^2(1-x^3)} + \dots = \mathop{\sum}_{m=1}^{\infty} {x^{m(m+1)/2}.(1-x^m) \over \prod_{i=1}^m (1 - x^i)^2}$$ Note the appearance of the triangular numbers in the exponents of the numerator. I believe $F(x)$ has some interesting interpretations in terms of partitions that I am unable to see now. Please see the aside below.
To conclude, $a_n$ is the coefficient of $x^n$ in $F(x)$.
Silly Checks
We will use the examples in the question to check equation (3).
Note that $$ f(3,2) = \mathop{\sum}_{r=1}^2f(3-2,r-1).(2-r+1) = f(1,1).(2-2+1) = 1 $$ We have used he fact that $f(n,0) = 0$ for any $n$. $$ f(n,2) = \mathop{\sum}_{r=1}^2f(n-2,r-1).(2-r+1) = 0 \quad \text{for } n >3 $$ Note that there is only one arrangement with 2 coins in the bottom layer when $n=3$. For $n > 3$ and $k=2$ the RHS of equation (3) evaluates to zero because $f(n,1) = f(n,0) =0 $ for $n>1$. This agrees with examples where we don't see any arrangement with $2$ coins in the bottom layer for $n > 3$. $$ f(n,n-1) = \mathop{\sum}_{r=1}^{n-1} f(1,r-1).(n-1-r+1) = n-2 $$ Note that $f(1,0) = 0$ and $f(1,a) = 0$ for $a>1$. The above expression also agrees with the examples shown in the question.
Aside:
The solution to the problem in the wikipedia link (different from the question here) is the Ramanujan continued fraction (described in the first reference in the wikipedia link).