login
A293153
Number of linear extensions of a certain poset C^bar_n.
1
1, 2, 12, 150, 3192, 103050, 4686660, 285159966, 22346336880, 2190484006290, 262452778322940, 37721725955429670, 6403456745121882600, 1267187306764190765850, 289083710604023135810100, 75296935345163706056184750, 22204989048146847440246995680, 7359190013115437279346917463330
OFFSET
0,2
COMMENTS
Exercise 12 of Morales et al. says that a(n) is the number of permutations (a_1,...,a_n,b_1,...b_n) in S_{2n} such that a_i < b_j for all 1 <= i < j <= n.
This is also the number of permutations in the interval [id, (2*n,n,2*n-1,n-1,...,n+1,1)] in the weak Bruhat order of permutations. - Alejandro H. Morales, Aug 20 2024
LINKS
C. Gaetz and Y. Gao, Separable elements in splittings of Weyl groups, Advances in Mathematics, 374 (2020), 107389. See proof of Theorem 6.
Alejandro H. Morales, I. Pak, and G. Panova, Why is pi < 2 phi?, Preprint, 2016; Why Is Pi Less Than Twice Phi?, The American Mathematical Monthly, 125 (2018), 715-723. See Exercise 12 and Open Problem 16. Beware of the erroneous a(5).
PROG
(Rust)
use permutator::heap_permutation;
fn main() {
for n in 1..=7 {
let mut c = 0;
heap_permutation(&mut Vec::from_iter(0..2*n), |p| c += ok(p, n) as u64);
println!("{c}");
}
}
fn ok(p: &[usize], n: usize) -> bool {
for i in 0..n {
for j in i+1..n {
if p[i] > p[n+j] {
return false
}
}
}
true
} // Andrey Zabolotskiy, Aug 06 2024
CROSSREFS
Cf. A010050.
Sequence in context: A289987 A105558 A322399 * A375233 A374869 A340026
KEYWORD
nonn
AUTHOR
N. J. A. Sloane, Oct 09 2017
EXTENSIONS
Edited, corrected and extended by Andrey Zabolotskiy, Aug 06 2024
a(0)=1 prepended and a(8)-a(17) added by Alois P. Heinz, Aug 06 2024
STATUS
approved