A393539 - OEIS

A393539

Dimension of the random-to-random subalgebra of the n-th symmetric group algebra.

1, 1, 2, 4, 7, 15, 30, 54, 95, 159, 257, 400, 613, 919, 1352, 1970, 2830, 4017, 5654, 7877, 10886, 14941, 20352, 27541, 37071, 49613, 66026, 87464, 115285, 151285, 197728, 257356, 333673, 431067, 554907, 711948, 910530, 1160846, 1475512, 1870199, 2363847

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,3

COMMENTS

Let A be the group algebra of the symmetric group S_n over a field of characteristic 0. Consider the k-random-to-random shuffles R_{n,k} for all k = 0, 1, 2, ... (see Brauner et al. (2025) for their definition, taking q = 1). These shuffles generate a commutative subalgebra of A. The dimension of this algebra is a(n).

Combinatorially, a(n) is the number of distinct content sets of horizontal strips lambda/mu, where lambda is a partition of n and mu is a partition contained in lambda with the property that mu is neither a single nonempty row nor a single odd-length column (this property is equivalent to requiring the existence of a desarrangement tableau of shape mu). Here, the "content set" of a horizontal strip is the set of all differences j - i, where (i, j) ranges over the cells of the strip. (For a proof, see forthcoming work by Brauner, Commins, Grinberg and Saliola.)

REFERENCES

Sarah Brauner, Patricia Commins, Darij Grinberg, and Franco Saliola, The random-to-random subalgebra, forthcoming.

LINKS

Sean A. Irvine, Table of n, a(n) for n = 0..50

Sarah Brauner, Patricia Commins, Darij Grinberg, and Franco Saliola, The q-deformed random-to-random family in the Hecke algebra, arXiv:2503.17580 [math.CO], 2025.

EXAMPLE

We have a(3) = 4, since the only interesting k-random-to-random shuffle for n = 3 is R_{3,1} = 3 id + 2 cyc(1,2) + 2 cyc(2,3) + cyc(1,2,3) + cyc(1,3,2), which has a minimal polynomial of degree 4 and whose polynomials include the other k-random-to-random shuffles (this part does not generalize beyond n = 3).

PROG

(SageMath)

def has_desarrangement_tableau(mu):

return (len(mu) != 1) and not (len(mu) % 2 == 1 and mu[0] == 1)

def A393539(n):

content_sets = set()

for lam in Partitions(n):

for k in range(n+1):

for mu in lam.remove_horizontal_border_strip(k):

if has_desarrangement_tableau(mu):

lamu = SkewPartition([lam, mu])

content_set = tuple(sorted([j-i for (i, j) in lamu.cells()]))