%I #23 Aug 03 2017 00:56:52
%S 1,2,3,5,6,10,11,16,19,26,27,41,42,55,64,81,83,113,115,149,165,197,
%T 203,266,276,329,358,429,440,553,565,672,722,832,874,1060,1085,1252,
%U 1342,1558,1603,1901,1955,2249,2410,2708,2805,3287,3394,3852,4078,4594,4756,5456,5668,6379,6738,7484,7767,8884
%N Number of partitions of n with parts (with repetitions) forming a division lattice (i.e., closed under GCD and LCM).
%e For n=6, the only one of the 11 partitions of 6 that fails is [3,2,1]; so a(6) = 10.
%p with(combinat): ans := []: b := []: for n to 30 do p := partition(n): np := nops(p): nn := np: print(n); for i to np do ss := convert(p[i],set):s := convert(ss,list): ns := nops(s): t := true:
%p for j to ns-1 do for k from j+1 to ns do if evalb(not(member(gcd(s[j],s[k]),s)) or not(member(lcm(s[j],s[k]),s))) then t := false: fi: od: od:
%p if t=false then nn := nn-1:fi od: ans := [op(ans),[n,np,nn]]: b := [op(b),[nn]]: od: print(ans); print(b); save b,ans,bans;
%t ok[partition_] := Module[{p = Flatten[ If[ Length[#] > 2, Take[#, 2], #] & /@ Split[partition]], m}, m = Length[p]; Do[ If[ ! MemberQ[p, GCD[p[[i]], p[[j]]]] || ! MemberQ[p, LCM[p[[i]], p[[j]]]], Return[False]], {i, 1, m-1}, {j, i+1, m}] =!= False]; a[n_] := Length[ Select[ IntegerPartitions[n], ok]]; Table[an = a[n]; Print[an]; an, {n, 1, 60}] (* _Jean-François Alcover_, Sep 21 2012 *)
%o (PARI) ok(v)=v=vecsort(Vec(v),,8); for(i=if(v[1]==1,2,1),#v-1,for(j=i+1,#v, if(!vecsearch(v, gcd(v[i],v[j])) || !vecsearch(v,lcm(v[i],v[j])), return(0))));1
%o a(n)=my(P=partitions(n));sum(i=1,#P,ok(P[i])) \\ _Charles R Greathouse IV_, Sep 21 2012
%o (Sage)
%o def A051839(n):
%o def closed(P):
%o S = Set(iter(P))
%o for p in S.subsets(2):
%o if not lcm(p) in S or not gcd(p) in S: return false
%o return true
%o count = 0
%o for p in Partitions(n):
%o if closed(p): count += 1
%o return count
%o # _Peter Luschny_, Sep 21 2012
%K nonn,nice
%O 1,2
%A John McKay (mckay(AT)cs.concordia.ca), Dec 13 1999
%E More terms from Antonio G. Astudillo (afg_astudillo(AT)lycos.com), Apr 05 2003
%E a(46)-a(60) from _Charles R Greathouse IV_, Sep 21 2012