@NicholasRoberts by Maschke, $\Bbb C[S_3]$ is semisimple. There are three conjugacy classes in $S_3$ (as conjugacy classes in $S_n$ correspond to cycle types), so we get $\Bbb C[S_3] \cong \Bbb C \times \Bbb \times M_{2\times2 }(\Bbb C)$. Let $V_1$, $V_2$, $V_3$ be the three irreducible representations such that $V_1$ and $V_2$ are 1-dimensional and $V_3$ is two-dimensional.
Let $\chi$ be the character of $V$.
Choose a basis $v,w$ of $\Bbb C^2$, then we get a basis for $V$ over $\Bbb C$ by $B= (v \otimes v \otimes v, v \otimes v \otimes w, v \otimes w \otimes v, w \otimes v \otimes v, v \ot…

Suppose $k >2$. Call the $k$-element set $X$ and the set of $n$-colorings of $X$ $\operatorname{Col}_n(X)$. Fix two colors $a,b$ from our $n$ available colors, then we can write down an injection of $X$ to $\operatorname{Col}_n(X)$ given by sending $x \in X$ to the coloring that paints $x$ in $a$ und paints all other elements$b$.
This defines $2^n$ different embeddings of $X$ to $\operatorname{Col}_n(X)$ and it's easy that the associated embeddings of representations have pairwise trivial intersection. Thus in the decomposition of the permutation representation associated to $\operatorname{…

@TobiasKildetoft consider any way of writing $k=(a_1+a_2+\dots+a_l)$ with $a_i \in \Bbb N$, consider the set $\operatorname{Part}(X,(a_1,a_2, \dots, a_l))$ of all partitions of $X$ into a partition consisting of an $a_1$ element set, an $a_2$ element set etc. $\operatorname{Part}(X,(a_1,a_2, \dots, a_l))$ carries a natural $S_k$ action.
Fix a $l$ possible colors $c_1, \dots, c_l$
Define a map $\operatorname{Part}(X,(a_1,a_2, \dots, a_l)) \to \operatorname{Col}_n(X)$ by sending a partition $P=\{P_1, \dots, P_l\}$ to the coloring that colors all elements from $P_1$ in $a_1$, all elements in $…