cp's OEIS Frontend

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

%I A365002 #22 Jan 11 2024 16:22:39
%S A365002 1,1,2,4,8,10,26,32,63,84,157,207,383,477,768,1108,1710,2261,3536,
%T A365002 4605,6869,9339,13343,17653,25785,33463,46752,61549,85614,110861,
%U A365002 153719,197345,268623,346845,463513,593363,797082,1011403,1335625,1703143,2232161,2820539
%N A365002 Number of ways to write n as a nonnegative linear combination of a strict integer partition.
%C A365002 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).
%H A365002 Alois P. Heinz, <a href="/A365002/b365002.txt">Table of n, a(n) for n = 0..500</a>
%e A365002 The a(1) = 1 through a(5) = 10 ways:
%e A365002   1*1  1*2  1*3      1*4      1*5
%e A365002        2*1  3*1      2*2      5*1
%e A365002             0*2+3*1  4*1      0*2+5*1
%e A365002             1*2+1*1  0*2+4*1  0*3+5*1
%e A365002                      0*3+4*1  0*4+5*1
%e A365002                      1*2+2*1  1*2+3*1
%e A365002                      1*3+1*1  1*3+1*2
%e A365002                      2*2+0*1  1*3+2*1
%e A365002                               1*4+1*1
%e A365002                               2*2+1*1
%t A365002 combs[n_,y_]:=With[{s=Table[{k,i},{k,y},{i,0,Floor[n/k]}]}, Select[Tuples[s],Total[Times@@@#]==n&]];
%t A365002 Table[Sum[Length[combs[n,y]], {y,Select[Join@@IntegerPartitions/@Range[n], UnsameQ@@#&]}],{n,0,15}]
%o A365002 (Python)
%o A365002 from itertools import combinations
%o A365002 from collections import Counter
%o A365002 from sympy.utilities.iterables import partitions
%o A365002 def A365002(n):
%o A365002     aset = Counter(tuple(sorted(set(p))) for p in partitions(n))
%o A365002     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
%Y A365002 Row sums of lower-left half of A364916 as an array.
%Y A365002 Column sums of right half of A364916 as a triangle.
%Y A365002 For all positive coefficients we have A000041, non-strict A006951.
%Y A365002 A000041 counts integer partitions, strict A000009.
%Y A365002 A008284 counts partitions by length, strict A008289.
%Y A365002 A364350 counts combination-free strict partitions, complement A364839.
%Y A365002 A364913 counts combination-full partitions.
%Y A365002 Cf. A066328, A116861, A364272, A364907, A364910, A364911, A364912, A365004.
%K A365002 nonn
%O A365002 0,3
%A A365002 _Gus Wiseman_, Aug 22 2023
%E A365002 a(16)-a(34) from _Chai Wah Wu_, Sep 20 2023
%E A365002 a(35)-a(38) from _Chai Wah Wu_, Sep 21 2023
%E A365002 a(0)=1 and a(39)-a(41) from _Alois P. Heinz_, Jan 11 2024