0
$\begingroup$

I have been studying combinatorics lately, and I came across this cyclic representation of permutations and Stirling numbers. I understood some stuff, but other stuff are still unclear to me.

For example, if I have a permutation like this:

\begin{bmatrix}1 & 2 & 3 & 4 & 5 & 6 & 7\\4 & 6 & 3 & 1 & 7 & 5 &2\\\end{bmatrix}

The cyclic representation of it can be $(14)(3)(2657)$, because I can go $1 \rightarrow 4 \rightarrow 1$, same for $(2657)$, and $3$ is fixed point.

What confuses me is that if I have two cycles in $S_7$ like $(12)$ and $(13)$, that it can also be written as $(12)\circ(13) = (132)$, I don't see this exactly. Doesn't $(132)$ mean that there is a cycle like $1 \rightarrow 3 \rightarrow 2$?

Another things is that each $\pi \in S_n$ is a product of cycles, or even a product of transpositions. I mean why can I write $(14)(2657) = (14)(27)(25)(26)$? Or for example, for $S_4$ why is $(12)(3)(4) = (12)(12)(12) = (12)(34)(34)$? I see that it is equal to just $(12)$ cause we can ignore the fixed points, but the other options are not clear to me.

Lastly, if I have a Stirling number something like $S_{4,3}$, which as long as I know means the number of permutations of a $4-$set, which has $3$ cycles, where we count fixpoints as cycles too, how can I calculate its value?

$\endgroup$
0
$\begingroup$

I'm not sure what you mean by, "can be written as". $(132)$ is its own permutation. The idea is that you're performing a sort of function composition: $(12)$ maps $1$ to $2$ and $2$ to $1$ and the second maps $1$ to $3$ and $3$ to $1$. Going by the basics of function composition, you first perform the one to the right, $(13)$. However, after $3$ goes to $1$, $(12)$ then sends it to $2$ and $2$ goes to $1$. Thus, we get $(132)$. This should hopefully answer your second question, though it's worth noting that the other ways you had of writing $(12)$ were all equal, they were just more complicated ways of writing the same thing.

With Stirling numbers of the first kind, there is a generating function, but I assume that you're just looking a way to calculate this specific example. If you were to put $4$ elements into $3$ cycles, what has to happen? You have to have one transposition and the rest have to be single element cycles, which you can just ignore. Since it's a transposition, order doesn't matter (the number of circular permutations of two elements is one), so it's the same as picking a pair out of $[4]$ to be the transposition.

Note that $S(n,k)$ is more commonly the notation for Stirling numbers of the second kind, which refer to set partitions. What you want is $s(n,k)$ for Stirling numbers of the first kind, or, more likely $c(n,k)$, for unsigned Stirling numbers of the first kind. If you want the signed Stirling number, you have to multiply the unsigned one by $-1^{n-k}$.

$\endgroup$
  • $\begingroup$ Thanks, your answer was helpful, do I saw a more complex function compositions for permutations, it was like $f = (12)(45)$, and $g = (125)(34)$, which resulted in $f \circ g = (125)(34)$. How exactly was this achieved? $\endgroup$ – user72151 Nov 14 '15 at 18:46
  • $\begingroup$ That, I'm afraid, isn't right. It should be $f \circ g=(2435)$. This could only be true if $f$ were the identity permutation, for $f \circ g$ to be equal to $g$. Perhaps check your notes again, because I can't see how someone would have gotten this answer. $\endgroup$ – Kevin Long Nov 14 '15 at 18:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy