OFFSET
0,7
COMMENTS
Number of fountains of n coins with at most two successive coins on the same level.
LINKS
Joerg Arndt and Alois P. Heinz, Table of n, a(n) for n = 0..1000
FORMULA
a(n) ~ c / r^n, where r = 0.733216317061133379740342579187365700397652443391231594... and c = 0.172010618097928709454463097802313209201440229976513439... . - Vaclav Kotesovec, Feb 17 2017
EXAMPLE
The a(10) = 4 such compositions are:
:
: 1: [ 1 2 1 2 1 2 1 ] (composition)
:
: o o o
: ooooooo (rendering as composition)
:
: O O O
: O O O O O O O (rendering as fountain of coins)
:
:
: 2: [ 1 2 1 2 3 1 ]
:
: o
: o oo
: oooooo
:
: O
: O O O
: O O O O O O
:
:
: 3: [ 1 2 3 1 2 1 ]
:
: o
: oo o
: oooooo
:
: O
: O O O
: O O O O O O
:
:
: 4: [ 1 2 3 4 ]
:
: o
: oo
: ooo
: oooo
:
: O
: O O
: O O O
: O O O O
:
MAPLE
b:= proc(n, i) option remember; `if`(n=0, 1, add(
`if`(i=j, 0, b(n-j, j)), j=1..min(n, i+1)))
end:
a:= n-> b(n, 0):
seq(a(n), n=0..60); # Alois P. Heinz, Mar 11 2014
MATHEMATICA
b[n_, i_] := b[n, i] = If[n == 0, 1, Sum[If[i == j, 0, b[n-j, j]], {j, 1, Min[n, i+1]}]];
a[n_] := b[n, 0];
a /@ Range[0, 60] (* Jean-François Alcover, Nov 07 2020, after Alois P. Heinz *)
PROG
(Sage) # translation of the Maple program by Alois P. Heinz
@CachedFunction
def F(n, i):
if n == 0: return 1
return sum( (i!=j) * F(n-j, j) for j in [1..min(n, i+1)] ) # A238870
# return sum( F(n-j, j) for j in [1, min(n, i+1)] ) # A005169
def a(n): return F(n, 0)
print([a(n) for n in [0..50]])
# Joerg Arndt, Mar 20 2014
CROSSREFS
Cf. A023361 (fountains of coins with all valleys at lowest level).
KEYWORD
nonn
AUTHOR
Joerg Arndt, Mar 09 2014
STATUS
approved