login
A007767
Number of pairs of permutations of degree n that avoid (12,21).
4
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.
Adam Hammett and Boris Pittel, How often are two permutations comparable?, Transactions of the AMS 360:9 (2008), 4541-4568.
FORMULA
a(n) = Sum_{k=1..n!} k * A263754(n,k). - Alois P. Heinz, Jun 06 2016
PROG
(Java) See link.
CROSSREFS
Sequence in context: A209305 A182957 A307375 * A075820 A145081 A020562
KEYWORD
nonn
AUTHOR
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