A103580 - OEIS

%I #30 Sep 10 2022 01:50:01

%S 1,2,4,6,11,15,26,36,57,79,130,170,276,379,579,784,1249,1654,2615,

%T 3515,5343,7256,11352,14930,23203,31378,47510,63777,98680,130502,

%U 201356,270037,407428,548089,840170,1110428,1701871,2284324,3440336,4601655

%N Number of nonempty subsets S of {1,2,3,...,n} that have the property that no element x of S is a nonnegative integer linear combination of elements of S-{x}.

%H Fausto A. C. Cariboni, <a href="/A103580/b103580.txt">Table of n, a(n) for n = 1..100</a>

%H Sergey Kitaev, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL9/Kitaev/kitaev45.html">Independent Sets on Path-Schemes</a>, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.2.

%H Sean Li, <a href="https://arxiv.org/abs/2208.14587">Counting numerical semigroups by Frobenius number, multiplicity, and depth</a>, arXiv:2208.14587 [math.CO], 2022.

%F a(n) = A326083(n) - 1. - _Gus Wiseman_, Jun 07 2019

%e a(4) = 6 because the only permissible subsets are {1}, {2}, {3}, {4}, {2,3}, {3,4}.

%e From _Gus Wiseman_, Jun 07 2019: (Start)

%e The a(1) = 1 through a(6) = 15 nonempty subsets of {1..n} containing none of their own non-singleton nonzero nonnegative linear combinations are:

%e   {1}  {1}  {1}    {1}    {1}      {1}

%e        {2}  {2}    {2}    {2}      {2}

%e             {3}    {3}    {3}      {3}

%e             {2,3}  {4}    {4}      {4}

%e                    {2,3}  {5}      {5}

%e                    {3,4}  {2,3}    {6}

%e                           {2,5}    {2,3}

%e                           {3,4}    {2,5}

%e                           {3,5}    {3,4}

%e                           {4,5}    {3,5}

%e                           {3,4,5}  {4,5}

%e                                    {4,6}

%e                                    {5,6}

%e                                    {3,4,5}

%e                                    {4,5,6}

%e a(n) is also the number of nonempty subsets of {1..n} containing all of their own nonzero nonnegative linear combinations <= n. For example the a(1) = 1 through a(6) = 15 subsets are:

%e   {1}  {2}    {2}      {3}        {3}          {4}

%e        {1,2}  {3}      {4}        {4}          {5}

%e               {2,3}    {2,4}      {5}          {6}

%e               {1,2,3}  {3,4}      {2,4}        {3,6}

%e                        {2,3,4}    {3,4}        {4,5}

%e                        {1,2,3,4}  {3,5}        {4,6}

%e                                   {4,5}        {5,6}

%e                                   {2,4,5}      {2,4,6}

%e                                   {3,4,5}      {3,4,6}

%e                                   {2,3,4,5}    {3,5,6}

%e                                   {1,2,3,4,5}  {4,5,6}

%e                                                {2,4,5,6}

%e                                                {3,4,5,6}

%e                                                {2,3,4,5,6}

%e                                                {1,2,3,4,5,6}

%e (End)

%t Table[Length[Select[Subsets[Range[n],{1,n}],SubsetQ[#,Select[Plus@@@Tuples[#,2],#<=n&]]&]],{n,10}] (* _Gus Wiseman_, Jun 07 2019 *)

%Y Cf. A007865, A050291, A051026, A085489, A139384, A151897, A308546.

%Y Cf. A326020, A326076, A326080, A326083, A326114.

%K nonn

%O 1,2

%A _Jeffrey Shallit_, Mar 23 2005

%E More terms from _David Wasserman_, Apr 16 2008