A007767 Number of pairs of permutations of degree n that avoid (12,21).

1, 1, 3, 17, 151, 1899, 31711, 672697, 17551323, 549500451, 20246665349, 864261579999, 42190730051687, 2329965898878307, 144220683681814515, 9926440976428215117, 754465679498026783923, 62939664181821196179459, 5732069150321309755351161, 567176164248814234096702451

Offset

0,3

Comments

A pair of permutations (p,q) of degree n avoid (12,21) if there do not exist indices 1<=i<j<=n such that p_i < p_j and q_j < q_i. - Noam Zeilberger, Jun 06 2016 (via Steve Linton)

Number of intervals (i.e. ordered pairs (x,y) such that x<=y) in the permutation lattice of size n, that is, pairs of permutations (x,y) related by the weak Bruhat order x<=y iff inversions(x) is a subset of inversions(y) (see Hammett and Pittel, p. 4567). - Noam Zeilberger, Jun 01 2016

Links

Andrew Elvey Price, Table of n, a(n) for n = 0..26

Noga Alon, Kirill Rudov, and Leeat Yariv, Dominance Solvability in Random Games, Princeton Univ. (2020).

Noga Alon, Kirill Rudov, and Leeat Yariv, Online Appendix for 'Dominance Solvability in Random Games', Princeton Univ. (2021).

Grégory Chatel, Vincent Pilaud, and Viviane Pons, The weak order on integer posets, arXiv:1701.07995 [math.CO], 2017.

Clément Chenevière, Enumerative study of intervals in lattices of Tamari type, Ph. D. thesis, Univ. Strasbourg (France), Ruhr-Univ. Bochum (Germany), HAL tel-04255439 [math.CO], 2024. See pp. 3, 33, 145.

Joël Gay and Vincent Pilaud, The weak order on Weyl posets, arXiv:1804.06572 [math.CO], 2018.

Benjamin Gunby, Asymptotics of Pattern Avoidance in the Permutation-Tuple and Klazar Set Partition Settings, arXiv:1609.06023 [math.CO], 2017.

Adam Hammett and Boris Pittel, How often are two permutations comparable?, Transactions of the AMS 360:9 (2008), 4541-4568.

Evgeny Kapun, Java program for generating terms a(0)-a(13).

Formula

a(n) = Sum_{k=1..n!} k * A263754(n,k). - Alois P. Heinz, Jun 06 2016

Prog

(Java) See link.

Crossrefs

Cf. A000260, A263754.

Sequence in context: A209305 A182957 A307375 * A075820 A145081 A020562

Adjacent sequences: A007764 A007765 A007766 * A007768 A007769 A007770

Keyword

nonn

Author

Steve Linton

Extensions

a(0)=1 prepended by Alois P. Heinz, Jun 06 2016

a(10)-a(13) from Evgeny Kapun, Dec 11 2016

More terms from Andrew Elvey Price, Feb 08 2024

Status

approved