A051839 Number of partitions of n with parts (with repetitions) forming a division lattice (i.e., closed under GCD and LCM).

1, 2, 3, 5, 6, 10, 11, 16, 19, 26, 27, 41, 42, 55, 64, 81, 83, 113, 115, 149, 165, 197, 203, 266, 276, 329, 358, 429, 440, 553, 565, 672, 722, 832, 874, 1060, 1085, 1252, 1342, 1558, 1603, 1901, 1955, 2249, 2410, 2708, 2805, 3287, 3394, 3852, 4078, 4594, 4756, 5456, 5668, 6379, 6738, 7484, 7767, 8884

Offset: 1

Author

John McKay (mckay(AT)cs.concordia.ca), Dec 13 1999

Keywords

• nonn
• nice

Examples

			For n=6, the only one of the 11 partitions of 6 that fails is [3,2,1]; so a(6) = 10.
		

Programs

Maple

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:
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:
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;

Mathematica

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 *)

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
a(n)=my(P=partitions(n));sum(i=1,#P,ok(P[i])) \\ Charles R Greathouse IV, Sep 21 2012

Sage

def A051839(n):
    def closed(P):
        S = Set(iter(P))
        for p in S.subsets(2):
            if not lcm(p) in S or not gcd(p) in S: return false
        return true
    count = 0
    for p in Partitions(n):
        if closed(p): count += 1
    return count
# Peter Luschny, Sep 21 2012

Extensions

More terms from Antonio G. Astudillo (afg_astudillo(AT)lycos.com), Apr 05 2003

a(46)-a(60) from Charles R Greathouse IV, Sep 21 2012