A293153 - OEIS

%I #34 Aug 21 2024 05:45:56

%S 1,2,12,150,3192,103050,4686660,285159966,22346336880,2190484006290,

%T 262452778322940,37721725955429670,6403456745121882600,

%U 1267187306764190765850,289083710604023135810100,75296935345163706056184750,22204989048146847440246995680,7359190013115437279346917463330

%N Number of linear extensions of a certain poset C^bar_n.

%C 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.

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

%H C. Gaetz and Y. Gao, <a href="https://doi.org/10.1016/j.aim.2020.107389">Separable elements in splittings of Weyl groups</a>, Advances in Mathematics, 374 (2020), 107389. See proof of Theorem 6.

%H Alejandro H. Morales, I. Pak, and G. Panova, <a href="https://www.math.ucla.edu/~pak/papers/EulerFib4-journal.pdf">Why is pi < 2 phi?</a>, Preprint, 2016; <a href="https://doi.org/10.1080/00029890.2018.1496757">Why Is Pi Less Than Twice Phi?</a>, The American Mathematical Monthly, 125 (2018), 715-723. See Exercise 12 and Open Problem 16. Beware of the erroneous a(5).

%o (Rust)

%o use permutator::heap_permutation;

%o fn main() {

%o     for n in 1..=7 {

%o         let mut c = 0;

%o         heap_permutation(&mut Vec::from_iter(0..2*n), |p| c += ok(p, n) as u64);

%o         println!("{c}");

%o     }

%o }

%o fn ok(p: &[usize], n: usize) -> bool {

%o     for i in 0..n {

%o         for j in i+1..n {

%o             if p[i] > p[n+j] {

%o                 return false

%o             }

%o         }

%o     }

%o     true

%o } // _Andrey Zabolotskiy_, Aug 06 2024

%Y Cf. A010050.

%K nonn

%O 0,2

%A _N. J. A. Sloane_, Oct 09 2017

%E Edited, corrected and extended by _Andrey Zabolotskiy_, Aug 06 2024

%E a(0)=1 prepended and a(8)-a(17) added by _Alois P. Heinz_, Aug 06 2024