The following notes are based on email messages from Lee Hae-hwang in April 2002. I am grateful to my colleague Peter Shor for help in interpreting these pictures. - Neil Sloane

Sequence A026644 satisfies the recurrence a(1) = 2, a(2) = 4 and for n >=2, a(n+1) = a(n) + 2*a(n-1) + 2.

Lee Hae-hwang's very nice observation is that this sequence gives the number of leaves (or nodes of degree 1) in the n-th plant in the following sequence of "rosemary" plants:

These are constructed as follows. We begin with the first plant, which has two leaves (because a(1) = 2) and a single red node of degree three.

The rules for getting the next plant from the previous one are:

• For a red node:

  
                                  ------ RED ------
                                          |
                                          |
                                          |
  ----- RED -----     becomes     ----- GREEN -----
         |                                |
         |                                |
         |                                |
  
  

• For a green node:

                                      
                                     /        \       
         |                          RED   |  RED
         |                         /  \   |   / \
         |                             \  |  /    
  ---- GREEN ----     becomes     ----- BLACK -----
         |                                |
         |                                |
         |                                |
  
  

• Black nodes do nothing.

The Recurrences

Let R(n) = number of red nodes at the n-th stage,
let G(n) = number of green nodes,
and let a(n) be the number of leaves.

Then we have:
R(n+1) = R(n) + 2*G(n),
G(n+1) = R(n),
a(n+1) = a(n) + 2*R(n) + 4*G(n).

Also: R(n+1) = G(n), G(n) forms sequence A001045, and of course a(n) is sequence A026644.

See the entries for these two sequences for further information.