login

Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.

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

%I #13 Dec 30 2023 21:23:37

%S 1,1,1,5,5,7,51,45,89,109,709,733,1495,1935,3119,13785,16611,29035,

%T 44611,68733,95193,372897,435007,781345,1177181,1866659,2600537,

%U 3906561,12052631,14610799,25407653,37652265,59943351,84060993,128112805,172172117,480353257,578740011

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

%C 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 The a(0) = 1 through a(5) = 7 ways:

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

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

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

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

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

%e 1*4+1*1

%e 5*1+0*4

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

%t Table[Length[Join@@Table[combs[n,ptn],{ptn,Join@@Permutations/@Select[IntegerPartitions[n],UnsameQ@@#&]}]],{n,0,5}]

%o (Python)

%o from math import factorial

%o from sympy.utilities.iterables import partitions

%o def A364909(n):

%o if n == 0: return 1

%o aset = tuple(set(p) for p in partitions(n) if max(p.values(),default=0)==1)

%o 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 The case with no zero coefficients is A032020.

%Y The version for partitions is A364907, strict A364910(n) = A364916(n,n).

%Y The non-strict version is A364908.

%Y A000041 counts integer partitions, strict A000009.

%Y A011782 counts compositions, strict A032020.

%Y A008284 counts partitions by length, strict A008289.

%Y A097805 counts compositions by length, strict A072574.

%Y Cf. A116861, A364350, A364839, A364906, A364912, A364914, A365002, A365004.

%K nonn

%O 0,4

%A _Gus Wiseman_, Aug 18 2023

%E a(18)-a(37) from _Chai Wah Wu_, Sep 21 2023