A364909 Number of ways to write n as a nonnegative linear combination of a strict integer composition of n.

1, 1, 1, 5, 5, 7, 51, 45, 89, 109, 709, 733, 1495, 1935, 3119, 13785, 16611, 29035, 44611, 68733, 95193, 372897, 435007, 781345, 1177181, 1866659, 2600537, 3906561, 12052631, 14610799, 25407653, 37652265, 59943351, 84060993, 128112805, 172172117, 480353257, 578740011

Offset: 0

Author

Gus Wiseman, Aug 18 2023

Keywords

• nonn

Comments

A way of writing n as a (presumed 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).

Examples

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

Crossrefs

The case with no zero coefficients is A032020.

The version for partitions is A364907, strict A364910(n) = A364916(n,n).

The non-strict version is A364908.

A000041 counts integer partitions, strict A000009.

A011782 counts compositions, strict A032020.

A008284 counts partitions by length, strict A008289.

A097805 counts compositions by length, strict A072574.

Cf. A116861, A364350, A364839, A364906, A364912, A364914, A365002, A365004.

Programs

Mathematica

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

Python

from math import factorial
from sympy.utilities.iterables import partitions
def A364909(n):
    if n == 0: return 1
    aset = tuple(set(p) for p in partitions(n) if max(p.values(),default=0)==1)
    return sum(factorial(len(t)) for p in partitions(n) for t in aset if set(p).issubset(t)) # Chai Wah Wu, Sep 21 2023

Extensions

a(18)-a(37) from Chai Wah Wu, Sep 21 2023