A395312 - OEIS

%I #6 May 26 2026 18:45:06

%S 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,

%T 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,

%U 138,0,1,165,6,1,196,1,1,231,5,1,275,3,1,322,6

%N 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.

%H Felix Huber, <a href="/A395312/b395312.txt">Rows n = 0 .. 2049, flattened</a>

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

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

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

%e The triangle begins:

%e   n\k |  0    1    2

%e   ----+--------------

%e    0  |  1

%e    1  |  1

%e    2  |  1    1

%e    3  |  1    1

%e    4  |  1    2

%e    5  |  1    2

%e    6  |  1    3    1

%e    7  |  1    4    0

%e    8  |  1    6    0

%e    9  |  1    7    0

%e   10  |  1    9    1

%e   11  |  1   12    0

%e   12  |  1   15    2

%e 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].

%p A111972:= proc(n) option remember;

%p     `if`(n = 0, 0, max(A111972(n - 1), nops(ifactors(n)[2])))

%p end proc:

%p with(NumberTheory):

%p N := 28: # Enlarge if you want more rows

%p K := A111972(N):

%p t := Array(0 .. N, 0 .. K):

%p for k from 0 to K do

%p     t[0, k] := 1

%p end do:

%p for k from 0 to K do

%p     for i from 1 to N do

%p         if Omega(i, 'distinct') = k then

%p             for n from i to N do

%p                 t[n, k] := t[n, k] + t[n - i, k]

%p             end do

%p         end if

%p     end do

%p end do:

%p T := (n, k) -> t[n, k]:

%p seq(seq(T(n, k), k = 0 .. A111972(n)), n = 0 .. N);

%Y Cf. A001221, A023894, A111972, A394211.

%K nonn,tabf,easy

%O 0,8

%A _Felix Huber_, May 22 2026