login
Number of partitions of n into nonzero triangular numbers.
(Formerly M0234)
116

%I M0234 #125 Jul 15 2024 12:21:10

%S 1,1,1,2,2,2,4,4,4,6,7,7,10,11,11,15,17,17,22,24,25,32,35,36,44,48,50,

%T 60,66,68,81,89,92,107,117,121,141,153,159,181,197,205,233,252,262,

%U 295,320,332,372,401,417,465,501,520,575,619,645,710,763

%N Number of partitions of n into nonzero triangular numbers.

%C Also number of decreasing integer sequences l(1) >= l(2) >= l(3) >= .. 0 such that sum('i*l(i)','i'=1..infinity)=n.

%C a(n) is also the number of partitions of n such that #{parts equal to i} >= #{parts equal to j} if i <= j.

%C Also the number of partitions of n (necessarily into distinct parts) where the part sizes are monotonically decreasing (including the last part, which is the difference between the last part and a "part" of size 0). These partitions are the conjugates of the partitions with number of parts of size i increasing. - _Franklin T. Adams-Watters_, Apr 08 2008

%C Also partitions with condition as in A179255, and additionally, if more than one part, first difference >= first part: for example, a(10)=7 as there are 7 such partitions of 10: 1+2+3+4 = 1+2+7 = 1+3+6 = 1+9 = 2+8 = 3+7 = 10. - _Joerg Arndt_, Mar 22 2011

%C Number of members of A181818 with a bigomega value of n (cf. A001222). - _Matthew Vandermast_, May 19 2012

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H T. D. Noe and Vaclav Kotesovec, <a href="/A007294/b007294.txt">Table of n, a(n) for n = 0..10000</a> (terms 0..1000 from T. D. Noe)

%H Gert Almkvist, <a href="https://arxiv.org/abs/math/0612446">Asymptotics of various partitions</a>, arXiv:math/0612446 [math.NT], 2006.

%H G. E. Andrews, <a href="https://dx.doi.org/10.1007/PL00001284">MacMahon's Partition Analysis II: Fundamental Theorems</a>, Annals Combinatorics, 4 (2000), 327-338.

%H N. A. Brigham, <a href="https://doi.org/10.1090/S0002-9939-1950-0034409-3">A General Asymptotic Formula for Partition Functions</a>, Proc. Amer. Math. Soc., vol. 1 (1950), p. 191.

%H Jorge A. Campos-Gonzalez-Angulo, Raphael F. Ribeiro, and Joel Yuen-Zhou, <a href="https://arxiv.org/abs/2101.09475">Generalization of the Tavis-Cummings model for multi-level anharmonic systems</a>, arXiv:2101.09475 [physics.optics], 2021.

%H Zhicheng Gao, Andrew MacFie and Daniel Panario, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v18i1p143">Counting words by number of occurrences of some patterns</a>, The Electronic Journal of Combinatorics, 18 (2011), #P143.

%H Igor Pak, <a href="https://arxiv.org/abs/1803.06636">Complexity problems in enumerative combinatorics</a>, arXiv:1803.06636 [math.CO], 2018.

%H James A. Sellers, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL7/Sellers/sellers58.html">Partitions Excluding Specific Polygonal Numbers As Parts</a>, Journal of Integer Sequences, Vol. 7 (2004), Article 04.2.4.

%H Jan Snellman and Michael Paulsen, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL7/Snellman/snellman2.html">Enumeration of Concave Integer Partitions</a>, Journal of Integer Sequences, Vol. 7, 2004.

%H Gus Wiseman, <a href="/A325325/a325325.txt">Sequences counting and ranking integer partitions by the differences of their successive parts.</a>

%F G.f.: 1/Product_{k>=2} (1-z^binomial(k, 2)).

%F For n>0: a(n) = b(n, 1) where b(n, k) = if n>k*(k+1)/2 then b(n-k*(k+1)/2, k) + b(n, k+1) else (if n=k*(k+1)/2 then 1 else 0). - _Reinhard Zumkeller_, Aug 26 2003

%F For n>0, a(n) is Euler Transform of [1,0,1,0,0,1,0,0,0,1,0,0,0,0,1,...], i.e A010054, n>0. - _Benedict W. J. Irwin_, Jul 29 2016

%F a(n) ~ exp(3*Pi^(1/3) * Zeta(3/2)^(2/3) * n^(1/3) / 2) * Zeta(3/2) / (2^(7/2) * sqrt(3) * Pi * n^(3/2)) [Brigham 1950 (exponential part), Almkvist 2006]. - _Vaclav Kotesovec_, Dec 31 2016

%F G.f.: Sum_{i>=0} x^(i*(i+1)/2) / Product_{j=1..i} (1 - x^(j*(j+1)/2)). - _Ilya Gutkovskiy_, May 07 2017

%e 6 = 3+3 = 3+1+1+1 = 1+1+1+1+1+1 so a(6) = 4.

%e a(7)=4: Four sequences as above are (7,0,..), (5,1,0,..), (3,2,0,..),(2,1,1,0,..). They correspond to the partitions 1^7, 2 1^5, 2^2 1^3, 3 2 1^2 of seven or in the main description to the partitions 1^7, 3 1^4, 3^2 1, 6 1.

%e From _Gus Wiseman_, May 03 2019: (Start)

%e The a(1) = 1 through a(9) = 6 partitions using nonzero triangular numbers are the following. The Heinz numbers of these partitions are given by A325363.

%e 1 11 3 31 311 6 61 611 63

%e 111 1111 11111 33 331 3311 333

%e 3111 31111 311111 6111

%e 111111 1111111 11111111 33111

%e 3111111

%e 111111111

%e The a(1) = 1 through a(10) = 7 partitions with weakly decreasing multiplicities are the following. Equivalent to Matthew Vandermast's comment, the Heinz numbers of these partitions are given by A025487 (products of primorial numbers).

%e 1 11 21 211 2111 321 3211 32111 32211 4321

%e 111 1111 11111 2211 22111 221111 222111 322111

%e 21111 211111 2111111 321111 2221111

%e 111111 1111111 11111111 2211111 3211111

%e 21111111 22111111

%e 111111111 211111111

%e 1111111111

%e The a(1) = 1 through a(11) = 7 partitions with weakly increasing differences (where the last part is taken to be zero) are the following. The Heinz numbers of these partitions are given by A325362 (A = 10, B = 11).

%e (1) (2) (3) (4) (5) (6) (7) (8) (9) (A) (B)

%e (21) (31) (41) (42) (52) (62) (63) (73) (83)

%e (51) (61) (71) (72) (82) (92)

%e (321) (421) (521) (81) (91) (A1)

%e (531) (631) (731)

%e (621) (721) (821)

%e (4321) (5321)

%e (End)

%p b:= proc(n,i) option remember;

%p if n<0 then 0

%p elif n=0 then 1

%p elif i=0 then 0

%p else b(n, i-1) +b(n-i*(i+1)/2, i)

%p fi

%p end:

%p a:= n-> b(n, floor(sqrt(2*n))):

%p seq(a(n), n=0..100); # _Alois P. Heinz_, Mar 22 2011

%p isNondecrP :=proc(L) slp := DIFF(DIFF(L)) ; min(op(%)) >= 0 ; end proc:

%p A007294 := proc(n) local a, p; a := 0 ; if n = 0 then return 1 ; end if; for p in combinat[partition](n) do if nops(p) = nops(convert(p, set)) then if isNondecrP(p) then if nops(p) =1 then a := a+1 ; elif op(2, p) >= 2*op(1, p) then a := a+1; end if; end if; end if; end do; a ; end proc:

%p seq(A007294(n), n=0..30) ; # _R. J. Mathar_, Jan 07 2011

%t CoefficientList[ Series[ 1/Product[1 - x^(i(i + 1)/2), {i, 1, 50}], {x, 0, 70}], x]

%t (* also *)

%t t = Table[n (n + 1)/2, {n, 1, 200}] ; p[n_] := IntegerPartitions[n, All, t]; Table[p[n], {n, 0, 12}] (*shows partitions*)

%t a[n_] := Length@p@n; a /@Range[0, 80]

%t (* _Clark Kimberling_, Mar 09 2014 *)

%t b[n_, i_] := b[n, i] = Which[n < 0, 0, n == 0, 1, i == 0, 0, True, b[n, i-1]+b[n-i*(i+1)/2, i]]; a[n_] := b[n, Floor[Sqrt[2*n]]]; Table[a[n], {n, 0, 100}] (* _Jean-François Alcover_, Apr 09 2014, after _Alois P. Heinz_ *)

%t Table[Length[Select[IntegerPartitions[n],OrderedQ[Differences[Append[#,0]]]&]],{n,0,30}] (* _Gus Wiseman_, May 03 2019 *)

%t nmax = 58; t = Table[PolygonalNumber[n], {n, nmax}];

%t Table[Count[IntegerPartitions@n, x_ /; SubsetQ[t, x]], {n, 0, nmax}] (* _Robert Price_, Aug 02 2020 *)

%o (Sage)

%o def A007294(n):

%o has_nondecreasing_diffs = lambda x: min(differences(x, 2)) >= 0

%o special = lambda x: (x[1]-x[0]) >= x[0]

%o allowed = lambda x: (len(x) < 2 or special(x)) and (len(x) < 3 or has_nondecreasing_diffs(x))

%o return len([1 for x in Partitions(n, max_slope=-1) if allowed(x[::-1])]) # _D. S. McNeil_, Jan 06 2011

%o (PARI) N=66; Vec(1/prod(k=1,N,1-x^(k*(k+1)\2))+O(x^N)) \\ _Joerg Arndt_, Apr 14 2013

%o (Haskell)

%o a007294 = p $ tail a000217_list where

%o p _ 0 = 1

%o p ks'@(k:ks) m = if m < k then 0 else p ks' (m - k) + p ks m

%o -- _Reinhard Zumkeller_, Jun 28 2013

%o (Python)

%o from functools import lru_cache

%o from sympy import divisors

%o from sympy.ntheory.primetest import is_square

%o @lru_cache(maxsize=None)

%o def A007294(n):

%o @lru_cache(maxsize=None)

%o def a(n): return is_square((n<<3)+1)

%o @lru_cache(maxsize=None)

%o def c(n): return sum(d for d in divisors(n,generator=True) if a(d))

%o return (c(n)+sum(c(k)*A007294(n-k) for k in range(1,n)))//n if n else 1 # _Chai Wah Wu_, Jul 15 2024

%Y Cf. A000217, A051533, A000294.

%Y Cf. A102462.

%Y Row sums of array A176723 and triangle A176724. - _Wolfdieter Lang_, Jul 19 2010

%Y Cf. A179255 (condition only on differences), A179269 (parts strictly increasing instead of nondecreasing). - _Joerg Arndt_, Mar 22 2011

%Y Cf. A024940, A280366.

%Y Row sums of A319797.

%Y Cf. A007862, A025487, A240026, A320509, A325324, A325354, A325356, A325362, A325363.

%K nonn

%O 0,4

%A _N. J. A. Sloane_, _Mira Bernstein_

%E Additional comments from _Roland Bacher_, Jun 17 2001