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

Author

Gus Wiseman, Dec 07 2022

Keywords

• nonn

Examples

			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)
		

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.

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.

Programs

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}]

Extensions

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