login
Number of partitions of n into parts having a common factor.
68

%I #30 Jan 20 2018 17:27:54

%S 0,0,1,1,2,1,4,1,5,3,8,1,14,1,16,9,22,1,38,1,45,17,57,1,94,7,102,30,

%T 138,1,218,1,231,58,298,21,451,1,491,103,644,1,919,1,1005,203,1256,1,

%U 1784,15,1993,299,2439,1,3365,62,3735,492,4566,1,6252,1,6843,819,8349,107,11096

%N Number of partitions of n into parts having a common factor.

%H Alois P. Heinz, <a href="/A018783/b018783.txt">Table of n, a(n) for n = 0..10000</a>

%H L. Naughton, G. Pfeiffer, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL16/Naughton/naughton2.html">Integer Sequences Realized by the Subgroup Pattern of the Symmetric Group</a>, J. Int. Seq. 16 (2013) #13.5.8

%F a(n) = -Sum_{d|n, d<n} moebius(n/d)*A000041(d) = A000041(n) - A000837(n). - _Vladeta Jovovic_, Jun 17 2003

%p with(numtheory): with(combinat):

%p a:= n-> `if`(n=0, 0,

%p numbpart(n) -add(mobius(n/d)*numbpart(d), d=divisors(n))):

%p seq(a(n), n=0..100); # _Alois P. Heinz_, Nov 29 2011

%t A000837[n_] := Sum[ MoebiusMu[n/d]*PartitionsP[d], {d, Divisors[n]}]; a[0] = 0; a[n_] := PartitionsP[n] - A000837[n]; Table[a[n], {n, 0, 66}] (* _Jean-François Alcover_, Oct 03 2013, after _Vladeta Jovovic_ *)

%o (PARI) a(n) = - sumdiv(n, d, (d<n)*moebius(n/d)*numbpart(d)); \\ _Michel Marcus_, Oct 07 2017

%Y Cf. A000041, A000837, A083710.

%K nonn

%O 0,5

%A _David W. Wilson_