|
See also A000375, which is the main entry for this problem.
Comments from Joshua Zucker (joshua.zucker(AT)gmail.com), Jan 24 2007: (Start)
For some n, there are some longest chains which end up sorted and some which don't, like n = 6, with the following four chains that end sorted and one that does not:
The examples below use 0 through n-1 instead of 1 through n.
((#(4 5 3 0 2 1) #(2 0 3 5 4 1) #(3 0 2 5 4 1) #(5 2 0 3 4 1) #(1 4 3 0 2 5) #(4 1 3 0 2 5) #(2 0 3 1 4 5) #(3 0 2 1 4 5) #(1 2 0 3 4 5) #(2 1 0 3 4 5) #(0 1 2 3 4 5))
(#(3 4 5 1 0 2) #(1 5 4 3 0 2) #(5 1 4 3 0 2) #(2 0 3 4 1 5) #(3 0 2 4 1 5) #(4 2 0 3 1 5) #(1 3 0 2 4 5) #(3 1 0 2 4 5) #(2 0 1 3 4 5) #(1 0 2 3 4 5) #(0 1 2 3 4 5))
(#(3 0 4 1 5 2) #(1 4 0 3 5 2) #(4 1 0 3 5 2) #(5 3 0 1 4 2) #(2 4 1 0 3 5) #(1 4 2 0 3 5) #(4 1 2 0 3 5) #(3 0 2 1 4 5) #(1 2 0 3 4 5) #(2 1 0 3 4 5) #(0 1 2 3 4 5))
(#(2 5 4 0 3 1) #(4 5 2 0 3 1) #(3 0 2 5 4 1) #(5 2 0 3 4 1) #(1 4 3 0 2 5) #(4 1 3 0 2 5) #(2 0 3 1 4 5) #(3 0 2 1 4 5) #(1 2 0 3 4 5) #(2 1 0 3 4 5) #(0 1 2 3 4 5)))
(#(3 0 5 4 1 2) #(4 5 0 3 1 2) #(1 3 0 5 4 2) #(3 1 0 5 4 2) #(5 0 1 3 4 2) #(2 4 3 1 0 5) #(3 4 2 1 0 5) #(1 2 4 3 0 5) #(2 1 4 3 0 5) #(4 1 2 3 0 5) #(0 3 2 1 4 5))
And for some n, e.g. n=12, none of the longest chains end up sorted (and hence A000375 and A000376 are different). I did an exhaustive search with n = 12 working backwards from sorted and found 63 as the longest chain beginning with one of these four:
#(9 10 6 0 2 7 1 8 11 5 3 4)
#(9 10 6 0 1 2 7 8 11 5 3 4)
#(7 8 11 5 0 6 10 9 2 1 3 4)
#(5 0 1 7 10 3 11 8 9 6 2 4)
But 65 is attainable if you don't assume it ends up sorted. (End)
| 