A366129 Number of finite sets of positive integers with greatest non-subset-sum n.

1, 2, 2, 4, 4, 6, 7, 11, 11, 15, 18, 23, 28, 36, 40, 50, 59, 70, 83, 101, 118, 141, 166, 195, 227, 268, 306, 358, 414, 478, 549, 640, 730, 846, 968, 1113, 1271, 1462, 1657, 1897, 2154, 2451

Offset: 1

Author

Gus Wiseman, Oct 07 2023

Keywords

• nonn
• more

Comments

A non-subset-sum of a set summing to n is a positive integer up to n that is not the sum of any subset. For example, the non-subset-sums of {1,3,4} are {2,6}.

Examples

			The a(1) = 1 through a(8) = 11 sets:
  {2}  {3}    {4}    {5}      {6}      {7}      {8}        {9}
       {1,3}  {1,4}  {2,3}    {2,4}    {2,5}    {2,6}      {2,7}
                     {1,5}    {1,6}    {3,4}    {3,5}      {3,6}
                     {1,2,5}  {1,2,6}  {1,7}    {1,8}      {4,5}
                                       {1,3,4}  {1,3,5}    {2,3,4}
                                       {1,2,7}  {1,2,8}    {1,9}
                                                {1,2,3,8}  {1,3,6}
                                                           {1,4,5}
                                                           {1,2,9}
                                                           {1,2,3,9}
                                                           {1,2,4,9}
		

Crossrefs

For least instead of greatest: A188431, non-strict A126796 (ranks A325781).

The version counting multisets instead of sets is A366127.

These sets counted by sum are A365924, strict A365831.

A046663 counts partitions without a submultiset summing k, strict A365663.

A325799 counts non-subset-sums of prime indices.

A365923 counts partitions by number of non-subset-sums, strict A365545.

Cf. A006827, A276024, A284640, A304792, A365543, A365658, A365661, A365918, A365920, A365921, A365925.

Programs

Mathematica

nmz[y_]:=Complement[Range[Total[y]], Total/@Subsets[y]];
Table[Length[Select[Join@@IntegerPartitions/@Range[n,2*n], UnsameQ@@#&&Max@@nmz[#]==n&]],{n,15}]

Extensions

a(31)-a(42) from Erich Friedman, Nov 13 2024