login
A326116
Number of subsets of {2..n} containing no products of two or more distinct elements.
8
1, 2, 4, 8, 16, 28, 56, 100, 200, 364, 728, 1232, 2464, 4592, 8296, 15920, 31840, 55952, 111904, 195712, 362336, 697360, 1394720, 2334112, 4668224, 9095392, 17225312, 31242784, 62485568, 106668608, 213337216, 392606528, 755131840, 1491146912, 2727555424, 4947175712
OFFSET
1,2
COMMENTS
First differs from A308542 at a(12) = 1232, A308542(12) = 1184.
If this sequence counts product-free sets, A308542 counts product-closed sets.
LINKS
Fausto A. C. Cariboni, Table of n, a(n) for n = 1..47
FORMULA
For n > 0, a(n) = A326117(n) - 1.
EXAMPLE
The a(6) = 28 subsets:
{} {2} {2,3} {2,3,4} {2,3,4,5}
{3} {2,4} {2,3,5} {2,4,5,6}
{4} {2,5} {2,4,5} {3,4,5,6}
{5} {2,6} {2,4,6}
{6} {3,4} {2,5,6}
{3,5} {3,4,5}
{3,6} {3,4,6}
{4,5} {3,5,6}
{4,6} {4,5,6}
{5,6}
MATHEMATICA
Table[Length[Select[Subsets[Range[2, n]], Intersection[#, Select[Times@@@Subsets[#, {2}], #<=n&]]=={}&]], {n, 10}]
PROG
(PARI)
a(n)={
my(recurse(k, ep)=
if(k > n, 1,
my(t = self()(k + 1, ep));
if(!bittest(ep, k),
forstep(i=n\k, 1, -1, if(bittest(ep, i), ep=bitor(ep, 1<<(k*i))));
t += self()(k + 1, ep);
);
t);
);
recurse(2, 2);
} \\ Andrew Howroyd, Aug 25 2019
KEYWORD
nonn
AUTHOR
Gus Wiseman, Jun 06 2019
EXTENSIONS
Terms a(21)-a(36) from Andrew Howroyd, Aug 25 2019
STATUS
approved