|
%I #62 Aug 08 2018 22:35:30
%S 1,1,1,2,3,4,7,11,16,25,40,61,94,147,227,351,546,846,1309,2030,3147,
%T 4876,7558,11715,18154,28136,43609,67586,104748,162346,251610,389958,
%U 604381,936699,1451743,2249991,3487153,5404570,8376292,12982016,20120202,31183350
%N Number of compositions of n into positive triangular numbers.
%C 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
%H Alois P. Heinz, <a href="/A023361/b023361.txt">Table of n, a(n) for n = 0..5256</a> (terms n = 0..500 from T. D. Noe)
%H N. Robbins, <a href="http://ac.inf.elte.hu/Vol_043_2014/239_43.pdf">On compositions whose parts are polygonal numbers</a>, Annales Univ. Sci. Budapest., Sect. Comp. 43 (2014) 239-243. See p. 242.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/q-PochhammerSymbol.html">q-Pochhammer Symbol</a>.
%F G.f. : 1 / (1 - Sum_{k>=1} x^(k*(k+1)/2) ).
%F 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
%F a(n) = a(n-1) + a(n-3) + a(n-6) + a(n-10) + ... _Gregory L. Simay_, Jun 09 2016
%F 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
%F 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
%e From _Joerg Arndt_, Mar 25 2014: (Start)
%e There are a(9) = 25 compositions of 9 such that either c(k) = c(k-1) + 1 or c(k) = 1:
%e 01: [ 1 1 1 1 1 1 1 1 1 ]
%e 02: [ 1 1 1 1 1 1 1 2 ]
%e 03: [ 1 1 1 1 1 1 2 1 ]
%e 04: [ 1 1 1 1 1 2 1 1 ]
%e 05: [ 1 1 1 1 2 1 1 1 ]
%e 06: [ 1 1 1 1 2 1 2 ]
%e 07: [ 1 1 1 1 2 3 ]
%e 08: [ 1 1 1 2 1 1 1 1 ]
%e 09: [ 1 1 1 2 1 1 2 ]
%e 10: [ 1 1 1 2 1 2 1 ]
%e 11: [ 1 1 1 2 3 1 ]
%e 12: [ 1 1 2 1 1 1 1 1 ]
%e 13: [ 1 1 2 1 1 1 2 ]
%e 14: [ 1 1 2 1 1 2 1 ]
%e 15: [ 1 1 2 1 2 1 1 ]
%e 16: [ 1 1 2 3 1 1 ]
%e 17: [ 1 2 1 1 1 1 1 1 ]
%e 18: [ 1 2 1 1 1 1 2 ]
%e 19: [ 1 2 1 1 1 2 1 ]
%e 20: [ 1 2 1 1 2 1 1 ]
%e 21: [ 1 2 1 2 1 1 1 ]
%e 22: [ 1 2 1 2 1 2 ]
%e 23: [ 1 2 1 2 3 ]
%e 24: [ 1 2 3 1 1 1 ]
%e 25: [ 1 2 3 1 2 ]
%e The last few, together with the corresponding fountains of coins are:
%e . 20: [ 1 2 1 1 2 1 1 ]
%e .
%e . O O
%e . O O O O O O O
%e .
%e .
%e . 21: [ 1 2 1 2 1 1 1 ]
%e .
%e . O O
%e . O O O O O O O
%e .
%e .
%e . 22: [ 1 2 1 2 1 2 ]
%e .
%e . O O O
%e . O O O O O O
%e .
%e .
%e . 23: [ 1 2 1 2 3 ]
%e .
%e . O
%e . O O O
%e . O O O O O
%e .
%e .
%e . 24: [ 1 2 3 1 1 1 ]
%e .
%e . O
%e . O O
%e . O O O O O O
%e .
%e .
%e . 25: [ 1 2 3 1 2 ]
%e .
%e . O
%e . O O O
%e . O O O O O
%e (End)
%e Applying recursion formula: 40 = a(10) = a(9) + a(7) + a(4) + a(0) = 25 + 11 + 3 + 1. - _Gregory L. Simay_, Jun 14 2016
%p a:= proc(n) option remember; `if`(n=0, 1,
%p add(`if`(issqr(8*j+1), a(n-j), 0), j=1..n))
%p end:
%p seq(a(n), n=0..50); # _Alois P. Heinz_, Jul 31 2017
%t (1/(2 - QPochhammer[x^2]/QPochhammer[x, x^2]) + O[x]^30)[[3]] (* _Vladimir Reshetnikov_, Sep 23 2016 *)
%t a[n_] := a[n] = If[n == 0, 1, Sum[ If[ IntegerQ[ Sqrt[8j+1]], a[n-j], 0], {j, 1, n}]];
%t Table[a[n], {n, 0, 50}] (* _Jean-François Alcover_, Jun 05 2018, after _Alois P. Heinz_ *)
%o (PARI)
%o N=66; x='x+O('x^N);
%o Vec( 1/( 1 - sum(k=1,1+sqrtint(2*N), x^binomial(k+1,2) ) ) )
%o /* _Joerg Arndt_, Sep 30 2012 */
%Y Cf. A106332.
%K nonn
%O 0,4
%A _David W. Wilson_, Jun 14 1998
| 