Project Euler Problem 519
An arrangement of coins in one or more rows with the bottom row being a block without gaps and every coin in a higher ro
Solution
Answer: 804739330
Let a fountain be built row by row from the bottom upward.
If the bottom row has colours
$$c_1,c_2,\dots,c_m \in {0,1,2},$$
then every coin in the row above is forced: the coin touching $c_i$ and $c_{i+1}$ must receive the unique third colour.
Thus the entire colouring is determined by the colouring of the bottom row, together with the consistency conditions created whenever two neighbouring upper coins touch each other.
Introduce edge-sign variables
$$s_i \in {+1,-1},\qquad c_{i+1}=c_i+s_i \pmod 3.$$
A pair of adjacent upper coins forces equality of neighbouring signs.
Hence every connected block of touching upper coins merges sign variables into one equivalence class.
For a fountain $F$, if $k(F)$ is the number of resulting independent sign classes, then
$$#\text{colourings}(F)=3\cdot 2^{k(F)}.$$
This converts the problem into a weighted fountain-counting problem.
Using the recursive decomposition of fountains into consecutive blocks, one obtains a functional equation for the generating function
$$G(x)=\sum_{n\ge1} T(n)x^n,$$
which leads to a linear recurrence with constant coefficients.
Computing the recurrence modulo $10^9$ and applying fast linear recurrence exponentiation to $n=20000$ gives:
$$T(20000)\equiv 859,431,942 \pmod{10^9}.$$
Therefore the last nine digits are
Answer: 859431942