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,4

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).

Links

Table of n, a(n) for n=0..37.

Example

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

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}]

Prog

(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

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.

Sequence in context: A301733 A114367 A093311 * A328344 A100128 A212004

Adjacent sequences: A364906 A364907 A364908 * A364910 A364911 A364912

Keyword

nonn

Author

Gus Wiseman, Aug 18 2023

Extensions

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

Status

approved