A337083 Number of spanning trees of the 1-skeleton of the (n-1)-dimensional permutohedron.

1, 1, 6, 101154816, 6187732257761496793412385090375984958331031826464768000000000

Offset: 1

Author

Richard Stanley, Aug 14 2020

Keywords

• nonn

Comments

We have the factorizations:

a(4) = 2^15 * 3^2 * 7^3.

a(5) = 2^59 * 3^15 * 5^9 * 7^5 * 11^6 * 23^5 * 29^4 * 41^4.

a(6) = 2^215 * 3^178 * 5^47 * 7^15 * 11^39 * 13^10 * 19^16 * 23^15 * 29^16 * 41^16 * 61^5 * 67^9 * 71^5 * 1931^16 * 3253^9.

Examples

			For n=3 the permutohedron is a hexagon, which has six spanning trees.
		

Links

• Richard Stanley, Table of n, a(n) for n = 1..6
• Eric Weisstein's World of Mathematics, Bruhat Graph
• Wikipedia, Permutohedron

Crossrefs

Cf. A006237.

Programs

Python

import sympy,itertools
def A337083(n):
  p=tuple(itertools.permutations(range(n)))
  m=len(p)
  q={p[i]:i for i in range(m)}
  Q=sympy.diag(*[n-1]*m)
  for i in range(m):
    for k in range(n-1):
      Q[i,q[p[i][:k]+tuple(reversed(p[i][k:k+2]))+p[i][k+2:]]]=-1
  return Q[:m-1,:m-1].det() # Pontus von Brömssen, Jan 18 2021

Extensions

a(1) prepended by Pontus von Brömssen, Jan 19 2021