|
|
A023361
|
|
Number of compositions of n into positive triangular numbers.
|
|
35
|
|
|
1, 1, 1, 2, 3, 4, 7, 11, 16, 25, 40, 61, 94, 147, 227, 351, 546, 846, 1309, 2030, 3147, 4876, 7558, 11715, 18154, 28136, 43609, 67586, 104748, 162346, 251610, 389958, 604381, 936699, 1451743, 2249991, 3487153, 5404570, 8376292, 12982016, 20120202, 31183350
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
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
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
|
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:
|
|
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}]];
|
|
PROG
|
(PARI)
N=66; x='x+O('x^N);
Vec( 1/( 1 - sum(k=1, 1+sqrtint(2*N), x^binomial(k+1, 2) ) ) )
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|