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

%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