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
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