cp's OEIS Frontend

A103580 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}.

%I A103580 #30 Sep 10 2022 01:50:01
%S A103580 1,2,4,6,11,15,26,36,57,79,130,170,276,379,579,784,1249,1654,2615,
%T A103580 3515,5343,7256,11352,14930,23203,31378,47510,63777,98680,130502,
%U A103580 201356,270037,407428,548089,840170,1110428,1701871,2284324,3440336,4601655
%N A103580 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 A103580 Fausto A. C. Cariboni, <a href="/A103580/b103580.txt">Table of n, a(n) for n = 1..100</a>
%H A103580 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 A103580 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 A103580 a(n) = A326083(n) - 1. - _Gus Wiseman_, Jun 07 2019
%e A103580 a(4) = 6 because the only permissible subsets are {1}, {2}, {3}, {4}, {2,3}, {3,4}.
%e A103580 From _Gus Wiseman_, Jun 07 2019: (Start)
%e A103580 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 A103580   {1}  {1}  {1}    {1}    {1}      {1}
%e A103580        {2}  {2}    {2}    {2}      {2}
%e A103580             {3}    {3}    {3}      {3}
%e A103580             {2,3}  {4}    {4}      {4}
%e A103580                    {2,3}  {5}      {5}
%e A103580                    {3,4}  {2,3}    {6}
%e A103580                           {2,5}    {2,3}
%e A103580                           {3,4}    {2,5}
%e A103580                           {3,5}    {3,4}
%e A103580                           {4,5}    {3,5}
%e A103580                           {3,4,5}  {4,5}
%e A103580                                    {4,6}
%e A103580                                    {5,6}
%e A103580                                    {3,4,5}
%e A103580                                    {4,5,6}
%e A103580 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 A103580   {1}  {2}    {2}      {3}        {3}          {4}
%e A103580        {1,2}  {3}      {4}        {4}          {5}
%e A103580               {2,3}    {2,4}      {5}          {6}
%e A103580               {1,2,3}  {3,4}      {2,4}        {3,6}
%e A103580                        {2,3,4}    {3,4}        {4,5}
%e A103580                        {1,2,3,4}  {3,5}        {4,6}
%e A103580                                   {4,5}        {5,6}
%e A103580                                   {2,4,5}      {2,4,6}
%e A103580                                   {3,4,5}      {3,4,6}
%e A103580                                   {2,3,4,5}    {3,5,6}
%e A103580                                   {1,2,3,4,5}  {4,5,6}
%e A103580                                                {2,4,5,6}
%e A103580                                                {3,4,5,6}
%e A103580                                                {2,3,4,5,6}
%e A103580                                                {1,2,3,4,5,6}
%e A103580 (End)
%t A103580 Table[Length[Select[Subsets[Range[n],{1,n}],SubsetQ[#,Select[Plus@@@Tuples[#,2],#<=n&]]&]],{n,10}] (* _Gus Wiseman_, Jun 07 2019 *)
%Y A103580 Cf. A007865, A050291, A051026, A085489, A139384, A151897, A308546.
%Y A103580 Cf. A326020, A326076, A326080, A326083, A326114.
%K A103580 nonn
%O A103580 1,2
%A A103580 _Jeffrey Shallit_, Mar 23 2005
%E A103580 More terms from _David Wasserman_, Apr 16 2008