This site is supported by donations to The OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A114717 Number of linear extensions of the divisor lattice of n. 12
 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 5, 1, 2, 2, 1, 1, 5, 1, 5, 2, 2, 1, 14, 1, 2, 1, 5, 1, 48, 1, 1, 2, 2, 2, 42, 1, 2, 2, 14, 1, 48, 1, 5, 5, 2, 1, 42, 1, 5, 2, 5, 1, 14, 2, 14, 2, 2, 1, 2452, 1, 2, 5, 1, 2, 48, 1, 5, 2, 48, 1, 462, 1, 2, 5, 5, 2, 48, 1, 42, 1, 2, 1, 2452, 2, 2, 2, 14, 1, 2452, 2 (list; graph; refs; listen; history; text; internal format)
 OFFSET 1,6 COMMENTS Notice that only the powers of the primes determine a(n), so a(12) = a(75) = 5. For prime powers, the lattice is a chain, so there is 1 linear extension. a(p^1*q^n) = A000108(n+1), the Catalan numbers. Alternatively, the number of ways to arrange the divisors of n in such a way that no divisor has any of its own divisors following it. E.g. for 12, the following five arrangements are possible: 1,2,3,4,6,12; 1,2,3,6,4,12; 1,2,4,3,6,12; 1,3,2,4,6,12 and 1,3,2,6,4,12. But 1,2,6,4,3,12 is not possible because 3 divides 6 but follows it. Thus a(12)=5. - Antti Karttunen, Jan 11 2006 For n = p1^r1 * p2^r2, the lattice is a grid (r1+1)*(r2+1), whose linear extensions are counted by ((r1+1)(r2+1))!/Product[(r1+1+k)!/k!,{k,0,r2}]. Cf. A060854. REFERENCES Brightwell, Graham and Winkler, Peter, Counting linear extensions. Order 8 (1991), no. 3, 225-242. Pruesse, Gary and Ruskey, Frank, Generating linear extensions fast, SIAM J.Comput.23 (1994), no. 2, 373-386. Stanley, R., Enumerative Combinatorics, Vol. 2, Proposition 7.10.3 and Vol. 1, Sec 3.5 Chains in Distributive Lattices. LINKS Alois P. Heinz, Table of n, a(n) for n = 1..10000 MAPLE with(numtheory): b:= proc(s) option remember;       `if`(nops(s)<2, 1, add(`if`(nops(select(y->        irem(y, x)=0, s))=1, b(s minus {x}), 0), x=s))     end: a:= proc(n) local l, m;       l:= sort(ifactors(n)[2], (x, y)-> x[2]>y[2]);       m:= mul(ithprime(i)^l[i][2], i=1..nops(l));       b(divisors(m) minus {1, m})     end: seq(a(n), n=1..100);  # Alois P. Heinz, Jun 29 2012 MATHEMATICA b[s_List] := b[s] = If[Length[s]<2, 1, Sum[If[Length[Select[s, Mod[#, x] == 0 &]] == 1, b[Complement[s, {x}]], 0], {x, s}]]; a[n_] := Module[{l, m}, l = Sort[ FactorInteger[n], #1[[2]] > #2[[2]] &]; m = Product[Prime[i]^l[[i]][[2]], {i, 1, Length[l]}]; b[Divisors[m] // Rest // Most]]; Table[a[n], {n, 1, 100}] (* Jean-François Alcover, May 28 2015, after Alois P. Heinz *) CROSSREFS Cf. A060854, A114714, A114715, A114716, A119842. Sequence in context: A009191 A229969 A260909 * A080388 A104308 A175456 Adjacent sequences:  A114714 A114715 A114716 * A114718 A114719 A114720 KEYWORD nonn,hard AUTHOR Mitch Harris and Antti Karttunen, Dec 27, 2005 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified August 16 19:19 EDT 2018. Contains 313809 sequences. (Running on oeis4.)