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

%I #22 Jan 11 2024 16:22:39

%S 1,1,2,4,8,10,26,32,63,84,157,207,383,477,768,1108,1710,2261,3536,

%T 4605,6869,9339,13343,17653,25785,33463,46752,61549,85614,110861,

%U 153719,197345,268623,346845,463513,593363,797082,1011403,1335625,1703143,2232161,2820539

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

%C 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 Alois P. Heinz, <a href="/A365002/b365002.txt">Table of n, a(n) for n = 0..500</a>

%e The a(1) = 1 through a(5) = 10 ways:

%e 1*1 1*2 1*3 1*4 1*5

%e 2*1 3*1 2*2 5*1

%e 0*2+3*1 4*1 0*2+5*1

%e 1*2+1*1 0*2+4*1 0*3+5*1

%e 0*3+4*1 0*4+5*1

%e 1*2+2*1 1*2+3*1

%e 1*3+1*1 1*3+1*2

%e 2*2+0*1 1*3+2*1

%e 1*4+1*1

%e 2*2+1*1

%t combs[n_,y_]:=With[{s=Table[{k,i},{k,y},{i,0,Floor[n/k]}]}, Select[Tuples[s],Total[Times@@@#]==n&]];

%t Table[Sum[Length[combs[n,y]], {y,Select[Join@@IntegerPartitions/@Range[n], UnsameQ@@#&]}],{n,0,15}]

%o (Python)

%o from itertools import combinations

%o from collections import Counter

%o from sympy.utilities.iterables import partitions

%o def A365002(n):

%o aset = Counter(tuple(sorted(set(p))) for p in partitions(n))

%o 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 Row sums of lower-left half of A364916 as an array.

%Y Column sums of right half of A364916 as a triangle.

%Y For all positive coefficients we have A000041, non-strict A006951.

%Y A000041 counts integer partitions, strict A000009.

%Y A008284 counts partitions by length, strict A008289.

%Y A364350 counts combination-free strict partitions, complement A364839.

%Y A364913 counts combination-full partitions.

%Y Cf. A066328, A116861, A364272, A364907, A364910, A364911, A364912, A365004.

%K nonn

%O 0,3

%A _Gus Wiseman_, Aug 22 2023

%E a(16)-a(34) from _Chai Wah Wu_, Sep 20 2023

%E a(35)-a(38) from _Chai Wah Wu_, Sep 21 2023

%E a(0)=1 and a(39)-a(41) from _Alois P. Heinz_, Jan 11 2024