cp's OEIS Frontend

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

%I A364909 #13 Dec 30 2023 21:23:37
%S A364909 1,1,1,5,5,7,51,45,89,109,709,733,1495,1935,3119,13785,16611,29035,
%T A364909 44611,68733,95193,372897,435007,781345,1177181,1866659,2600537,
%U A364909 3906561,12052631,14610799,25407653,37652265,59943351,84060993,128112805,172172117,480353257,578740011
%N A364909 Number of ways to write n as a nonnegative linear combination of a strict integer composition of n.
%C A364909 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).
%e A364909 The a(0) = 1 through a(5) = 7 ways:
%e A364909   .  1*1  1*2  1*3      1*4      1*5
%e A364909                0*2+3*1  0*3+4*1  0*4+5*1
%e A364909                1*1+1*2  1*1+1*3  1*1+1*4
%e A364909                1*2+1*1  1*3+1*1  1*2+1*3
%e A364909                3*1+0*2  4*1+0*3  1*3+1*2
%e A364909                                  1*4+1*1
%e A364909                                  5*1+0*4
%t A364909 combs[n_,y_]:=With[{s=Table[{k,i},{k,y},{i,0,Floor[n/k]}]},Select[Tuples[s],Total[Times@@@#]==n&]];
%t A364909 Table[Length[Join@@Table[combs[n,ptn],{ptn,Join@@Permutations/@Select[IntegerPartitions[n],UnsameQ@@#&]}]],{n,0,5}]
%o A364909 (Python)
%o A364909 from math import factorial
%o A364909 from sympy.utilities.iterables import partitions
%o A364909 def A364909(n):
%o A364909     if n == 0: return 1
%o A364909     aset = tuple(set(p) for p in partitions(n) if max(p.values(),default=0)==1)
%o A364909     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
%Y A364909 The case with no zero coefficients is A032020.
%Y A364909 The version for partitions is A364907, strict A364910(n) = A364916(n,n).
%Y A364909 The non-strict version is A364908.
%Y A364909 A000041 counts integer partitions, strict A000009.
%Y A364909 A011782 counts compositions, strict A032020.
%Y A364909 A008284 counts partitions by length, strict A008289.
%Y A364909 A097805 counts compositions by length, strict A072574.
%Y A364909 Cf. A116861, A364350, A364839, A364906, A364912, A364914, A365002, A365004.
%K A364909 nonn
%O A364909 0,4
%A A364909 _Gus Wiseman_, Aug 18 2023
%E A364909 a(18)-a(37) from _Chai Wah Wu_, Sep 21 2023