A276187 - OEIS

%I #29 Sep 15 2022 09:06:14

%S 0,1,4,7,18,21,48,63,94,105,220,235,482,529,600,711,1438,1501,3020,

%T 3211,3594,3849,7720,7975,11142,11877,14628,15459,30946,31201,62432,

%U 69855,76126,80221,89820,91611,183258,192601,208600,214231,428502,431573,863188,900563

%N Number of subsets of {1,..,n} of cardinality >= 2 such that the elements of each counted subset are pairwise coprime.

%C n is prime if and only if a(n) = 2*a(n-1)+n-1. - _Robert Israel_, Aug 24 2016

%H Robert Israel, <a href="/A276187/b276187.txt">Table of n, a(n) for n = 1..340</a>

%F a(n) = A320426(n) - 1. - _Gus Wiseman_, May 08 2021

%e From _Gus Wiseman_, May 08 2021: (Start)

%e The a(2) = 1 through a(6) = 21 sets:

%e   {1,2}   {1,2}    {1,2}     {1,2}      {1,2}

%e           {1,3}    {1,3}     {1,3}      {1,3}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

%e                                        {3,4,5}

%e                                       {1,2,3,5}

%e                                       {1,3,4,5}

%e (End)

%p f:= proc(S) option remember;

%p     local s, Sp;

%p     if S = {} then return 1 fi;

%p     s:= S[-1];

%p     Sp:= S[1..-2];

%p     procname(Sp) + procname(select(t -> igcd(t,s)=1, Sp))

%p end proc:

%p seq(f({$1..n}) - n - 1, n=1..50); # _Robert Israel_, Aug 24 2016

%t f[S_] := f[S] = Module[{s, Sp}, If[S == {}, Return[1]]; s = S[[-1]]; Sp = S[[1;;-2]]; f[Sp] + f[Select[Sp, GCD[#, s] == 1&]]];

%t Table[f[Range[n]] - n - 1, {n, 1, 50}] (* _Jean-François Alcover_, Sep 15 2022, after _Robert Israel_ *)

%o (Sage)

%o from sage.combinat.subsets_pairwise import PairwiseCompatibleSubsets

%o def is_coprime(x, y): return gcd(x, y) == 1

%o max_n = 40

%o seq = []

%o for n in range(1, max_n+1):

%o     P = PairwiseCompatibleSubsets(range(1,n+1), is_coprime)

%o     a_n = len([1 for s in P.list() if len(s) > 1])

%o     seq.append(a_n)

%o print(seq)

%o (PARI) f(n,k=1)=if(n==1, return(2)); if(gcd(k,n)==1, f(n-1,n*k)) + f(n-1,k)

%o a(n)=f(n)-n-1 \\ _Charles R Greathouse IV_, Aug 24 2016

%Y Cf. A000010, A002088, A018805.

%Y The case of pairs is A015614.

%Y The indivisible instead of coprime version is A051026(n) - n.

%Y Allowing empty sets and singletons gives A084422.

%Y The relatively prime instead of pairwise coprime version is A085945(n) - 1.

%Y Allowing all singletons gives A187106.

%Y Allowing only the singleton {1} gives A320426.

%Y Row sums of A320436, each minus one.

%Y The maximal case is counted by A343659.

%Y The version for sets of divisors is A343655(n) - 1.

%Y A000005 counts divisors.

%Y A186972 counts pairwise coprime k-sets containing n.

%Y A186974 counts pairwise coprime k-sets.

%Y A326675 ranks pairwise coprime non-singleton sets.

%Y Cf. A007360, A063647, A186971, A302696, A305713, A320423, A320430, A326077, A327516, A337485.

%K nonn

%O 1,3

%A _Robert C. Lyons_, Aug 23 2016

%E Name and example edited by _Robert Israel_, Aug 24 2016