|
%I #36 Dec 30 2023 17:01:01
%S 1,1,2,5,10,23,47,102,207,440,890,1847,3730,7648,15400,31332,62922,
%T 127234,255374,514269,1030809,2071344,4148707,8321937,16660755,
%U 33384685,66812942,133789638,267685113,535784667,1071878216,2144762139,4290261840,8583175092,17168208940,34342860713
%N Number of subsets of {1..n} with a subset summing to n.
%F a(n) = 2^n-A365377(n). - _Chai Wah Wu_, Sep 09 2023
%e The a(1) = 1 through a(4) = 10 sets:
%e {1} {2} {3} {4}
%e {1,2} {1,2} {1,3}
%e {1,3} {1,4}
%e {2,3} {2,4}
%e {1,2,3} {3,4}
%e {1,2,3}
%e {1,2,4}
%e {1,3,4}
%e {2,3,4}
%e {1,2,3,4}
%t Table[Length[Select[Subsets[Range[n]],MemberQ[Total/@Subsets[#],n]&]],{n,0,10}]
%o (PARI) isok(s, n) = forsubset(#s, ss, if (vecsum(vector(#ss, k, s[ss[k]])) == n, return(1)));
%o a(n) = my(nb=0); forsubset(n, s, if (isok(s, n), nb++)); nb; \\ _Michel Marcus_, Sep 09 2023
%o (Python)
%o from itertools import combinations, chain
%o from sympy.utilities.iterables import partitions
%o def A365376(n):
%o if n == 0: return 1
%o nset = set(range(1,n+1))
%o s, c = [set(p) for p in partitions(n,m=n,k=n) if max(p.values(),default=1) == 1], 1
%o for a in chain.from_iterable(combinations(nset,m) for m in range(2,n+1)):
%o if sum(a) >= n:
%o aset = set(a)
%o for p in s:
%o if p.issubset(aset):
%o c += 1
%o break
%o return c # _Chai Wah Wu_, Sep 09 2023
%Y The case containing n is counted by A131577.
%Y The version with re-usable parts is A365073.
%Y The complement is counted by A365377.
%Y The complement w/ re-usable parts is A365380.
%Y Main diagonal of A365381.
%Y A000009 counts sets summing to n, multisets A000041.
%Y A000124 counts distinct possible sums of subsets of {1..n}.
%Y A124506 appears to count combination-free subsets, differences of A326083.
%Y A364350 counts combination-free strict partitions, complement A364839.
%Y A365046 counts combination-full subsets, differences of A364914.
%Y Cf. A007865, A085489, A088809, A093971, A103580, A151897, A236912, A237668, A326080, A364534.
%K nonn
%O 0,3
%A _Gus Wiseman_, Sep 08 2023
%E a(16)-a(25) from _Michel Marcus_, Sep 09 2023
%E a(26)-a(32) from _Chai Wah Wu_, Sep 09 2023
%E a(33)-a(35) from _Chai Wah Wu_, Sep 10 2023
|
