Is there formulas for $\sum_{g\in G}|\operatorname{Fix}(g)|^n$? I saw a problem in Show $r(x)|G|=\sum_{g\in G}|Fix(g)|^2$ where $(G,X)$ is a transitive group and $r(x)$=#{different orbits of X under $Stab(x)$}
Let $(G,X)$ be a transitive group action, that is, for any $x,y\in X$,there exists an element $g\in G$ s.t. $g*x=y$. Fix $x\in X$. Let $r(x)$ be the number of different orbits of $X$ under $\operatorname{Stab}(x)$. Show that  $r(x)|G|=\sum_{g\in G}|\operatorname{Fix}(g)|^2$.
Can this be generalized such that if the assumptions stays on the same and $n\in \mathbb{N}$ then $\sum_{g\in G}|\operatorname{Fix}(g)|^n$ can be represented in some closed form with respect to the variables $r(x)$ and $|G|$? If there is not known general solution, what do we know about some fixed powers of $n$?
 A: $|\text{Fix}(g)|^n$ is the number of fixed points of $G$ acting diagonally on $X^n$. By Burnside's lemma, it follows that
$$\frac{1}{|G|} \sum_{g \in G} |\text{Fix}(g)|^n$$
is the number of orbits of $G$ acting on $X^n$.
If $G$ acts transitively on $X$ then we can count the number of orbits of $X^2$ as follows. First, $X^2$ splits into the diagonal elements $(x, x)$, which consist of one orbit, and then the off-diagonal elements $(x, y), y \neq x$. Since $G$ acts transitively we may pick representatives of each orbit of the form $(x_0, y)$ for any fixed $x_0 \in X$. By orbit-stabilizer the number of such orbits is then the number of orbits of $y$ under the action of $\text{Stab}(x_0)$.
You can do a similar but more complicated analysis for $X^n$ by breaking its orbits up according to which elements are equal to which other elements (equivalently, breaking it up according to the orbits of the action of $\text{Sym}(X)$), which shows in particular that the above sum is at least the number of partitions of $\{ 1, 2, \dots n \}$ into at most $|X|$ nonempty subsets (this is a sum of Stirling numbers of the second kind $S(n, k), k \le |X|$), with equality iff the action of $G$ is $k$-transitive for $k \le n$. 
A: This is an answer in a slightly different direction, using notation from character theory and considering higher transitivity degrees of $G$. Let $G$ act on a set $X$ of cardinality $n$ and let and $\pi(g)=\{x \in X: x^g=x\} (=Fix(g))$. Then this non-negative integer valued function is called the permutation character of the action (it is really a character: let $V$ be a vector space of dimension $n$ over a field $K$ of characteristic $0$, with basis $\{v_1, \cdots, v_n\}$. Then $V$ can be turned into a $K[G]$-module (called the permutation module) by $v_xg=v_{x^g}$. Clearly $V$ affords $\pi$.). Now the following can be proved (the first statement is basically the Cauchy-Frobenius Orbit-Stabilizer Theorem. Write $G_x=\{g \in G: x^g=x\} (=Stab(x))$.
$(a)$ $[\pi,1_G]=\frac{1}{|G|}\sum_{g \in G}\pi(g)=\#$orbits of $X$ under the action of $G$.
$(b)$ $[\pi,\pi]=\frac{1}{|G|}\sum_{g \in G}\pi(g)^2=\#$ orbits of $X$ under the action of $G_x$.
So far, so good, nothing that you did not know. Now, this can be generalized as follows. The total number of partitions of the set $X$ 
is called the Bell number $B_n$. The first several Bell (or exponential) numbers are $B_0 = 1, B_1 = 1, B_2 = 2, B_3 = 5, B_4 = 15, B_5 = 52, B_6 = 203$ (sequence A000110 in the OEIS). The Bell numbers can be recovered from their generating function 
$\sum_{n=0}^{\infty}\frac{B_n}{n!}z^n=e^{e^z-1}$. They share very nice combinatorial properties, see here for example. As Qiaochu mentioned in his excellent answer, the number of partitions of the set $X$ into exactly $k$ non-empty subsets is the Stirling number of the second kind $S(n,k)$. Bell and Stirling numbers obviously relate to each other through: $\sum_{k=0}^nS(n,k)=B_n$. Now we can formulate the generalization (for a proof see for example B. Huppert, Endliche Gruppen I, 20.4 Satz (you can read this even if your German is not at the level it should be ...))
$(c)$ $G$ acts $k$-transitively on $X$ if and only if $[\pi,\pi^{i-1}]=\frac{1}{|G|}\sum_{g \in G}\pi(g)^i=B_i$ for all $i \in \{1, \cdots, k\}$.
(Here it is understood that $\pi^0=1_G$. For the sake of completeness: $k$-transitive means that $G$ can move with a single element any two $k$-tuples of elements of $X$, $k \leq n$.)
