|
| |
|
|
A114717
|
|
Number of linear extensions of the divisor lattice of n.
|
|
9
| |
|
|
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; 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 (His-Firstname.His-Surname(AT)gmail.com), 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.
|
|
|
CROSSREFS
| Cf. A060854, A114714, A114715, A114716.
Sequence in context: A159269 A186728 A009191 * A080388 A104308 A175456
Adjacent sequences: A114714 A114715 A114716 * A114718 A114719 A114720
|
|
|
KEYWORD
| nonn,hard
|
|
|
AUTHOR
| Mitch Harris (Harris.Mitchell (AT) mgh.harvard.edu) and Antti Karttunen (His-Firstname.His-Surname(AT)gmail.com), Dec 27, 2005
|
| |
|
|
