A046663 - OEIS

A046663

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

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, 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, 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

(list; table; graph; refs; listen; history; text; internal format)

OFFSET

2,4

LINKS

Alois P. Heinz, Rows n = 2..98, flattened

P. Erdős, J. L. Nicolas and A. Sárközy, On the number of partitions of n without a given subsum (I), Discrete Math., 75 (1989), 155-166 = Annals Discrete Math. Vol. 43, Graph Theory and Combinatorics 1988, ed. B. Bollobas.

EXAMPLE

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.

Triangle T(n,k) begins:

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, 7, 8;

12, 9, 12, 9, 17, 9, 12, 9, 12;

...

From Gus Wiseman, Oct 11 2023: (Start)

Row n = 8 counts the following partitions:

(8) (8) (8) (8) (8) (8) (8)

(62) (71) (71) (71) (71) (71) (62)

(53) (53) (62) (62) (62) (53) (53)

(44) (44) (611) (611) (611) (44) (44)

(422) (431) (44) (53) (44) (431) (422)

(332) (422) (521) (422) (332)

(2222) (2222) (5111) (2222) (2222)

(332)

(End)

MAPLE

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

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

end:

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

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

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

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

end:

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

seq(seq(T(n, k), k=1..n-1), n=2..16); # Alois P. Heinz, Jul 13 2012

MATHEMATICA

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 *)

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

CROSSREFS

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

Central diagonal n = 2k is A006827.

The complement with expanded domain is A365543.

The strict case is A365663, complement A365661.

Row sums are A365918, complement A304792.

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

A000041 counts integer partitions, strict A000009.

A276024 counts distinct subset-sums of partitions.

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

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