When we're talking about the degree of a permutation group, the actual group structure doesn't matter. So in your example, the fact that $5 \equiv 2 \pmod 3$ is completely irrelevant; all that matters is that $C_3$ is (somehow) acting on $\{1, 2, 3, 4, 5\}$, and consequently will be said to have degree $5 = \left\lvert \{1, 2, 3, 4, 5\} \right\rvert$ in this case. In fact, if we're thinking about the action of any group on $\{1, 2, 3, 4, 5\}$, it will be said to have degree $5$, in that situation.
The term degree in this context is relative; it's not an intrinsic property of a group, but a property of the group action. It's similar to how a polynomial like $x^2 + 1$ would be considered irreducible -- over $\Bbb R$. But it can be factored as $(x - i)(x + i)$ over $\Bbb C$; the context is extremely relevant.
So, it's probably helpful to think of a permutation group as a whole bunch of data tied together: a group $G$, a set $\Omega$, and the action $G \times \Omega \to \Omega$ (or if you prefer, the homomorphism $\phi: G \to {\rm Sym}(\Omega)$) of $G$ on $\Omega$.
Example: The group of rotational symmetries of a cube is the symmetric group ${\rm Sym}(4)$, the full permutation group of the four diagonals of the cube. Thus we can think of ${\rm Sym}(4)$ as a permutation group in several ways, including but definitely not limited to:
A permutation group of degree $4$, if we think of it as acting on the diagonals of the cube.
A permutation group of degree $6$, if we think of it as acting on the faces of the cube.
A permutation group of degree $12$, if we think of it as acting on the edges of the cube, or
A permutation group of degree $8$, if we think of it as acting on the vertices of the cube.
Any subgroups of ${\rm Sym}(4)$, including $C_3$, also act on any of the above sets, and would have the same degrees in each situation.
I've written some comments on your question above. I don't entirely follow exactly what your question is, but hopefully this answer will be helpful.
A more general formulation of what it seems like you're writing is the following.
Let $X$ be a set. Let $\newcommand\scrA{\mathscr{A}}\scrA$ be a partition of $X$, so
$$\bigcup_{A\in\scrA} A = X,$$
and if $A\ne B \in \scrA$, we have $A\cap B = \varnothing$. Then we can define the symmetric group of the partition $\scrA$ to be the subset of the symmetric group of $X$,
$$S_\scrA := \{ \sigma \in S_X : \sigma A= A,\forall A\in \scrA\}.$$
Then, observe that $$S_\scrA \simeq \prod_{A\in \scrA} S_A,$$
and that if $\sigma\in S_X$ is a permutation, then we can let $\newcommand\scrO{\mathscr{O}}\scrO$ be the partition of $X$ into orbits under
$\langle\sigma\rangle$, and observe that $\langle \sigma\rangle \subseteq S_\scrO$.
Thus by the natural isomorphism above, $\sigma$ can be written as the product of the
permutations it induces on each orbit.
Thus we just need to show that $\sigma$ induces a cyclic permutation on each orbit
of $\langle \sigma \rangle$. However this is immediate, since an orbit $\langle \sigma\rangle x$ is by definition
the set of $\sigma^ix$ where $x\in X$, and $\sigma(\sigma^ix)=\sigma^{i+1}x$.
Thus on an orbit $\langle \sigma \rangle x$, $\sigma$ is the cycle
$$\begin{pmatrix} x&\sigma x & \sigma^2 x & \cdots & \sigma^{k-1}x\end{pmatrix},$$
where $k$ is the order of $\sigma$ when restricted to this orbit.
Best Answer
If I am understanding correctly, you already have used the fact that you can decompose the symmetric group by cycle type. So for a fixed integer partition first select the elements to put in each cycle, so you have $$\underbrace{\binom{n}{1}\binom{n-1}{1}\cdots \binom{n-i_1+1}{1}}_{i_1\text{ times}}\underbrace{\binom{n}{1}\binom{n-i_1}{2}\cdots \binom{n-i_1-i_2+1}{2}}_{i_2\text{ times}}\cdots $$ which by cancelling out the factorials gives $$\frac{n!}{1!^{i_1}2!^{i_2}\cdots m!^{i_m}}.$$ Now that you have selected the cycles, you have to multiply for in how many ways you can get a cycle of length $j$ the $i_j$ times, that is $(j-1)!^{a_j}$ giving you $$\frac{n!((1-1)!^{i_1}(2-1)!^{i_2}\cdots (m-1)!^{i_m})}{1!^{i_1}2!^{i_2}\cdots m!^{i_m}}=\frac{n!}{1^{i_1}2^{i_2}\cdots m^{i_m}}.$$ Also, notice that when you selected the $i_j$ cycles, you were giving them an order, you want to take that order out, so yoy have to divide by $i_1!\cdot i_2!\cdots i_m!.$ That gives you the formula you have.
Edit: Remember that two permutations have the same cycle type if they have the same cycle structure in the sense that their share the amount of cycles of size $j$ for every $j.$ So you can decompose the sum in adding the permutations with cycle type $(i_1,\cdots ,i_m)$ where $i_j$ is the number of cycles of length $j.$ Notice that fixed this tuple, you have that $1\cdot i_1+2\cdot i_2+\cdots +m\cdot i_m=n$ because you were partitioning the $n$ elements in these cycles. Then what I explained earlier is how you follow.