|
|
A046663
|
|
Triangle: T(n,k) = number of partitions of n (>=2) with no subsum equal to k (1 <= k <= n-1).
|
|
56
|
|
|
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
|
|
|
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, 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;
...
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)}):
|
|
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.
For subsets instead of partitions we have A366320, complement A365381.
A276024 counts distinct subset-sums of partitions.
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
EXTENSIONS
|
Corrected and extended by Don Reble, Nov 04 2001
|
|
STATUS
|
approved
|
|
|
|