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,2

Links

Table of n, a(n) for n=1..60.

Example

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

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

Prog

(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

Crossrefs

Sequence in context: A298363 A018396 A003238 * A130714 A130689 A024560

Adjacent sequences: A051836 A051837 A051838 * A051840 A051841 A051842

Keyword

nonn,nice

Author

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

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

Status

approved