A395190 a(n) is the number of partitions of n into distinct parts that contain a subset whose product is n.

1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 4, 1, 3, 4, 3, 1, 8, 1, 12, 8, 6, 1, 35, 1, 8, 15, 31, 1, 75, 1, 47, 31, 17, 55, 153, 1, 23, 59, 277, 1, 319, 1, 174, 286, 45, 1, 979, 1, 367, 192, 388, 1, 1123, 517, 1600, 331, 111, 1, 4836, 1, 147, 1889, 2045, 1374, 3533, 1, 1638

Offset

1,6

Links

Felix Huber, Table of n, a(n) for n = 1..2143

Formula

a(n) = 1 <=> n is in A000961.

1 <= a(n) <= A000009(n) for n >= 1.

Example

a(12) = 4: [12], [3, 4, 5], [2, 4, 6], [1, 2, 3, 6], since in each case a subset of the parts has product 12 (namely 12; 3*4; 2*6; and 2*6, respectively).

Maple

f := proc(r, l) option remember;
    local d, s, t;
    if r = 1 then return [[]] end if;
    s := []:
    for d in NumberTheory:-Divisors(r) do
        if d >= l and d > 1 then
            for t in f(r/d, d + 1) do
                s := [op(s), [d, op(t)]]
            end do
        end if
    end do;
    s
end:
p := n -> f(n, 2):
A395190 := proc(n)
    local a, b, i, j, l;
    a := 0:
    for j in p(n) do
        l := remove(x -> member(x, j), [seq(i, i = 1 .. n)]):
        b := proc(m, i, l) option remember;
            `if`(m = 0, 1, `if`(i = 0, 0, b(m, i - 1, l) + `if`(l[i] > m, 0, b(m - l[i], i - 1, l))))
        end proc:
        a := a + b(n - add(j), nops(l), l)
    end do;
    a
end proc:
seq(A395190(n), n = 1 .. 68);

Crossrefs

Cf. A000009, A000961, A045778.

Sequence in context: A353666 A051119 A159269 * A186728 A158298 A009191

Adjacent sequences: A395187 A395188 A395189 * A395191 A395192 A395193

Keyword

nonn

Author

Felix Huber, May 10 2026

Status

approved