A260700 Number of distinct parabolic double cosets of the symmetric group S_n.

1, 3, 19, 167, 1791, 22715, 334031, 5597524, 105351108, 2200768698, 50533675542, 1265155704413, 34300156146805, 1001152439025205, 31301382564128969, 1043692244938401836, 36969440518414369896, 1386377072447199902576, 54872494774746771827248, 2285943548113541477123970

Offset

1,2

Comments

This is closely related to the number of contingency tables on n elements (see A120733), but many contingency tables correspond to the same parabolic double coset, e.g., for n=2, there are 5 contingency tables, but only 3 distinct cosets.

Links

Thomas Browning, Table of n, a(n) for n = 1..400

Sara Billey, Matjaz Konvalinka, T. Kyle Petersen, William Slofstra, and Bridget Tenner, Parabolic double cosets in Coxeter groups, Discrete Mathematics and Theoretical Computer Science, Submitted, 2016.

Sara Billey, Matjaz Konvalinka, T. Kyle Petersen, William Slofstra, and Bridget Tenner, Parabolic double cosets in Coxeter groups, Electron. J. Combin., Volume 25, Issue 1 (2018) P1.23.

Thomas Browning, Counting Parabolic Double Cosets in Symmetric Groups, arXiv:2010.13256 [math.CO], 2020.

Masato Kobayashi, Construction of double coset system of a Coxeter group and its applications to Bruhat graphs, arXiv:1907.11801 [math.CO], 2019.

Formula

a(n) is asymptotic to n! / (2^(log(2)/2 + 2) * log(2)^(2*n + 2)). [Conjectured Vaclav Kotesovec Sep 08 2020, proved Thomas Browning Oct 26 2020]

Example

For n=2, there are three parabolic double cosets: {12}, {21}, and {12, 21}.

Crossrefs

Cf. A120733.

Sequence in context: A256710 A215093 A201123 * A105624 A238640 A349253

Adjacent sequences: A260697 A260698 A260699 * A260701 A260702 A260703

Keyword

nonn

Author

Kyle Petersen, Nov 16 2015

Extensions

More terms from Thomas Browning, Sep 07 2020

Status

approved