A320387 Number of partitions of n into distinct parts such that the successive differences of consecutive parts are nonincreasing, and first difference <= first part.

1, 1, 1, 2, 1, 2, 3, 2, 2, 4, 3, 4, 5, 3, 5, 7, 4, 7, 8, 6, 8, 11, 7, 9, 13, 9, 11, 16, 12, 15, 18, 13, 17, 20, 17, 21, 24, 19, 24, 30, 22, 28, 34, 26, 34, 38, 30, 37, 43, 37, 42, 48, 41, 50, 58, 48, 55, 64, 53, 64, 71, 59, 73, 81, 69, 79, 89, 79, 90, 101, 87, 100, 111

Offset

0,4

Comments

Partitions are usually written with parts in descending order, but the conditions are easier to check "visually" if written in ascending order.

Generating function of the "second integrals" of partitions: given a partition (p_1, ..., p_s) written in weakly decreasing order, write the sequence B = (b_1, b_2, ..., b_s) = (p_1, p_1 + p_2, ..., p_1 + ... + p_s). The sequence gives the coefficients of the generating function summing q^(b_1 + ... + b_s) over all partitions of all nonnegative integers. - William J. Keith, Apr 23 2022

From Gus Wiseman, Jan 17 2023: (Start)

Equivalently, a(n) is the number of multisets (weakly increasing sequences of positive integers) with weighted sum n. For example, the Heinz numbers of the a(0) = 1 through a(15) = 7 multisets are:

1 2 3 4 7 6 8 10 15 12 16 18 20 26 24 28

5 11 9 17 19 14 21 22 27 41 30 32

13 23 29 31 33 55 39 34

25 35 37 43 45

49 77 47

65

121

These multisets are counted by A264034. The reverse version is A007294. The zero-based version is A359678.

(End)

Links

Fausto A. C. Cariboni, Table of n, a(n) for n = 0..2000 (terms 0..300 from Seiichi Manyama)

Formula

G.f.: Sum_{k>=1} x^binomial(k,2)/Product_{j=1..k-1} (1 - x^(binomial(k,2)-binomial(j,2))). - Andrew Howroyd, Jan 22 2023

Example

There are a(29) = 15 such partitions of 29:
  01: [29]
  02: [10, 19]
  03: [11, 18]
  04: [12, 17]
  05: [13, 16]
  06: [14, 15]
  07: [5, 10, 14]
  08: [6, 10, 13]
  09: [6, 11, 12]
  10: [7, 10, 12]
  11: [8, 10, 11]
  12: [3, 6, 9, 11]
  13: [5, 7, 8, 9]
  14: [2, 4, 6, 8, 9]
  15: [3, 5, 6, 7, 8]
There are a(30) = 18 such partitions of 30:
  01: [30]
  02: [10, 20]
  03: [11, 19]
  04: [12, 18]
  05: [13, 17]
  06: [14, 16]
  07: [5, 10, 15]
  08: [6, 10, 14]
  09: [6, 11, 13]
  10: [7, 10, 13]
  11: [7, 11, 12]
  12: [8, 10, 12]
  13: [3, 6, 9, 12]
  14: [9, 10, 11]
  15: [4, 7, 9, 10]
  16: [2, 4, 6, 8, 10]
  17: [6, 7, 8, 9]
  18: [4, 5, 6, 7, 8]

Mathematica

prix[n_]:=If[n==1, {}, Flatten[Cases[FactorInteger[n], {p_, k_}:>Table[PrimePi[p], {k}]]]];
ots[y_]:=Sum[i*y[[i]], {i, Length[y]}];
Table[Length[Select[Range[2^n], ots[prix[#]]==n&]], {n, 10}] (* Gus Wiseman, Jan 17 2023 *)

Prog

(Ruby)
def partition(n, min, max)
  return [[]] if n == 0
  [max, n].min.downto(min).flat_map{|i| partition(n - i, min, i - 1).map{|rest| [i, *rest]}}
end
def f(n)
  return 1 if n == 0
  cnt = 0
  partition(n, 1, n).each{|ary|
    ary << 0
    ary0 = (1..ary.size - 1).map{|i| ary[i - 1] - ary[i]}
    cnt += 1 if ary0.sort == ary0
  }
  cnt
end
def A320387(n)
  (0..n).map{|i| f(i)}
end
p A320387(50)
(PARI) seq(n)={Vec(sum(k=1, (sqrtint(8*n+1)+1)\2, my(t=binomial(k, 2)); x^t/prod(j=1, k-1, 1 - x^(t-binomial(j, 2)) + O(x^(n-t+1)))))} \\ Andrew Howroyd, Jan 22 2023

Crossrefs

Cf. A007294, A179254, A179255, A179269, A320382, A320385, A320388.

Number of appearances of n > 0 in A304818, reverse A318283.

A053632 counts compositions by weighted sum.

A358194 counts partitions by weighted sum, reverse A264034.

Weighted sum of prime indices: A359497, A359676, A359682, A359754, A359755.

Cf. A029931, A359361, A359397, A359674, A359677, A359678.

Sequence in context: A111725 A302257 A324748 * A304707 A112218 A172366

Adjacent sequences: A320384 A320385 A320386 * A320388 A320389 A320390

Keyword

nonn

Author

Seiichi Manyama, Oct 12 2018

Status

approved