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}.
1, 2, 4, 6, 11, 15, 26, 36, 57, 79, 130, 170, 276, 379, 579, 784, 1249, 1654, 2615, 3515, 5343, 7256, 11352, 14930, 23203, 31378, 47510, 63777, 98680, 130502, 201356, 270037, 407428, 548089, 840170, 1110428, 1701871, 2284324, 3440336, 4601655
Offset: 1
Keywords
Examples
a(4) = 6 because the only permissible subsets are {1}, {2}, {3}, {4}, {2,3}, {3,4}.
From _Gus Wiseman_, Jun 07 2019: (Start)
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:
{1} {1} {1} {1} {1} {1}
{2} {2} {2} {2} {2}
{3} {3} {3} {3}
{2,3} {4} {4} {4}
{2,3} {5} {5}
{3,4} {2,3} {6}
{2,5} {2,3}
{3,4} {2,5}
{3,5} {3,4}
{4,5} {3,5}
{3,4,5} {4,5}
{4,6}
{5,6}
{3,4,5}
{4,5,6}
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:
{1} {2} {2} {3} {3} {4}
{1,2} {3} {4} {4} {5}
{2,3} {2,4} {5} {6}
{1,2,3} {3,4} {2,4} {3,6}
{2,3,4} {3,4} {4,5}
{1,2,3,4} {3,5} {4,6}
{4,5} {5,6}
{2,4,5} {2,4,6}
{3,4,5} {3,4,6}
{2,3,4,5} {3,5,6}
{1,2,3,4,5} {4,5,6}
{2,4,5,6}
{3,4,5,6}
{2,3,4,5,6}
{1,2,3,4,5,6}
(End)
Links
- Fausto A. C. Cariboni, Table of n, a(n) for n = 1..100
- Sergey Kitaev, Independent Sets on Path-Schemes, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.2.
- Sean Li, Counting numerical semigroups by Frobenius number, multiplicity, and depth, arXiv:2208.14587 [math.CO], 2022.
Crossrefs
Programs
-
Mathematica
Table[Length[Select[Subsets[Range[n],{1,n}],SubsetQ[#,Select[Plus@@@Tuples[#,2],#<=n&]]&]],{n,10}] (* Gus Wiseman, Jun 07 2019 *)
Formula
a(n) = A326083(n) - 1. - Gus Wiseman, Jun 07 2019
Extensions
More terms from David Wasserman, Apr 16 2008