A238870 Number of compositions of n with c(1) = 1, c(i+1) - c(i) <= 1, and c(i+1) - c(i) != 0.

1, 1, 0, 1, 1, 0, 2, 2, 1, 4, 4, 4, 9, 10, 11, 21, 25, 30, 51, 62, 80, 125, 157, 208, 309, 399, 536, 772, 1013, 1373, 1938, 2574, 3503, 4882, 6540, 8918, 12329, 16611, 22672, 31183, 42182, 57588, 78952, 107092, 146202, 200037, 271831, 371057, 507053, 689885, 941558, 1285655, 1750672, 2388951, 3260459, 4442179, 6060948

Offset: 0

Author

Joerg Arndt, Mar 09 2014

Keywords

• nonn

Comments

Number of fountains of n coins with at most two successive coins on the same level.

Examples

			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
:
		

Links

• Joerg Arndt and Alois P. Heinz, Table of n, a(n) for n = 0..1000

Crossrefs

Cf. A005169 (fountains of coins), A001524 (weakly unimodal fountains of coins).

Cf. A186085 (1-dimensional sandpiles), A227310 (rough sandpiles).

Cf. A023361 (fountains of coins with all valleys at lowest level).

Programs

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 *)

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

Formula

a(n) ~ c / r^n, where r = 0.733216317061133379740342579187365700397652443391231594... and c = 0.172010618097928709454463097802313209201440229976513439... . - Vaclav Kotesovec, Feb 17 2017