Aquatic opera

A partial solution...

The answer is found using the following recursion relation:

Let $N_n$ be the number of ways that $n$ sea creatures could form this line:

• $N_0 = 1$
• $N_1 = 3$
• $N_{n} = 2N_{n-1} + N_{n-2}$ for $n>1$

Using this relation,

$N_{10} = \boxed{8119}$

To see how this recurrence relation is derived see Arthur's solution below...

Let $S_n$ , $D_n$ and $W_n$ denote the number of lines of length $n$ ending with a Shark, with a Dolphin and with a Whale respectively. In this notation, it is evident the answer we seek is $S_{10}+D_{10}+W_{10}$ .

Now the three recurrence relations arise:

(1) $S_{n+1}=S_n+W_n$

(2) $D_{n+1}=D_n+W_n$

(3) $W_{n+1}=S_n+D_n+W_n$

because, in words, while a whale can be 'put on the end' of any previous line, a shark cannot be put on the end of a whale line, and a whale cannot be put on the end of a shark line.

Now, it helps to also define $\Sigma_n=S_n+D_n+W_n$ , so we are looking for $\Sigma_{10}$ . Adding together our recursion relations (1), (2) and (3):

$S_{n+1}+D_{n+1}+W_{n+1}=2S_n+2D_n+3W_n$

$\Sigma_{n+1}=2(S_n+D_n+W_n)+W_n$

$\Sigma_{n+1}=2\Sigma_n+W_n$

Since $W_{n+1}=S_n+D_n+W_n=\Sigma_n$ , $W_n=\Sigma_{n-1}$ so

$\Sigma_{n+1}=2\Sigma_n+\Sigma_{n-1}$ , thus Geoff's recurrence relation is derived. It is left to find base cases $\Sigma_1=3$ and $\Sigma_2=7$ to work up to $\Sigma_{10}=\boxed{8119}$ , using artithmetic or a quick piece of code e.g

def sum(n):
    if n==1:
        return 3
    if n==2:
        return 7
    else:
        return 2*s(n-1) + s(n-2)

print(s(10))
...
>>>8119