A093971 -id:A093971 - cp's OEIS frontend

A365069 Number of subsets of {1..n} containing n and some element equal to the sum of two or more distinct other elements. A variation of non-binary sum-full subsets without re-usable elements.

0, 0, 0, 1, 2, 7, 17, 41, 88, 201, 418, 892, 1838, 3798, 7716, 15740

Offset: 0

Gus Wiseman, Aug 26 2023

nonn

The complement is counted by A365071. The binary case is A364756. Allowing elements to be re-used gives A365070. A version for partitions (but not requiring n) is A237668.

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

Steven R. Finch, Monoids of natural numbers, March 17, 2009.

The complement w/ re-usable parts is A288728, first differences of A007865.
First differences of A364534.
The binary complement is A364755, first differences of A085489.
The binary version is A364756, first differences of A088809.
The version with re-usable parts is A365070, first differences of A093971.
The complement is counted by A365071, first differences of A151897.
A124506 counts nonnegative combination-free subsets, differences of A326083.
A365046 counts nonnegative combination-full subsets, differences of A364914.
For partitions: A108917, A236912, A237113, A237668, A364532, A364913.
Strict partitions: A116861, A364272, A364349, A364350, A364839, A364916.
Cf. A050291, A326080, A363226, A364346, A364348, A364670.

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

a(n) = 2^(n-1) - A365070(n).

First differences of A364534.

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.

Original entry on oeis.org

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

Gus Wiseman, Aug 26 2023

nonn

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

			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}

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

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.

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

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

First differences of A151897.

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

A366131 Number of subsets of {1..n} with two elements (possibly the same) summing to n.

Original entry on oeis.org

0, 0, 2, 2, 10, 14, 46, 74, 202, 350, 862, 1562, 3610, 6734, 14926, 28394, 61162, 117950, 249022, 484922, 1009210, 1979054, 4076206, 8034314, 16422922, 32491550, 66045982, 131029082, 265246810, 527304974, 1064175886, 2118785834, 4266269482, 8503841150, 17093775742, 34101458042, 68461196410, 136664112494

Offset: 0

Gus Wiseman, Oct 07 2023

			The a(0) = 0 through a(5) = 14 subsets:
  .  .  {1}    {1,2}    {2}        {1,4}
        {1,2}  {1,2,3}  {1,2}      {2,3}
                        {1,3}      {1,2,3}
                        {2,3}      {1,2,4}
                        {2,4}      {1,3,4}
                        {1,2,3}    {1,4,5}
                        {1,2,4}    {2,3,4}
                        {1,3,4}    {2,3,5}
                        {2,3,4}    {1,2,3,4}
                        {1,2,3,4}  {1,2,3,5}
                                   {1,2,4,5}
                                   {1,3,4,5}
                                   {2,3,4,5}
                                   {1,2,3,4,5}

Index entries for linear recurrences with constant coefficients, signature (2,3,-6).

The complement is counted by A117855.
For pairs summing to n + 1 we have A167936.
A068911 counts subsets of {1..n} w/o two distinct elements summing to n.
A093971/A088809/A364534 count certain types of sum-full subsets.
Cf. A008967, A167762, A238628, A365376, A365377, A365381, A365541, A365544.

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

def A366131(n): return (1<>1)<<1) if n else 0 # Chai Wah Wu, Nov 14 2023

From Chai Wah Wu, Nov 14 2023: (Start)
a(n) = 2*a(n-1) + 3*a(n-2) - 6*a(n-3) for n > 3.
G.f.: 2*x^2*(1 - x)/((2*x - 1)*(3*x^2 - 1)). (End)

A366130 Number of subsets of {1..n} with a subset summing to n + 1.

Original entry on oeis.org

0, 0, 1, 2, 7, 15, 38, 79, 184, 378, 823, 1682, 3552, 7208, 14948, 30154, 61698, 124302, 252125, 506521, 1022768, 2051555, 4127633, 8272147, 16607469, 33258510, 66680774, 133467385, 267349211, 535007304, 1071020315, 2142778192, 4288207796

Offset: 0

Gus Wiseman, Oct 07 2023

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

For pairs summing to n + 1 we have A167762, complement A038754.
For n instead of n + 1 we have A365376, for pairs summing to n A365544.
The complement is counted by A365377 shifted.
The complement for pairs summing to n is counted by A365377.
A068911 counts subsets of {1..n} w/o two distinct elements summing to n.
A093971/A088809/A364534 count certain types of sum-full subsets.
Cf. A004526, A004737, A008967, A046663, A238628, A365381, A365541.

Table[Length[Select[Subsets[Range[n]],MemberQ[Total/@Subsets[#],n+1]&]],{n,0,10}]

from itertools import combinations
from sympy.utilities.iterables import partitions
def A366130(n):
    a = tuple(set(p.keys()) for p in partitions(n+1,k=n) if max(p.values(),default=0)==1)
    return sum(1 for k in range(2,n+1) for w in (set(d) for d in combinations(range(1,n+1),k)) if any(s<=w for s in a)) # Chai Wah Wu, Nov 24 2023

Diagonal k = n + 1 of A365381.

a(20)-a(32) from Chai Wah Wu, Nov 24 2023

cp's OEIS Frontend

A365069 Number of subsets of {1..n} containing n and some element equal to the sum of two or more distinct other elements. A variation of non-binary sum-full subsets without re-usable elements.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A366131 Number of subsets of {1..n} with two elements (possibly the same) summing to n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Python

Formula

A366130 Number of subsets of {1..n} with a subset summing to n + 1.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Python

Formula

Extensions