login
Number of arithmetic progressions of 2 or more nonnegative integers, strictly increasing with sum n.
14

%I #53 Sep 30 2019 03:15:01

%S 1,1,3,2,3,6,4,4,8,7,6,11,7,8,15,9,9,17,10,13,20,13,12,22,15,15,24,18,

%T 15,32,16,18,29,20,22,36,19,22,34,27,21,42,22,26,46,27,24,45,27,34,45,

%U 31,27,52,35,35,50,34,30,64,31,36,59,38,40,65,34,40,60,51,36,71,37,43

%N Number of arithmetic progressions of 2 or more nonnegative integers, strictly increasing with sum n.

%C From _Petros Hadjicostas_, Sep 28 2019: (Start)

%C We want to find the number of pairs of integers (b, w) such that b >= 0 and w >= 1 and there is an integer m >= 1 so that m*b + (1/2)*m*(m-1)*w = n.

%C If we insist that b > 0, we get A049982 (= number of arithmetic progressions of 2 or more positive integers, strictly increasing with sum n). The number of integers m >= 1 such that (1/2)*m*(m-1)*w = n equals A007862(n) (= number of triangular numbers that divide n).

%C Thus, to get a(n), we add A049982(n) to A007862(n).

%C (End)

%H Andrew Howroyd, <a href="/A127938/b127938.txt">Table of n, a(n) for n = 1..10000</a>

%H Sadek Bouroubi and Nesrine Benyahia Tani, <a href="http://ftp.math.uni-rostock.de/pub/romako/heft64/bou64.pdf">Integer partitions into arithmetic progressions</a>, Rostok. Math. Kolloq. 64 (2009), 11-16.

%H Sadek Bouroubi and Nesrine Benyahia Tani, <a href="https://www.emis.de/journals/INTEGERS/papers/j7/j7.Abstract.html">Integer partitions into arithmetic progressions with an odd common difference</a>, Integers 9(1) (2009), 77-81.

%H Graeme McRae, <a href="https://web.archive.org/web/20081122034835/http://2000clicks.com/MathHelp/BasicSequenceA049982.htm">Counting arithmetic sequences whose sum is n</a>.

%H Graeme McRae, <a href="/A049988/a049988.pdf">Counting arithmetic sequences whose sum is n</a> [Cached copy]

%H Augustine O. Munagi, <a href="https://www.emis.de/journals/INTEGERS/papers/k7/k7.Abstract.html">Combinatorics of integer partitions in arithmetic progression</a>, Integers 10(1) (2010), 73-82.

%H Augustine O. Munagi and Temba Shonhiwa, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL11/Shonhiwa/shonhiwa13.html">On the partitions of a number into arithmetic progressions</a>, Journal of Integer Sequences 11 (2008), Article 08.5.4.

%H A. N. Pacheco Pulido, <a href="http://www.bdigital.unal.edu.co/7753/">Extensiones lineales de un poset y composiciones de números multipartitos</a>, Maestría thesis, Universidad Nacional de Colombia, 2012.

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Arithmetic_progression">Arithmetic progression</a>.

%F G.f.: x/(x^3 - x - x^2 + 1) + x^3/(x^6 - x^3 - x^3 + 1) + x^6/(x^10 - x^6 - x^4 + 1) + ... = Sum_{k >= 2} x^{t(k-1)}/(x^{t(k)} - x^{t(k-1)} - x^k + 1), where t(k) = A000217(k) is the k-th triangular number. Term k of this generating function generates the number of arithmetic progressions of k nonnegative integers, strictly increasing with sum n.

%F a(n) = A049982(n) + A007862(n). - _Petros Hadjicostas_, Sep 28 2019

%e a(10) = 7 because there are five 2-element arithmetic progressions that sum to 10, as well as 1+2+3+4 and 0+1+2+3+4.

%o (PARI) seq(n)={Vec(sum(k=1, (sqrtint(8*n+1)-1)\2, x^binomial(k+1, 2)/(x^binomial(k+2, 2) - x^binomial(k+1, 2) - x^(k+1) + 1) + O(x*x^n)))} \\ _Andrew Howroyd_, Sep 28 2019

%Y Cf. A000217, A007862, A014405, A014406, A049980, A049981, A049982, A049983, A049986, A049987.

%K nonn

%O 1,3

%A _Graeme McRae_, Feb 08 2007