Look at the orbit of (123). In general, two elements of S_n are conjugate if and only if their disjoint cyclic notations `look' the same.

Sorry - just realised - your N is wrong. It should consist of all permutations where 4 does not appear in it's disjoint cycle notation! You can think of it as all the elements of S_4 written in disjoint cycle notation.

So, N={id, (12), (13), (23), (123), (132)}, which is isomorphic to S_3 (obviously).