How can we realize different combinatorial objects as the dimension of a construction on vector spaces? Are the resulting algebras useful?

Question

Fix a vector space $V$ of dimension $n$ over some field $F$. Here are three commonly seen constructions:

• its $k$th tensor power, $T^kV$, which has dimension $n^k$
• its $k$th exterior power, $\Lambda^k(V)$, which has dimension $\binom{n}{k}$
• its $k$th symmetric power, $S^k(V)$, which has dimension $\binom{n+k-1}{k}$

Let $X$ denote one of these constructions. Then the "$X$ algebra", namely $\bigoplus_{k=0}^\infty X^k(V)$ with an algebra structure on it, tends to be rather important (for example, the tensor, exterior, and symmetric algebras all satisfy universal properties, and are used all over mathematics).

I recently noticed that the dimensions of the above three constructions were all answers to one of the questions of the "twelvefold way" of combinatorics (specifically, see here). The 12 questions ask for the number of functions from a $k$-element set $K$ to an $n$-element set $N$, under 3 different restrictions (no restriction, injective, surjective) and up to 4 different equivalence relations (equality, up to permutation of $K$, up to a permutation of $N$, up to a permutation of both).

The tensor power has dimension $n^k$, and so would correspond to (no restriction, equality).

The exterior power has dimension $\binom{n}{k}$, and so would correspond to (injective, up to permutation of $K$).

The symmetric power has dimension $\binom{n+k-1}{k}$, and so would correspond to (no restriction, up to permutation of $K$)

So my questions are:

• Can we provide a unified combinatorial explanation of why the tensor, exterior, and symmetric powers have the dimensions that they do, using the framework of the twelvefold way? I am guessing that we want $N$ to be a basis for $V$ (hence having $n$ elements) and $K$ to be any $k$-element set; but in what way does the tensor power correspond to all functions from $K$ to $N$? How does the construction of the exterior power from the tensor power correspond to the restricting attention to the injective functions from $K$ to $N$, and only up to permutation of $K$?
• Given this (hypothetical) unified explanation, what are the constructions on $V$ (presumably, they will be some quotients of the tensor power) that correspond to the other 9 combinatorial questions of the twelvefold way?
• Where do the resulting algebras of these new constructions, formed as before by direct summing over all $k$, show up? For each, can we work out what universal property it satisfies? Or (perhaps too optimistically), can we try to reverse engineer the correct universal property that will produce a construction with the desired dimension / combinatorial interpretation?

---

EDIT: Spurred by Gowers's recent question, I decided to bump this question to the front page to get some fresh eyes on it. Igor's answer is very helpful, in that it says not to necessarily expect an explicit algebra / "power" construction, and Richard's answer also sounds great (though I'm afraid the reference he pointed to went too fast for me to follow), but ultimately I'm still wondering if any piece of the twelvefold way other than the three I listed does have such a construction.

Richard - I don't know anything about Young Tableaux beyond the Wikipedia page, but it seems like there aren't any other "natural" arrangements of $n$ squares other than the ones you mentioned. Might this explain why there doesn't appear to be any other "power" constructions of the kind I'm looking for? Could you explain where the "$k$" is in this approach?

Igor - I will certainly take your word that the "right" approach is through spaces of invariants, but while you explain how $S_k$ acting on $\mathbb{C}[S_k]$ by conjugation can get us a space of dimension $p(k)$, this is still not quite the $p_n(k)$ or $p_n(n+k)$ that occur in the twelvefold way. Could you explain for example the group algebra and action on it that corresponds to the exterior or symmetric power - and if possible in a way that highlights why that choice of algebras and actions is related to considering functions $f:K\rightarrow N$ under (injective, up to permutation of $K$) or (no restriction, up to permutation of $K$)?

If we were to switch from algebra / "power" constructions to spaces of invariants, I suppose I would restate my goal as: is there a single group $G$ such that there are twelve group actions on $\mathbb{C}[G]$, the spaces of invariants of which had the dimensions appearing in the twelvefold way, and with the definition of each action clearly showing its relationship with the corresponding (restriction, equivalence). Perhaps $G=(\mathbb{Z}/n\mathbb{Z})^k$ ?

Of course, I will continue to welcome any ideas on the problem as previously stated.

Answer 1

Tensor power, exterior power, and symmetric power are example of polynomial functors. The general theory of polynomial functors unifies them combinatorially in terms of Young tableaux, RSK, etc. Tensor power corresponds to the skew shape consisting of $n$ disjoint squares; exterior power to a column of length $n$; and symmetric power to a row of length $n$. A standard reference (though not so user-friendly) is the appendix to Chapter 1 of Macdonald's Symmetric Functions and Hall Polynomials.

Answer 2

Let me put it this way: the twelvefold way is kind of like a table of elements. It is a convenient mnemonic to organize pre- 20th century combinatorial objects, which used to assorted. Following the analogy, just because both Oxygen and Gold are on the same list (and people tend to enjoy both), that doesn't mean they have similar physical features. In the same way, binomial coefficients are sometimes related, but often have little in common with integer partitions, and both have many books written about them. The main common feature: both count the number of orbits under the action of $S_n$ on certain combinatorial objects. Thus, from a modern point of view, the "right" way of thinking about them is not to think of them as bases in certain algebras, but as dimensions of invariants under a certain action. Sometimes there is still an explicit algebra (exterior power like you mention for binomial coefficients, or a algebra of symmetric functions where Schur functions corresponding to partitions form a basis), and they are all fundamental, very useful and have been thoroughly studied, but these algebras have also relatively little in common.

Answer 3

Maybe you want to look at Multisets and the combinatorics of symmetric functions and Tensor species and symmetric functions by Miguel Mendez.