A365002 Number of ways to write n as a nonnegative linear combination of a strict integer partition.

1, 1, 2, 4, 8, 10, 26, 32, 63, 84, 157, 207, 383, 477, 768, 1108, 1710, 2261, 3536, 4605, 6869, 9339, 13343, 17653, 25785, 33463, 46752, 61549, 85614, 110861, 153719, 197345, 268623, 346845, 463513, 593363, 797082, 1011403, 1335625, 1703143, 2232161, 2820539

Offset

0,3

Comments

A way of writing n as a (nonnegative) linear combination of a finite sequence y is any sequence of pairs (k_i,y_i) such that k_i >= 0 and Sum k_i*y_i = n. For example, the pairs ((3,1),(1,1),(1,1),(0,2)) are a way of writing 5 as a linear combination of (1,1,1,2), namely 5 = 3*1 + 1*1 + 1*1 + 0*2. Of course, there are A000041(n) ways to write n as a linear combination of (1..n).

Links

Alois P. Heinz, Table of n, a(n) for n = 0..500

Example

The a(1) = 1 through a(5) = 10 ways:
  1*1  1*2  1*3      1*4      1*5
       2*1  3*1      2*2      5*1
            0*2+3*1  4*1      0*2+5*1
            1*2+1*1  0*2+4*1  0*3+5*1
                     0*3+4*1  0*4+5*1
                     1*2+2*1  1*2+3*1
                     1*3+1*1  1*3+1*2
                     2*2+0*1  1*3+2*1
                              1*4+1*1
                              2*2+1*1

Mathematica

combs[n_, y_]:=With[{s=Table[{k, i}, {k, y}, {i, 0, Floor[n/k]}]}, Select[Tuples[s], Total[Times@@@#]==n&]];
Table[Sum[Length[combs[n, y]], {y, Select[Join@@IntegerPartitions/@Range[n], UnsameQ@@#&]}], {n, 0, 15}]

Prog

(Python)
from itertools import combinations
from collections import Counter
from sympy.utilities.iterables import partitions
def A365002(n):
    aset = Counter(tuple(sorted(set(p))) for p in partitions(n))
    return sum(sum(aset[t] for t in aset if set(t).issubset(set(q))) for l in range(1, n+1) for q in combinations(range(1, n+1), l) if sum(q)<=n) # Chai Wah Wu, Sep 20 2023

Crossrefs

Row sums of lower-left half of A364916 as an array.

Column sums of right half of A364916 as a triangle.

For all positive coefficients we have A000041, non-strict A006951.

A000041 counts integer partitions, strict A000009.

A008284 counts partitions by length, strict A008289.

A364350 counts combination-free strict partitions, complement A364839.

A364913 counts combination-full partitions.

Cf. A066328, A116861, A364272, A364907, A364910, A364911, A364912, A365004.

Sequence in context: A308832 A124849 A056654 * A370663 A020950 A056386

Adjacent sequences: A364999 A365000 A365001 * A365003 A365004 A365005

Keyword

nonn

Author

Gus Wiseman, Aug 22 2023

Extensions

a(16)-a(34) from Chai Wah Wu, Sep 20 2023

a(35)-a(38) from Chai Wah Wu, Sep 21 2023

a(0)=1 and a(39)-a(41) from Alois P. Heinz, Jan 11 2024

Status

approved