|
Search: id:A114717
|
|
|
| A114717 |
|
Number of linear extensions of the divisor lattice of n. |
|
+0
10
|
|
| 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; listen)
|
|
|
OFFSET
|
1,6
|
|
|
COMMENT
|
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: A051119 A159269 A009191 this_sequence A080388 A104308 A122377
Adjacent sequences: A114714 A114715 A114716 this_sequence 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
|
|
|
Search completed in 0.002 seconds
|
