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

Author

Steve Linton

Keywords

• nonn

Comments

A pair of permutations (p,q) of degree n avoid (12,21) if there do not exist indices 1<=iNoam 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).

Crossrefs

Cf. A000260, A263754.

Programs

Java

// See Kapun link.

Formula

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

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