login
A364909
Number of ways to write n as a nonnegative linear combination of a strict integer composition of n.
4
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).
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.
Sequence in context: A301733 A114367 A093311 * A328344 A100128 A212004
KEYWORD
nonn
AUTHOR
Gus Wiseman, Aug 18 2023
EXTENSIONS
a(18)-a(37) from Chai Wah Wu, Sep 21 2023
STATUS
approved