cp's OEIS Frontend

A023361 Number of compositions of n into positive triangular numbers.

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