login
Irregular triangle read by rows where T(n,k) is the number of subsets of {1..n} with a subset summing to k.
32

%I #6 Sep 08 2023 22:53:05

%S 1,2,1,4,2,2,1,8,4,4,5,2,2,1,16,8,8,10,10,7,5,5,2,2,1,32,16,16,20,20,

%T 23,15,15,12,12,8,5,5,2,2,1,64,32,32,40,40,46,47,38,33,35,29,28,21,17,

%U 14,13,8,5,5,2,2,1,128,64,64,80,80,92,94,102,79,82,76,75,68,64,53,48,43,34,33,23,19,15,13,8,5,5,2,2,1

%N Irregular triangle read by rows where T(n,k) is the number of subsets of {1..n} with a subset summing to k.

%C Row lengths are A000124(n) = 1 + n*(n+1)/2.

%e Triangle begins:

%e 1

%e 2 1

%e 4 2 2 1

%e 8 4 4 5 2 2 1

%e 16 8 8 10 10 7 5 5 2 2 1

%e 32 16 16 20 20 23 15 15 12 12 8 5 5 2 2 1

%e 64 32 32 40 40 46 47 38 33 35 29 28 21 17 14 13 8 5 5 2 2 1

%e Array begins:

%e k=0 k=1 k=2 k=3 k=4 k=5 k=6 k=7 k=8 k=9

%e -------------------------------------------------------

%e n=0: 1

%e n=1: 2 1

%e n=2: 4 2 2 1

%e n=3: 8 4 4 5 2 2 1

%e n=4: 16 8 8 10 10 7 5 5 2 2

%e n=5: 32 16 16 20 20 23 15 15 12 12

%e n=6: 64 32 32 40 40 46 47 38 33 35

%e n=7: 128 64 64 80 80 92 94 102 79 82

%e n=8: 256 128 128 160 160 184 188 204 207 184

%e n=9: 512 256 256 320 320 368 376 408 414 440

%e The T(5,8) = 12 subsets are:

%e {3,5} {1,2,5} {1,2,3,4} {1,2,3,4,5}

%e {1,3,4} {1,2,3,5}

%e {1,3,5} {1,2,4,5}

%e {2,3,5} {1,3,4,5}

%e {3,4,5} {2,3,4,5}

%t Table[Length[Select[Subsets[Range[n]],MemberQ[Total/@Subsets[#],k]&]],{n,0,8},{k,0,n*(n+1)/2}]

%Y Row lengths are A000124 = number of distinct sums of subsets of {1..n}.

%Y Central column/main diagonal is A365376.

%Y A000009 counts sets summing to n.

%Y A000124 counts distinct possible sums of subsets of {1..n}.

%Y A365046 counts combination-full subsets, differences of A364914.

%Y Cf. A007865, A085489, A093971, A103580, A131577, A151897, A326080, A364272, A364534, A365073, A365377, A365380.

%K nonn,tabf

%O 0,2

%A _Gus Wiseman_, Sep 08 2023