A395312 Triangle read by rows: T(n, k) is the number of partitions of n into parts having exactly k distinct prime factors, with 0 <= k <= A111972(n) for n >= 1 and k = 0 for n = 0.

1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 3, 1, 1, 4, 0, 1, 6, 0, 1, 7, 0, 1, 9, 1, 1, 12, 0, 1, 15, 2, 1, 19, 0, 1, 23, 1, 1, 29, 1, 1, 37, 1, 1, 44, 0, 1, 54, 3, 1, 66, 0, 1, 80, 3, 1, 96, 2, 1, 115, 3, 1, 138, 0, 1, 165, 6, 1, 196, 1, 1, 231, 5, 1, 275, 3, 1, 322, 6

Offset

0,8

Links

Felix Huber, Rows n = 0 .. 2049, flattened

Formula

G.f.: For fixed k, Sum_{n >= 0} T(n, k) x^n = Product_{m >= 1, A001221(m) = k} 1/(1 - x^m).

T(n, 0) = 1. For n >= 1 the only allowed part is 1; for n = 0 this counts the empty partition.

T(n, 1) = A023894(n).

Example

The triangle begins:
  n\k |  0    1    2
  ----+--------------
   0  |  1
   1  |  1
   2  |  1    1
   3  |  1    1
   4  |  1    2
   5  |  1    2
   6  |  1    3    1
   7  |  1    4    0
   8  |  1    6    0
   9  |  1    7    0
  10  |  1    9    1
  11  |  1   12    0
  12  |  1   15    2
T(18, 2) = 3 since the partitions of 18 into parts having exactly 2 distinct prime factors are [18], [6, 12] and [6, 6, 6].

Maple

A111972:= proc(n) option remember;
    `if`(n = 0, 0, max(A111972(n - 1), nops(ifactors(n)[2])))
end proc:
with(NumberTheory):
N := 28: # Enlarge if you want more rows
K := A111972(N):
t := Array(0 .. N, 0 .. K):
for k from 0 to K do
    t[0, k] := 1
end do:
for k from 0 to K do
    for i from 1 to N do
        if Omega(i, 'distinct') = k then
            for n from i to N do
                t[n, k] := t[n, k] + t[n - i, k]
            end do
        end if
    end do
end do:
T := (n, k) -> t[n, k]:
seq(seq(T(n, k), k = 0 .. A111972(n)), n = 0 .. N);

Crossrefs

Cf. A001221, A023894, A111972, A394211.

Sequence in context: A202853 A228572 A334675 * A078380 A062356 A257993

Adjacent sequences: A395309 A395310 A395311 * A395313 A395314 A395315

Keyword

nonn,tabf,easy

Author

Felix Huber, May 22 2026

Status

approved