login
Triangle: T(n,k) = number of partitions of n (>=2) with no subsum equal to k (1 <= k <= n-1).
56

%I #43 Oct 14 2023 14:15:22

%S 1,1,1,2,2,2,2,2,2,2,4,3,5,3,4,4,4,4,4,4,4,7,5,7,8,7,5,7,8,7,7,8,8,7,

%T 7,8,12,9,12,9,17,9,12,9,12,14,11,12,12,13,13,12,12,11,14,21,15,19,15,

%U 21,24,21,15,19,15,21,24,19,20,19,21,22,22,21,19,20,19,24,34,23,30,24,30,25,46,25,30,24,30,23,34

%N Triangle: T(n,k) = number of partitions of n (>=2) with no subsum equal to k (1 <= k <= n-1).

%H Alois P. Heinz, <a href="/A046663/b046663.txt">Rows n = 2..98, flattened</a>

%H P. Erdős, J. L. Nicolas and A. Sárközy, <a href="http://dx.doi.org/10.1016/0012-365X(89)90086-1">On the number of partitions of n without a given subsum (I)</a>, Discrete Math., 75 (1989), 155-166 = Annals Discrete Math. Vol. 43, Graph Theory and Combinatorics 1988, ed. B. Bollobas.

%e For n = 4 there are two partitions (4, 2+2) with no subsum equal to 1, two (4, 3+1) with no subsum equal to 2 and two (4, 2+2) with no subsum equal to 3.

%e Triangle T(n,k) begins:

%e 1;

%e 1, 1;

%e 2, 2, 2;

%e 2, 2, 2, 2;

%e 4, 3, 5, 3, 4;

%e 4, 4, 4, 4, 4, 4;

%e 7, 5, 7, 8, 7, 5, 7;

%e 8, 7, 7, 8, 8, 7, 7, 8;

%e 12, 9, 12, 9, 17, 9, 12, 9, 12;

%e ...

%e From _Gus Wiseman_, Oct 11 2023: (Start)

%e Row n = 8 counts the following partitions:

%e (8) (8) (8) (8) (8) (8) (8)

%e (62) (71) (71) (71) (71) (71) (62)

%e (53) (53) (62) (62) (62) (53) (53)

%e (44) (44) (611) (611) (611) (44) (44)

%e (422) (431) (44) (53) (44) (431) (422)

%e (332) (422) (521) (422) (332)

%e (2222) (2222) (5111) (2222) (2222)

%e (332)

%e (End)

%p g:= proc(n, i) option remember;

%p `if`(n=0, 1, `if`(i>1, g(n, i-1), 0)+`if`(i>n, 0, g(n-i, i)))

%p end:

%p b:= proc(n, i, s) option remember;

%p `if`(0 in s or n in s, 0, `if`(n=0 or s={}, g(n, i),

%p `if`(i<1, 0, b(n, i-1, s)+`if`(i>n, 0, b(n-i, i,

%p select(y-> 0<=y and y<=n-i, map(x-> [x, x-i][], s)))))))

%p end:

%p T:= (n, k)-> b(n, n, {min(k, n-k)}):

%p seq(seq(T(n, k), k=1..n-1), n=2..16); # _Alois P. Heinz_, Jul 13 2012

%t g[n_, i_] := g[n, i] = If[n == 0, 1, If[i > 1, g[n, i-1], 0] + If[i > n, 0, g[n-i, i]]]; b[n_, i_, s_] := b[n, i, s] = If[MemberQ[s, 0 | n], 0, If[n == 0 || s == {}, g[n, i], If[i < 1, 0, b[n, i-1, s] + If[i > n, 0, b[n-i, i, Select[Flatten[s /. x_ :> {x, x-i}], 0 <= # <= n-i &]]]]]]; t[n_, k_] := b[n, n, {Min[k, n-k]}]; Table[t[n, k], {n, 2, 16}, {k, 1, n-1}] // Flatten (* _Jean-François Alcover_, Aug 20 2013, translated from Maple *)

%t Table[Length[Select[IntegerPartitions[n],FreeQ[Total/@Subsets[#],k]&]],{n,2,10},{k,1,n-1}] (* _Gus Wiseman_, Oct 11 2023 *)

%Y Column k = 0 and diagonal k = n are both A002865.

%Y Central diagonal n = 2k is A006827.

%Y The complement with expanded domain is A365543.

%Y The strict case is A365663, complement A365661.

%Y Row sums are A365918, complement A304792.

%Y For subsets instead of partitions we have A366320, complement A365381.

%Y A000041 counts integer partitions, strict A000009.

%Y A276024 counts distinct subset-sums of partitions.

%Y A364272 counts sum-full strict partitions, sum-free A364349.

%Y Cf. A000124, A002219, A093971, A108917, A122768, A299701, A365658.

%K nonn,easy,look,nice,tabl

%O 2,4

%A _N. J. A. Sloane_

%E Corrected and extended by _Don Reble_, Nov 04 2001