Tensor powers of the standard representation Consider $V_{(n-1, 1)}$, the $n-1$ dimensional irreducible representation of $S_n$, i.e. the "standard" or "defining" representation.  Is there a nice formula for how the $k$-th tensor power of $V_{(n-1, 1)}$ decomposes into irreps?
 A: You want the "partition algebras". Some references to get you started are:
MR1317365 (97b:82023)  Jones, V. F. R.  The Potts model and the symmetric group.
 Subfactors (Kyuzeso, 1993), 
 259--267, World Sci. Publ., River Edge, NJ,  1994. 
MR1399030 (98g:05152)  Martin, Paul . The structure of the partition algebras.
 J. Algebra  183  (1996),  no. 2, 319--358.
MR2143201 (2006g:05228)  Halverson, Tom ;  Ram, Arun . Partition algebras.
 European J. Combin.  26  (2005),  no. 6, 869--921.
The partition algebras are the endomorphism algebras of the tensor powers of, $V$, the 
natural representation of $S_n$. As has been mentioned in the comments this decomposes
as the sum of the trivial representation and the representation you are interested in.
You can recover information about the representation you are interested in from the partition algebras. For example, instead of looking at all set partitions, you only
consider set partitions with no singleton.
A: The problem has been solved in the reference indicated in the comment
by Vasu Vineet, namely:
"Combinatorial Operators for Kronecker Powers of Representations of Sn" by
Alain Goupil and Cedric Chauve. However, one cannot say that the formulas in Propositions 1 and 2 of this paper are "nice".
A: For convenience consider the representation $Y=V_n\oplus V_{n-1,1}$ instead of $V_{n-1,1}$. Then the multiplicity of the representation of $S_n$ indexed by the partition $\lambda$ of $n$ in the $k$th tensor power of $Y$ equals the scalar product of the symmetric function $s_1^k$ (where $s_1=x_1+x_2+\cdots$ denotes a Schur function) with the plethysm $s_\lambda[1+h_1+h_2+h_3+\cdots]$, where $h_i$ is the complete symmetric function of degree $i$. This follows from the theory of inner plethysm; see Exercise 7.74 of Enumerative Combinatorics, volume 2. Since plethysm is in general intractable, I don't expect anything much simpler. This result does allow, however, these decompositions to be computed using Stembridge's Maple package SF for small values of $n$ and $k$.
Addendum. I used the method of Exercise 7.74 to get the analogous result for $V_{n-1,1}$. 
Namely, the multiplicity of the representation of $S_n$ indexed by the partition $\lambda$ of $n$ in the $k$th tensor power of $V_{n-1,1}$ equals the scalar product of $s_1^k$ with the symmetric function $(1-e_1+e_2-e_3+\cdots)\cdot s_\lambda[1+h_1+h_2+h_3+\cdots]$, where $e_i$ is an elementary symmetric function.
Addendum #2. A alternative formulation is the following. The multiplicity of the representation of $S_n$ indexed by the partition $\lambda$ of $n$ in the $k$th tensor power of $V_{n-1,1}$ equals the scalar product of $(s_1-1)^k$ with the symmetric function $s_\lambda[1+h_1+h_2+h_3+\cdots]$.
News flash! I said above that plethysm in in general intractable. Indeed, the Schur function expansion of $s_\lambda[1+h_1+h_2+\cdots]$ looks hopeless to me. However, taking the scalar product with $s_1^k$ results in a lot of simplification. I can show the following. The multiplicity of the representation of $S_n$ indexed by the partition $\lambda$ of $n$ in the $k$th tensor power of $V_n\oplus V_{n-1,1}$ equals the coefficient of $s_\lambda$ in the Schur function expansion of $(1+h_1+h_2+\cdots)\cdot \sum_{j=1}^k
S(k,j)s_1^j$, where $S(k,j)$ is a Stirling number of the second kind. (After obtaining this result, I noticed that it is essentially the same as Corollary 2 of the Goupil-Chauve paper mentioned in Vasu Vineet's comment.) Since for fixed $j$ we have $S(k,j)=\frac{1}{j!}\sum_{i=1}^j (-1)^{j-i}{j\choose i}i^k$, we can get explicit formulas for the multiplicities for fixed $\lambda$ that don't involve Stirling numbers. For instance, when $\lambda=(3)$ the multiplicity is $\frac{1}{6}(3^k+3)$, for $\lambda=(2,1)$ it is $3^{k-1}$, and for $\lambda=(1,1,1)$ it is $\frac{1}{6}(3^k-3)$. In particular, the multiplicity for $\lambda = (1^n)$ (i.e., $n$ parts equal to 1) is $S(k,n)+S(k,n-1)$.
