OFFSET
0,4
COMMENTS
Number of compositions [c(1), c(2), c(3), ...] of n such that either c(k) = c(k-1) + 1 or c(k) = 1; see example. Same as fountains of coins (A005169) where each valley is at the lowest level. - Joerg Arndt, Mar 25 2014
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..5256 (terms n = 0..500 from T. D. Noe)
N. Robbins, On compositions whose parts are polygonal numbers, Annales Univ. Sci. Budapest., Sect. Comp. 43 (2014) 239-243. See p. 242.
Eric Weisstein's World of Mathematics, q-Pochhammer Symbol.
FORMULA
G.f. : 1 / (1 - Sum_{k>=1} x^(k*(k+1)/2) ).
a(n) ~ c * d^n, where d = 1/A106332 = 1.5498524695188884304192160776463163555... is the root of the equation d^(1/8) * EllipticTheta(2, 0, 1/sqrt(d)) = 4 and c = 0.492059962414480455851222791075288170662444559041717451009563731799... - Vaclav Kotesovec, May 01 2014, updated Feb 17 2017
a(n) = a(n-1) + a(n-3) + a(n-6) + a(n-10) + ... Gregory L. Simay, Jun 09 2016
G.f.: 1/(2 - (x^2;x^2)_inf/(x;x^2)_inf), where (a;q)_inf is the q-Pochhammer symbol. - Vladimir Reshetnikov, Sep 23 2016
G.f.: 1/(2 - theta_2(sqrt(q))/(2*q^(1/8))), where theta_2() is the Jacobi theta function. - Ilya Gutkovskiy, Aug 08 2018
EXAMPLE
From Joerg Arndt, Mar 25 2014: (Start)
There are a(9) = 25 compositions of 9 such that either c(k) = c(k-1) + 1 or c(k) = 1:
01: [ 1 1 1 1 1 1 1 1 1 ]
02: [ 1 1 1 1 1 1 1 2 ]
03: [ 1 1 1 1 1 1 2 1 ]
04: [ 1 1 1 1 1 2 1 1 ]
05: [ 1 1 1 1 2 1 1 1 ]
06: [ 1 1 1 1 2 1 2 ]
07: [ 1 1 1 1 2 3 ]
08: [ 1 1 1 2 1 1 1 1 ]
09: [ 1 1 1 2 1 1 2 ]
10: [ 1 1 1 2 1 2 1 ]
11: [ 1 1 1 2 3 1 ]
12: [ 1 1 2 1 1 1 1 1 ]
13: [ 1 1 2 1 1 1 2 ]
14: [ 1 1 2 1 1 2 1 ]
15: [ 1 1 2 1 2 1 1 ]
16: [ 1 1 2 3 1 1 ]
17: [ 1 2 1 1 1 1 1 1 ]
18: [ 1 2 1 1 1 1 2 ]
19: [ 1 2 1 1 1 2 1 ]
20: [ 1 2 1 1 2 1 1 ]
21: [ 1 2 1 2 1 1 1 ]
22: [ 1 2 1 2 1 2 ]
23: [ 1 2 1 2 3 ]
24: [ 1 2 3 1 1 1 ]
25: [ 1 2 3 1 2 ]
The last few, together with the corresponding fountains of coins are:
. 20: [ 1 2 1 1 2 1 1 ]
.
. O O
. O O O O O O O
.
.
. 21: [ 1 2 1 2 1 1 1 ]
.
. O O
. O O O O O O O
.
.
. 22: [ 1 2 1 2 1 2 ]
.
. O O O
. O O O O O O
.
.
. 23: [ 1 2 1 2 3 ]
.
. O
. O O O
. O O O O O
.
.
. 24: [ 1 2 3 1 1 1 ]
.
. O
. O O
. O O O O O O
.
.
. 25: [ 1 2 3 1 2 ]
.
. O
. O O O
. O O O O O
(End)
Applying recursion formula: 40 = a(10) = a(9) + a(7) + a(4) + a(0) = 25 + 11 + 3 + 1. - Gregory L. Simay, Jun 14 2016
MAPLE
a:= proc(n) option remember; `if`(n=0, 1,
add(`if`(issqr(8*j+1), a(n-j), 0), j=1..n))
end:
seq(a(n), n=0..50); # Alois P. Heinz, Jul 31 2017
MATHEMATICA
(1/(2 - QPochhammer[x^2]/QPochhammer[x, x^2]) + O[x]^30)[[3]] (* Vladimir Reshetnikov, Sep 23 2016 *)
a[n_] := a[n] = If[n == 0, 1, Sum[ If[ IntegerQ[ Sqrt[8j+1]], a[n-j], 0], {j, 1, n}]];
Table[a[n], {n, 0, 50}] (* Jean-François Alcover, Jun 05 2018, after Alois P. Heinz *)
PROG
(PARI)
N=66; x='x+O('x^N);
Vec( 1/( 1 - sum(k=1, 1+sqrtint(2*N), x^binomial(k+1, 2) ) ) )
/* Joerg Arndt, Sep 30 2012 */
CROSSREFS
KEYWORD
nonn
AUTHOR
David W. Wilson, Jun 14 1998
STATUS
approved
