login
Number of partitions of n into distinct parts such that (greatest part) - (least part) = (number of parts).
16

%I #63 Sep 23 2021 04:15:48

%S 0,0,0,1,0,1,1,2,0,2,2,2,2,2,1,4,3,2,3,3,2,4,4,4,3,4,2,5,5,3,5,6,3,5,

%T 3,5,6,6,4,6,6,4,6,6,3,7,7,7,6,6,5,7,7,5,6,8,6,8,8,6,8,8,4,9,6,7,9,9,

%U 7,7,9,8,9,9,5,9,7,8,10,10

%N Number of partitions of n into distinct parts such that (greatest part) - (least part) = (number of parts).

%C Note that partitions into distinct parts are also called strict partitions.

%C a(n) is the number of strict partitions of n into nearly consecutive parts, that is, the number of ways to write n as a sum of terms i, i+1, i+2, ..., i+k (i>=1, k>=2) where one of the interior parts i+1, i+2, ..., i+k-1 is missing. Examples of nearly consecutive partitions (corresponding to the initial nonzero values of a(n)) are 13, 24, 124, 134, 35, 235, 46, ... . - _Don Reble_, Sep 07 2021

%C Let T(n) = n*(n+1)/2 = A000217(n) denote the n-th triangular number.

%C Theorem A. a(n) = b(n) - c(n), where b(n) is the inverse triangular number sequence A003056, that is, b(n) is the maximal i such that T_i <= n, and c(n) is the number of partitions of n into consecutive parts = number of odd divisors of n = A001227(n).

%C This theorem was conjectured by _Omar E. Pol_ in February 2018, and proved independently by _William J. Keith_ and _Roland Bacher_ on Sep 05 2021. The elegant proof given in the link below is due to _Don Reble_.

%H N. J. A. Sloane, <a href="/A238005/b238005.txt">Table of n, a(n) for n = 1..20000</a>

%H N. J. A. Sloane, <a href="/A238005/a238005_2.txt">Proof of Theorem A in A238005</a>

%F G.f. = (x/(1-x)) * Sum_{k >= 1} x^(k*(k+1)/2) * (1 - x^(k-1)) / (1 - x^k). This follows from Theorem A and the g.f.s for A003056 and A001227. - _William J. Keith_, Sep 05 2021

%F a(n) = A238007(n) - A238006(n). - _Omar E. Pol_, Sep 11 2021

%F A001227(n) + a(n) + A238006(n) = A000009(n). - _R. J. Mathar_, Sep 23 2021

%e a(8) = 2 counts these partitions: 53, 431.

%t z = 70; q[n_] := q[n] = Select[IntegerPartitions[n], Max[Length /@ Split@#] == 1 &]; p1[p_] := p1[p] = DeleteDuplicates[p]; t[p_] := t[p] = Length[p1[p]];

%t Table[Count[q[n], p_ /; Max[p] - Min[p] < t[p]], {n, z}] (* A001227 *)

%t Table[Count[q[n], p_ /; Max[p] - Min[p] <= t[p]], {n, z}] (* A003056 *)

%t Table[Count[q[n], p_ /; Max[p] - Min[p] == t[p]], {n, z}] (* A238005 *)

%t Table[Count[q[n], p_ /; Max[p] - Min[p] > t[p]], {n, z}] (* A238006 *)

%t Table[Count[q[n], p_ /; Max[p] - Min[p] >= t[p]], {n, z}] (* A238007 *)

%t {0}~Join~Array[Floor[(Sqrt[1 + 8 #] - 1)/2] - DivisorSum[#, 1 &, OddQ] &, 102] (* _Michael De Vlieger_, Feb 18 2018 *)

%o (PARI) a(n) = if (n, (sqrtint(8*n+1)-1)\2 - sumdiv(n, d, d%2), 0); \\ _Michel Marcus_, Mar 01 2018

%Y Cf. A000009, A000217, A001227, A003056, A238006, A238007.

%Y a(n) is also the number of zeros in the n-th row of the triangles A196020, A211343, A231345, A236106, A237048 (simpler), A239662, A261699, A271344, A272026, A280850, A285574, A285891, A285914, A286013, A296508 (and possibly others). _Omar E. Pol_, Feb 17 2018

%Y Row sums of A347579. - _Omar E. Pol_, Sep 07 2021

%K nonn,easy

%O 1,8

%A _Clark Kimberling_, Feb 17 2014

%E Edited by _N. J. A. Sloane_, Sep 11 2021, mostly to add Theorem A.