Number of $n$-cycles fixed by a permutation of $S_n$. Let $\sigma\in S_n$ be a permutation consisting of $m$ $d$-cycles. I want to show that the number of $n$-cycles $\sigma$ commutes with is $\phi(d)m^{d-1}(d-1)!$. If I write $\sigma=(a_{1, 1},\ldots, a_{1, d})\cdots (a_{m, 1},\ldots, a_{m, d})$, then I can find an $n$-cycle whose $m$th power is $\sigma$ by placing $a_{1, 1}$ first, determining the positions of the $a_{1, k}$'s. There are then $m(d-1)$ positions to place $a_{2, 1}$, determining everything in the second $d$-cycles, and then $m(d-2)$ places to put $a_{3, 1}$, etc. This gives me $m^{d-1}(d-1)!$, but I'm missing a factor of $\phi(d)$ (or perhaps $\phi(m)$)...are there other $n$-cycles that would commute with $\sigma$ that I'm not counting? 
 A: Your $n$-cycle $c$ cannot fix any proper non-empty subset of $\{1,...,n\}$. In particular, if $n>md$,  $\{a_{1,1},...,a_{1,d},...,a_{m,1},...,a_{m,d}\}$ is not fixed by $c$ and  hence cannot fix $\sigma$. So you must assume $n=md$.
Out of curiosity, I have tested your formula for $n:=20$, $m:=5$ and $d:=4$ in Magma (see here http://magma.maths.usyd.edu.au/calc/) :

G:=Sym(20);
s:=G!(1,2,3,4)(5,6,7,8)(9,10,11,12)(13,14,15,16)(17,18,19,20);
c:=G!(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20);
H:=Centralizer(G,s);
n:=0;
struct:=CycleStructure(c);
for h in H do 
if CycleStructure(h) eq struct then n:=n+1;end if;
end for;
n;Factorization(n);

The permutation $s$ is your $\sigma$ and $c$ is defined just to have an example of $n$-cycle (it is a technical auxiliar, I don't know how to implement clearly a $n$-cycle structure, it is just meant to create "struct"). The formula gives you $1500$ for this but Magma gives you $12288=2^{12}.3^1$. Well, although your reasoning certainly gives you some, I don't think this a way to go because $c$ could commute with $\sigma$ without $\sigma$ being a power of $c$.
Now i will give you the answer, I think the number is :
$$\varphi(d)d^{m-1}(m-1)! $$
The reason is the following, set :
$$\sigma_k:=(a_{k,1},...,a_{k,d}) $$
Then if a $n$-cycle commutes with $\sigma$ it must induce a permutation of the set $X:=\{\sigma_1,...,\sigma_m\}$, and because $c$ is a $n$ cycle this permutation must be cyclic as well. There are $(m-1)!$ cyclic permutations of $X$, choose one : $\kappa$. Then if $c$ induces $\kappa$ this means that :
$$c\sigma_{k}c^{-1}=\sigma_{\kappa(k)} $$
Once this is set you have to choose $a_{1,1}$, $a_{2,1}$ ...$a_{m,1}$. For $a_{1,1}$ you have $d$ choices ($a_{1,\kappa(1)}$,...,$a_{d,\kappa(1)}$) let's say $a_{i_1,\kappa(1)}$. Now you must choose an image for $a_{i_1,\kappa(1)}$ this will be $a_{i_2,\kappa^2(1)}$ ($d$ choices as well) and so on up to $a_{i_{m-1},\kappa^{m-1}(1)}$. This gives you a cycle of the form :
$$c=(a_{1,1},a_{i_1,\kappa(1)},a_{i_2,\kappa^2(1)}...,a_{i_{m-1},\kappa^{m-1}(1)},A,*****) $$
I claim that once $A$ is chosen there is at most one choice for $c$. So it suffices to choose $A$. But now $c^m$ must be a product of $m$ $d$-cycles. 
Finally, any choices of $A$ within the elements  $a_{1,1}$,...,$a_{d,1}$ will allow you to construct one and only one permutation, so it suffices to understand which choice will allow you to reconstruct a $n$-cycle. This is given by all the $\sigma_1^k(a_{1,1})$ for which $\sigma_1^k$ is a $d$-cycle, this is exactly $\varphi(d)$. Hence we have on the whole :
$$\varphi(d)d^{m-1}(m-1)!\text{ choices.} $$
