login
Number of integer partitions of n whose distinct parts are pairwise coprime.
21

%I #15 Nov 02 2019 19:59:11

%S 1,1,2,3,6,7,13,16,23,29,42,49,69,83,102,126,161,191,239,281,336,402,

%T 484,566,672,787,919,1067,1251,1449,1684,1934,2223,2554,2920,3341,

%U 3821,4344,4928,5586,6334,7163,8091,9100,10228,11492,12902,14449,16167,18058

%N Number of integer partitions of n whose distinct parts are pairwise coprime.

%C Two parts are coprime if they have no common divisor greater than 1. For partitions of length 1 note that (1) is coprime but (x) is not coprime for x > 1.

%H Andrew Howroyd, <a href="/A304709/b304709.txt">Table of n, a(n) for n = 1..500</a>

%F a(n) = A304712(n) + 1 - A000005(n). - _Andrew Howroyd_, Nov 02 2019

%e The a(6) = 7 integer partitions of 6 whose distinct parts are pairwise coprime are (51), (411), (321), (3111), (2211), (21111), (111111).

%t Table[Select[IntegerPartitions[n],CoprimeQ@@Union[#]&]//Length,{n,20}]

%o (PARI)

%o lista(nn)={local(Cache=Map());

%o my(excl=vector(nn, n, sum(i=1, n-1, if(gcd(i,n)>1, 2^(n-i)))));

%o my(c(n, m, b)=

%o if(n==0, 1,

%o while(m>n || bittest(b,0), m--; b>>=1);

%o my(hk=[n, m, b], z);

%o if(!mapisdefined(Cache, hk, &z),

%o z = if(m, self()(n, m-1, b>>1) + self()(n-m, m, bitor(b, excl[m])), 0);

%o mapput(Cache, hk, z)); z));

%o my(a(n)=c(n, n, 0) + 1 - numdiv(n));

%o for(n=1, nn, print1(a(n), ", "))

%o } \\ _Andrew Howroyd_, Nov 02 2019

%Y Cf. A000005, A007359, A007360, A018783, A051424, A078374, A101268, A289508, A289509, A302569, A302696, A302698, A302796, A302797, A304711, A304712.

%K nonn

%O 1,3

%A _Gus Wiseman_, May 17 2018