A358902 Number of integer compositions of n whose parts have weakly decreasing numbers of distinct prime factors (A001221).

1, 1, 2, 3, 5, 8, 13, 21, 33, 53, 84, 134, 213, 338, 536, 850, 1349, 2136, 3389, 5367, 8509, 13480, 21362, 33843, 53624, 84957, 134600, 213251, 337850, 535251, 847987, 1343440, 2128372, 3371895, 5341977, 8463051, 13407689, 21241181, 33651507, 53312538, 84460690

Offset

0,3

Links

Alois P. Heinz, Table of n, a(n) for n = 0..5004 (first 101 terms from Lucas A. Brown)

Lucas A. Brown, Python program.

Example

The a(0) = 1 through a(6) = 13 compositions:
  ()  (1)  (2)   (3)    (4)     (5)      (6)
           (11)  (21)   (22)    (23)     (24)
                 (111)  (31)    (32)     (33)
                        (211)   (41)     (42)
                        (1111)  (221)    (51)
                                (311)    (222)
                                (2111)   (231)
                                (11111)  (321)
                                         (411)
                                         (2211)
                                         (3111)
                                         (21111)
                                         (111111)

Maple

p:= proc(n) option remember; nops(ifactors(n)[2]) end:
b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<0, 0,
      add((t-> `if`(t<=i, b(n-j, t), 0))(p(j)), j=1..n)))
    end:
a:= n-> b(n$2):
seq(a(n), n=0..40);  # Alois P. Heinz, Feb 14 2024

Mathematica

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], GreaterEqual@@PrimeNu/@#&]], {n, 0, 10}]

Crossrefs

For lengths of partitions see A141199, compositions A218482.

The strictly decreasing case is A358903.

A001222 counts prime factors, distinct A001221.

A011782 counts compositions.

A116608 counts partitions by sum and number of distinct parts.

A334028 counts distinct parts in standard compositions.

A358836 counts multiset partitions with all distinct block sizes.

Cf. A046660, A056239, A071625, A129519, A300335, A358831, A358908, A358911.

Sequence in context: A334738 A286938 A055806 * A023438 A117760 A181600

Adjacent sequences: A358899 A358900 A358901 * A358903 A358904 A358905

Keyword

nonn

Author

Gus Wiseman, Dec 07 2022

Extensions

a(21) and beyond from Lucas A. Brown, Dec 15 2022

Status

approved