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

Author

Kyle Petersen, Nov 16 2015

Keywords

• nonn

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.

Examples

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

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.

Crossrefs

Cf. A120733.

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]

Extensions

More terms from Thomas Browning, Sep 07 2020