A365071 Number of subsets of {1..n} containing n such that no element is a sum of distinct other elements. A variation of non-binary sum-free subsets without re-usable elements.

0, 1, 2, 3, 6, 9, 15, 23, 40, 55, 94, 132, 210, 298, 476, 644, 1038, 1406, 2149, 2965, 4584, 6077, 9426, 12648, 19067, 25739, 38958, 51514, 78459, 104265, 155436, 208329, 312791, 411886, 620780, 823785, 1224414, 1631815, 2437015, 3217077, 4822991

Offset: 0

Author

Gus Wiseman, Aug 26 2023

Keywords

• nonn

Comments

The complement is counted by A365069. The binary version is A364755, complement A364756. For re-usable parts we have A288728, complement A365070.

Examples

			The subset {1,3,4,6} has 4 = 1 + 3 so is not counted under a(6).
The subset {2,3,4,5,6} has 6 = 2 + 4 and 4 = 1 + 3 so is not counted under a(6).
The a(0) = 0 through a(6) = 15 subsets:
  .  {1}  {2}    {3}    {4}      {5}      {6}
          {1,2}  {1,3}  {1,4}    {1,5}    {1,6}
                 {2,3}  {2,4}    {2,5}    {2,6}
                        {3,4}    {3,5}    {3,6}
                        {1,2,4}  {4,5}    {4,6}
                        {2,3,4}  {1,2,5}  {5,6}
                                 {1,3,5}  {1,2,6}
                                 {2,4,5}  {1,3,6}
                                 {3,4,5}  {1,4,6}
                                          {2,3,6}
                                          {2,5,6}
                                          {3,4,6}
                                          {3,5,6}
                                          {4,5,6}
                                          {3,4,5,6}
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 0..85
• Steven R. Finch, Monoids of natural numbers, March 17, 2009.

Crossrefs

First differences of A151897.

The version with re-usable parts is A288728 first differences of A007865.

The binary version is A364755, first differences of A085489.

The binary complement is A364756, first differences of A088809.

The complement is counted by A365069, first differences of A364534.

The complement w/ re-usable parts is A365070, first differences of A093971.

A108917 counts knapsack partitions, strict A275972.

A124506 counts combination-free subsets, differences of A326083.

A364350 counts combination-free strict partitions, complement A364839.

A365046 counts combination-full subsets, differences of A364914.

Partitions: A236912, A237113, A237668, A364532, A364272, A364349, A364913.

Cf. A050291, A095944, A103580, A324741, A326080, A326117, A341507, A364533.

Programs

Mathematica

Table[Length[Select[Subsets[Range[n]], MemberQ[#,n]&&Intersection[#, Total/@Subsets[#,{2,Length[#]}]]=={}&]], {n,0,10}]

Formula

a(n) + A365069(n) = 2^(n-1).

First differences of A151897.

Extensions

a(14) onwards added (using A151897) by Andrew Howroyd, Jan 13 2024