A353837 Number of integer partitions of n with all distinct run-sums.

1, 1, 2, 3, 4, 7, 10, 14, 17, 28, 35, 49, 62, 85, 107, 149, 174, 238, 305, 384, 476, 614, 752, 950, 1148, 1451, 1763, 2205, 2654, 3259, 3966, 4807, 5773, 7039, 8404, 10129, 12140, 14528, 17288, 20668, 24505, 29062, 34437, 40704, 48059, 56748, 66577, 78228

Offset

0,3

Comments

The run-sums of a sequence are the sums of its maximal consecutive constant subsequences (runs). For example, the run-sums of (2,2,1,1,1,3,2,2) are (4,3,3,4). The first partition whose run-sums are not all distinct is (2,1,1).

Links

Max Alekseyev, Table of n, a(n) for n = 0..100

Example

The a(0) = 1 through a(6) = 10 partitions:
  ()  (1)  (2)   (3)    (4)     (5)      (6)
           (11)  (21)   (22)    (32)     (33)
                 (111)  (31)    (41)     (42)
                        (1111)  (221)    (51)
                                (311)    (222)
                                (2111)   (321)
                                (11111)  (411)
                                         (2211)
                                         (21111)
                                         (111111)

Mathematica

Table[Length[Select[IntegerPartitions[n], UnsameQ@@Total/@Split[#]&]], {n, 0, 15}]

Prog

(Sage) a353837 = lambda n: sum( abs(BipartiteGraph( Matrix(len(p), len(D:=list(set.union(*map(lambda t: set(divisors(t)), p)))), lambda i, j: p[i]%D[j]==0) ).matching_polynomial()[len(D)-len(p)]) for p in Partitions(n, max_slope=-1) ) # Max Alekseyev, Sep 11 2023

Crossrefs

For multiplicities instead of run-sums we have A098859, ranked by A130091.

For equal run-sums we have A304442, ranked by A353833 (nonprime A353834).

These partitions are ranked by A353838, complement A353839.

The version for compositions is A353850, ranked by A353852.

The weak version (rucksack partitions) is A353864, ranked by A353866.

The weak perfect version is A353865, ranked by A353867.

A005811 counts runs in binary expansion.

A275870 counts collapsible partitions, ranked by A300273.

A351014 counts distinct runs in standard compositions.

A353832 represents the operation of taking run-sums of a partition.

A353840-A353846 pertain to partition run-sum trajectory.

A353849 counts distinct run-sums in standard compositions.

Cf. A000041, A008284, A047966, A071625, A073093, A116608, A175413, A181819, A333755, A353848, A353867.

Sequence in context: A228588 A189720 A072958 * A062426 A184639 A035565

Adjacent sequences: A353834 A353835 A353836 * A353838 A353839 A353840

Keyword

nonn

Author

Gus Wiseman, May 26 2022

Status

approved