A088528 Let m = number of ways of partitioning n into parts using all the parts of a subset of {1, 2, ..., n-1} whose sum of all parts of a subset is less than n; a(n) gives number of different subsets of {1, 2, ..., n-1} whose m is 0.

0, 0, 1, 1, 3, 3, 6, 6, 10, 12, 17, 18, 26, 30, 40, 44, 58, 66, 84, 95, 120, 135, 166, 186, 230, 257, 314, 350, 421, 476, 561, 626, 749, 831, 986, 1095, 1276, 1424, 1666, 1849, 2138, 2388, 2741, 3042, 3522, 3879, 4441, 4928, 5617, 6222, 7084, 7802, 8852, 9800

Offset

1,5

Comments

Note that {2, 3} is counted for n = 6 because although 6 = 2+2+2 = 3+3, there is no partition that includes both 2 and 3. - David Wasserman, Aug 09 2005

Said differently, a(n) is the number of finite nonempty sets of positive integers with sum < n that cannot be linearly combined using all positive coefficients to obtain n. - Gus Wiseman, Sep 10 2023

Links

Table of n, a(n) for n=1..54.

Example

a(5)=3 because there are three different subsets, {2}, {3} & {4}; a(6)=3 because there are three different subsets, {4}, {5} & {2,3}.
From Gus Wiseman, Sep 10 2023: (Start)
The set {3,5} is not counted under a(8) because 1*3 + 1*5 = 8, but it is counted under a(9) and a(10), and it is not counted under a(11) because 2*3 + 1*5 = 11.
The a(3) = 1 through a(11) = 17 subsets:
  {2}  {3}  {2}  {4}    {2}    {3}    {2}    {3}      {2}
            {3}  {5}    {3}    {5}    {4}    {4}      {3}
            {4}  {2,3}  {4}    {6}    {5}    {6}      {4}
                        {5}    {7}    {6}    {7}      {5}
                        {6}    {2,5}  {7}    {8}      {6}
                        {2,4}  {3,4}  {8}    {9}      {7}
                                      {2,4}  {2,5}    {8}
                                      {2,6}  {2,7}    {9}
                                      {3,4}  {3,5}    {10}
                                      {3,5}  {3,6}    {2,4}
                                             {4,5}    {2,6}
                                             {2,3,4}  {2,8}
                                                      {3,6}
                                                      {3,7}
                                                      {4,5}
                                                      {4,6}
                                                      {2,3,5}
(End)

Mathematica

combp[n_, y_]:=With[{s=Table[{k, i}, {k, y}, {i, 1, Floor[n/k]}]}, Select[Tuples[s], Total[Times@@@#]==n&]];
Table[Length[Select[Select[Subsets[Range[n]], 0<Total[#]<n&], combp[n, #]=={}&]], {n, 15}] (* Gus Wiseman, Sep 12 2023 *)

Crossrefs

The complement is A088571, allowing sum n A088314.

For sets with max < n instead of sum < n we have A365045, nonempty A070880.

For nonnegative coefficients we have A365312, complement A365311.

For sets with max <= n we have A365322.

For partitions we have A365323, nonnegative A365378.

A116861 and A364916 count linear combinations of strict partitions.

A326083 and A124506 appear to count combination-free subsets.

Cf. A000009, A326080, A364350, A364534, A365043, A365321, A365380.

Sequence in context: A343481 A237665 A355394 * A363241 A220153 A219627

Adjacent sequences: A088525 A088526 A088527 * A088529 A088530 A088531

Keyword

easy,nonn

Author

Naohiro Nomoto, Nov 16 2003

Extensions

More terms from David Wasserman, Aug 09 2005

Status

approved