Consider $V_{(n1, 1)}$, the $n1$ 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_{(n1, 1)}$ decomposes into irreps?
For convenience consider the representation $Y=V_n\oplus V_{n1,1}$ instead of $V_{n1,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_{n1,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_{n1,1}$ equals the scalar product of $s_1^k$ with the symmetric function $(1e_1+e_2e_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_{n1,1}$ equals the scalar product of $(s_11)^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_{n1,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 GoupilChauve paper mentioned in Vasu Vineet's comment.) Since for fixed $j$ we have $S(k,j)=\frac{1}{j!}\sum_{i=1}^j (1)^{ji}{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^{k1}$, and for $\lambda=(1,1,1)$ it is $\frac{1}{6}(3^k3)$. In particular, the multiplicity for $\lambda = (1^n)$ (i.e., $n$ parts equal to 1) is $S(k,n)+S(k,n1)$. 


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), 259267, World Sci. Publ., River Edge, NJ, 1994. MR1399030 (98g:05152) Martin, Paul . The structure of the partition algebras. J. Algebra 183 (1996), no. 2, 319358. MR2143201 (2006g:05228) Halverson, Tom ; Ram, Arun . Partition algebras. European J. Combin. 26 (2005), no. 6, 869921. 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. 


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". 


$V = 1\oplus V_{(n1,1)}$
, so the problem boils down to figuring out how the tensor powers of$V_{(n1,1)}$
decompose. In general, determining how tensor products decompose is hard (the Kronecker problem), but this case may be known. – Amritanshu Prasad Oct 5 '12 at 6:12