1,6

The singleton and the all-ones partitions are ignored, so that a(n)=0 if n is prime. If a partition is listed as m_1^am_2^bm_3^c..., then it is counted exactly when gcd(a,b,c,...)>1. These are equinumerous (conjugate) with those partitions for which gcd(m_1,m_2,...)>1 (less 1, the singleton), hence the formula.

a(n) = A018783(n)-1, n>1. - Vladeta Jovovic, Jul 28 2005

a(25) = 6: 1^(15)2^5 = 5{1, 1, 1, 2}, 1^52^(10) = 5{1, 2, 2}, 1^(10)3^5 = 5{3, 1, 1}, 2^53^5 = 5{3, 2}, 1^44^4 = 5{4, 1}, 5^5 = 5{5}.

Note that A000041(25)=P(25)=1958, only 6 of which satisfy the criterion.

with(combinat):PartMulti:=proc(n::nonnegint) local count, a, i, j, b, m, k, part_vec;

bigcount:=0; if isprime(n) then return(bigcount) else ps:=partition(n); b:=nops(ps);

for m from 2 to b-1 do p:=ps[m]; a:=nops(p); part_vec:=array(1..n);

for k from 1 to n do part_vec[k]:=0 od;

for i from 1 to a do j:=p[i]; part_vec[j]:=part_vec[j]+1 od;

g:=0; for j from 1 to n do g:=igcd(g, part_vec[j]) od;

if g>1 then bigcount:=bigcount+1 fi od; return(bigcount) end if end proc;

seq(PartMulti(q), q=1..49);

Table[Length[Select[IntegerPartitions[n], And[Length[#]<n, GCD@@Length/@Split[#]>1]&]], {n, 20}] (* Gus Wiseman, Dec 06 2018 *)

Cf. A000837, A018783, A047966, A100953, A303386, A303547, A303553, A319149, A319162, A319164, A319810.

Sequence in context: A152770 A098601 A113486 * A322335 A389281 A245907

Adjacent sequences: A108569 A108570 A108571 * A108573 A108574 A108575

Len Smiley, Jul 25 2005

More terms from Gus Wiseman, Dec 06 2018

approved